Решение задач линейного программирования и анализ чувствительности с помощью MS Excel

Окончательно математическая модель нашей проблемы запишется следующим образом:

 

максимизировать z = 2000*х1 + 2500*х2 при выполнении ограничений

 

х1 + х2 £ 500,

х1 ³ 200,

х2 £ 150,

0,05*х1 + 0,1*х2 £ 50,

0,07*x1 + 0,08*x2 £ 30,

0,04*x1 + 0,07*x2 £ 25,

х2 ³ 0.

 

Любое решение (т.е. пара значений переменных х1 и х2), удовлетворяющее всем ограничениям модели, называется допустимым. В нашем примере решение х1 = 200 и х2 = 150 будет допустимым, поскольку не нарушает ни одного ограничения, включая условия неотрицательности. Чтобы убедиться в этом, надо подставить значения х1 = 200 и х2 = 150 в левые части ограничений, выполнить вычисления и проверить, что ни одно неравенство не нарушается. Значение целевой функции при этом решении будет равно z = 2000*200 + 2500*150 = 775 000 (руб.).

Итак, математическая модель построена, осталось найти решение модели. Для выполнения этого дела мы привлечем программу электронных таблиц Excel, а еще точнее — надстройку Поиск решения.

 

III. Прежде чем начать выполнение каких-либо вычислений в Excel, надо перевести нашу построенную математическую модель на рабочий лист Excel. Для этого следует определить, в каких ячейках будут располагаться переменные решения, записать в нужные ячейки формулы, по которым будут вычисляться целевая функция и функции ограничений (левые части ограничений), надо записать в отдельные ячейки значения правых частей ограничений. Всю эту совокупность значений и формул, записанных на рабочем листе, назовем табличной моделью.

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

♦ Значения переменных располагаются в отдельных ячейках и группируются в отдельный блок ячеек.

♦ Каждому ограничению отводится отдельная строка или столбец таблицы. Ограничения группируются в отдельный блок ячеек.

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

♦ Коэффициенты целевой функции должны храниться в отдельной строке, располагаясь непосредственно под или над соответствующими переменными; формула для вычисления целевой функции должна находиться в соседней ячейке.

♦ В каждой строке ограничений за ячейками, содержащими коэффициенты данного ограничения, следует ячейка, в которую записывается вычисленное значение функции ограничения (значение левой части ограничения). За ней может следовать ячейка, в которой стоит соответствующий знак неравенства или равенства ограничения, а затем ячейка, содержащая значение правой части ограничения. Желательно, чтобы правые части ограничений были константами, а не формулами. Дополнительно можно иметь ячейку, в которой вычислена разность между значениями левой и правой частей неравенства.

♦ Условия неотрицательности переменных решения не обязательно включать в табличную модель. Как правило, они опускаются и указываются непосредственно в диалоговом окне средства Поиск решения.

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

Пример табличной модели для нашей задачи показан на рис. 1. Здесь значения переменных решения записаны в ячейках В4 и С4 с соответствующими заголовками в ячейках В3 и С3. Вначале значения переменных произвольные. Коэффициенты, стоящие перед переменными в формуле целевой функции, записаны в ячейки В8 и С8, а само значение целевой функции вычисляется в ячейке D8 (соответствующие заголовки записаны над этими ячейками). Ниже в диапазоне В11:С17 записаны коэффициенты функций ограничений, в диапазоне D11:D17 вычисляются значения левых частей ограничений, в диапазоне Е11:Е17 записаны знаки неравенств ограничений, а в диапазоне Fl1:F17 — значения правых частей ограничений. Наконец, внизу в строке 20 под «левым» заголовком Решение еще раз повторены значения переменных и целевой функции.

Рис. 1. Табличная модель для вычисления производственного плана

Формулы, по которым выполняются все вычисления на данном рабочем листе, показаны на рис. 2. Для вычисления линейных функций подходит функция СУММПРОИЗВ(массив1;массив2), которая суммирует попарные произведения элементов двух диапазонов, заданных аргументами функции массив1 и массив2. Например, формула =СУММПРОИЗВ($В$4:$С$4;В8:С8), вычисляющая значение целевой функции в ячейке D8, эквивалентна такой формуле: =В4*В8+С4*С8. Абсолютные ссылки $В$4:$С$4 на диапазон В4:С4, содержащий значения переменных х1 и х2, сделаны для того, чтобы можно было скопировать эту формулу из ячейки D8 в ячейки D11:D17 для вычисления левых частей неравенств, где также участвуют значения переменных решения.

Рис. 2. Формулы табличной модели

Левые части ограничений, поскольку это линейные функции, также вычисляются с помощью функции СУММПРОИЗВ. Даже если это простые ограничения типа х2 £ 150, которые здесь представляются как 0*x1 + 1*х2 £ 150 (ограничение 2 на рис. 1).

Обратите внимание на то, что ограничения сгруппированы по типу неравенств — сначала идут ограничения типа <=, а затем типа >=. Конечно, порядок представления этих групп несущественен.

Существенно само наличие групп однотипных ограничений, что позволит в дальнейшем задавать их в средстве Поиск решения не по отдельности, а целой группой. Знаки неравенств в диапазоне Е11:Е17 вставлены только для пояснения ограничений, средство Поиск решения их не использует. Зато средство Поиск решения использует заголовки строк, содержащих ограничения (использует в своих отчетах, как показано далее). Поэтому рекомендуется давать более содержательные заголовки, даже чем те, что показаны на рис. 1 в ячейках А11:А17. Например, такие: Ограничение на объем производства, Маркетинговое ограничение или Ограничение, не знаю, откуда оно взялось. С другой стороны, заголовки не являются обязательным элементом табличной модели — средство Поиск решения прекрасно вычислит результат и без них. Заголовки полезны для документирования модели.

