Методическое пособие по оптимизационным задачам

Оптимизационные задачи – это такие экономические задачи, в которых необходимо найти экстремальное (т.е. максимальное или минимальное) значение целевой функции, действуя в рамках заданных ограничений.

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

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

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

Рассмотрим принцип решения оптимизационных задач на конкретных примерах.

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

Требуется:

1. Сформулировать прямую оптимизационную задачу на максимум общей выручки от реализации изделий.

2. Найти оптимальный план выпуска изделий с помощью инструмента «Поиск решения» в программе Excel.

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

Пусть Х₁, Х₂, Х₃, Х₄ – количество изделий каждого вида, которое требуется изготовить.

Так как для изготовления этих изделий могут использоваться только имеющиеся запасы сырья, то составим систему ограничений, исходя из нормы расхода сырья на единицу изделия:

1* Х₁ + 0*Х₂ + 2*Х₃ + 1*Х₄ ≤ 180

0* Х₁ + 1*Х₂ + 3*Х₃ + 2*Х₄ ≤ 210

4* Х₁ + 2*Х₂ + 0*Х₃ + 4*Х₄ ≤ 800

Количество изделий может быть только положительным:

Х₁ ≥0; Х₂ ≥0; Х₃ ≥0; Х₄ ≥0;

Для нахождения оптимального плана выпуска требуется найти такие значения Х₁, Х₂, Х₃, Х₄ , которые будут удовлетворять системе ограничений и при которых целевая функция (выручка) получит максимальное значение.

Общая выручка рассчитывается, исходя из количества изделий и их цены:

F(X) =9* Х₁ + 6*Х₂ + 4*Х₃ + 7*Х₄ → max

(F(X)- целевая функция).

Примечание. Подобные задачи в программе Excel с помощью инструмента «Поиск решения».

В Excel 2007 этот инструмент находится в пункте «Данные».

Если он не подключен, то необходимо выполнить следующие шаги:

- другие команды

- надстройки

- управление (надстройки Excel) – перейти

В Excel 2003 подключаем данный инструмент через Сервис – Надстройки – Поиск решения

Ход решения задачи в программе Excel:

1. Ввести таблицу с данными задачи в программу Excel:

2. Для искомых данных (Х₁, Х₂, Х₃, Х₄) выделить ячейки B10:E10 (сначала они будут пустыми, затем после решения задачи в них будет отражен результат решения)

3. Записать формулы для левой части каждого неравенства из системы ограничений в ячейки В12, В13, В14

В ячейке В12 должна быть формула:

=B3*$B$10+C3*$C$10+D3*$D$10+E3*$E$10

(знак доллара ставится клавишей F4 для того, чтобы зафиксировать соотв. ячейки (абсолютная адресация). Формулу можно скопировать в ячейки В13 и В14).

В ячейке В13 должна быть формула:

=B4*$B$10+C4*$C$10+D4*$D$10+E4*$E$10

В ячейке В14 должна быть формула:

=B5*$B$10+C5*$C$10+D5*$D$10+E5*$E$10

Примечание. В этих ячейках будет отображаться 0, так как значения переменных пока нулевые.

4. Затем в ячейку В17 нужно записать формулу для целевой функции:

=B6*$B$10+C6*$C$10+D6*$D$10+E6*$E$10

(ее также можно скопировать из ячейки В14)

5. После того, как все формулы записаны, следует открыть:

Данные – Поиск решения

6. В бланке «Поиск решения» необходимо указать:

Оптимизировать целевую функцию: В17

До ● Максимум

Изменяя ячейки переменных:

В соответствии с ограничениями:

Добавить

В окне «Добавление ограничения» в первой позиции «Ссылка на ячейки» указать ячейки В12:В14 (выделить их левой клавишей мыши), в середине выбрать знак ограничения (<=), в позиции «Ограничение» указать ячейки F3:F5 и нажать ОК.

Затем добавить еще одно ограничение:

(Так как количество изделий может быть только целым числом).

Следующий шаг