Использование линейного программирования для решения задач оптимизации

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

Геометрический метод

Рассмотрим задачу линейного программирования в стандартной форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c1x1+c2x2 принимает максимальное (или минимальное) значение.

Рассмотрим так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е. F = a, или

c1x1+c2x2 = а (1)

линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

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

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

Уравнение линии функции (1) есть уравнение прямой линии. При различных уровнях а

Линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами c1 и c2 и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные “параллели ”, расположенные обычно под углом к осям координат.

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

Пусть имеются три линии уровня :

F=c1x1 + c2x2 = а1 (I)

F=c1x1 + c2x2 = а2 (II)

F=c1x1 + c2x2 = а3 (III)

Причём линия II заключена между линиями I и III. Тогда а1 < а2 < а3 и а1 > а2 > а3.

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

Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на какой них уровень больше. Например, одну из линий взять проходящей через начало координат (если линия функция имеет вид F=c1x1 + c2x2, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1 – это точка С или А).

Двойственная задача.

Общая схема построения двойственной задачи.

Если задана общая задача ЛП:

где D определяется системой уравнений и неравенств:

то двойственной по отношению к ней называется общая задача ЛП:

где D* определяется системой уравнений и неравенств:

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1.  Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

3.  Матрица ограничений задачи А транспонируется.

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

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

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

((D*)*, (f*)*)≡(D, f),

Основные теоремы:

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

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

Теорема 3 (об оценках). Значение переменных в оптимальном  решении двойственной задачи представляет собой оценки влияния свободных членов bi в системе ограничения прямой задачи на величину целевой функции f(x*)

II. Практический раздел

2.1 Решение транспортной задачи

На три базы: А1, А2, А3 поступил однородный груз в количествах : 120,150,100, соответственно. Груз требуется перевезти в пять пунктов:85 в пункт B1, 65 в пункт В2, 90 в пункт В3,  60 в пункт В4, 70 в пункт В5.

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

Решение:

Математическая модель транспортной задачи:

F = ∑∑cijxij,    (1)

при условиях:

∑xij = ai,  i = 1,2,…, m,   (2)

∑xij = bj,  j = 1,2,…, n,   (3)

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

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 120 + 150 + 100 = 370

∑b = 85 + 65 + 90 + 60 + 70 = 370

Занесем исходные данные в распределительную таблицу.