Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 18 стр.

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


      Эта формула позволяет увидеть, что если выбрано k такое, что Δk<0, то
на следующей итерации будет получена точка с большим значением целевой
функции (т. к. Θ ≥0). Если Δk>0, то произойдет уменьшение целевой функ-
ции, при Δk=0 значение целевой функции не изменится. Eсли Δk<0, но все
a ik ≤0 , то, выбирая любое положительное число в качестве Θ, будем полу-
чать допустимую, но не базисную точку(см. ф-лу (8)). Значение целевой
функции в этой точке изменяется в соответствии с формулой (9), поэтому
если Θ выбирать как угодно большим, то значение функции цели будет не-
ограниченно увеличиваться. Следовательно, в таком случае можно сделать
вывод о неограниченности целевой функции на допустимом множестве.
      Теорема 1. Если все оценки, соответствующие некоторой базисной
точке x B , неотрицательны, то есть ∆ j =∑ c i a ij −c j ≥0, ∀j =1, n , то та-
                                                  i∈I
кая точка является оптимальной в задаче (1)-(3).
      Сформулированные факты позволяют сконструировать алгоритм базо-
вого симплексного метода.

                       Алгоритм базового симплексного метода

Начало. Задана исходная базисная точка x B : x TB =( x i , i ∈I ; x j =0, j ∈J ).
Вычислить оценки по формуле ∆ j =∑ ci a ij −c j , j ∈J .
                                         i∈I
2. Проверить, если все Δj ≥0, то перейти к п.8.
3. Проверить, если ∃k ∈J : ∆k <0 и все a ik ≤0, то перейти к п.10.
4. Выбрать k: Δk<0 и вектор Ak имеет хотя бы одну строго
положительную координату (возможен произвольный выбор такого номера k,
например,   max ∆j =∆k        )
            j:Δ j <0

                                                  xl            x
5. Вычислить параметр Θ по формуле Θ =                =min i
                                                  a lk i:aik >0 a ik
6. Осуществить переход к новой базисной точке с помощью метода
Жордана-Гаусса с направляющим элементом alk.
7. Изменить исходную информацию:
                  x                     x
x B ← x BH =( xi − l a ik , i ∈I ; x k = l ; x j =0, j ∈J , j ≠k ).
                  a lk                  a lk
I ← I \ {l} ∪ {k}; J ← J \ {l} ∪ {k}
Перейти к п.1.
8. Если существует номер s ∈J : ∆s =0 ,то выписать ответ: x B - оптимальная
точка, в задаче имеется бесчисленное множество решений.
9. Если для всех j ∈J , ∆ j >0 , то выписать ответ:


                                         20