Студопедия  
Главная страница | Контакты | Случайная страница

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

Глава I. Метод Гомори. Решения задач целочисленнного программирования.[3]

Метод Гомори. Решения задач целочисленнного программирования. [3]

В общем случае задача целочисленного программирования формулируется следующим образом: найтии максимум или минимум функции

Z(X) =

При условиях

, i-1, 2, …, m,

, j=1, 2, …, т,

Согласно методу Гомори задача линейного программирования сначала решается симплексным методом без учета целочисленности переменных. Если оптимальное решение оказывается целочисленным, то решение задачи заканчивается. Если оптимальное решение нецелочисленное, то из системы ограничений выбирается уравнение, для которого дробная часть координаты оптимального решения имеет наибольшее значение, и на его основе составляется дополнительное ограничение. Дополнительное ограничение отсекает от области допустимых решений нецелочисленное оптимальное решение, но при этом сохраняет целочисленные вершины этой области.

Пусть i-е ограничение задачи, находящееся в последней симплексной таблице, имеет вид

,

где – базисная переменная в уравнении;

– коэффициенты при неизвестных (коэффициенты разложений векторов условий по базису опорного решения);

– свободные переменные в системе уравнений;

- правая часть уравнения (координата оптимального решения), которая является дробным числом.

Тогда дополнительное ограничение имеет вид

- 0,

где - дробная часть ;

–дробная часть .

Число () называется целой частью числа , если оно наиболее близкое к нему целое и не превосходит .

Дробная часть числа находится как разность этого числа и его целой части:

= – ().

Например, для числа целая часть () = 1, дробная часть равна – 1 = . Для числа - целая часть ) = -2, дробная часть равна - – (-2) = . Дробная часть числа всегда неотрицательная и меньше единицы.

В неравенство вводится дополнительная переменная , получается уравнение

- + = 0.

В систему ограничений задачи это ограничение записывается в виде

- = - .

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

Задача не имеет целочисленного решения, если оптимальное решение содержит координату с дробной частью и все коэффициенты соответствующего уравнения являются целыми.

 




Дата добавления: 2015-01-29; просмотров: 18 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав