Модели оптимального планирования

"Модели оптимального планирования"

Сегодня на уроке мы с вами заканчиваем изучение теоретических основ «Информационного моделирования». На прошлом уроке мы занимались моделированием корреляционных зависимостей. И узнали, что существует два вида зависимостей. Уже хорошо знакомая функциональная зависимость (когда определённому значению независимой переменной соответствует строго определённое значение зависимой переменной) и корреляционная.

Корреляционная зависимость – это такая зависимость, когда данному значению одной величины соответствует целый ряд значений другой, причём при изменении данной величины меняются и другие значения, а также и его среднее. То есть зависимость между величинами, каждая из которых подвергается неконтролируемому разбросу.

При изучении корреляционных зависимостей мы рассмотрели два вида задач.

Первый вид – Оказывает ли фактор В какое-либо заметное постоянное влияние на фактор А?

Второй – Какие из факторов B, C или D оказывают наибольшее влияние на фактор А?

Так же мы узнали, что раздел математической статистики, который исследует корреляционные зависимости, называется корреляционным анализом.

Затем, рассмотрев пример корреляционной зависимости, мы пришли к тому, что оценку корреляции величин начинают с высказывания гипотезы о возможном характере зависимости между их значениями.

Чаще всего считают, что это линейная зависимость. Тогда мера корреляционной зависимости – это величина, которая называется коэффициентом корреляции.

Коэффициент корреляции (обычно обозначают греческой буквой ƍ) характеризует величину, отражающую степень взаимосвязи двух переменных между собой. ƍ может изменяться в пределах от -1 до +1. То есть в зависимости от того к чему будет ближе коэффициент корреляции к нулю, к плюс или минус единице, зависимость может быть соответственно сильной или отсутствовать вообще.

Но существуют задачи другого типа.

На прошлом уроке мы рассмотрели зависимость производительности труда рабочего на предприятии от энерговооружённости данного предприятия, то есть от условий работы, которые предприятие создаёт для своего рабочего.

Но для того чтобы предприятие развивалось и модернизировалось нужно научиться оптимально использовать ресурсы при производственном планировании. Например, научиться находить оптимальные комбинации различных видов продукции для хранения на складах. А также минимизировать транспортные расходы, при перевозке продукции.

Сегодня на уроке мы свами будем разбираться со следующими вопросами:

· Что такое оптимальное планирование и в чём состоит задача оптимального планирования.

· Что такое плановые показатели, ресурсы и цели.

· А также, какое программирование называется математическим, а какое линейным.

Объектом планирования может стать любая система: от детского сада до предприятия-гиганта, любая отрасль промышленности или сельского хозяйства, любой регион и, наконец, государство.

При постановке задачи учитывают следующее:

· Имеющиеся плановые показатели: икс, игрек и другие:

· Имеющиеся ресурсы: R1, R2 и другие. За счёт ресурсов достигаются плановые показатели. Но ресурсы практически всегда ограничены.

· И стратегическая цель. Цель зависит от значений плановых показателей и на неё ориентируются при планировании.

Тогда оптимальным планом называется значение плановых показателей при достижении стратегической цели, с учётом ограниченности ресурсов.

Рассмотрим примеры.

Пусть объектом планирования является транспортная компания, которая занимается доставкой товаров из нескольких предприятий, нескольким потребителям.

Основными ресурсами транспортной компании будут транспортные средства, необходимые для перевозки товаров, а также расходы на перевозку. Стратегической целью данной компании будет планирование маршрута так, чтобы расходы на перевозку были минимальными.

Или другой пример: Пусть объектом моделирования является средняя общеобразовательная школа.

Плановыми показателями здесь могут выступить, например, количество учителей и учащихся. Основными ресурсами деятельности школы являются объём финансирования, оснащённость учебных кабинетов средствами обучения, например, учебными стендами, плакатами, интерактивной доской и компьютерами. Естественно в школе стратегической целью является образование и воспитание школьников. А количественной мерой будет повышение среднего балла успеваемости.

На уроках информатики логично, для решения задач использовать компьютер. Следовательно, нужно информационную модель преобразовать в математическую, то есть представить в виде формул, уравнений и других средств математики.

Давайте рассмотрим пример решения задачи оптимального планирования с помощью компьютера.

