Статья на тему " О математических методах исследования в задачах Линейного программирования " .

О математических методах исследования в задачах

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

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

Найти   f₀(x)=c₁x₁+c₂x₂+...+c_nx_n                       (1)

где  x=(x₁,x₂,...,x_n)-вектор переменной

        c_j, j=1,2,...,n- коэффициенты целевой функции

        a_ij, i=1,2,...,n; j=1,2,...,n- коэффициент ограничений

        b=(b_1,b₂,...,b_n)-вектор свободных членов

        A=[a_ij]_m´n      

ЗЛП в стандартной форме записи:

[f₀(x)=]                          [g₀(y)=]

R=                             Q=

Где: А^Т-транспонированная матрица A^Т=[a_ij]_m´n      

ЗЛП в канонической форме записи:

[f₀(x)=]                          [g₀(y)=]

R=                             Q=

Эквивалентные преобразования ЗЛП.

  Эквивалентные преобразования не изменяют решения ЗЛП , то есть эквивалентность относительно решения.

1.     Переход от задачи  max к задаче min:

[f₀(x)=]-от этой задачи перейти к задаче на min

f₀(x)= -[f₀(x)]

f₀(x)==[-]

g₀(y)== -g₀(y)=[]

2.Переход от ограничения равенства к ограничению неравенства (заключается в переходе к двум противоположным неравенствам).

³b_i

£b_i

При решении задачи  на  f₀(x) имеем следующие ограничения:

-£b_i

£b_i

При решении задачи на f₀(x) ограничения следующие:

³b_i

-³b_i

3.     Переход от ограничений неравенств к ограничениям равенства:

£b_i  добавляется неотрицателбная часть: +x_n+i=bi, где x_n+i³0 (дополнительная переменная)

³c_j        вычтем константу :  -x_m+j=c_j ,где x_м+j³0

4.     Переход от переменной неопределённого знака к неотрицательной переменной.

      x   ³£ 0   

Введём две новые переменные:U_j³ 0;

                                                      V_j³0.

Получим: x_j=  U_j -V_j

5. Переход от переменной, ограниченной сверху к неотрицательной переменной:

x_k³d_k, d_k=const,d_k>0

Введём новые переменные: W_k=x_k-d_k , W_k>0

Замечание: не допускается деление ограничений на какое-либо число или умножение ,так как при этом изменяется решение ЗЛП, то есть получаем задачу . не эквивалентную исходной.      

Симплекс – метод решения задачи линейного программирования на максимум в стандартной форме записи при .

          Симплекс – метод для решения задачи линейного программирования на максимум основан на методе Жордана (1838-1922) решения систем линейных алгебраических уравнений.

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

          Основоположником же рассматриваемого метода считается Канторович, представивший в 1938 году “метод допустимого улучшения плана”, предполагая, что начальное решение уже имеется, в отличие от Данцига, у которого начальное решение находится с помощью симплекс – преобразований. Однако Нобелевская премия была получена им лишь в 1975 году.

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

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

.

От задачи (1) – (3) перейдем к задаче в канонической форме записи. Для этого введем дополнительные переменные  и разрешим относительно них систему ограничений – равенств, при этом :

.

Введем вектор , т. е.

Тогда

        Заметим, что симплекс – метод применяется только при выполнении ограничения (3).

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

1.    

2.     - начало итерационного процесса

3.    

4.      иначе см. пункт 12 (столбец  будет разрешающим)

5.      иначе см. пункт 14

6.    

7.    

8.    

9.    

10. - переход к следующей итерации.

11. - новый базис. Далее переходим на пункт 3.

Особенности алгоритма.

12. Если , то существует альтернативный оптимум, и см. пункт 5

13. , то найдено оптимальное решение, иначе см. пункт 14.

14. Задача линейного программирования не имеет смысла.

15. Конец

 

 

ТЕОРЕМА О СИМПЛЕКСНЫХ ПРЕОБРАЗОВАНИЯХ

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

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

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

 (1)

Тогда

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

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

Тогда .

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

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

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

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

.

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

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

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

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

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

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

1.    

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

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

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

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

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

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

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

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

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

1.    

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

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

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

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

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

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

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

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

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

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

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

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

1. Каждому ограничению типа равенства и неравенства ставится в соответствие двойственная переменная	1.
2. Если исходная задача была на минимум, то двойственная будет на максимум:	2.
3.	3.
4.	4.
5.	5.
6.	6.

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

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

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

 (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.  Конец.

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

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

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

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

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

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

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

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