Использование Excel для решения задач линейного программирования
В Excel имеется эффективный инструмент для решения задач оптимизации – программная надстройка Поиск решения. Установка этой надстройки производится через меню Сервис► Надстройки, после чего в диалоговом окне Надстройки необходимо пометить пункт Поиск решения и нажать кнопку ОК. После установки этой надстройки в меню Сервис появляется дополнительный пункт Поиск решения. Рассмотрим его использование для решения задач ЛП на примере 2.1. Введем данные в электронную таблицу так, как это показано ниже. Таблица 2.10
Для переменных x1 и x2 отведены ячейки B2 и C2. Эти ячейки называются изменяемыми ячейками. В эти ячейки ничего не заносится, и в результате решения задачи в них будут записаны оптимальные значения переменных. В ячейки D3–D6 вводятся формулы для вычисления левых частей ограничений, а в ячейку D7 – формула для вычисления целевой функции. Знаки доллара в формулах введены для того, чтобы формулы в ячейках D4–D7 можно было получить копированием формулы из ячейки D3.
Рис. 2.15
Затем в меню Сервис выбираем процедуру Поиск решения. В появившемся окне (рис. 2.15) устанавливаем целевую ячейку D7, выбираем вариант оптимизации (максимизация), вводим адреса изменяемых ячеек и ограничения. Для ввода ограничений используем кнопку Добавить. Кнопки Изменить и Удалить служат соответственно для изменения или удаления помеченного ограничения. Кнопка Предположить служит для автоматического выбора изменяемых ячеек. Далее нажимаем кнопку Параметры, и в появившемся окне устанавливаем флажки Линейная модель (в этом случае при решении задачи будет использоваться симплекс-метод) и Неотрицательные значения. Остальные значения можно оставить без изменения. Нажимаем кнопку ОК. Для решения задачи в окне Поиск решения нажимаем кнопку Выполнить. После нахождения решения появляется диалоговое окно для выбора типа отчета. Выбираем два типа: Результаты и Устойчивость, и нажимаем ОК. Первоначальная электронная таблица заполняется результатами, полученными при решении (табл. 2.11). Таблица 2.11
Отчеты появляются на отдельных листах книги Excel. Отчет Результаты состоит из трех таблиц и имеет следующий вид. Таблицы 2.12
В первой из этих таблиц указано оптимальное значение целевой функции, во второй – значения переменных, в третьей – оптимальные расходы ресурсов, их статус и допустимое снижение запасов недефицитных ресурсов без изменения оптимального решения. Фактически вся эта информация содержится в итоговой таблице 2.11 (или легко извлекается из нее). Отчет Устойчивость состоит из двух таблиц и имеет следующий вид: Таблицы 2.13
Первая из этих таблиц содержит диапазоны изменения коэффициентов целевой функции, в которых не происходит изменения оптимального решения. Во второй таблице приводятся теневые цены ресурсов и диапазоны изменения запасов каждого из ресурсов (при условии неизменности других ресурсов), в которых теневые цены остаются неизменными. Значения 1E+30, приведенные в таблице, означают возможность бесконечного увеличения правых частей соответствующих ограничений без изменения теневых цен. При решении задач ЦЛП, в том числе и задач с булевыми переменными, с помощью программы Поиск решения, никаких дополнительных сложностей не возникает: нужно лишь при вводе ограничений ввести дополнительные ограничения – все или часть переменных принимают целые (или двоичные) значения. Для таких задач выводится только один тип отчета – отчет по результатам. Решение транспортной задачи в Excel проиллюстрируем на примере 2.12. Введем данные в электронную таблицу так, как показано в таблице 2.14. Таблица 2.14
В ячейки B3: F6 запишем исходные данные: в ячейках B3: E5 содержатся тарифы перевозок от соответствующего поставщика к соответствующему потребителю, в ячейках B6: E6 – потребности потребителей, а в ячейках F3: F5 – запасы поставщиков. Ячейки B7: E9 отведем под значения переменных – объемы перевозок от соответствующего поставщика к соответствующему потребителю, т. е. эти ячейки будут изменяемыми. В ячейках B10: E10 содержатся формулы, по которым подсчитывается общий объем груза, перевезенный данному потребителю, а в ячейках F7: F9 – объем груза, вывезенного от данного поставщика. В ячейке F10 содержится формула для целевой функции – суммарная стоимость всех перевозок. Выполнив процедуру Поиск решения (указав в качестве цели минимизацию содержимого ячейки F10 и введя ограничения F7: F9 = F3: F5, B10: E10 = B6: E6), получим результат в виде таблицы 2.15. Таблица 2.15
[1] Существуют и другие универсальные методы решения ЗЛП. Например, метод разрешающих множителей, разработанный советским математиком Л. В. Канторовичем в 1939 г. [2] Название ОЗЛП и КЗЛП не являются общепринятыми. В ряде работ основную задачу называют канонической, а каноническая не имеет специального названия. [3] Целой частью числа a называется наибольшее целое число, не превосходящее a. Оно обозначается [ a ]. Например, [2, 3]=2, а [–2, 3]=-3. Дробной частью числа a называется разность между числом a и его целой частью. Она обозначается {a}. Таким образом, по определению, {a}=a–[a], т. е. a=[a]+{a}. Например, {2, 3}=2, 3 – 2=0, 3,
|