На рыбоводческом комплексе занимаются разведением карпов и толстолобиков. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество корма каждого вида, которое должны ежедневно получать карпы и толстолобики, приведено в таблице. В ней же указаны общее количество корма каждого вида, которое может быть использовано комплексом, а также прибыль от реализации рыбы.

Нужно определить, сколько карпов и толстолобиков следует выращивать на рыбоводческом комплексе, чтобы прибыль от их реализации максимальной.

Естественно, что это чисто учебный пример. Вряд ли существует такой рыбоводческий комплекс, который занимается разведением всего двух видов рыб, да и наибольшая выручка – это не единственная цель его работы.

Итак, здесь плановыми показателями являются:

Икс штук – карпов и игрек штук – толстолобиков.

Ресурсами в этом примере можно назвать количество корма каждого вида, которое должны ежедневно получать карпы и толстолобики.

Для упрощения решения задачи, будем считать, что другие ресурсы, например, электроэнергия, не ограничены.

Из условия задачи известно, что для обеспечения нормальных условий выращивания карпов и толстолобиков используются три вида кормов. Также известно количество корма каждого вида, которое должны ежедневно получать карпы и толстолобики, и общее количество корма каждого вида, которое может быть использовано рыбоводческим комплексом. Составим систему неравенств.

Итак, для первого корма. Ежедневно карпы должны получать 2 единицы первого корма, а толстолобики 3 единицы, но в месяц количество потребления первого корма рыбами не должно превышать 150-ти единиц.

Аналогично составим неравенства для второго и третьего корма.

К трём полученным неравенствам нужно добавить условия положительности значений величин икс и игрек, так как не может быть отрицательное число карпов и толстолобиков. В итоге получим следующую систему неравенств.

Теперь сформулируем стратегическую цель. Нам нужно определить, сколько карпов и толстолобиков следует выращивать на рыбоводческом комплексе, чтобы прибыль от реализации рыбы была максимальной.

По условию мы знаем, что прибыль от реализации одного карпа равна 16 условным единицам, а толстолобика – 12 у.е., тогда сумма 16x+12y должна стремиться к максимуму.

Цель рыбоводческого комплекса – получение максимальной выручки от продажи рыбы.

Рассмотрим записанное выражение как функцию от x, y.

То есть f_xy, игрек равно 16x + 12y.

Такая функция называется целевой функцией.

Следовательно, получение оптимального плана свелось к следующей математической задаче:

Требуется найти значения плановых показателей x и y, которые будут удовлетворять данной системе неравенств и придавать максимальное значение целевой функции.

Итак, мы построили математическую модель задачи оптимального планирования для рыбоводческого комплекса.

Решить данную задачу нам помогут средства, реализованные в табличном процессоре Excel.

Математическое программирование— это раздел математики, содержащий методы решения задач оптимального планирования.

Так как в целевую функцию f_xy игрек величины икс и игрек входят линейно, то есть они в первой степени, то нашу задачу можно отнести к разделу этой науки, который называется линейное программирование.

Линейное программирование –это раздел математического программирования, решающий задачи оптимального планирования с линейной целевой функцией.

Для решения задачи в MS Excel, создадим таблицу с исходными данными.

Ячейки В7 и С7 оставим соответственно для значений х (количество выращиваемых карпов) и у (количество выращиваемых толстолобиков).

В ячейки В2:С2 введём коэффициенты в ограничениях по первому корму, то есть 2 и 3 соответственно. В ячейки В3:С3 по второму корму. И в В4:С4 по третьему. Далее В диапазон ячеек Д2:Д4 запишем общее количество корма каждого вида, которое может быть использовано комплексом.

В ячейки В6 и С6 запишем коэффициенты целевой функции, в нашем случае это 16 и 12.

Далее в ячейку В8 введём формулу целевой функции. Будем использовать встроенную функцию СУММПРОИЗВ.

Данная функция перемножает соответствующие элементы заданных списков, а затем складывает полученные произведения.

Аргументами функции СУММПРОИЗВ являются диапазоны ячеек, причём все диапазоны должны иметь одинаковые размерности.

