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

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


следует ожидать, что в оптимальной точке при достаточно большом M все
значения zi будут равны нулю. Однако это возможно только в случае, если в
исходной задаче допустимое множество не пусто. Имеет место следующая
теорема.
      Теорема 2. Если исходная задача имеет решение, то существует такое
число M0, что при всех M>M0 вспомогательная М-задача тоже имеет реше-
                            � x* �
ние, и в любом ее решении � * � точка z*=0, а x* будет решением исходной
                             � z �
                              � �
задачи.
      Следствие 1. Если при решении произвольной задачи линейного про-
граммирования М-методом будет получена такая оптимальная точка, что
z*≠0, то в исходной задаче допустимое множество пусто.
      Из теоремы следует, что решение можно осуществлять, фиксируя не-
которое большое число M, однако обычно поступают иначе, используя прин-
цип метода искусственного базиса. Число M при этом не фиксируется, остав-
ляется в задаче в качестве параметра, который позволяет осуществлять не-
прерывное двухэтапное решение задачи. На первом этапе алгоритма осуще-
                                                              m
ствляется максимизация второй группы слагаемых β0 =−M ∑ z i → max , а
                                                             i =1
после достижения максимума непрерывно переходят к оптимизации исход-
ной целевой функции, либо делают вывод о неразрешимости исходной зада-
чи. До тех пор пока переменные zi>0, т.е. являются базисными, и значение
целевой функции, и оценки ∆ j можно представить в виде α j +Mβ j , j =1, n .
Следовательно, если вводить в базис такой вектор Aj, что соответствующее
значение β j <0, то это приведет к увеличению значения β0 . Максимальное
значение будет получено, когда все β j будут неотрицательными. Очевидно,
что при этом возможны две ситуации: β0 <0 и β0 =0 . Рассмотрим оба эти
случая.
      1. Оптимальное значение β 0 <0 . Наличие такой ситуации на одной из
итераций означает, что допустимое множество исходной задачи пусто, т.к.
оптимальная точка имеет координаты zi >0.
      2. Оптимальное значение β0 =0 . Такой вариант возможен, в свою оче-
редь, в двух ситуациях:
а) Все искусственные переменные выведены из базиса и равны, как небазис-
ные переменные, нулю. В этом случае получена базисная точка исходной
задачи и продолжается оптимизация исходной целевой функции по базовому
алгоритму симплексного метода .
б) Искусственные переменные zi не выведены из базиса, но их значения рав-
ны нулю. В этом случае мы имеем дело с вырожденной ситуацией, и базис-
ная точка, полученная на этой итерации, является вырожденной базисной

                                   25