Если вы не знаете, как отобразить на рабочем листе Excel формулы, а не значения (как на рис. 2), то это делается так. Надо выполнить команду Сервис->Параметры и в открывшемся диалоговом окне Параметры на вкладке Вид установить флажок формулы. Отображение формул может оказаться полезным, полезно при отладке модели. В Excel 2007 и выше отображение формул осуществляется через меню Параметры Excel->Дополнительно, выбирая для данного листа Показывать формулы, а не их значения

Теперь, когда табличная модель построена и проверена, пришло время ее решить. Для этого используем надстройку Excel Поиск решения. Если в меню Сервис вы не находите одноименной команды, то это означает, что данная надстройка не подключена к Excel. Для ее подключения выполните команду Сервис->Надстройки и в открывшемся диалоговом окне Надстройки в списке Доступные надстройки установите флажок Поиск решения.

Для Excel 2007 и выше Поиск решения находится во вкладке Данные->Анализ. Подключение осуществляется через меню Параметры Excel->Надстройки. Выбираем в списке Надстройки Excel и нажимаем кнопку Перейти…

Покажем общую схему применения средства Поиск решения для решения задач линейной оптимизации.

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

♦ переменные решения, точнее, ячейки, содержащие значения этих переменных, называются изменяемыми ячейками,

♦ ячейка, содержащая значение целевой функции, называется целевой ячейкой,

♦ ограничения так и будут называться ограничениями.

 

Схема применения средства Поиск решения выглядит так:

1. Пусть на рабочем листе Excel уже создана табличная модель задачи линейной оптимизации.

2. После проверки и отладки модели переходим к этапу оптимизации, выбрав команду Поиск решения в меню Сервис.

3. В открывшемся диалоговом окне Поиск решения укажите данные, необходимые для поиска оптимального решения (рис. 3).

Рис. 3. Задание  параметров для поиска решения

• В поле Установить целевую ячейку вводится адрес ячейки, содержащей значение целевой функции. Для нашей модели в это поле следует ввести D8, но лучше щелкнуть указателем мыши на этой ячейке, чтобы ввести ее адрес автоматически.

• Параметры области Равной диалогового окна Поиск решения позволяют задать тип оптимизации. В данном случае необходимо максимизировать значение целевой функции. Для этого нужно щелкнуть на переключателе максимальному значению.

• Поле Изменяя ячейки позволяет указать ячейки, в которых содержатся переменные модели; в данном случае это диапазон В4:С4.

4. Далее необходимо задать ограничения. Щелчок на кнопке Добавить открывает диалоговое окно Добавление ограничения, показанное на рис. 4,

• В нашем примере в поле Ссылка на ячейку вводим или указываем на рабочем листе ссылку на диапазон D11:D15, в соседнем поле оставляем знак неравенства <=, а в поле Ограничение вводим или указываем на рабочем листе ссылку на диапазон F11:F15.

• Щелкаем на кнопке Добавить и вводим вторую группу ограничений: в поле Ссылка на ячейку вводим D16:D17, в соседнем раскрывающемся списке выбираем знак неравенства >=, а в поле Ограничение вводим F16:F17. Затем щелкаем на кнопке ОК и возвращаемся в диалоговое окно Поиск решения.

Рис. 4. Задание  ограничений

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

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

• В данном примере, поскольку мы работаем с линейной моделью, надо установить флажок Линейная модель (рис. 5).

• Если в модели условия неотрицательности налагаются на все переменные, следует установить флажок Неотрицательные значения. В нашем примере условие неотрицательности налагается только на переменную x2 поэтому этот флажок мы не устанавливаем.

• Флажок Автоматическое масштабирование рекомендуем устанавливать всегда.

• Если хотите проследить каждую итерацию процесса вычисления, установите флажок Показывать результаты итераций. Если хотите сразу получить результат вычислений без подглядывания в вычислительную кухню, не устанавливайте этот флажок.

• Переключатели, расположенные в областях Оценки, Разности, Метод поиска, предназначены для нелинейных моделей. Поэтому сейчас мы их оставляем без внимания.

• Щелчок на кнопке ОК возвращает в диалоговое окно Поиск решения.

6. После задания необходимых данных (указания ячейки, содержащей формулу для вычисления целевой функции, ячеек, в которых находятся переменные, и задания ограничений) щелкните на кнопке Выполнить.

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

8. После окончания работы Поиск решения выведет на экран диалоговое окно Результаты поиска решения (рис. 6), в котором можно указать, обновить ли исходную модель (т.е. занести ли в ячейки значения оптимального решения) и создавать ли отчет.

Рис. 5. Диалоговое окно Параметры поиска решения

Диалоговое окно Результаты поиска решения сообщает о завершении поиска (см. рис. 6). Если оптимальное решение найдено, в диалоговом окне Результаты поиска решения должно отобразиться сообщение Решение найдено. Все ограничения и условия оптимальности выполнены. Если получено такое сообщение, можно или сохранить найденное решение, выбрав соответствующий параметр, или отбросить его, выбрав параметр Восстановить исходные значения. В результате ячейкам переменных будут возвращены значения, которые в них находились до запуска программы Поиск решения. Существует возможность также получить три типа отчетов о решении. Каждый отчет выводится на новый лист рабочей книги.

Рис. 6. Успешное завершение решения задачи оптимизации

В нашем примере решение найдено, оно показано на рис. 6: надо производить 257,14 т краски А и 150 т краски Б, при этом будет получена прибыль в размере 889 285,17 руб. В диалоговом окне Результаты поиска решения мы также указали, что надо создать отчеты.

 

IV. Теперь покажем, что делать дальше с полученным «компьютерным» решением, и как на его основе найти «настоящее» решение проблемы.