Встроенная функция СУММПРОИЗВ будет записываться следующим образом: равно СУММПРОИЗВ, далее в круглых скобках нужно указать два диапазона ячеек, которые нужно перемножить и затем сложить произведения. В нашей задаче целевая функция записана следующим образом: шестнадцать икс плюс двенадцать игрек, то есть нам нужно найти сумму произведений коэффициентов целевой функции и переменных. Указываем первый диапазон В6:С6 точка с запятой и второй диапазон В7:С7.

Функция СУММПРОИЗВ перемножит соответствующие ячейки диапазона, то есть В6 умножит на В7, а С6 умножит на С7. Затем полученные произведения суммирует.

В ячейку Е2 введём ограничения. Снова будем использовать встроенную функцию СУММПРОИЗВ. Здесь первый диапазон ячеек – это коэффициенты в ограничениях для первого корма, а второй – переменные. Аналогично заполним ограничения для второго и третьего корма.

Теперь необходимо вызвать программу оптимизации и сообщить ей, где расположены данные. Для этого необходимо сначала загрузить её.

Откроим вкладку Файл и выберем пункт Параметры. Далее выбираем команду Надстройки, а затем в окне Управление выбираем пункт Надстройки Excel. Нажимаем кнопку Перейти. Теперь в окне Доступные надстройки установим флажок Поиск решения и нажимаем кнопку ОК.

После загрузки надстройки «Поиск решения» на вкладки Данные в группе Анализ становится доступна команда Поиск решения. Выбираем её, после чего перед нами открывается соответствующая форма.

Далее необходимо выполнить следующий алгоритм:

Ввести координату ячейки с целевой функцией. В нашем случае это В8. (Заметим, что если перед этим установить курсор на ячейку В8, то ввод произойдёт автоматически).

Поставить отметку «максимальному значению», то есть сообщить программе, что нас интересует нахождение максимума целевой функции.

В поле «Изменяя ячейки переменных» ввести В7:С7, то есть сообщить, какое место отведено под значения переменных-плановых показателей.

В поле «Ограничения» надо ввести информацию о неравенствах-ограничениях следующим образом: щёлкнуть по кнопке «Добавить».

Итак, первое неравенство имеет вид 150 больше либо равно два икс плюс три игрек. Теперь в появившемся диалоговом окне «Добавление ограничения» ввести ссылку на ячейку Д2, выбрать из меню знак неравенства больше либо равно и ввести ссылку на ячейку Е2; снова щёлкнуть по кнопке «добавить» и аналогично ввести второе ограничение Д3 больше либо равно Е3 и так далее. В конце нажимаем ОК.

Закрываем диалоговое окно «Добавление ограничения». Снова появится форма «Поиск решения». После завершения ввода всех ограничений и параметров нажимаем «Найти решение» и получаем искомое решение задачи.

То есть в результате применения инструмента Поиск решения получен следующий оптимальный план разведения карпов и толстолобиков на рыбоводческом комплексе: нужно вырастить 57 карпов и 12 толстолобиков.

Решение данной задачи может быть представлено и в дробных числах, но так как у нас в задаче надо найти количество рыб, а оно не может быть дробным числом, мы числа округляем до целых.

Представим систему полученных нами неравенств на координатной плоскости.

То есть нам нужно изобразить пять прямых, соответствующих следующим линейным уравнениям:

В результате мы получим четырёхугольник ABCD. Любая точка четырёхугольника является решением нашей системы неравенств. Если икс равно 57, а игрек равно 12, то в этой точке значение целевой функции Эф от пятидесяти семи и двенадцати равно 1056. Если один карп стоит 16 условных единиц, а толстолобик 12, то полученная выручка составит 1056 условных единиц. Этой точке соответствует точка Бэ на нашем графике.

Итак, сегодня на уроке мы с вами построили модель оптимального планирования на рыбоводческом комплексе.

А теперь давайте повторим всё, что мы узнали сегодня на уроке:

Оптимальное планирование — это определение значений плановых показателей с учётом ограниченности ресурсов при условии достижения заданной цели.

Ограниченность ресурсов может описываться с помощью:

· системы неравенств;

· системы равенств;

· смешанной системы.

Цель описывается функцией, для которой требуется найти минимум или максимум.

Microsoft Excel имеет специальное средство Поиск решения для решения задач оптимального планирования.