Теорема о симплексных преобразованиях

Теорема о симплексных преобразованиях

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

Доказательство:

         Рассмотрим разрешающую строку :

 (1)

Тогда

Рекомендуемые материалы

         Покажем, что это решение не улучшает целевой функции:

Введем обозначение: , причем .(2)

Тогда .

         Теорема доказана.

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

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

выводе переменной , что не нарушает условие неотрицательности базисных переменных:

.

Примечание 2. Рассмотренная задача линейного программирования всегда имеет решение, по крайней мере тривиальное, т. е.

. Для симплекс – таблицы .

Примечание 3. Если среди свободных членов задачи линейного программирования имеются отрицательные, то симплекс – метод разбивается на два этапа:

· Нахождение дополнительного решения

· Нахождение оптимального решения

НАХОЖДЕНИЕ ДОПУСТИМОГО РЕШЕНИЯ

1.

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

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

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

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

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

Пусть дана задача

Нахождение оптимального решения состоит из двух этапов:

1. Нахождение дополнительного решения.

2. Нахождение оптимального решения.

1.

     , иначе задача не имеет смысла.

Далее выполняются обыкновенные жордановы исключения:

· на месте разрешающего элемента ставится 1

· элементы строки, кроме разрешающей, записываются с обратным знаком

· элементы столбца, кроме разрешающего, остаются без изменений

· остальные коэффициенты считаются по правилу прямоугольника

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

2. В строке  находим , а разрешающая строка находится как .

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

ЭЛЕМЕНТЫ ТЕОРИИ ДВОЙСТВЕННОСТИ

1. Построение двойственных задач.

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

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

Лемма (критерий оптимального решения прямой и двойственной задач). Пусть - допустимые решения соответственно прямой и двойственной задач. И если выполняется условие  , то эти решения являются оптимальными.

         Без ограничения общности рассмотрим задачу в стандартной форме записи:

 (3) - (4)

         Построим двойственную задачу:

 (5)

 (6) – (7)

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

 (8)     (9).

Откуда следует:

 (10)

(11)

         Докажем, что эти решения являются оптимальными.

Доказательство.

         Предположим противное. Пусть существует решение задачи (1)  (12).

Объединяя (1) и (12), получим:

 (13)

Откуда следует:

 (14), что противоречит (11). Значит, предположение было сделано неверно, т. е. другого  не существует.

         Приведем доказательство для двойственной задачи. Пусть существует решение  (15).

Объединяя (1) и (15), получим:

 (16) и  (17).

Получили, что неравенство (17) противоречит (12), т. е.  не является оптимальным решением.

Лемма доказана.

         На этом правиле основан симплекс – метод.

2. Двойственный симплекс – метод.

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

Для ограничений (3) введем дополнительные переменные  и разрешим полученные уравнения относительно этих базисных переменных:

.

Введем дополнительные переменные , которые по построению будут положительны, и разрешим относительно этих базисных переменных ограничения (6):

.

         В двойственной симплекс- таблице уравнения для прямой задачи записываем по строкам, а для двойственной – по столбцам. Алгоритм же двойственного симплекс – метода соответствует алгоритму решения задач на минимум:

1. .

a) нахождение допустимого решения двойственной задачи

b) нахождение допустимого и одновременно оптимального решения прямой задачи

2.

3. , иначе см. пункт 9.

4. , иначе см. пункт 11.

5. .

6.

                     .

7.

8. , переходим на пункт 3.

9. Находим дополнительное и одновременно оптимальное решение:

, иначе см. пункт 12.

10. , пункт 6. Иначе см. пункт 13.

11.  Задача линейного программирования не имеет смысла, либо не имеет решения, а ДЗЛП не имеет решения.

12.  .

13.  Задача линейного программирования не имеет решения. ДЗЛП не имеет решения, либо не имеет смысла.

14.  Конец.

15.

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

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

Вам также может быть полезна лекция "19 Материальный баланс процесса выпарнки".

РЕШЕНИЕ ЗАДАЧ В ОБЩЕЙ ФОРМЕ ЗАПИСИ И ФОРМЫ НАХОЖДЕНИЯ РЕШЕНИЯ

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

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

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

         Если переменные неопределенного знака, то критерий оптимального решения не работает. А если есть ограничения равенствами, то это означает, что нет базисного решения. Если возможно, эта строка выбирается разрешающей, и меняются местами свободная переменная и 0-строка, 0-столбец вычеркивается, но запишется уравнение для двойственной переменной. Это для ограничений- равенств в прямой задаче.

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