86035 (612624), страница 3
Текст из файла (страница 3)
|
|
|
| |||||||||||||||||||||
| b | ξ | ξ3 | ξ4 | x4 | x5 | ξ2 | |||||||||||||||||
| F | -14 | 0 | -3/5 | 0 | -14/5 | -3/5 | -14/5 | ||||||||||||||||
| x1 | 2 | 0 | 1/5 | 0 | -2/5 | 1/5 | -2/5 | ||||||||||||||||
| x6 | 5 | 0 | 0 | 1 | 1 | 0 | 1 | ||||||||||||||||
| x2 | 4 | 0 | 1/5 | 0 | 3/5 | 1/5 | -3/5 | ||||||||||||||||
| x3 | 7 | -1 | 3/5 | 0 | -1/5 | 3/5 | -1/5 | ||||||||||||||||
|
| f | 0 | -1 | -1 | -1 | 0 | 0 | -1 | |||||||||||||||
| b | x4 | x5 | |
| F | -14 | -14/5 | -3/5 |
| x6 | 5 | 1 | 0 |
| x2 | 4 | 3/5 | 1/5 |
| x3 | 7 | -1/5 | 3/5 |
| x1 | 2 | -2/5 | 1/5 |
Допустимое базисное оптимальное решение:
X = (2, 4, 7, 0, 0, 5)
F = -14 
2.1.7 Решение двойственной задачи
Прямая задача:
Двойственная задача:
Приводим к каноническому виду:
y1, y3 – базисные переменные, y2, y4, y5, y6 – свободные переменные
| ↑ | ||||||||||||
| b | y2 | y4 | y5 | y6 | ||||||||
| ← | y1 | 14 | 5 | -5 | 2 | -3 | 14/5 | |||||
| 14/5 | 1/5 | -1 | 2/5 | -3/5 | ||||||||
| y3 | 9 | 3 | -3 | 1 | -2 | 3 | ||||||
| -42/5 | -3/5 | 3 | -6/5 | 9/5 | ||||||||
| Ф’ | 112 | 35 | -40 | 12 | -25 | |||||||
| -98 | -7 | 35 | -14 | 21 | ||||||||
| b | y2 | y4 | y5 | y6 | ||||||||||||
| y1 | 14/5 | 1/5 | -1 | 2/5 | -3/5 | |||||||||||
| y3 | 3/5 | -3/5 | 0 | -1/5 | -1/5 | |||||||||||
| Ф’ | 14 | -7 | -5 | -2 | -4 | |||||||||||
| x1 | x2 | x3 | x4 | x5 | x6 |
| ↕ | ↕ | ↕ | ↕ | ↕ | ↕ |
| y5 | y6 | y1 | y2 | y3 | y4 |
| 2 | 4 | 7 | 0 | 0 | 5 |
F’ = Ф’ = 14
X = (2,4,7,0,0,5)
F= -F’ = -14
2.2 Задача целочисленного линейного программирования
2.2.1 Постановка задачи целочисленного линейного программирования
Решить ЗЦЛП, при условии целочисленности всех переменных, входящих в задачу, методом ветвей и границ и методом отсекающих плоскостей (методом Гомори).
2.2.2 Метод Гомори
x3, x4 – базисные переменные, x1, x2 – свободные переменные
| ↑ | ||||||||
| b | x1 | x2 | ||||||
| x3 | 11 | 2 | 3 | 11/2 | ||||
| -5 | -1/2 | -1/2 | ||||||
| ← | x4 | 10 | 4 | 1 | 10/4 | |||
| 5/2 | 1/4 | 1/4 | ||||||
| F’ | 0 | 2 | 1 | |||||
| -5 | -1/2 | -1/2 | ||||||
| ↑ | |||||||||
| b | x4 | x2 | |||||||
| ← | x3 | 6 | -1/2 | 5/2 | 12/5 | ||||
| 12/5 | -1/5 | 2/5 | |||||||
| x1 | 5/2 | 1/4 | 1/4 | 10 | |||||
| -3/5 | 1/20 | -1/10 | |||||||
| F’ | -5 | -1/2 | 1/2 | ||||||
| -6/5 | 1/10 | -1/5 | |||||||
| b | x1 | x2 | ||||||
| x3 | 12/5 | -1/5 | 2/5 | |||||
| x4 | 19/10 | 3/10 | -1/10 | |||||
| F’ | -31/5 | -2/5 | -1/5 | |||||
X = (19/10, 12/5, 0, 0)
F = -F’ = 31/5
Составляем неравенство Гомори:
| ↑ | |||||||||||
| b | x4 | x3 | |||||||||
| F’ | -31/5 | -2/5 | -1/5 | ||||||||
| 1/5 | 1/10 | -1/2 | |||||||||
| x2 | 12/5 | -1/5 | 2/5 | ||||||||
| -2/5 | -1/5 | 1 | |||||||||
| x1 | 19/10 | 3/10 | -1/10 | ||||||||
| 1/10 | -1/4 | ||||||||||
| ← | u2 | -2/5 | -1/5 | -2/5 | |||||||
| 1 | 1/2 | -5/2 | |||||||||
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
