|
В качестве упражнений решить задачи § 2 симплексным методом. Указание: первый выбранный план должен быть опорным, т. е. все свободные члены после выражения базисных переменных через свободные должны быть неотрицательными. Если это не так, то надо искать новое базисное решение до тех пор, пока оно не будет неотрицательным. Только после этого можно приступать к реализации симплекс-метода.
§ 4. Решение задачи линейного программирования
в Excel 1. Автоматизация решения задачи
линейного программирования
Д
ля решения оптимизационных задач можно использовать надстройку «Поиск решения» табличного процессора Excel. В Microsoft Office Excel 2007 надстройка «Поиск решения» доступна на вкладке Данные в группе Анализ. Если она еще не загружена, ее необходимо загрузить. Необходимую инструкцию можно найти в Справке (Рис. 2).
Рис. 2. Загрузка надстройки
П
Рис. 3. Вкладка Данные
осле загрузки надстройка «Поиск решения» появится на вкладке Данные в группе Анализ (Рис. 3).
Рассмотрим решение задачи о выборе оптимального рациона питания со стр. 40 в табличном процессоре Excel с помощью инструмента «Поиск решения»:
L(x) = 7x1 + 9x2 → min (минимизация стоимости рациона),
при ограничениях:
x1 0, x2 0.
Рис. 4. Диалоговое окно Поиск решения
При нажатии на кнопку Поиск решения появится диалоговое окно (Рис. 4).
И
Рис. 5. Начальные значения переменных, ограничений и целевой функции
нструмент «Поиск решения» приложения Microsoft Office Excel использует программу нелинейной оптимизации Generalized Reduced Gradient. Чтобы правильно провести этот диалог, надо подготовить данные задачи в ячейках листа. При этом часть ячеек будет содержать подписи (т. е. текст, подписи обрабатываться не будут, их назначение — сделать диалог максимально удобным, легко воспринимаемым пользователем), а часть — расчетные формулы или конкретные числовые значения. Как видим на Рис. 4, во-первых,
в диалоге надо сослаться на ячейку листа, в которой хранится значение целевой функции: Установить целевую ячейку, и выбрать радиокнопку в соответствии с условием оптимизации. Во-вторых, на листе надо выбрать ячейки, в которых будут храниться текущие значения переменных, входящих в задачу: Изменяя ячейки. Для этого в ячейках А1 и А2 разместим подписи «х1» и «х2» соответственно, а под ними, в ячейках В1
и В2 — первоначальные значения этих переменных, например, числа 100 и 100 соответственно. В-третьих, необходимо указать ограничения в окне Ограничения. Для этого в ячейках А4:А6 разместим подписи «28x1+32x2=», «47x1 + 83x2=», «x1=» соответственно, а в ячейках справа от них — В4:В6 — формулы со ссылками на ячейки А2 и В2, в которых хранятся значения x1 и x2: «=28*A2 + 32*B2», «=47*A2+83*B2», «=A2». При этом в ячейках В4:В6 появятся соответствующие начальным значениям переменных числа — значения рассчитываемых величин белков, углеводов и смеси № 5 (Рис. 5).
Далее в ячейке А8 поместим подпись целевой функции, а в ячейке справа от нее — расчетную формулу. Чтобы увидеть все формулы одновременно, надо на вкладке Формулы в группе Зависимости формул
нажать кнопку Показать формулы (Рис. 6).
П
Рис. 6. Отображение формул
ри этом текст формул в ячейках выравнивается по левому краю.
После того, как необходимая подготовка листа выполнена, вызывается инструмент «Поиск решения», в окне Установить целевую ячейку указывается ссылка на ячейку $B$8 (в то время, как указатель находится в окне, достаточно щелкнуть по этой ячейке и перейти в другое окно диалога), выбирается радиокнопка минимальному значению. В окне Изменяя ячейки необходимо протащить мышь по ячейкам значений x1 и x2: $A$2:$B$2. Примерный вид экрана после этих действий изображен на Рис. 7.
Рис. 7. Проведение диалога в окне Поиск решения
П
Рис. 8. Диалоговое окно Добавление ограничения
осле этого надо перейти в окно Ограничения и нажать на кнопку Добавить. Появится диалоговое окно как на Рис. 8.
П
Рис. 9. Проведение диалога Добавление ограничения
одробно опишем добавление ограничения по белкам. В окне Ссылка на ячейку сошлемся на ячейку, в которой хранится рассчитанное по формуле текущее значение количества белков, т. е. на $B$4. В среднем окне из списка выберем тип ограничения: >=. В окне Ограничение укажем конкретное значение 14 (Рис. 9).
Рис. 10. Окончательный вид окна Поиск решения
После этого нажмем кнопку Добавить, и введем по очереди остальные ограничения задачи. В конце нажмем ОК, все ограничения появятся в окне Ограничения. Надо помнить и про требования неотрицательности переменных, которые тоже являются ограничениями. После указания всех необходимых ограничений окно Поиск решения выглядит как на Рис. 10.
После нажатия на кнопку Выполнить инструмент «Поиск решения» реализует оптимизационный алгоритм, появляется сообщение о том, что решение найдено (Рис. 11), а в изменяемых и в зависящих от них ячейках появляются оптимальные значения величин.
Рис. 11. Оптимальное решение задачи о рационе питания
Полученное решение совпадает с решением, найденным ранее с помощью графического метода. При этом ограничения по белкам и углеводам являются активными, так как их оптимальные значения в ячейках В4 и В5 в точности равны правым частям соответствующих неравенств. Далее можно провести эксперимент с данным сценарием, задавая различные начальные значения переменных в ячейках А2 и В2, в том числе и отрицательные. Легко убедиться в том, что независимо от начальных значений x1 и x2, встроенный алгоритм поиска оптимального решения задачи линейного программирования будет давать один и тот же результат. Такое свойство алгоритма называется устойчивостью по начальным данным.
П
редложенный вариант оформления листа книги Excel для применения инструмента «Поиск решения» не является оптимальным. Например, для того, чтобы решить эту же задачу при других коэффициентах в ограничениях и целевой функции, надо в ячейке с соответствующей формулой вручную изменить такие коэффициенты. А при изменении правых частей ограничений необходимо вызвать диалоговое окно Поиск решения и поменять правые части в ограничениях в соответствующем окне. Можно предложить другой, более универсальный, способ расположения данных задачи и оформления ссылок (Рис. 12).
Рис. 12. Универсальное оформление задачи линейного программирования
В этом случае во всех ячейках находятся конкретные числа, в ячейке D7 и лежащих ниже — формулы. Причем, если в D7 поместить формулу «=B7*$B$3+C7*$C$3», то ее можно скопировать вниз в ячейки D8, D9, D12, и необходимые формулы в них появятся автоматически. Значительно упрощается при этом и организация диалога в окне Поиск решения (
Рис. 13).
Рис. 13. Организация диалога в окне Поиск решения
Для решения одной конкретной задачи можно использовать любой из предложенных подходов, но если требуется провести экономический анализ, то второй, несомненно, будет предпочтительнее. Ведь в этом случае нет необходимости менять сценарий, вносить поправки в окне Поиск решения, достаточно менять числа на листе книги Excel. Например, выясним, при какой минимальной стоимости в рублях килограмма В-риса ограничение по смеси № 5 становится активным при неизменной стоимости смеси № 5. Будем менять в сторону увеличения цену 1 кг В-риса
с шагом 1, каждый раз возвращая начальные значения 100 и 100 в ячейки В2 и С2 и запуская инструмент «Поиск решения». Тогда при цене
13 руб./кг В-риса получим, что активными станут ограничения по углеводам и смеси № 5 (Рис. 14).
Рис. 14. Результат экономического анализа по изменению целевой функции
Приведем еще несколько примеров использования инструмента «Поиск Решения».
Рассмотрим пример со с. 14, так называемую транспортную задачу (ТЗ). Ее графическое решение представлено на с. 35—36. Исходную ситуацию в ТЗ удобно представить в специальной таблице — макете, в которой отражены запасы у поставщиков Аi, потребности (заявки) потребителей Bj и тарифы перевозок Cij. На Рис. 15 такая таблица обведена утолщенной рамкой, а собственно тарифы В3:D4 выделены имеющими яркие границы ячейками. Остальные данные ясны из подписей в этой таблице. Особенность подготовки данных ТЗ на листе книги Excel состоит в том, что нет возможности подписать переменные: они имеют табличную структуру и характеризуются двумя индексами. Ниже таблицы тарифов создадим точно такую же таблицу начальных значений переменных В8:D9, не подписывая их. Ясно, что формулы суммирования по строкам или по столбцам можно автоматически набирать с помощью кнопки автосуммы и дальнейшего копирования. Для удобства формирования целевой функции создадим ниже таблицу произведений тарифов на перевозки В13:D14, набрав формулу «=B3*B8» в ячейке В13 и скопировав ее по горизонтали, а затем всю строку — по вертикали.
Рис. 15. Подготовка данных транспортной задачи
Тогда в ячейке значения целевой функции можно задать формулу «=СУММ(B13:D14)». Все необходимые формулы показаны на Рис. 16.
Рис. 16. Формулы при подготовке данных транспортной задачи
О
кно Поиск решения должно содержать требование неотрицательности, наложенное на все переменные (Рис. 17).
Рис. 17. Требование неотрицательности переменных в окне Ограничения
Такие ограничения можно задать по отдельности, а можно наложить его сразу на все ячейки диапазона B13:D14 (Рис. 18).
Рис. 18. Наложение одинаковых ограничений на диапазон значений
Результат работы инструмента «Поиск решения» представлен на рис. 41.
Рис. 19. Оптимальное решение транспортной задачи
2. Графическое решение задачи
линейного программирования в Excel
Р
ассмотрим пример со с. 49 (Задача 4. Лист, подготовленный к применению инструмента «Поиск решения» выглядит как на Рис. 20
Рис. 20. Задача об оптимальном использовании сырья
и
ли с указанием формул, как на Рис. 21.
Рис. 21. Перечень формул в задаче об оптимальном использовании сырья
Покажем, как можно с помощью Excel графически построить МДР, найти оптимальное значение целевой функции, провести экономический анализ. Самое трудное, выбрать точки для построения прямых — границ ограничений — на диаграмме Excel. Поскольку границей каждого ограничения является прямая, заданная в виде «в отрезках» , то можно выбрать точки пересечения таких прямых с осями координат: (0; c/b) и (c/a; 0). Но такой подход возможен, если граница не параллельна ни одной из осей координат, то есть в случае, когда ни один из коэффициентов при переменных в уравнении прямой не обращается в 0. В случае же задания границы в виде прямую будем задавать точками (c/a; c/a) и (c/a; 0), а в случае — точками (0; c/b) и (c/b; c/b). В дальнейшем покажем, как точку с ненулевыми координатами можно уточнить, добиваясь наиболее привлекательного вида ОДР. Для рассмотренной задачи введем формулы координат необходимых точек прямых в части листа после заголовка «Точки графиков».
Рис. 22. Задание точек пересечения с осями
Здесь в ячейках В16 и С16 хранятся координаты точки пересечения границы ограничения по стали-45 с осью Oy, а в ячейках В17 и С17 —
с осью Ох. Граница ограничения по чугуну параллельна оси Ох, поэтому в соответствии с изложенным выше соглашением в ячейки В18 и С18 поместим координаты 0 и c/b соответственно, а в В19 и С19 — c/b и c/b. Аналогично задаем точки для построения границ ограничений по бронзе, стали-3 и прямой, отражающей положение целевой функции для текущих значений переменных, которые, напоминаем, задаются произвольно. Далее построим диаграмму, содержащую единственную прямую — границу первого ограничения по стали-45: выделив ячейки В16:С17, вызовем Вставка — Точечная — Точечная с прямыми отрезками (Рис. 23).
Рис. 23. Вставка диаграммы ограничения по стали-45
Появится диаграмма, примерно как на Рис. 24.
Рис. 24. Диаграмма ограничения по стали-45
Замечаем, что автоматика неправильно интерпретировала данные: вместо нужных нам точек (0; 80,5) и (107,33; 0) на диаграмме использованы точки (0; 107,33) и (80,5; 0). Для изменения диаграммы и смены подписи «Ряд 1» на «Сталь-45» щелкнем правой кнопкой мыши в области диаграммы и из появившегося контекстного меню выберем пункт Выбрать данные (Рис. 25).
Рис. 25. Редактирование диаграммы
Рис. 26. Изменение ряда данных
Далее в появившемся диалоговом окне Выбор источника данных при выделенной строке «Ряд 1» нажмем кнопку Изменить (Рис. 26).
В открывшемся новом диалоговом окне, таком, как на Рис. 27,
Рис. 27. Изменение ряда и подписи ряда
д
Рис. 28. Добавление ряда ограничения по чугуну
ля задания имени ряда в окне Имя ряда щелкнем по ячейке с подписью «Сталь-45», удалим значения в окне Значения Х и протащим мышь по ячейкам с первыми координатами точек построения — В16:В17, удалим значения в окне Значения Y и протащим мышь по ячейкам со вторыми координатами точек построения — С16:С17, нажмем кнопки ОК, закрывая все диалоговые окна. На диаграмме вместо слов «Ряд 1» появится «Сталь-45», а прямая изменит наклон. Заметим, что данная задача решается на листе Лист3 книги Excel, поэтому указание на этот лист будет предшествовать ссылкам на ячейки. Остальные прямые будем добавлять последовательно в виде новых рядов данных. Описанным выше способом вызовем диалоговое окно Выбор источника данных, и в нем нажмем кнопку Добавить. В строке Имя ряда щелкнем по ячейке с подписью «Чугун», в строке Значения Х протащим мышь по ячейкам с первыми координатами точек для построения прямой В18:В19, в строке Значения Y — по ячейкам со вторыми координатами С18:С19 (Рис. 28). После нажатия на кнопку ОК на диаграмме появится новая прямая с нужной подписью. В диалоговом окне Выбор источника данных снова нажмем кнопку Добавить и аналогично последовательно добавим данные по бронзе, стали-3 и целевой функции. Окончательный вид диаграммы показан на Рис. 29.
Рис. 29. Диаграмма ограничений по 4 видам сырья
Она, очевидно, имеет ряд недостатков. В ней единичные отрезки по осям имеют разную длину, ограничение по чугуну хочется вытянуть горизонтально до пересечения с другими прямыми. Щелкнем по области построения диаграммы и опытным путем изменим ее размеры так, чтобы единичные отрезки по осям были примерно одинаковыми, не меняя при этом размеры области диаграммы. Чтобы изменить расположение ограничения по чугуну, заменим формулу в ячейке В19 на конкретное подходящее число, например, на 100. Улучшенная диаграмма будет выглядеть примерно так, как на Рис. 30. Зная, что в задаче с ограничениями по ресурсам в качестве решения любого из ограничений выбирается полуплоскость, содержащая начало координат («нижняя» полуплоскость), легко получаем МДР. К тому же, понимая, что из себя представляет МДР, можно увидеть и точку, в которой целевая функция достигает оптимального значения.
Рис. 30. Окончательный вид диаграммы
Далее на основе данных этой задачи с помощью инструмента «Поиск решения» можно провести поиск оптимального решения. При этом изменится положение целевой функции на диаграмме: она займет оптимальное положение (Рис. 31).
Рис. 31. Оптимальное положение целевой функции
И по диаграмме (Рис. 31), и по текущим значениям правых частей ограничений в таблице видно, что активными являются ограничения по стали-3 и стали-45, а пассивными — по чугуну и бронзе (Рис. 32). Суточные запасы чугуна можно снизить до 34,75 кг, а бронзы — до 122 кг.
Рис. 32. Оптимальное решение задачи в Excel
П
Рис. 33. Увеличение ограничения по стали-45
окажем, как можно провести экономический анализ активных ограничений. Будем, например, увеличивать суточные запасы стали-45
в ячейке Е7, каждый раз после изменения заново запуская инструмент «Поиск решения».
При значении 380 кг видим, что активными стали ограничения по бронзе, стали-45 и стали-3 (Рис. 33), а границы соответствующих неравенств пересекаются в одной точке, которая и является оптимальным решением (Рис. 34). Дальнейшее увеличение ограничения по стали-45 делает это ограничение пассивным.
Рис. 34. Три активных ограничения
Рассмотрим более сложный пример оптимального решения и экономического анализа задачи линейного программирования с ограничением по ресурсам. Эта задача была предложена на II очном туре Всероссийской междисциплинарной олимпиады «Информационные технологии в сложных системах» по профилю «Сложные социально-экономические системы» в октябре 2010 года.
Задача. Предположим, Вы являетесь владельцем пекарни, которая специализируется на производстве сдобного печенья и бисквитов. Данные о ценах, затратах соответствующих ресурсов на 1 кг продукции
и доступных объемах запасов ресурсов приведены в таблице 18.
Таблица 18
Ресурсы
|
Сдоб. печ.
|
Бисквиты
|
Запасы
|
Мука, кг
|
0,58
|
0,3
|
750
|
Масло, кг
|
0,25
|
0,05
|
500
|
Яичный порошок, кг
|
0,18
|
0,8
|
700
|
Сахар, кг
|
0,1
|
0,5
|
200
|
Крахмал, кг
|
0
|
0,07
|
100
|
Труд, чел./дн.
|
0,08
|
0,09
|
120
|
Оборудование 1, маш./смен.
|
0,02
|
0,07
|
100
|
Оборудование 2, маш./смен.
|
0,07
|
0,08
|
100
|
Цена за 1 кг продукции, руб.
|
31
|
29
|
|
Имеющийся запас сахара можно пополнить, исходя из цены 14 руб. за 1 кг сахара. Сколько сахара выгодно докупить и какова ожидаемая величина прироста выручки?
Р
ешение. Подготовим данные на листе Excel, как это было описано на с. 94, и запустим инструмент «Поиск решения». Получим оптимальное значение целевой функции и активные ограничения по муке и сахару (Рис. 35). Теперь будем увеличивать запасы сахара, например:
Рис. 35. Оптимальное решение
с рис. 57 шагом 10 и выполнять поиск решения до тех пор, пока ограничение по сахару не станет пассивным. Обнаружим, что при запасах сахара в 230 кг ограничение по сахару становится пассивным, а активными будут ограничения по муке и оборудованию 2. Текущее значение сахара при этом равно 226,378 кг. Ведем это значение в ячейку Е10 и снова запустим «Поиск решения». Видим, что сразу три ограничения становятся активными: по муке, сахару и оборудованию 2 (Рис. 36). Значит, дальнейшее увеличение запасов сахара не влияет на оптимальное значение целевой функции. Ожидаемая величина прироста выручки будет вычисляться как разность между оптимальным значением целевой функции при запасах сахара 226,378 кг и 200 кг, из которой надо вычесть сумму, потраченную на покупку дополнительного сахара:
Рис. 36. Три активных ограничения
Заметим, что по смыслу задачи значения переменных должны быть целыми. Для этого в окне Поиск решения необходимо ввести дополнительное ограничение целочисленности на значения ячеек $B$3:$C$3 (Рис. 37).
В этом случае оптимальное решение почти не будет отличаться от полученного выше, но оптимальные значения переменных в ячейках $B$3:$C$3 будут выражаться целыми числами (Рис. 38), а текущие значения ограничений по муке и по сахару будут более других близки к граничным. Этот факт говорит об активности данных ограничений.
Рис. 38. Целочисленное оптимальное решение
Путем увеличения правой части ограничения по сахару обнаружим, что при запасах в 226,5 кг сахара активными станут три ограничения: по муке, сахару и оборудованию 2. Соответствующее решение предлагается получить самостоятельно. Значение целевой функции при этом составит 42 873 руб. Следовательно, ожидаемая величина прироста выручки будет
Итак, решение указанной задачи выглядит так: необходимо докупить 26,5 кг сахара; при этом прирост выручки составит 408 руб.
В процессе решения этой задачи удалось обойтись без графического представления данных. Но целесообразно рассмотреть и его. Построим границы МДР и целевую функцию так, как было описано на с. 100—106Error: Reference source not found. Видим, что диаграмма получилась крайне неудачной; большое количество ограничений и сильно отличающиеся координаты точек пересечения
с осями их границ делают ее практически не читаемой. Но в то же время, благодаря легенде (и данным в таблице как на с. 109), видим, что ограничения по маслу, крахмалу, оборудованию 1 не участвуют в ограничении МДР. Их границы можно выделить непосредственно на диаграмме и удалить клавишей Del. На диаграмме автоматически изменятся максимальные значения по осям (Рис. 40).
Р
ис. 39. Ограничения и целевая функция
Рис. 40. Удаление пассивных ограничений
После этого можно скорректировать максимальные значения по осям, последовательно выделив их и вызвав из контекстного меню пункт Формат оси… Видим, что важные в задаче ограничения будут хорошо различимы, если максимальные значения по горизонтальной и вертикальной осям зафиксировать в точках 2 000 и 1 000 соответственно (Рис. 41).
Рис. 41. Изменение максимальных значений по осям
Теперь хорошо видно, что ограничение по сахару можно увеличивать до тех пор, пока граница не пройдет через точку пересечения границ по муке и оборудованию 2.
Рис. 42. Оптимальное решение с активными ограничениями по муке, сахару
и оборудованию 2
Зная, что нужное число 226,5, введем его в ячейку Е10, запустим «Поиск решения». Оптимальное положение целевой функции с тремя активными ограничениями показано на Рис. 42. На этом примере показано, как удалять с диаграммы мешающие пассивные ограничения, делать диаграмму с МДР более информативной.
Do'stlaringiz bilan baham: |
