Лекции.Орг


Поиск:




Алгоритм метода Гомори № 1




1.

Решим -задачу методом последовательного улучшения плана.
  1. Если все базисные компоненты оптимального решения -задачи
целые, то и есть решение -задачи.

3.

Если некоторая компонента оптимального решения - задачи
  1. нецелая, то переходим к п.2.
  2. Если в оптимальном плане единственная компонента нецелая,то дополнительное ограничение (2.1). строится по этой координате.

Если нецелых компонент в плане более одной, то выберем координату с

наименьшим номером. Пусть этой компонентой оказалась .  

Дополнительное линейное ограничение запишем в виде:

(2.2)

 

, (2.3)

6. Добавим условия 2.2. и 2.3 к условиям -задачи. Получим новую -задачу. Так как оптимальное решение -задачи определяло одну из вершин многогранника условий, то оно может быть выбрано в качестве первоначального опорного решения для вновь полученной задачи.

Последнюю симплексную таблицу -задачи берем в качестве  

 

исходной для -задачи, дополнив ее условием 2.2.

Симплексная таблица для -задачи получается из последней путем

окаймления строкой с элементами , , j не  

 

принадлежит базису задачи задачи.

Причем,

,

, j принадлежит базису задачи.

Получим новую задачу, переменными которой являются .

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

Обозначим через k номер псевдорешения -задачи; тогда направляющей строкой является i+k+1-я строка, k=0,1,2,... Поэтому на каждом этапе преобразования таблицы вектор будет выводиться из таблицы.

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

Процедуру решения -задачи и анализа полученного решения назовем большой итерацией. Номер большой итерации совпадает с номером

решаемой задачи.

Теорема 2.3. (о конечности первого алгоритма Гомори)

Пусть множество оптимальных планов - задачи ограничено

и выполняются следующие условия:

1) - целые коэффициенты целевой функции F, строка целевой функции в симплексной таблице учитывается при выборе строки для построения правильного отсечения;

2) справедливо одно из двух утверждений: либо целевая функция ограничена снизу на , либо -задача имеет хотя бы один план.





Поделиться с друзьями:


Дата добавления: 2016-10-30; Мы поможем в написании ваших работ!; просмотров: 547 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Наука — это организованные знания, мудрость — это организованная жизнь. © Иммануил Кант
==> читать все изречения...

801 - | 691 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.