Зенкевич Н.А. Практикум по исследованию операций

Подождите немного. Документ загружается.

6.1. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ EXCEL 141

В результате получаем оптимальное решение модели.

Рис.6.1.6. Результаты решения

Отчет по результатам. Отчет по результатам подробно описывает табличную мо-

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

Для ячеек с ограничениями кроме исходного неравенства указываются еще два значе-

ния: статус и разница. Если ограничение, выраженное неравенством с операторами ≤

или ≥, при нахождении оптимального решения становится равенством, то эта конструк-

ция приобретает статус связанной. Соответственно в графе Разница пишется ноль. В

противном случае, если конструкция сохраняется в виде неравенства, в графе Разница

фиксируется разность между ограничением и значением, принятым при решении, такая

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

В рассматриваемом примере значение максимума целевой функции z = 12, 67 на-

ходится таблице Целевая ячейка в графе Результат, при начальных значениях, на-

ходящихся в изменяемых ячейках (исходное значение z = 0). Оптимальные значения

переменных x

, x

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

таблицы Ограничения находим, что связанными являются ограничения (1)и (2), т.е.

ресурсы А и В являются дефицитными и используются полностью, о чем говорит Раз-

ница равная нулю для этих ограничений. Спрос не является дефицитным, т.к. Статус

соответствующей конструкции – несвязанная и Разница не равна нулю (см. рис.6.1.7).

142 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

Рис.6.1.7. Отчет по результатам

6.1.3 Транспортная задача

Рассмотрим следующую транспортную задачу. Даны объемы производства трех заводов,

вектор a

и спрос четырех рынков вектор b

. Представленная транспортная модель –

сбалансирована, то есть

i=1

j=1

= 100.

1 8 2 8 30

c = 4 7 5 1 50

5 3 4 4 20

15 15 40 30

6.1.4 Решение транспортной задачи средствами Excel

Исходные данные. Оформим исходные данные задачи (матрицу стоимостей перевоз-

ки)в виде таблицы ячейки B9:E11. В отдельные строку и столбец внесем данные об

объеме производства заводов G9:G11 и спросе рынков B11:E11.

6.1. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ EXCEL 143

Рис.6.1.8. Табличная модель транспортной задачи

Изменяемые ячейки. Отведем в таблице место под изменяемые ячейки B9:E11,

которые соответствуют плану перевозок x

. Выделим эти ячейки рамкой – здесь мы

получим оптимальный план перевозок.

Целевая ячейка. В ячейке С3 введем целевую функцию L =

i=1

j=1

с помощью

формулы:

= СУММПРОИЗВ(B11 : E13; B16 : E18).

Функция СУММПРОИЗВ находится в разделе Математические и возвращает сум-

му произведения соответствующих элементов массивов.

Ограничения. Нам известно, что объем производства каждого из заводов может

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

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

просуммировать величины x

по каждому i и j.

Просуммируем каждое x

по j, для этого в ячейку B21 записываем формулу

= СУММ(B16 : B18),

аналогично поступаем с ячейками C21, D21, E21.

В меню Сервис находим пункт Поиск решения. (Этот пункт меню не входит в

стандартную установку Excel, если он не установлен, необходимо его установить допол-

нительно с компакт-диска MS Oﬃce.)

144 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

Рассмотрим элементы диалогового окна Поиск решения (см. Рис. 6.1.9.)

Рис. 6.1.9. Диалоговое окно Поиск решения

В поле Установить целевую ячейку дается ссылка на ячейку с функцией, для

которой будет находиться максимум, минимум или заданное значений. В нашем случае

вводится С3. В нашей задаче установим переключатель в положение Минимальному

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

В поле Изменяя ячейки в нашем случае введем диапазон $B$16:$E$18.

Ограничения, налагаемые на переменные задачи, отображаются в поле Ограниче-

ния. (рис. 6.1.10)

Рис.6.1.10. Диалоговое окно Добавление ограничения

В результате должны быть введены следующие ограничения:

$B$21 = $B$14;

$C$21 = $C$14;

$D$21 = $D$14;

$E$21 = $E$14;

$G$16 = $G$9;

$G$17 = $G$10;

$G$18 = $G$11;

Теперь нажмите кнопку Параметры в диалоговом окне Поиск решения, для того

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

6.1. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ EXCEL 145

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

Вернитесь в диалог Поиск решения нажатием кнопки ОК. Нажатие кнопки Вы-

полнить открывает окно Результаты поиска решения, которое сообщает, что реше-

ние найдено (рис. 6.1.12.).

Рис.6.1.12. Диалоговое окно Результаты поиска решений

В результате получаем оптимальное решение модели.

Рис.6.1.13. Оптимальное решение транспортной модели

146 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

В рассматриваемом примере значение максимума целевой функции L = 240 находит-

ся таблице Целевая ячейка в графе Результат, при начальных значениях, находящих-

ся в изменяемых ячейках (исходное значение L = 0). Оптимальные значения переменных

находятся в таблице Изменяемые ячейки в графе Результат (см рис.6.1.14.).

Рис.6.1.14. Отчет по результатам

6.2 Решение оптимизационных задач средствами LINGO

Пакет LINGO предназначен для решения линейных оптимизационных задач. При помо-

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

