Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Первый алгоритм Гомори
|
|
Рассмотрим полностью целочисленную задачу линейного программирования, в которой n1 = n.
Пусть 
– оптимальный опорный план задачи 
на целочисленность. Если они все целые, то 
. Если хотя бы одна координата, допустим 
, будет нецелой, поступим следующим образом.
Обозначим через N совокупность небазисных переменных и на основании последней симплексной таблицы выразим целевую функцию и все переменные 
через небазисные переменные 
:
(20)
Так как 
– нецелая величина, обозначим ближайшее целое число, не превосходящее 
, через 
(целая часть 
) и определим дробную часть числа 
(21)
Очевидно, 
.
Теорема 1: Пусть 
– допустимое решение задачи 
. Тогда соотношение
(22)
определяют правильное отсечение.
Доказательство: Запишем выражение (21) в виде
Используя выражение (22), получим
Или
.
На основании предположения теоремы о допустимости решения задачи 
и 
– целые. Величины 
и 
целые по определению. Следовательно, 
тоже целое.
Докажем, что 
. Предположим, что 
. Это значит, что
По определению дробной части 
. По условию теоремы x – допустимое решение задачи , поэтому 
. Следовательно, 
, 
. Отсюда 
, или, что то же самое, 
. Итак, 
– нецелое, а это противоречит только что доказанному. Следовательно, предположение 
неверное.
Теорема доказана.
Следствие: Любое оптимальное решение 
задачи 
, не являющиеся допустимым решением задачи не удовлетворяет условию правильного отсечения (22).
Доказательство: Пусть 
– оптимальное решение задачи 
, 
–дробное. Покажем, что не удовлетворяет условию отсечения. Из оптимальности плана следует, что 
. Поэтому 
. Учитывая это, подставим 
в выражение (22):
что противоречит условию .
Важной проблемой метода отсечения является нарастание количества дополнительных ограничений по мере решения вспомогательных задач, оптимальные планы которых будут содержать нецелые координаты, т.е. возникает проблема размерности. Гомори предложил прием, ограничивающий размеры рассматриваемых расширенных симплексных таблиц числом 
, где n – количество переменных задач 
, k – число ее небазисных переменных. Этот прием основан на том, что дополнительные ограничения (правильные отсечения) 
интересуют нас лишь как способ отсечения нецелочисленного оптимального решения 
и перехода от задачи 
к задаче 
. Заметим, что переменная 
выводится из базиса сразу же после введения ограничения:
,
.
[5]
Date: 2016-07-22; view: 324; Нарушение авторских прав