Пример отсутствия решения задачи, решаемой симплекс методом
Условие задачи
Математическая модель задачи: Математическая модель задачи:F = 4 · x1 + 5 · x2 + 4 · x3 → max
| 2·x1 | + 3·x2 | – 6·x3 | ≤ | 240 | |
| 4·x1 | + 2·x2 | – 4·x3 | ≤ | 200 | |
| 4·x1 | + 6·x2 | – 8·x3 | ≤ | 160 | |
| x1 ≥ 0 | x2 ≥ 0 | x3 ≥ 0 |
Решаем симплекс методом.
Вводим дополнительные переменные x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, чтобы неравенства преобразовать в равенства.
| 2·x1 | + 3·x2 | – 6·x3 | + 1·x4 | + 0·x5 | + 0·x6 | = | 240 | |
| 4·x1 | + 2·x2 | – 4·x3 | + 0·x4 | + 1·x5 | + 0·x6 | = | 200 | |
| 4·x1 | + 6·x2 | – 8·x3 | + 0·x4 | + 0·x5 | + 1·x6 | = | 160 | |
| x1 ≥ 0 | x2 ≥ 0 | x3 ≥ 0 | x4 ≥ 0 | x5 ≥ 0 | x6 ≥ 0 |
В качестве базиса возьмем
x4 = 240; x5 = 200; x6 = 160.
Данные заносим в симплекс таблицу.
Симплекс таблица № 1
| Cj | 4 | 5 | 4 | 0 | 0 | 0 | |||
| Ci | Базис | bi | x1 | x2 | x3 | x4 | x5 | x6 | Q |
| 0 | x4 | 240 | 2 | 3 | – 6 | 1 | 0 | 0 | 80 |
| 0 | x5 | 200 | 4 | 2 | – 4 | 0 | 1 | 0 | 100 |
| 0 | x6 | 160 | 4 | 6 | – 8 | 0 | 0 | 1 | 26,67 |
| Δi | 0 | – 4 | – 5 | – 4 |
Целевая функция:
F = 3∑i = 1Ci·bi = 0 · 240 + 0 · 200 + 0 · 160 = 0
Вычисляем оценки по формуле:
Δ(xj) = 3∑i = 1Ci·aij – Cj.
Оценки базисных переменных всегда равны нулю. Для свободных переменных, имеем:
Δ(x1) = 0 · 2 + 0 · 4 + 0 · 4 – 4 = – 4
Δ(x2) = 0 · 3 + 0 · 2 + 0 · 6 – 5 = – 5
Δ(x3) = 0 · ( – 6) + 0 · ( – 4) + 0 · ( – 8) – 4 = – 4
Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка
Δ(x2) = – 5.
Вводим переменную x2 в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение Qi = bi/ai2 для столбца x2:
Q1 = 240 / 3 = 80
Q2 = 200 / 2 = 100
Q3 = 160 / 6 = 26,67
Наименьшее неотрицательное отношение Q3 = 26,67 в строке 3. Переменная x6 выходит из базиса.
Вводим переменную x2 в базис. Переменную в строке x6 выводим из базиса. Для этого выполняем эквивалентные преобразования, чтобы столбец x2 состоял из единицы, в строке x2, и нулей, в остальных строках.
3-ю строку делим на 6
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2
| Cj | 4 | 5 | 4 | 0 | 0 | 0 | ||
| Ci | Базис | bi | x1 | x2 | x3 | x4 | x5 | x6 |
| 0 | x4 | 240 – 3·803 | 2 – 3·23 | 3 – 3·1 | – 6 – 3·( – 43) | 1 – 3·0 | 0 – 3·0 | 0 – 3·16 |
| 0 | x5 | 200 – 2·803 | 4 – 2·23 | 2 – 2·1 | – 4 – 2·( – 43) | 0 – 2·0 | 1 – 2·0 | 0 – 2·16 |
| 5 | x2 | 803 | 23 | 1 | – 43 | 0 | 0 | 16 |
Подробные вычисления
240 – 3·803 = 240 – 2403 = 240 – 80 = 160
2 – 3·23 = 2 – 63 = 2 – 2 = 0
– 6 – 3·( – 43) = – 6 – -123 = – 6 + 4 = – 2
200 – 2·803 = 200 – 1603 = 200·3–1603 = 4403
4 – 2·23 = 4 – 43 = 4·3–43 = 83
– 4 – 2·( – 43) = – 4 – -83 = -4·3+83 = – 43
Получаем новую таблицу.
Симплекс таблица № 2
| Cj | 4 | 5 | 4 | 0 | 0 | 0 | |||
| Ci | Базис | bi | x1 | x2 | x3 | x4 | x5 | x6 | Q |
| 0 | x4 | 160 | 0 | 0 | – 2 | 1 | 0 | – 12 | < 0 |
| 0 | x5 | 4403 | 83 | 0 | – 43 | 0 | 1 | – 13 | < 0 |
| 5 | x2 | 803 | 23 | 1 | – 43 | 0 | 0 | 16 | < 0 |
| Δi | 4003 | – 23 | – 323 | 56 |
Целевая функция:
F = 3∑i = 1Ci·bi = 0 · 160 + 0 · 4403 + 5 · 803 = 4003 ≈ 133,3
Вычисляем оценки по формуле:
Δ(xj) = 3∑i = 1Ci·aij – Cj.
Оценки базисных переменных всегда равны нулю. Для свободных переменных, имеем:
Δ(x1) = 0 · 0 + 0 · 83 + 5 · 23 – 4 = – 23 ≈ – 0,6667
Δ(x3) = 0 · ( – 2) + 0 · ( – 43) + 5 · ( – 43) – 4 = – 323 ≈ – 10,67
Δ(x6) = 0 · ( – 12) + 0 · ( – 13) + 5 · 16 – 0 = 56 ≈ 0,8333
Поскольку есть отрицательные оценки, то план не оптимален.
Наименьшая оценка Δ(x3) = – 10,67. Вводим переменную x3 в базис.
Определяем переменную, выходящую из базиса из условия, чтобы остальные базисные переменные не приняли отрицательных значений. Для этого находим наименьшее неотрицательное отношение Qi = bi/ai2 для столбца x3:
Q1 = 160 / ( – 2) < 0
Q2 = 4403 / ( – 43) < 0
Q3 = 803 / ( – 43) < 0
Поскольку среди значений нет неотрицательных, то решения не существует. Целевая функция может быть сделана сколь угодно большой.
Fmax = ∞
x1 = 0; x2 = ∞; x3 = ∞.
Автор: Олег Одинцов. Опубликовано: