Решение оптимизационных задач в Excel

Пример 1 Транспортная задача.

Груз, хранящийся на двух складах (A и B) и требующий для перевозки 20 и 30 автомашин соответственно, необходимо перевезти в три магазина. Первому магазину требуется 10 машины груза, второму – 30 и третьему – 10. Стоимости перевозки одной автомашины указаны в следующей таблице:

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

Решение задачи

1.Подготовка задачи к решению

Пусть x_ij количество автомашин перевезенных из пунктов (склады А и В) отправления в пункты назначения (магазины 1, 2 и 3);

Тогда система ограничений и целевая функция(транспортные расходы) запишутся следующим образом:

4x₁₁ + 9х₁₂ + 3х₁₃ +4х₂₁+8 х₂₂+x₂₃Þ min (целевая функция);

2.Подготовка рабочей книги.

Для решения задачи в Excel запишем ее в виде, представленном на рис. 1.

Рисунок 1 – Вид рабочего листа Excel

Далее вызываем Поиск решения из меню Сервис.

Определяем целевую ячейку (в нашем случае D18), устанавливаем переключатель в минимальное значение. Вводим диапазон изменяемых ячеек ($B$4: $D$5) и вносим ограничения.

Прежде всего, количество перевозимого груза не может быть отрицательным ($B$4: $D$5$> = 0), далее добавляем ограничения на потребности и запасы груза, которые должно быть равны требуемым (В$13=D$13), и т.д. по всем ограничениям.

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

Пример 2 ЗАДАЧА ПЛАНИРОВАНИЯ.

Рассмотрим в качестве примера мебельную фабрику, производящую столы и стулья. Расход ресурсов на их производство и прибыль от их реализации представлены в таблице:

Кроме того, на производство 80 столов заключен контракт с муниципалитетом, который должен быть безусловно выполнен. Необходимо найти такую оптимальную производственную программу, чтобы прибыль от реализации продукции была максимальной.

Пусть x₁ - количество столов;

х₂ - количество стульев.

Тогда система ограничений и целевая функция запишутся следующим образом:

180 x₁ + 20 х₂ Þ max (целевая функция, выражающая планируемую прибыль в рублях от реализации всего объема продукции);

0.5 x₁ + 0.04 х₂ 200 (ограничения по имеющемуся объему древесины);

12 x₁ + 0.6 х₂ 1800 (ограничения по доступному объему трудовых ресурсов);

x₁80 (контракт с муниципалитетом);

x₁ 0; х₂ 0;

x₁, х₂ - целые числа.

Для подготовки к решению задачи в Excel запишем ее в виде, представленном на рис. 4

Рисунок 2 – Запись исходных данных для решения задачи линейной оптимизации

Для решения задачи вызовем меню Сервис-Поиск решения.

В открывшемся диалоговом окне Поиск решения (рис. 5) укажем:

· адрес целевой ячейки (в нашем примере D5);

диапазон искомых ячеек (А2: A3);

· ограничения: А2> =80

A2: A3=целое

A2: A3> =0

В2< =D2

B3< =D3.

Рисунок 3 – Диалоговое окно Поиск Решения

Добавления, изменения и удаления ограничений производятся с помощью кнопок Добавить, Изменить, Удалить.

Для нахождения оптимального решения нажмем кнопку Выполнить. В результате в ячейке таблицы получим значение целевой функции – 42400 рублей при x₁ = 80 и x₂ = 1400.

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

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

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

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

* сохранить на текущем рабочем листе найденное оптимальное решение;

* восстановить первоначальные значения;

* сохранить сценарий;

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

Рисунок 5 - Диалоговое окно Результаты поиска решения

Если щелкнуть по кнопке ОК, то на месте исходной таблицы получим таблицу с найденными оптимальными значениями.