Двойственные цены для третьего и четвертого ограничений в данной модели равны нулю при изменении значений правых частей этих неравенств от -1,5 до со и от 1,5 до со соответственно. Это означает, что ограничения, налагаемые рынком на структуру производства (ограничение на производство краски для внутренних работ до 2 т и т.п.), в данной ситуации не оказывают влияния на оптимальное решение.

2.4.2. Решение задач ЛП с помощью Excel

Покажем на модели Reddy Mikks, как надо располагать данные на рабочем листе, чтобы было удобно использовать средство Excel Поиск решения (файл рабочей книги ch2SolverReddyMikks.xls5). В верхней части рис. 2.10 показано табличное представление этой модели. Здесь содержится 4 типа данных:

1) входные данные (затененные ячейки В5:С9 и F6:F9),

2) значения переменных и целевой функции (ячейки в прямоугольнике B13:D13),

3) формулы, по которым вычисляются значения целевой функции и левых частей ограничений (ячейки D5:D9) и

4) поясняющие заголовки и надписи.

- £=В5*В$13+С5*С$13

Б С Р~1 Е Модель Reddy Mikks

Всего Ограничении

Up--

Поиск решения

□ Установить целевую ячейку:

Равной: <! максимальному значению

<** минимальному значению Изменяя ячейки:

<~ значению:

Выполни!

Закрыт-

Параметр!

Восста Га

Рис. 2.10. Решение задачи ЛП в Excel

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

6 Рабочие книги Excel, которые упоминаются в первых девяти главах, русифицированы и содержатся на прилагаемом к книге компакт-диске. Их названия совпадают с названиями исходных файлов, перед которыми стоит слово Копия . Например, русифицированный вариант данной рабочей книги имеет название Копия ch2SolverReddyMikks.xls. - Прим. ред.

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

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

Отметим, что вы должны ввести формулу только в ячейку D5, а затем ее надо скопировать в ячейки D6:D9. Чтобы правильно скопировать формулы, в формуле ячейки D5 надо ссылки на ячейки В13 и С13 (содержащих значения хх и х2) сделать абсолютными в виде $В$13 и $С$13. Для больших табличных моделей в ячейку D5 можно ввести формулу

= СУММПРОИЗВ(В5:С5;$В$13:$С$13) и затем скопировать ее в ячейки D6:D9.

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

в поле ввода Установить целевую ячейку вводится D5;

устанавливается переключатель Равной максимальному значению;

в поле ввода Изменяя ячейки вводится $В$13:$С$13.

Эта информация указывает средству Поиск решения, что переменные находятся в ячейках В13 и С13, и надо найти максимум целевой функции, значение которой вычисляется в ячейке D5.

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

$D$6:$D$9<=$F$6:$F$9

Напомним, что в ячейках F6:F9 записаны значения правых частей ограничений. Теперь осталось ввести ограничения неотрицательности для переменных. С помощью диалогового окна Добавление ограничения вводим

$В$13:$С$13>=0

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

Теперь все готово для решения нашей задачи, достаточно щелкнуть на кнопке Выполнить в диалоговом окне Поиск решения. Но перед этим желательно проверить установленные параметры работы средства Поиск решения (максимальное время поиска решения, максимальное количество итераций, относительная погрешность и т.д.), для чего надо открыть диалоговое окно Параметры поиска решения, щелкнув на кнопке Параметры. Самое важное - установить опцию Линейная модель. В этом же окне можно указать, что все переменные должны быть неотрицательными (опция Неотрицательные значения).6

Если табличная модель создана правильно, то решение появится в выходных ячейках табличной модели (в нашем случае в ячейках B13:D13). Также появится новое диалоговое Результаты поиска решения, которое даст возможность получить более детальную информацию о решении в виде отчетов, включая важный отчет по устойчивости. Эти отчеты формируются на отдельных листах рабочей книги. На рис. 2.11 показан отчет по устойчивости для модели Reddy Mikks. Информация в этом отчете полностью совпадает с той, что предоставляет программа TORA, и интерпретируется аналогичным образом. Заметим, что здесь теневая цена - то же самое, что dual price (двойственная цена) в отчете программы TORA.

Необходимо подчеркнуть, что описанная табличная модель Reddy Mikks построена и решена прямолинейно . Другие модели могут потребовать определенных ухищрений и преобразований для того, чтобы к ним можно было применить средство Поиск решения. Один класс таких моделей ЛП, а именно сетевых моделей, будет рассмотрен в главе 6.

2.4.3. Решение задач ЛП с помощью LINGO и AMPL

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

Для выполнения таких задач существует несколько коммерческих программных пакетов, среди которых назовем AMPL, GAMS, LINGO и MPL. Основная идея

Необходимо предостеречь от некоторых причуд средства Поиск решения. Если вы зададите слишком малое значение Относительная погрешность (например, 0,000000001), то можете получить странное сообщение, что для вашей модели не выполняются предположения о линейности. Также вследствие округления значений в выходных отчетах можно получить не совсем точные значения (например, 1Е-14 вместо 0 или 9,999999999999 вместо 10).