Произвольной задачи линейного программирования

 

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

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

Ax + Ez=b (b ³ 0)

x ³0, z ³0.

Очевидно, что начальная базисная точка может быть выписана в виде . Такое преобразование исходной задачи не является эквивалентным. Однако, как легко заметить, точкам , где все  соответствуют точки x, являющиеся допустимыми в исходной задаче. Следовательно, желательно составить новую задачу таким образом, чтобы ее решениями являлись векторы вида . Эта цель может быть достигнута за счет создания специальной целевой функции, например, . Итак, свяжем с исходной задачей новую (искусственную) z-задачу вида

Ax + Ez=b (b ³ 0)

x ³0, z ³0.

Так как в этой задаче имеется исходная базисная точка, то задача может быть

решена базовым симплексным методом. Пусть получено решение   со значением целевой функции равным

Теорема 1. Если при решении z-задачи получено оптимальное значение целевой функции , то точка  является базисной в исходной задаче. Если , то допустимое множество исходной задачи пусто.

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

     M-метод. По условию исходной задачи составляется вспомогательная М-задача вида

Ax + Ez=b (b ³ 0)

x ³0, z ³0.

Здесь z - искусственные переменные, введенные в условие задачи с целью обеспечения исходной базисной точки, символом M обозначено - некоторое положительное число. Если М достаточно велико, то слагаемые с положительными z_i уменьшают значение целевой функции, что невыгодно с точки зрения максимизации. Происходит как бы "штрафование" целевой функции за то, что выбрана точка с положительными координатами z_i  . В связи с этим следует ожидать, что в оптимальной точке при достаточно большом M все значения z_i будут равны нулю. Однако это возможно только в случае, если в исходной задаче допустимое множество не пусто. Имеет место следующая теорема.

Теорема 2. Если исходная задача имеет решение, то существует такое число M⁰, что при всех M>M⁰ вспомогательная М-задача тоже имеет решение, и в любом ее решении  точка z*=0, а x* будет решением исходной задачи.

Следствие 1. Если при решении произвольной задачи линейного программирования М-методом будет получена такая оптимальная точка, что

z*¹ 0, то в исходной задаче допустимое множество пусто.

 

Из теоремы следует, что решение можно осуществлять, фиксируя некоторое большое число M, однако обычно поступают иначе, используя принцип метода искусственного базиса. Число M при этом не фиксируется, оставляется в задаче в качестве параметра, который позволяет осуществлять непрерывное двухэтапное решение задачи. На первом этапе алгоритма осуществляется максимизация второй группы слагаемых , а после достижения максимума непрерывно переходят к оптимизации исходной целевой функции, либо делают вывод о неразрешимости исходной задачи. До тех пор пока переменные z_i>0, т.е. являются базисными, и значение целевой функции, и оценки  можно представить в виде . Следовательно, если вводить в базис такой вектор A_j, что соответствующее значение <0, то это приведет к увеличению значения . Максимальное значение будет получено, когда все  будут неотрицательными. Очевидно, что при этом возможны две ситуации:  и . Рассмотрим оба эти случая.

1. Оптимальное значение . Наличие такой ситуации на одной из итераций означает, что допустимое множество исходной задачи пусто, т.к.

оптимальная точка имеет координаты z_i >0.

2. Оптимальное значение . Такой вариант возможен, в свою очередь, в двух ситуациях:

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

б) Искусственные переменные z_i не выведены из базиса, но их значения равны нулю. В этом случае мы имеем дело с вырожденной ситуацией, и базисная точка, полученная на этой итерации, является вырожденной базисной точкой исходной задачи. Она, как и в предыдущем случае, вообще говоря, не является оптимальной. Следовательно, необходимо продолжить поиск, не уменьшая при этом полученное оптимальное значение . По оценкам  (если такие есть) определяется вектор для введения в базис на данной итерации. Процесс продолжается до тех пор, пока не исчезнут такие j, что  соответствующий столбец A_j имеет элементы a_ij>0.

 

Итак, сформулируем  окончательную схему алгоритма.