Ветвь и отрежьте корректируемые упражнения

Упражнение 1

Давайте рассмотрим это линейная программа следующий :

Решить методом Гомори задачу (первые два разреза).

Решение

Решим релаксированную задачу в действительных числах. Решение:

Алгоритм секущей плоскости Гомори использует переменную с наибольшей нецелой частью, здесь x_1. Мы сформулируем новое ограничение, рассматривая только дробные остатки каждого коэффициента:

Мы создаем новый резервная переменная для этого нового ограничения, которое дает следующий словарь:

Эта программа не реализуема, поэтому необходимо сделать симплекс двойной. Другими словами, мы форсируем вывод x_5 (сюда входит x_4), это дает следующий словарь:

Решение по-прежнему неудовлетворительно, мы берем ограничение с наибольшей дробной долей, следовательно, x_2, что дает следующее сокращение (в дробном остатке):

Что дает новую переменную пробела x_6:

После применения двойного симплекса (x_6 вытесняется, а x_5 входит) получаем следующий результат:

Обратите внимание, что это все еще не решает нашу проблему!