Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Второй алгоритм Гомори





 

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

 

(23)

при условиях

 

(24)

(25)

(26)

 

Метод решения задачи (23) – (26) основывается на той же идее, что и метод решения полностью целочисленных задач. Сформулируем второй алгоритм Гомори в виде следующей теоремы.

Теорема 2: Пусть – оптимальное решение задачи и – соответствующая симплексная таблица. Если – не целое, то неравенство

 

(27)

или, что то же самое,

(28)

(29)

где

(30)

(31)

 

определяет оптимальное отсечение.

Мы проверим лишь условие отсечения. Для этого докажем, что оптимальное решение задачи , не являющееся допустимым решением исходной задачи (23) – (26), не удовлетворяет условиям отсечения. Пусть в оптимальном решении величина нецелая, . Так как в оптимальном решении все небазисные переменные равны нулю:

 

()

 

Тогда формула (8) примет вид

 

 

Поскольку по условию теоремы . Условие отсечения выполнено.

Правило построения правильного отсечения: Пусть не удовлетворяет условию целочисленности (26) и – симплекс-таблица, соответствующая полученному оптимальному решению задачи . Выберем

 

 

и построим правильное отсечение по формулам (28) – (31).

[11]

Date: 2016-07-22; view: 327; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию