55



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


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

, ( 6.1.0 )

где

,

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

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

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

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

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


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


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


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

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

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

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

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

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

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

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

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

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


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


Пример


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

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

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

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

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

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


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


прямая:

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


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

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

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

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

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

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


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

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


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

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



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

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














нет решений



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

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

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

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

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

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

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


Предположим, что множество ограничений содержит хотя бы одну допустимую точку и что ранг матрицы 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.

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

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

строка - целевая функция

строки-ограничения


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


ПЧ

1

0

0

B

N

b


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



ПЧ

1

0

1


Базисные переменные отмечены в таблице слева, а значения базисных переменных записаны в правой части таблицы.

Эта таблица содержит всю информацию, необходимую для завершения первого шага симплекс метода.

Если процесс прекращается, то есть текущая точка является оптимальной.


В противном случае:

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

где

- вектор

- матрица

- вектор

- скаляр


Если - то процесс прекращается - значение целевой функции неограниченно.

Если , то

так как записаны под ПЧ и соответственно, то следуя ( 6.4 .0 ) легко вычислить .

Базисная переменная , соответствующая минимальному отношению в ( 6.4 .0 ), выводится из базиса, а вводится в базис.

Далее проводим ведущее преобразование:

Строка, соответствующая (выводимая переменная из базиса) - ведущая строка.

Столбец, соответствующий (вводимая переменная в базис) - ведущий столбец.


  1. Разделить ведущую строку(соответствующую ) на ведущий элемент ;

  2. Умножить новую r - ую строку на и результат вычесть из i - ой строки ограничений для всех

  3. Умножить новую r - ую строку на и результат вычесть из строки целевой функции.


Пример:



Графически:


A(4/3, 11/3)

(0,3)





(0,0) (5,0)













Оптимальной является точка . Значение функции


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






Возьмем в качестве В матрицу

Так как ,

то найдена экстремальная точка:



ПЧ

1

-1

3

0

0

0

0

-1

2

1

0

6

0

1

1

0

1

5


- выводится из базиса

- вводится в базис

Новый базис



ПЧ

1

0

0

-9

0

1

0

3

0

0

1

2


Теперь:

- выводится из базиса

- вводится в базис.

Новый базис


ПЧ

1

0

0

0

0

1

0

1

0

Так как , то получено оптимальное решение.

      1. Выбор начальной экстремальной точки.

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

Из теоремы(о характеристиках экстремальных точек) нахождение начальной экстремальной точки связано с разбиением матрицы A на ,

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

N - матрица m x (n-m) ,

так чтобы . В предыдущем примере начальная точка определялась легко. В практических задачах определить начальную точку не так - то легко. Для этого используются различные приемы.


Начальная точка может быть получена введением искусственных переменных.

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

  1. Двухэтапный метод:

  • на первом этапе решения задачи вводится вектор - вектор искусственных переменных размерности m.

где - вектор, все компоненты которого равны единице.

После окончания первого этапа:

либо , либо

Если исходная система несовместна, то есть допустимая область пуста.

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

  • на втором этапе начиная из полученной точки решается задача минимизации целевой функции.

  1. M - метод:

В этом методе также вводятся искусственные переменные и каждой искусственной переменной назначается большой положительный штраф M (больше любого ci )


Задача линейного программирования принимает вид:

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

Если , то это означает, что система ( ) не имеет решения.


Замечание 1.

(зацикливание)

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

В принципе зацикливание преодолимо(оно встречается сравнительно редко) и в качестве практических рекомендаций может быть предложено несколько вариантов выбора следующей точки:

  • отказ от точки для которой ;

  • случайный выбор новой угловой точки

и так далее.


Случайные файлы

Файл
115914.rtf
35649.rtf
4992-1.rtf
124033.rtf
27828.rtf