Курсовая работа: Дискретное программирование

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

Двойственный симплекс-метод является основой для метода Гомори, так как он позволяет учитывать новые дополнительные ограничения (правильные отсечения) и переходить от текущего псевдоплана к новому оптимальному плану.

Можно доказать, что приведенный алгоритм конечен. Это означает, что на некотором шаге (итерации) будет найден целочисленный оптимальный план или обнаружен факт отсутствия допустимых целочисленных планов.

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

4.3 Пример решения ЦЗЛП методом Гомори

Рассмотрим особенности применения метода Гомори на конкретном примере. Пусть дана задача со следующими условиями:

4.3.1 Итерация 1

Используя обычный симплекс-алгоритм, решаем непрерывный аналог исходной задачи, в котором игнорируются условия целочисленности 25. В качестве исходного базиса можно взять первый и второй столбцы. На его основе заполняется таблица T(1,1) (первый индекс в обозначении таблицы соответствует "большой" итерации, а второй — "малой").

Как видно из строки оценок, данный базис является оптимальным, однако соответствующий ему план х ={11/5,17/5, 0) не является целочисленным, поэтому выбираем из таблицы T(1,1) строку, содержащую первый нецелый элемент, и согласно формуле 22 строим отсекающее ограничение:

после чего переходим к следующей "большой" итерации.

4.3.1 Итерация 2

С учетом сформированного отсекающего ограничения заполняем симплекс-таблицу T(2,1).

В соответствии с алгоритмом двойственного симплекс-метода переходим к следующему базису N(β(2,2))={1, 2, 3}.

План, достигнутый в таблице T(2,2), является не только оптимальным (b(β(2,2))>0), но и полностью состоит из целочисленных компонент, т. е. решение задачи найдено: х* = (1, 2, 1) и f(x)=7.

5. Метод ветвей и границ

5.1 Общая схема метода "ветвей и границ"

Другим широко применяемым для решения задач дискретного программирования методом является метод ветвей и границ. Впервые данный метод для решения ЦЗЛП предложили в 1960 г. Лэнг и Дойг, а его "второе рождение" произошло в 1963 г. в связи с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи о коммивояжере [33].

Вообще говоря, термин "метод ветвей и границ" является собирательным и включает в себе целое семейство методов, применяемых для решения как линейных, так и нелинейных дискретных задач, объединяемое общими принципами. Кратко изложим их.

Пусть стоит задача: (*)