Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Второй алгоритм Гомори
Данный алгоритм предназначен для решения задач, в которых требование целочисленности наложено на некоторые переменные (в частности и на все). Рассмотрим его применение к частично целочисленным задачам линейного программирования, имея в виду, что вычислительная схема будет справедлива и для полностью целочисленных задач. Пусть требуется максимизировать функцию
(23) при условиях
(24) (25) (26)
Метод решения задачи (23) – (26) основывается на той же идее, что и метод решения полностью целочисленных задач. Сформулируем второй алгоритм Гомори в виде следующей теоремы. Теорема 2: Пусть – оптимальное решение задачи и – соответствующая симплексная таблица. Если – не целое, то неравенство
(27) или, что то же самое, (28) (29) где (30) (31)
определяет оптимальное отсечение. Мы проверим лишь условие отсечения. Для этого докажем, что оптимальное решение задачи , не являющееся допустимым решением исходной задачи (23) – (26), не удовлетворяет условиям отсечения. Пусть в оптимальном решении величина нецелая, . Так как в оптимальном решении все небазисные переменные равны нулю:
()
Тогда формула (8) примет вид
Поскольку по условию теоремы . Условие отсечения выполнено. Правило построения правильного отсечения: Пусть не удовлетворяет условию целочисленности (26) и – симплекс-таблица, соответствующая полученному оптимальному решению задачи . Выберем
и построим правильное отсечение по формулам (28) – (31). [11]
|