Задачи линейного программирования 2 (стр. 4 из 5)
Максимальное значение функции на оптимальном решении равно:
Fmax = 0·9 + 8·10 + 20·16 + 0·0 + 0·0 + 0·96 = 400
Решение общей задачи ЛП: x1*= 0; x2* = 8; x3* = 20; Fmax= 400.
Индивидуальные задания. Решить задачу ЛП симплексным методом. Варианты заданий взять из индивидуальных заданий пункта 1.1.
1.3. Метод искусственного базиса.
В общем случае после приведения задачи ЛП к каноническому виду непосредственно записать опорный план не удается, т.к. среди векторов Pj
. нет m единичных. В этом случае задача ЛП решается методом искусственного базиса.Постановка задачи. Требуется найти максимум функции
(1.10) При условиях
(1.11) 
m<n,
но среди векторов Pj
нет m единичных.Определение. Задача, состоящая в определении максимума функции
(1.12)
при условиях
(1.13) 
называется расширенной по отношению к исходной задаче (1.10), (1.11).
Здесь M некоторые большие положительные числа, значения которых не задаются.
Расширенная задача (1.12), (1.13) имеет опорный план:
Переменные xn+1, xn+2 … xn+m называются искусственными, а система единичных векторов Pn+1, Pn+2 … Pn+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. Но среди векторов Pj
: 
есть только два единичных – P4 и P5. Поэтому составим расширенную задачу, введя искусственную переменную x7 в целевую функцию и в третье ограничение:
Расширенная задача имеет опорный план X=(0;0;0;24;22;0;10), определяемый базисом P4, P5, P7.
Составим исходную таблицу:
| i | Базис | Сб | P0 | 2 | –3 | 6 | 1 | 0 | 0 | -M | bi/aij | |
| P1 | P2 | P3 | P4 | P5 | P6 | P7 | ||||||
| 1 | P4 | 1 | 24 | 2 | 1 | –2 | 1 | 0 | 0 | 0 | ||
| 2 | P5 | 0 | 22 | 1 | 2 | 4 | 0 | 1 | 0 | 0 | 22/4 | |
| 3 | P7 | –M | 10 | 1 | –1 | 2 | 0 | 0 | –1 | 1 | 10/2 |  p.стр. |
| 4 | 24 | 0 | 4 | –8 | 0 | 0 | 0 | 0 | ||||
| 5 | –10 | –1 | 1 | –2 | 0 | 0 | 1 | 0 | ||||
 р.ст. |
F=1·24+0·22+(–M) ·10 = 24 – 10M
Δ1= 2·1 + 1·0 + 1·(–M) – 2 = 0 – M
Δ2= 1·1 + 2·0 + 2(–M)–(–3) =4 + M
Δ3= (–2)·1 + 4·0 + 2(–M)–6=–8–2M
Δ4= 1·1 + 0·0 + 0·(–M) – 1 = 0
Δ5= 0·1 + 0·0 + 0·(–M) – 0 = 0
Δ6= 0·1 + 0·0 + (–1)·(–M) – 0=M
Δ7= 0·1 + 0·0 + 1·(–M) – (–M)=0
При этом в (m+2)-й строке записываем коэффициенты при М. В начале проверяем условие
для последней (пятой) строки. Здесь есть отрицательные числа: 
и 
.Переходим к новому опорному плану по алгоритму симплекс-метода. Для этого исключим вектор P7 из базиса, а вектор P3 введем вместо него. В дальнейшем искусственный вектор P7 не имеет смысла вводить в базис, поэтому столбец P7 исключаем из таблицы.
Так как все искусственные векторы исключены из базиса то нет смысла включать в таблицу и (m+2)-ю (пятую для нашей задачи) строку.
Поэтому новая таблица имеет четыре строки и шесть столбцов:
| I | Базис | Сб | P0 | 2 | –3 | 6 | 1 | 0 | 0 | bi/aij | |
| P1 | P2 | P3 | P4 | P5 | P6 | ||||||
| 1 | P4 | 1 | 34 | 3 | 0 | 0 | 1 | 0 | –1 | ||
| 2 | P5 | 0 | 2 | –1 | 4 | 0 | 0 | 1 | 2 | 2/2 |  p.стр. |
| 3 | P3 | 6 | 5 | 1/2 | –1/2 | 1 | 0 | 0 | –1/2 | ||
| 4 | 64 | 4 | 0 | 0 | 0 | 0 | -4 | ||||
| р.ст. |
Полученное опорное решение Х=(0;0;5;34;2;0) не является оптимальным; т.к. Δ6<0.