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

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


       Очевидно, что начальная базисная точка может быть выписана в виде
( x j =0, j =1, n; z i =bi , i =1, m) . Такое преобразование исходной задачи не
                                                                 � x� � x�
является эквивалентным. Однако, как легко заметить, точкам �� �� =�� �� , где
                                                                  � z � � 0�
все z i =0 соответствуют точки x , являющиеся допустимыми в исходной
задаче. Следовательно, желательно составить новую задачу таким образом,
чтобы ее решениями являлись векторы вида ( x1 ,.., xn ,0,..,0) Эта цель может
быть достигнута за счет создания специальной целевой функции, например,
m
∑ zi →   min . Итак, свяжем с исходной задачей новую (искусственную) z-
i =1
задачу вида
                                         m
                                         ∑ zi →        min
                                         i =1
                              Ax + Ez=b (b≥0)
                                 x ≥0, z ≥0.
Так как в этой задаче имеется исходная базисная точка, то задача может быть
решена базовым симплексным методом. Пусть получено решение
                                                                         m
( x10 ,.., xn0 , z10 ,.., z m0 ) со значением целевой функции равным µ0 =∑ zi0
                                                                         i =1
      Теорема 1. Если при решении z-задачи получено оптимальное значе-
ние целевой функции µ0 =0 , то точка ( x10 ,.., xn0 ) является базисной в исход-
ной задаче. Если µ0 >0 , то допустимое множество исходной задачи пусто.
       Таким образом может быть решена проблема отыскания исходной
 базисной точки, однако непосредственное использование такого приема при
 решении ЗЛП не является рациональным, так как требует решения фактиче-
 ски двух задач: сначала z-задачи, а затем - исходной. Существует метод, по-
 зволяющий объединить эти два этапа.
      M-метод. По условию исходной задачи составляется вспомогательная
М-задача вида
                               n                m
                              ∑cjxj    −M ∑ z i → max
                              J =1              i =1
                              Ax + Ez=b (b≥0)
                                 x ≥0, z ≥0.
Здесь z - искусственные переменные, введенные в условие задачи с целью
обеспечения исходной базисной точки, символом M обозначено - некоторое
положительное число. Если М достаточно велико, то слагаемые с положи-
тельными zi уменьшают значение целевой функции, что невыгодно с точки
зрения максимизации. Происходит как бы "штрафование" целевой функции
за то, что выбрана точка с положительными координатами zi . В связи с этим


                                          24