Я пишу свой собственный MIP-решатель на Python, используя двойную симплексную таблицу и сокращения Гомори (для целей обучения).Я получил первичные, двойные и разрезы для хорошей работы.Однако при реализации предварительного масштабирования уравновешивания я заметил проблему, и теперь мне очень трудно понять, что я делаю неправильно.
Кажется, это проблема алгоритма, так как я согласен со всеми изменениями таблицывыполнено.
Давайте рассмотрим этот очень простой пример:
Развернуть: x2
1-е ограничение: 3 * x1 + 2 * x2 ≤ 6
2-е ограничение: -3 * x1 + 2 * x2 ≤ 0
Без предварительного масштабирования мой алгоритм работает хорошо, и соответствующая разработка таблицы показана ниже.Примечание: верхняя строка - это отрицательная целевая функция, поскольку я минимизирую.
Исходная таблица после добавления переменных слабины:
|0.0 | -1.0 |0.0 |0.0 |0.0 |
|3.0 |2.0 |1.0 |0.0 |6,0 |
| -3,0 |2.0 |0.0 |1.0 |0.0 |
Таблица после разворота (2, 1):
| -1.5 |0.0 |0.0 |0,5 |0.0 |
|6,0 |0.0 |1,0 | -1,0 |6,0 |
| -1,5 |1.0 |0.0 |0,5 |0.0 |
Таблица после поворота (1, 0):
|0.0 |0.0 |0,25 |0,25 |1,5 |
|1.0 |0.0 |0,17 | -0,17 |1,0 |
|0.0 |1.0 |0,25 |0,25 |1,5 |
Найдено первичное решение:
s: x1 = 1.0, x2 = 1.5 obj: -1.5
Таблица после добавления вырезки по Гомори:
|0.0 |0.0 |0,25 |0,25 |0.0 |1,5 |
|1.0 |0.0 |0,17 | -0,17 |0.0 |1,0 |
|0.0 |1.0 |0,25 |0,25 |0.0 |1,5 |
|0.0 |0,0 | -0,25 | -0,25 |1,0 | -0,5 |
Таблица после поворота (3, 2):
|0.0 |0.0 |0.0 |0,00 |1,00 |1,00 |
|1.0 |0.0 |0,0 | -0,33 |0,67 |0,67 |
|0.0 |1.0 |0.0 |0,00 |1,00 |1,00 |
|0.0 |0.0 |1.0 |1,00 | -4,00 |2,00 |
Найдено двойное решение:
s: x1 = 0,67, x2 = 1,0 объект: -1,0
Таблица после добавления вырезки по Гомори:
|0.0 |0.0 |0.0 |0,00 |1,00 |0.0 |1,00 |
|1.0 |0.0 |0,0 | -0,33 |0,67 |0.0 |0,67 |
|0.0 |1.0 |0.0 |0,00 |1,00 |0.0 |1,00 |
|0.0 |0.0 |1.0 |1,00 | -4,00 |0.0 |2,00 |
|0.0 |0.0 |0,0 | -0,67 | -0,67 |1,0 | -0,67 |
Таблица после поворота (4, 3):
|0.0 |0.0 |0.0 |0.0 |1.0 |0.0 |1,0 |
|1.0 |0.0 |0.0 |0.0 |1,0 | -0,5 |1,0 |
|0.0 |1.0 |0.0 |0.0 |1.0 |0.0 |1,0 |
|0.0 |0.0 |1.0 |0.0 | -5.0 |1,5 |1,0 |
|0.0 |0.0 |0.0 |1.0 |1,0 | -1,5 |1.0 |
Найдено двойное решение:
s: x1 = 1.0, x2 = 1.0 obj: -1.0
Найдено правильное целочисленное решение!
Теперь давайте вместо этого рассмотрим ту же проблему, но с масштабированием первого ограничения с коэффициентом 1/6 (это не должно изменить проблему).
Развернуть:x2
1-е ограничение: 0,5 * x1 + 0,33 * x2 ≤ 1
2-е ограничение: -3 * x1 + 2 * x2 ≤ 0
Исходная таблица после добавления слабых переменных:
|0,0 | -1,00 |0.0 |0.0 |0.0 |
|0,5 |0,33 |1.0 |0.0 |1,0 |
| -3,0 |2,00 |0.0 |1.0 |0.0 |
Таблица после разворота (2, 1):
| -1.5 |0.0 |0.0 |0,50 |0.0 |
|1.0 |0.0 |1,0 | -0,17 |1,0 |
| -1,5 |1.0 |0.0 |0,50 |0.0 |
Таблица после разворота (1, 0):
|0.0 |0.0 |1,5 |0,25 |1,5 |
|1.0 |0.0 |1,0 | -0,17 |1,0 |
|0.0 |1.0 |1,5 |0,25 |1,5 |
Найдено первичное решение:
s: x1 = 1,0, x2 = 1,5 объекта: -1,5
Таблица после добавления вырезки по Гомори:
| 0.0 | 0.0 | 1,5 | 0,25 | 0.0 | 1,5 |
| 1.0 | 0.0 | 1,0 | -0,17 | 0.0 | 1,0 |
| 0.0 | 1.0 | 1,5 | 0,25 | 0.0 | 1,5 |
| 0.0 | 0,0 | -0,5 | -0,25 | 1,0 | -0,5 | <- не похоже на действительный разрез? </p>
Таблица после разворота (3, 3):
| 0.0 | 0.0 | 1,00 | 0.0 | 1,00 | 1,00 |
| 1.0 | 0.0 | 1,33 | 0,0 | -0,67 | 1,33
| 0.0 | 1.0 | 1,00 | 0.0 | 1,00 | 1,00 |
| 0.0 | 0.0 | 2,00 | 1,0 | -4,00 | 2,00 |
Найдено двойное решение:
с: х1 = 1,33, х2 = 1,0 объект: -1,0
Таблица после добавления Gomory cut:
| 0.0 | 0.0 | 1,00 | 0.0 | 1,00 | 0.0 | 1,00 |
| 1.0 | 0.0 | 1,33 | 0,0 | -0,67 | 0.0 | 1,33
| 0.0 | 1.0 | 1,00 | 0.0 | 1,00 | 0.0 | 1,00 |
| 0.0 | 0.0 | 2,00 | 1,0 | -4,00 | 0.0 | 2,00 |
| 0.0 | 0,0 | -0,33 | 0,0 | -0,33 | 1,0 | -0,33 |
Таблица после разворота (4, 2):
| 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 3.0 | 0.0 |
| 1.0 | 0.0 | 0.0 | 0,0 | -2,0 | 4.0 | 0.0 |
| 0.0 | 1.0 | 0.0 | 0.0 | 0.0 | 3.0 | 0.0 |
| 0.0 | 0.0 | 0.0 | 1,0 | -6,0 | 6,0 | 0.0 |
| 0.0 | 0.0 | 1.0 | 0.0 | 1,0 | -3,0 | 1.0 |
Найдено двойное решение:
с: x1 = 0.0, x2 = 0.0 obj: -0.0
Неверное решение!