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

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

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

* удовлетворяют системе линейных уравнений

(4)

* являются неотрицательными, т.е.

(5)

* обеспечивают наименьшее значение линейной целевой функции

(6).

Всякое решение системы уравнений (4), удовлетво­ряющее системе неравенств (5), называется допусти­мым решением. Допустимое решение, которое минимизи­рует целевую функцию (6), называется оптимальным решением.

Рассмотрим пример задачи линейного программирова­ния (транспортную задачу).

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

Введем исходные данные. Ежедневно вывозится с пер­вой базы 12 т товара, со второй 15 т. При этом завозится в первый магазин 8 т, во второй 9 т, в третий 10 т. Стои­мость перевозки 1 т товара (в рублях) с баз в магазины дается следующей таблицей:

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

(7).

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

К данной системе уравнений нужно добавить систему неравенств

(8),

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

(9).

Таким образом, мы пришли к типичной задаче линей­ного программирования: найти оптимальные значения проектных параметров , удовлетворя­ющих условиям (7),(8) и минимизирующих об­щую стоимость перевозок (9).

Из анализа системы уравнений (7) следует, что только первые четыре уравнения являются независимы­ми, а последнее можно получить из них (путем сложе­ния первого и второго уравнений и вычитания из этой суммы третьего и четвертого уравнений). Поэтому фак­тически имеем систему

(10).

Число неизвестных на два больше числа уравнений, поэтому выразим через и все остальные неизвест­ные. Получим

(11).

Поскольку в соответствии с (8) все проектные параметры должны быть неотрицательны, то с учетом (11) получим следующую систему неравенств:

(12).

Эти неравенства можно записать в более компакт­ном виде:

, , (13).

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

(14).

Отсюда следует, что стоимость перевозок растет с уве­личением значений ; поэтому нужно взять их наи­меньшие допустимые значения. В соответствии с (13)

; примем . Исключая один из пара­метров, например , получим . Тогда

.

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