44.Алгоритм метода Гомори.

1.Симплекс-методом находят оптимальный план задачи. Если все компоненты оптимального плана целые, то он –оптимальный. В противном случае переходят к пункту 2

2.Среди нецелых компонент следует выбрать ту, у которой дробная часть является наибольшей и по соответствующей этой строке симплексной таблицы сформулировать правильное отсечение по формуле

(n-m,s=1)∑ {αkm+1}Xm+1≥{βk}

3.Сформулированное неравенство преобразовать в эквивалентное нулевое равенство и включить в симплексную таблицу с нецелочисленным оптимальным планом

4.Полученную расширенную задачу решают симплекс-методом. Если полученный план не является целочисленным нова переходят к пункту 2.

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

45.Метод ветвей и границ решения целочисленных задач.

Этот метод относится к группе комбинаторных.Применение этих методов заменяет полный перебор планов их частным перебором. Идея метода: пусть дана ЗЦЛП

f=(n,j=1)∑CjXi max

(n,j=1)∑AijXj=bi, i=1,m

xj≥0, j=1,n

xi-целое,j=1,n

Сначала в ОДЗ этой задачи определяется оптимальный план без учета условия целочисленности. Если в полученном решении некоторые переменные имеют дробное значение, то выбирают любую из дробных переменных и разветвляют исходную задачу на 2 подзадачи

f =∑CjXj max f =∑CjXj max

(n,j=1)∑AijXj≤bi, i=1,m (n,j=1)∑AijXj≤bi, i=1,m

Xk≤[Xk˚] Xk≥[Xk˚]+1

Xj≥0 Xj≥0

Xj-целое,j=1,n Xj-целое,j=1,n

Если после решения этих подзадач неизвестные не будут целочисленные, то выбирается задача с большим значением целевой функции и по неизвестной

Задача разбивается на 2 новые подзадачи. На каждом последующем шаге сравниваются целевые функции неразветвленных задач и ветвиться задача с большим значением целевой функции.