Алгоритм Гомори

12.12.2020

Алгоритм Гомори — алгоритм, который используется для решения полностью целочисленных задач линейного программирования. Алгоритм разработан в 1950-х годах американским математиком Ральфом Гомори.

Порядок действий

1. Используя симплекс-метод, без учёта требования целочисленности, получаем набор равенств:

x i + ∑ a ¯ i , j x j = b ¯ i , {displaystyle x_{i}+sum {ar {a}}_{i,j}x_{j}={ar {b}}_{i},}

где x i {displaystyle x_{i}} — переменные базиса, а x j {displaystyle x_{j}} — свободные переменные

2. Вводим новое ограничение ( k {displaystyle k} соответствует переменной x k , {displaystyle x_{k},} которая в оптимальном плане имеет максимальную дробную часть):

k = argmax t ( b ¯ t − ⌊ b ¯ t ⌋ ) = argmax t { b t } {displaystyle k={underset {t}{operatorname {argmax} }}({ar {b}}_{t}-lfloor {ar {b}}_{t} floor )={underset {t}{operatorname {argmax} }}{b_{t}}}

∑ ( ⌊ a ¯ k , j ⌋ − a ¯ k , j ) x j ⩽ ⌊ b ¯ k ⌋ − b ¯ k ∼ − ∑ { a k , j } x j ⩽ − { b ¯ k } ∼ ∑ { a k , j } x j ⩾ { b ¯ k } {displaystyle sum (lfloor {ar {a}}_{k,j} floor -{ar {a}}_{k,j})x_{j}leqslant lfloor {ar {b}}_{k} floor -{ar {b}}_{k}quad sim quad -sum {a_{k,j}}x_{j}leqslant -{{ar {b}}_{k}}quad sim quad sum {a_{k,j}}x_{j}geqslant {{ar {b}}_{k}}}

где ⌊ ⋅ ⌋ {displaystyle lfloor cdot floor } — пол (см. целая часть)

3. Если при решении с новым ограничением получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап.



Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru © 2020
При цитировании и использовании любых материалов ссылка на сайт обязательна