Условие
Решить задачу применив симплекс-метод к соответствующей двойственной задаче.
х1 – х2 – 6х3 + 2х4 + 12х5 → min
2х1 – х2 + х3 + х4 + 2х5 ≥ 3
-x1 + 2x2 – 2х3 + 3х4 + х5 ≥ 2
х1 – х2 + 3х3 + х4 + 3х5 ≥ 1
Решение
Запишем двойственную задачу:
2y1 – y2 + y3 ≤ 1
-y1 + 2y2 - y3 ≤ -1
y1 – 2y2 + 3y3 ≤ -6
y1 + 3y2 + y3 ≤ 2
2y1 + y2 + 3y3 ≤ 12
max(3y1 + 2y2 + y3) - ?
Сведём задачу к каноническому виду:
2y1 – y2 + y3 + y4 = 1
-y1 + 2y2 - y3 + y5 = -1
y1 – 2y2 + 3y3 + y6 = -6
y1 + 3y2 + y3 + y7 = 2
2y1 + y2 + 3y3 + y8 = 12
max(3y1 + 2y2 + y3) - ?
Все остальные вычисления и действия удобно производит в табличной форме (табл. 4 – 6).
Таблица 4
Симплексная таблица первого плана задачи
| Pi | Бy | y0 | 3 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | θ |
| y1 | y2 | y3 | y4 | y5 | y6 | y7 | y8 | ||||
| 0 | y4 | 1 | 2 | -1 | 1 | 1 | 0 | 0 | 0 | 0 | 0.5 |
| 0 | y5 | -1 | -1 | 2 | -1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | y6 | -6 | 1 | -2 | 3 | 0 | 0 | 1 | 0 | 0 | - |
| 0 | y7 | 2 | 1 | 3 | 1 | 0 | 0 | 0 | 1 | 0 | 2 |
| 0 | y8 | 12 | 2 | 1 | 3 | 0 | 0 | 0 | 0 | 1 | 6 |
| ∆j | 0 | -3 | -2 | -1 | 0 | 0 | 0 | 0 | 0 |
Таблица 5
Симплексная таблица второго плана задачи
| Pi | Бy | y0 | 3 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | θ |
| y1 | y2 | y3 | y4 | y5 | y6 | y7 | y8 | ||||
| 3 | y1 | 0.5 | 1 | -0.5 | 0.5 | 0.5 | 0 | 0 | 0 | 0 | - |
| 0 | y5 | -7 | 0 | 0 | 2 | 0 | 1 | 1 | 0 | 0 | ∞ |
| 0 | y6 | -8 | 0 | -5 | 2 | 0 | 0 | 1 | -1 | 0 | 1.6 |
| 0 | y7 | 1 | 0 | 5 | 0 | 0 | 1 | 0 | 1 | 0 | 0.2 |
| 0 | y8 | 11 | 0 | 2 | 2 | -1 | 0 | 0 | 0 | 1 | 5.5 |
| ∆j | 1.5 | 0 | -3.5 | 0.5 | 1.5 | 0 | 0 | 0 | 0 |
Таблица 6
Симплексная таблица третьего плана задачи
| Pi | Бy | y0 | 3 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | |
| y1 | y2 | y3 | y4 | y5 | y6 | y7 | y8 | ||||
| 3 | y1 | 0.6 | 1 | 0 | 0.5 | 0.5 | 0.1 | 0 | 0.1 | 0 | |
| 0 | y5 | -7 | 0 | 0 | 2 | 0 | 1 | 1 | 0 | 0 |
|
| 0 | y6 | -7 | 0 | 0 | 2 | 0 | 1 | 1 | 0 | 0 | |
| 2 | y2 | 0.2 | 0 | 1 | 0 | 0 | 0.2 | 0 | 0.2 | 0 | |
| 0 | y8 | 10.6 | 0 | 0 | 2 | -1 | -0.4 | 0 | -0.4 | 1 | |
| ∆j | 2.2 | 0 | 0 | 0.5 | 1.5 | 0.3 | 0 | 0.3 | 0 |
y4 ↔ x1 x1 = 1
y5 ↔ x2 x2 = 0
y6 ↔ x3 x3 = 0
y7 ↔ x4 x4 = 1
y8 ↔ x5 x5 = 0
Ответ: оптимальное решение х* = (1; 0; 0; 10), т.е. х1* = 1, х2* = 0, х3* = 0, х4* = 1, х5* = 0.
Задача 3
Для рытья котлована объёмом 1440 м3 строители получили три экскаватора. Мощный экскаватор производительностью 22.5 м3/час расходует в час 10 литров бензина. Аналогичные характеристики среднего экскаватора – 10 м3/час и 10/3 л/час, малого – 5 м3 и 2 л/час. Экскаваторы могут работать одновременно, не мешая друг другу. Запас бензина у строителей ограничен и равен 580 литров. Если рыть котлован только малым экскаватором, то бензина заведомо хватит, но это будет очень долго. Каким образом следует использовать имеющуюся технику, чтобы выполнить работу как можно скорее?