55

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

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

, ( 6.1.0 )

где

,

- вектор размерности , ,

- матрица размера ранга ,

- вектор размерности , . ( 6.1.0 )

Скалярное произведение называется целевой функцией. Коэффициенты целевой функции - это координаты вектора .

Множество называется множеством ограничений или допустимой областью задачи линейного программирования.

Задача ( 6.1 .0 ) - . ( 6.1 .0 ) называется задачей линейного программирования в каноническом виде.

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

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

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

Пусть , - экстремальные (угловые) точки, - экстремальные направления множества .

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

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

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

То есть это перебор всех точек многогранного множества. Но количество экстремальных точек для реальных задач велико, и способ перебора неприемлем.

6.1Геометрическая интерпретация.

Поверхность уровня целевой функции

представляет гиперплоскость. При изменении получаем семейство параллельных гиперплоскостей. Направление наискорейшего роста задается градиентом:

Градиент рисуется по осям

Пример

6.2Двойственные задачи линейного программирования.

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

Если исходная задача(прямая)

при условии , ,

то двойственная задача представляет задачу на минимум

при условии , ,

то есть в развернутом виде:

прямая:

двойственная:

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

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

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

6.3Основные теоремы линейного программирования.

Теорема 1(теорема существования).

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

Теорема 2(теорема двойственности).

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

Теорема 3(теорема о дополняющей нежесткости).

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

Геометрическое изображение двойственных задач при m=n=2.

Альтернативные варианты , возникающие при решении задач линейного программирования.

нет решений

6.4Симплексный метод.

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

Рассмотрим каноническую форму задачи линейного программирования:

Задача линейного программирования, где многогранное множество записано в другом виде:

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

Аналогично переменные , на которые не наложено требование не отрицательности переменных, представляются в виде:

Эти и некоторые другие преобразования используются для приведения задачи к каноническому виду.

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

Возьмем некоторую экстремальную (угловую) точку .

В силу теоремы (о характеристике экстремальных точек) эту точку характеризует представление матрицы A в виде ,

где В - матрица m x m полного ранга, называемая базисом, N - матрица m x (n-m) .

По этой же теореме вектор может быть представлен

Переменные, соответствующие столбцам матрицы В, называются базисными и обозначаются . Остальные переменные, соответствующие столбцам матрицы N, называются внебазисными.

Рассмотрим теперь произвольную точку для которой , и представим ее в виде

, тогда равенство можно записать в виде .

Следовательно

( 6.4.0 )

Используя ( 6.4 .0 ) получаем

( 6.4.0 )

Если , то в силу не отрицательности справедливо неравенство

и - оптимальная экстремальная точка.

Пусть

В частности пусть для некоторого j компонента

Рассмотрим точку

, где

- (n - m) - мерный единичный вектор

Тогда из ( 6.4 .0 ) следует, что

( 6.4.0)

так как

то

при

Положим

и рассмотрим 2 случая:

1. Так как , то для при всех

Следовательно, x - допустимая точка тогда и только тогда, когда .

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

1. . Пусть определено соотношением

( 6.4.0 )

где

есть i - ая компонента вектора .

В этом случае компоненты вектора определяются следующим образом:

( 6.4.0 )

, остальные компоненты равны нулю.

Положительными могут быть только , то есть не более m компонент.

Легко проверить, что соответствующие им столбцы матрицы A линейно независимы. Поэтому в силу теоремы(о характеристике экстремальных точек) точка x сама является экстремальной. То есть в этом случае говорят, что базисная переменная выводится из базиса, а внебазисная переменная вводится в базис на ее место.

Итак, если задана произвольная экстремальная угловая точка, то можно

1. либо установить, что она оптимальна;

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

3. либо найти экстремальную точку с лучшим значением целевой функции.

В последнем случае процесс повторяется.

1. начальный этап:

найти произвольную экстремальную точку x c базисом B. Если это сделать трудно, то использовать метод искусственных переменных.

2) основной этап:

шаг 1:

Пусть x - экстремальная точка c базисом B.

Вычислить

Если этот вектор , то остановится.

x - оптимальная экстремальная точка.

В противном случае выбрать наибольшую компоненту вектора

Предположим такая компонента - .

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

где - (n - m) - мерный единичный вектор.

Если , то перейти к шагу 2.

шаг 2:

Вычислить номер r в соответствии с ( 6.4 .0 ) и построить новую экстремальную точку по формуле ( 6.4 .0 ).

Сформировать новый базис, выводя из B столбец и вводя вместо него .

Повторить шаг 1.

6.4.1Табличное представление симплекс - метода.

Пусть имеется начальный базис B, соответствующий начальной экстремальной точке. Целевая функция и ограничения задачи линейного программирования могут быть записаны в виде: