Линейное и нелинейное программирование (стр. 3 из 5)
| ↑ | |||||||||
| 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 Постановка задачи целочисленного линейного программирования
Решить ЗЦЛП, при условии целочисленности всех переменных, входящих в задачу, методом ветвей и границ и методом отсекающих плоскостей (методом Гомори).
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 | |||
| b | x4 | u2 | |||
| F’ | -6 | -3/10 | -1/2 | ||
| x2 | 2 | -2/5 | 1 | ||
| x1 | 2 | 7/20 | -1/4 | ||
| x3 | 1 | 1/2 | -5/2 | ||
X = (2, 2, 1, 0)
F = -F’ = 6
 | b | x1 | x2 |
| x3 | 12/5 | -1/5 | 2/5 |
| x4 | 19/10 | 3/10 | -1/10 |
| F’ | -31/5 | -2/5 | -1/5 |
Задача № 1
Приводим к каноническому виду:
x3, x4, x5 – базисные переменные, x1, x2 – свободные переменные
| ↑ | |||||
| b | x1 | x2 | |||
| x3 | 11 | 2 | 3 | 11/2 | |
| -5 | -1/2 | -1/2 | |||
| ← | x4 | 10 | 4 | 1 | 5/2 |
| 5/2 | 1/4 | 1/4 | |||
| x5 | 2 | 0 | 1 | ||
| 0 | 0 | 0 | |||
| F’ | 0 | 2 | 1 | ||
| -5 | -1/2 | -1/2 | |||
| ↑ | |||||
| b | x4 | x2 | |||
| x3 | 6 | -1/2 | 5/2 | 12/5 | |
| -5 | 0 | -5/2 | |||
| x1 | 5/2 | 1/4 | 1/4 | 10 | |
| -1/2 | 0 | -1/4 | |||
| ← | x5 | 2 | 0 | 1 | 2 |
| 2 | 0 | 1 | |||
| F’ | -5 | -1/2 | 1/2 | ||
| -1 | 0 | -1/2 | |||
| b | x4 | x5 | |||
| x3 | 1 | -1/2 | -5/2 | ||
| x1 | 2 | 1/4 | -1/4 | ||
| x2 | 2 | 0 | 1 | ||
| F’ | -6 | -1/2 | -1/2 | ||
X = (2, 2, 1, 0, 0)
F’ = -6
F = -F’ = 6
Задача № 2
Решаем задачу с x2 ≥ 3 в подсистеме «Поиск решения» системы Excel. Получаем допустимое не оптимальное решение F = 5, X = (1, 3)
| =2*$B$1+$B$2 | 1 | =2*$B$1+3*$B$2 | 11 |
| 3 | =4*$B$1+$B$2 | 10 | |
| =$B$2 | 3 |
| 5 | 1 | 11 | 11 |
| 3 | 7 | 10 | |
| 3 | 3 |
| Ограничения | |||||
| Ячейка | Имя | Значение | Формула | Статус | Разница |
| $C$1 | 11 | $C$1<=$D$1 | связанное | 0 | |
| $C$2 | 7 | $C$2<=$D$2 | не связан. | 3 | |
| $C$3 | 3 | $C$3>=$D$3 | связанное | 0 | |
2.3 Задача целочисленного линейного программирования с булевскими переменными
2.3.1 Постановка задачи целочисленного линейного программирования с булевскими переменными
Составить самостоятельно вариант для задачи целочисленного линейного программирования с булевскими переменными с учетом следующих правил: в задаче используется не менее 5 переменных, не менее 4 ограничений, коэффициенты ограничений и целевой функции выбираются произвольно, но таким образом, чтобы система ограничений была совместна. Задание состоит в том, чтобы решить ЗЦЛП с булевскими переменными, используя алгоритм Баллаша и определить снижение трудоемкости вычислений по отношению к решению задачи методом полного перебора.
| № | x4 | x3 | x2 | x1 | x5 | Выполнение ограничений | Значение F | |||||
| 0 | 1 | 2 | 3 | 4 | 5 | |||||||
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | Fф=0 | |||||
| 2 | 0 | 0 | 0 | 0 | 1 | 44 | ||||||
| 3 | 0 | 0 | 0 | 1 | 0 | 17 | ||||||
| 4 | 0 | 0 | 0 | 1 | 1 | 61 | ||||||
| 5 | 0 | 0 | 1 | 0 | 0 | 13 | ||||||
| 6 | 0 | 0 | 1 | 0 | 1 | 57 | ||||||
| 7 | 0 | 0 | 1 | 1 | 0 | 30 | ||||||
| 8 | 0 | 0 | 1 | 1 | 1 | 74 | ||||||
| 9 | 0 | 1 | 0 | 0 | 0 | -10 | + | + | + | + | + | Fф=-10 |
| 10 | 0 | 1 | 0 | 0 | 1 | 34 | ||||||
| 11 | 0 | 1 | 0 | 1 | 0 | 7 | ||||||
| 12 | 0 | 1 | 0 | 1 | 1 | 51 | ||||||
| 13 | 0 | 1 | 1 | 0 | 0 | 3 | ||||||
| 14 | 0 | 1 | 1 | 0 | 1 | 47 | ||||||
| 15 | 0 | 1 | 1 | 1 | 0 | 20 | ||||||
| 16 | 0 | 1 | 1 | 1 | 1 | 64 | ||||||
| 17 | 1 | 0 | 0 | 0 | 0 | -49 | + | + | + | + | + | Fф=-49 |
| 18 | 1 | 0 | 0 | 0 | 1 | -5 | ||||||
| 19 | 1 | 0 | 0 | 1 | 0 | -32 | ||||||
| 20 | 1 | 0 | 0 | 1 | 1 | 12 | ||||||
| 21 | 1 | 0 | 1 | 0 | 0 | -36 | ||||||
| 22 | 1 | 0 | 1 | 0 | 1 | 8 | ||||||
| 23 | 1 | 0 | 1 | 1 | 0 | -19 | ||||||
| 24 | 1 | 0 | 1 | 1 | 1 | 25 | ||||||
| 25 | 1 | 1 | 0 | 0 | 0 | -59 | + | + | + | + | + | Fф=-59 |
| 26 | 1 | 1 | 0 | 0 | 1 | -15 | ||||||
| 27 | 1 | 1 | 0 | 1 | 0 | -42 | ||||||
| 28 | 1 | 1 | 0 | 1 | 1 | 2 | ||||||
| 29 | 1 | 1 | 1 | 0 | 0 | -46 | ||||||
| 30 | 1 | 1 | 1 | 0 | 1 | -2 | ||||||
| 31 | 1 | 1 | 1 | 1 | 0 | -29 | ||||||
| 32 | 1 | 1 | 1 | 1 | 1 | 15 | ||||||
Фильтрующее ограничение:
