Задачи линейного программирования 2 (стр. 3 из 5)
В (m+1)-й строке: F0 – текущее значение целевой функции; в столбцах Pj 
записаны числа
.Алгоритм решения.
1. Задачу ЛП приводят к каноническому виду и находят исходный опорный план.
2. Составляют исходную симплекс-таблицу.
3. Определяют, имеется ли хотя бы одно отрицательное число Δj в (m+1)-й строке. Если нет, то найденный опорный план оптимален.
4. Находят наименьшее отрицательное Δj и соответствующий столбец обозначают как разрешающий. Если в разрешающем столбце среди чисел aij нет положительных, то целевая функция не ограничена сверху, а задача ЛП не имеет решения.
5. Находят отношения bi к положительным aij разрешающего столбца. Минимальное из этих отношений определяет разрешающую строку.
6. На пересечении разрешающих строки и столбца определяют разрешающий элемент.
7. Все элементы разрешающей строки делят на разрешающий элемент.
8. Все элементы разрешающего столбца (кроме разрешающего элемента) заменяют нулями.
9. Остальные элементы таблицы рассчитываются по правилу прямоугольника и фиксируется введение в базис новой переменной. При этом разрешающая строка определяет переменную, которая исключается из базиса, а разрешающий столбец – переменную, которая вводится в базис.
10. Переходят к пункту 3.
Правило прямоугольника
a1 | … | A2 | | ||
… | … | ||||
a3 | … | А4 | |||
| |
p. строка
Пример. Решить задачу ЛП:
1. Представим задачу в каноническом виде:
Найдем опорный план X=(0,0,0,360,192,180). Т.о. базисные переменные x4, x5, x6; свободные – x1, x2, x3.
2. Составим исходную симплекс-таблицу:
| I | Базис | Сб | P0 | 9 | 10 | 16 | 0 | 0 | 0 | bi/aij | |
| P1 | P2 | P3 | P4 | P5 | P6 | ||||||
| 1 | P4 | 0 | 360 | 18 | 15 | 12 | 1 | 0 | 0 | 360/12=30 | |
| 2 | P5 | 0 | 192 | 6 | 4 | 8 | 0 | 1 | 0 | 192/8=24 | |
| 3 | P6 | 0 | 180 | 5 | 3 | 3 | 0 | 0 | 1 | 180/3=60 | |
| 4 | 0 | -9 | –10 | –16 | 0 | 0 | 0 | ||||
 p.ст. |
Δ1= 0·18 + 0·6 + 0·5 – 9 = – 9
Δ2= 0·15 + 0·4 + 0·3 – 10 = – 10
Δ3= 0·12 + 0·8 + 0·3 – 16 = – 16
Δ4= 0·1 + 0·0 + 0·0 – 0 = 0
Δ5= 0·0 + 0·1 + 0·0 – 0 = 0
Δ6= 0·0 + 0·0 + 0·1 – 0 = 0
3. Найденный опорный план X=(0,0,0,360,192,180) не оптимален, т.к. Δ1, Δ2, Δ3 – отрицательны.
4.
– разрешающий столбец5.
– разрешающая строка6. а23 = 8 – разрешающий элемент.
7, 8, 9, 10 Строим новую симплекс-таблицу по приведенному выше алгоритму, вводя в базис P3 вместо P5.
| I | Базис | Сб | P0 | 9 | 10 | 16 | 0 | 0 | 0 | bi/aij | |
| P1 | P2 | P3 | P4 | P5 | P6 | ||||||
| 1 | P4 | 0 | 72 | 9 | 9 | 0 | 1 | –3/2 | 0 | 72/9=8 |  p.стр |
| 2 | P3 | 16 | 24 | 6/8 | 1/2 | 1 | 0 | 1/8 | 0 | 24 :1/2 = 48 | |
| 3 | P6 | 0 | 108 | 11/4 | 3/2 | 0 | 0 | –3/8 | 1 | 108 : 3/2=72 | |
| 4 | 384 | 3 | –2 | 0 | 0 | 2 | 0 | ||||
| p.ст. |
Полученный опорный план X=(0,0,24,72,0,108) так же не оптимален, т.к. Δ2= – 2 < 0. Поэтому по алгоритму симплекс-метода переходим к новому опорному плану, вводя в базис P2 вместо P4.
| i | Базис | Сб | P0 | 9 | 10 | 16 | 0 | 0 | 0 | bi/aij |
| P1 | P2 | P3 | P4 | P5 | P6 | |||||
| 1 | P2 | 10 | 8 | 1 | 1 | 0 | 1/9 | –1/6 | 0 | |
| 2 | P3 | 16 | 20 | 1/4 | 0 | 1 | –1/8 | 5/24 | 0 | |
| 3 | P6 | 0 | 96 | 5/4 | 0 | 0 | –1/6 | –1/8 | 1 | |
| 4 | 400 | 5 | 0 | 0 | 2/9 | 5/3 | 0 |
Этот опорный план X*=(0; 8; 20; 0; 0; 96) оптимален, т.к. все Δj
неотрицательны.