B.3. Линейные оптимизационные задачи

Если целевая функция и система ограничений являются линейно зависимыми от переменных х₁, х₂, ... х_n, для решения оптимизационной задачи используются методы линейного программирования.

Линейная математическая модель в общем случае имеет следующий вид:

Z = z₁x₁+z₂x₂+...+z_nx_n → extr,

a₁₁x₁+a₁₂x₂+...+a_1nx_n < b₁,

a₂₁x₁+a₂₂x₂+...+a_2nx_n = b₂,

. . . . . . . . . . . . . . . . . . . . . . . .

a_m1x₁+a_m2x₂+...+a_mnx_n > b_m,

х_i > 0, i = 1, 2, ... n,

где z_i, b_j, a_ji - заданные постоянные величины, i = 1.2,…n; j = 1, 2, ... m.

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

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

Допустим, что в линейной математической модели (2.1) ищется минимум целевой функции

Z = z₁x₁+z₂x₂+...+z_nx_n → min.

Если по этой же математической модели нужно найти максимум целевой функции Z, то у коэффициентов целевой функции меняются знаки на противоположные и вновь ищется минимум функции Z

Z = - z₁x₁ - z₂x₂ -...- z_nx_n → min.

Таким образом, min (- z₁x₁- z₂x₂ -…- z_nx_n) = max ( z₁x₁+ z₂x₂+ …+ z_nx_n)

Порядок выполнения.

Пример. Решить задачу линейного программирования:

L = 5x₁ - 2x₃ min

- 5x₁ - x₂ + 2x₃ ≤ 2

- x₁+x₃ + x₄ ≤ 5

- 3x₁ + 5x₄ ≤ 7

X1, x2, x3, x4 – целые

0≤x_i≤100, i1,2…4

Для решения подобных задач в MS EXCEL предназначена команда Поиск решения из меню Сервис.

Пусть значения x₁, x₂, x₃, x₄ хранятся в ячейки A1:A4, a значение функции L - в ячейке С1.

Введем целевую функцию:

С1 = –5*A1 – 2*A3

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

С2 = –5*A1 - A2 + 2*A3

С3 = –А1 +А3 + А4

С4 = –3*А1 + 5*А4.

Пример заполнения экранной формы в MS Excel показан на рис. 1.

Рисунок. 1.

Таким образом, было задано условие исходной задачи линейного программирования. Выполним команду из главного меню Сервис  Поиск решения (рис. 1).

Рисунок. 2.

Устремим целевую функцию в ячейке C1 к минимуму. Для этого введем в поле Установить целевую функцию значение С1 и установим опцию "равной минимальному значению". В поле Изменяя ячейки необходимо указать адреса ячеек, в которых хранятся изменяемые значения. В нашем случае это ячейки А1:А4.

Для добавления ограничений необходимо щелкнуть по кнопке Добавить, появится диалоговое окно Добавить ограничение (рис. 2)

Рисунок. 3.

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

Щелчок по кнопке OK означает ввод очередного ограничения и возврат к диалоговому окну Поиск решения.

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

В нашем случае окно будет иметь вид, изображенный на рис. 3. Щелчок по кнопке Выполнить начнет процесс решения задачи, завершится который появлением диалогового окна, изображенного на рис. 4.

Рисунок. 4.

Рисунок. 5.

Щелчок по кнопке OK приведет к появлению в ячейке С1 значения целевой функции L, а в ячейках A1:A4 - значений переменных x₁-x₄, при которых целевая функция достигает минимального значения (рис. 6).

Рисунок. 6.

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

Итак, назначение основных кнопок и окон диалогового окна Поиск решения:

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

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

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

• Кнопка Предположить отыскивает все неформульные ячейки, прямо или непрямо зависящие от формулы в окне Установить целевую ячейку, и помещает их ссылки в окно Изменяя ячейки.

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

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

• Кнопка Выполнить запускает процесс решения определенной задачи.

• Кнопка Закрыть закрывает окно диалога, не решая проблемы. Сохраняются лишь изменения, сделанные при помощи кнопок Параметры, Добавить, Изменить и Удалить. Не сохраняются изменения, произведенные после использования данных кнопок.

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

• Кнопка Сбросить очищает все текущие установки задачи и возвращает все параметры к их значениям по умолчанию.

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

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

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

В задачи целочисленного программирования добавляется ограничение, что все x_i должны быть целыми.