Например, линейные модели большой размерности, решаемые при помощи симплекс-

метода, транспортная задача, задача о коммивояжере. Пакет LINGO может использо-

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

живает связь с различными системами управления базами данных такими как: Access,

dBase, Excel, FoxPro, Oracle, Paradox, SQL Server.

Тем самым данный пакет может быть применен для работы с реальными моделями.

Рассмотрим как можно использовать LINGO для решения рассмотренных ранее клас-

сов задач.

6.2. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ LINGO 147

6.2.1 Начальные сведения о пакете LINGO

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

Рис.6.2.1. Главное окно программы

Главное меню состоит из пунктов: File, Edit, LINGO, Windows, Help.

Пункт меню File содержит команды для создание нового документа, сохранения до-

кумента, печати документа и вызова ранее сохраненных документов).

Пункт меню Edit содержит команды по редактированию текста математической мо-

дели.

Пункт меню LINGO содержит команды для решения модели и создания отчетов о

полученом решении.

Пункт меню Windows содержит команды по управлению окнами программы.

Пункт меню Help содержит справочную информацию о программе.

6.2.2 Первый способ решения задачи ЛП в LINGO

Построим математическую модель в задаче об использовании сырья и решим ее с ис-

пользованием пакета LINGO.

Задача об использовании сырья

148 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

Предположим, что некоторое предприятие после выполнения основной производ-

ственной программы располагает запасами сэкономленного сырья трех видов – s

, s

соответственно в количествах b

, b

условных единиц. Из этого сырья может быть

изготовлено два вида изделий P

и P

. Известны – a

количество единиц вида сырья,

идущего на изготовление P

-го вида изделия, и c

– доход, получаемых от реализации

одной единицы каждого вида изделия. Все указанные величины представлены в следу-

ющей таблице:

Расход сырья на изделие

Вид сырья Запас сырья P

21(b

) 3(a

) 1(a

)

30(b

) 2(a

)

16(b

) 0(a

) 3(a

)

Прибыль от продажи единицы изделия P

равна 3 у.е., а для изделия P

– 2 у.е.

Задача сводится к тому, чтобы составить такой план выпуска п родукции, при котором

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

Для построения математической модели данной задачи вводятся обозначения: x

количество единиц изделий вида P

, x

- количество единиц изделий вида P

, которое

может выпустить предприятие. Зная количество сырья каждого вида, идущее на изго-

товление одной единицы изделия, составляем систему ограничений:

+ x

≤ 21,

+ 3x

≤ 30,

≤ 16;

≥ 0, x

≥ 0.

Последние два ограничения получаем исходя из физического смысла задачи.

Доход, получаемый от продажи x

единиц изделий P

и x

единиц изделий P

составит

z = 3x

+ 2x

Предприятие максимизирует получаемых доход, следовательно окончательная форму-

6.2. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ LINGO 149

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

max z = max(3x

+ 2x

);

+ x

≤ 21,

+ 3x

≤ 30,

≤ 16;

≥ 0, x

≥ 0.

После того как формализовали задачу, ее можно решать с использованием пакета LINGO.

Для этого надо в окне LINGO model записать нашу модель на языке LINGO. Язык дан-

ного пакета позволяет очень легко и наглядно записывать линейные модели.

Наиболее просто исходная задача в пакете LINGO может быть записана следующим

образом:

Рис.6.2.2. Математическая модель

Для того чтобы решить модель в активном окне необходимо на Панели инструмен-

тов

выбрать кнопку . После того как будет вызвана команда Solve, LINGO проверит

модель на наличие в ней синтаксических ошибок, например если LINGO найдет синтак-

сическую ошибку, тогда вашему вниманию будет предложено следующее окно:

Рис.6.2.3. Диалоговое окно LINGO Error Message

150 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

В окне LINGOError Message (Ошибка), LINGO показывает номер строки где обнару-

жена ошибка, текст строки и ставит указатель на символ, на котором была определена

ошибка. В большинстве случаев LINGO точно указывает на место, в котором была до-

пущена синтаксическая ошибка, однако бывают исключения. В этом случае необходимо

обратить внимание на соседние строки. В нашем случае LINGO указывает, что не хва-

тает знака (*) между константой 3 и переменной x_ 1.

После того как была выполнена команда Solve (в случае когда синтаксических оши-

бок больше не обнаружено), появляется окно Solver status window (окно состояния моде-

ли). Это окно содержит информацию о структуре модели, и предоставляет возможность

отсрочить решение модели. Ниже представлен вид Solver status window.

Рис.6.2.4. Диалоговое окно Solver status window

Solver status window используется для контроля процесса решения модели и ее раз-

мерности. Solver status window позволяет прервать работу модели используя Interrupt

Solver button. В большинстве случаев возможно возобновление вычислений в модели,

исключение составляют линейные модели, прерывание которых может привести к бес-

смысленным результатам. Однако это не является большой проблемой, поскольку время,

затрачиваемое на решение линейной модели очень мало, и следовательно большой необ-

ходимости в прерывании процесса решения нет.

Кнопка Close закрывает окно Solver status window. Доступ к этому окну можно по-

лучить из пункта меню Window|Status Window.

После окончания расчетов, LINGO создает окно с отчетом для модели. В отчете