Линейное программирование

В случае, когда оптимизируемая целевая функция (3.1) и ограничения (3.2) линейны, задача оптимизации решается методами линейного программирования и обычно называется задачей линейного программирования. Задача линейного программирования заключается в нахождении n переменных x_l, x₂ х₁, минимизирующих данную линейную функцию (целевую функцию):

(3.4)

(или максимизирующую — Z) при линейных ограничениях-равенствах:

(3.5)

и линейных ограничениях-неравенствах:

(3.6)

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

(3.7)

при т < п линейных ограничениях-равенствах

(3.8)

и n линейных ограничениях-неравенствах

(3.9)

Допустимым решением (планом) задачи линейного программирования является упорядоченное множество чисел (x₁,x₂ ,..., x_n ), удовлетворяющих ограничениям (3.8) и (3.9). Это точка в n-мерном пространстве. Допустимое решение, минимизирующее целевую функцию (3.7), называется оптимальным решением (оптимальным планом).

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

Процесс решения задачи линейного программирования обычно состоит из ряда этапов:

1-й этап: осмысление задачи, выделение наиболее важных
качеств, свойств, величин, параметров. Это можно делать, составляя схемы, таблицы, графики и т.п.;

2-й этап: введение обозначений (неизвестных). Желательно
ограничиваться как можно меньшим количеством неизвестных,
выражая по возможности одни величины через другие;

3-й этап: создание целевой функции. Обычно в качестве
цели могут выступать максимальная стоимость всего объема
продукции, максимальная прибыль, минимальные затраты и т. п.
Целевая функция записывается в виде (3.4) или (3.7).

4-й этап: составление системы ограничений, которым
должны удовлетворять введенные величины (3.5), (3.6) или (3.8), (3.9).

5-й этап: решение задачи на компьютере.

Инструментом для поиска решений задач оптимизации в
Excel служит процедура Поиск решения (Кнопка “Office” > Параметры Ехсеl > Надстройки > Поиск решения > ОК(Процедура «Поиск решения» появится во вкладке данные)). При этом открывается диалоговое окно Поиск решения.

Оно содержит следующие рабочие поля:

Установить целевую ячейку — служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта
ячейка должна содержать формулу;

Равной — служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить число, необходимо ввести его
в поле;

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

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

Ограничения — служит для отображения списка граничных
условий поставленной задачи;

Добавить — используется для отображения диалогового
окна Добавить ограничение;

Изменить — применяется для отображения диалогового
окна Изменить ограничение;

Удалить — служит для снятия указанного ограничения;

Выполнить — используется для запуска поиска решения
поставленной задачи;

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

Параметры — применяется для отображения диалогового
окна Параметры поиска решения, в котором можно загрузить или
сохранить оптимизируемую модель и указать предусмотренные
варианты поиска решения;

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

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