Линейное программирование. Задача линейного программирования (ЗЛП), страница 4

6. Симплексный метод решения ЗЛП

6.1 Идея симплексного метода

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

1. Создать начальный опорный план. В качестве начального опорного плана годится любой план вида , то есть точка в любой вершине многогранника планов. На рисунке за начальный опорный план принята точка 1.
2. Оценить, не является ли опорный план оптимальным планом. Если опорный план окажется оптимальным (точка 4), - решение задачи найдено. Если – нет, поиск следует продолжить.
3. Перейти к нехудшему плану. После перехода вновь выполнить действия, указанные в пункте 2.

6.2. Создание начального опорного плана

Метод создания начального опорного плана зависит от вида системы ограничений. Рассмотрим возможные варианты.

1.  Система ограничений представлена в канонической форме и имеет предпочтительный вид.

Предпочтительным называется такой вид ограничений, когда каждое ограничение – равенство содержит такую переменную х_i  с коэффициентом +1, которая в других равенствах имеет коэффициент, равный 0.

Например,

Предпочтительные переменные будем считать базисными. Остальные переменные – свободными. Свободные переменные приравняем нулю. Получаем следующий начальный опорный план:

x₀ = (b₁, b₂, b₃, 0, 0)

2.  Система ограничений представлена неравенствами, имеющими неканонический вид: 

;   ;   .

Систему ограничений приводят к каноническому виду, добавляя дополнительные переменные x_n+i (i = 1, … , m). В итоге получим

или, записав подробнее:

Система ограничений теперь имеет предпочтительный вид и позволяет составить начальный опорный план.

В целевую функцию дополнительные неизвестные входят с коэффициентами .

Следовательно, начальное значение целевой функции, соответствующее начальному опорному плану, равно

, то есть прибыль z равна нулю. Все сырье (b_i), не принося прибыли, остается на складе.

3.  Система ограничений имеет вид

Система ограничений представлена не в канонической форме. Вычтем в каждом ограничении i дополнительное неизвестное x_n+i (i = 1, … , m):

Система ограничений пробрела каноническую форму, однако не имеет предпочтительного вида и не позволяет составить начальный опорный план. Действительно, план (0, …, 0, -b₁, -b₂, …, -b_m) не допустим, так как отрицательные значения  x_n+i не имеют смысла и недопустимы.

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

4.  Система ограничений представлена в канонической форме, но не имеет предпочтительного вида.

Запишем целевую функцию -

                                                                     (6.1)                                       и ограничения -

      (i =  )                                                      (6.2)

x_j ³ 0                 (j =  )                                                       (6.3)

Чтобы придать системе ограничений (6.2) предпочтительный вид прибавим к каждому из них искусственную переменную w_i (i = ):

                                                     (6.4)

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

, а при поиске минимума – вид

.

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

Метод решения ЗЛП с введением искусственных переменных в литературе называют М – задачей или симплексным методом с искусственным базисом.

6.3. Признак оптимальности опорного плана

Любая ЗЛП может быть представлена в предпочтительном виде:

;