Δ₁= 0·18 + 0·6 + 0·5 – 9 = – 9

Δ₂= 0·15 + 0·4 + 0·3 – 10 = – 10

Δ₃= 0·12 + 0·8 + 0·3 – 16 = – 16

Δ₄= 0·1 + 0·0 + 0·0 – 0 = 0

Δ₅= 0·0 + 0·1 + 0·0 – 0 = 0

Δ₆= 0·0 + 0·0 + 0·1 – 0 = 0

4. Найденный опорный  план X=(0,0,0,360,192,180) не оптимален, т.к. Δ₁, Δ₂, Δ₃ – отрицательны.

5.  – разрешающий столбец
6. – разрешающая строка
7. а₂₃ = 8 – разрешающий элемент.

7, 8, 9, 10 Строим новую  симплекс-таблицу по приведенному выше алгоритму, вводя в базис P₃ вместо P₅.

      Полученный  опорный план X=(0,0,24,72,0,108) так же не оптимален, т.к.     Δ₂= – 2 < 0. Поэтому по алгоритму симплекс-метода переходим к новому опорному плану, вводя в базис P₂ вместо P₄.

Этот опорный  план X^*=(0; 8; 20; 0; 0; 96) оптимален, т.к. все Δ_j неотрицательны.

      Максимальное  значение функции на оптимальном  решении равно:

F_max = 0·9 + 8·10 + 20·16 + 0·0 + 0·0 + 0·96 = 400

Решение общей задачи ЛП: x₁^*= 0; x₂^* = 8; x₃^* = 20; F_max= 400. 

Индивидуальные  задания. Решить задачу ЛП симплексным методом. Варианты заданий взять из индивидуальных заданий пункта 1.1. 

     

3. Метод искусственного базиса.

     В общем  случае после приведения задачи ЛП к каноническому виду непосредственно  записать опорный план не удается, т.к. среди векторов P_j  . нет m единичных. В этом случае задача ЛП решается методом искусственного базиса.

Постановка  задачи. Требуется найти максимум функции  

    (1.10) 

      При условиях 

    (1.11) 

   

   

m<n, 

      но  среди векторов P_j нет m единичных.

      Определение. Задача, состоящая в определении максимума функции

  (1.12)

при условиях 

    (1.13) 

   

   

      называется  расширенной по отношению к исходной задаче (1.10), (1.11).

Здесь M некоторые  большие положительные числа, значения которых не задаются.

      Расширенная задача (1.12), (1.13) имеет опорный план: 

 

      Переменные x_n+1, x_n+2 … x_n+m называются искусственными, а система единичных векторов P_n+1, P_n+2 … P_n+m образует искусственный базис.

      Если  в оптимальном плане  расширенной задачи (1.12), (1.13) значения искусственных переменных равны нулю, то – есть оптимальный план исходной задачи (1.10), (1.11).

      Поэтому процесс решения задачи ЛП (1.10), (1.11) включает следующие этапы:

1. Для исходной задачи составляют расширенную задачу вида (1.12), (1.13).
2. Находят опорный план расширенной задачи.
3. С помощью вычислений симплекс-метода исключают искусственные вектора из базиса. В результате находят опорный план исходной задачи. Если искусственные переменные исключить из базиса не удается, то задача ЛП неразрешима.
4. Используя найденный опорный план исходной задачи (1.10), (1.11), либо находят симплекс-методом ее оптимальный план, либо устанавливают ее неразрешимость

Пример. Найти минимум функции

при условиях: 

 

 

Представим эту  задачу в каноническом виде: 

 

 

 

      Для образования базиса необходимо три  единичных вектора, т.к. m = 3. Но среди  векторов P_j : 

   

есть только два  единичных – P₄ и P₅. Поэтому составим расширенную задачу, введя искусственную переменную x₇ в целевую функцию и в третье ограничение: 

 

 

   

      Расширенная задача имеет опорный план X=(0;0;0;24;22;0;10), определяемый базисом P₄, P₅, P₇. 
 

Составим исходную таблицу:

F=1·24+0·22+(–M) ·10 = 24 –  10M

Δ₁= 2·1 + 1·0 + 1·(–M) – 2 = 0 – M

Δ₂= 1·1 + 2·0 + 2(–M)–(–3) =4 + M

Δ₃= (–2)·1 + 4·0 + 2(–M)–6=–8–2M

Δ₄= 1·1 + 0·0 + 0·(–M) – 1 = 0

Δ₅= 0·1 + 0·0 + 0·(–M) – 0 = 0

Δ₆= 0·1 + 0·0 + (–1)·(–M) – 0=M

Δ₇= 0·1 + 0·0 + 1·(–M) – (–M)=0

 

 

      При этом в (m+2)-й строке записываем коэффициенты при М. В начале проверяем условие для последней (пятой) строки. Здесь есть отрицательные числа: и .

      Переходим к новому опорному плану по алгоритму  симплекс-метода. Для этого исключим вектор P₇ из базиса, а вектор P₃ введем вместо него. В дальнейшем искусственный вектор P₇ не имеет смысла вводить в базис, поэтому столбец P₇ исключаем из таблицы.

      Так как все искусственные векторы  исключены из базиса то нет смысла включать в таблицу и (m+2)-ю (пятую для нашей задачи) строку.

      Поэтому новая таблица имеет четыре строки и шесть столбцов: