Гомори әдісі

Содержание:

 

1.Метод Гомори

 

2.Целочисленное линейное  программирование ориентировано  на решение задач линейного  программирования, в которых все  или некоторые переменные принимают  целочисленные значения.

 

3.Для решения целочисленной задачи линейного программирования Р. Гомори предложил метод отсечения плоскостей в 1958 г..

 

4.Алгоритм Гомори содержит  этапы:

Этап 1. Решение непрерывной  задачи. Если решение дробное переход  на 2 этап.

Этап 2. Решение расширенной  задачи.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

МЕТОД ГОМОРИ

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

Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом.

1. Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.
2. Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами:

- оно должно быть  линейным;

- должно отсекать найденный  оптимальный нецелочисленный план;

- не должно отсекать  ни одного целочисленного плана.

Для построения ограничения выбираем компоненту оптимального плана с наибольшей дробной частью и по соответствующей этой компоненте k-й строке симплексной таблицы записываем ограничение Гомори.

,  ,

где   f_k = x_j - [x_j];  

f_kj = z_kj - [z_kj];  

S^* - новая переменная;

[x_j], [z_kj] -ближайшее целое, не превосходящее x_j и z_kj соответственно.

3. Составленное ограничение добавляем к имеющимся в симплексной таблице, тем самым получаем расширенную задачу. Чтобы получить опорный план этой задачи, необходимо ввести в базис тот вектор, для которого величина   минимальна. И если для этого вектора величина   получается по дополнительной строке, то в следующей симплексной таблице будет получен опорный план. Если же величина   не соответствует дополнительной строке, то необходимо переходить к М-задаче (вводить искусственную переменную в ограничение Гомори).
4. Решаем при помощи обычных симплексных преобразований полученную задачу. Если решение этой задачи приводит к целочисленному оптимальному плану, то искомая задача решена. Если мы получили нецелочисленное решение, то снова добавляем одно дополнительное ограничение, и процесс вычислений повторяется. Проделав конечное число итераций, либо получаем оптимальный план задачи целочисленного программирования, либо устанавливаем ее неразрешимость.

Замечания:

1. Если дополнительная переменная S^* вошла в базис, то после пересчета какого-либо последующего плана соответствующие ей строку и столбец можно удалить (тем самым сокращается размерность задачи).
2. Если для дробного x_j обнаружится целочисленность всех коэффициентов соответствующего уравнения (строки), то задача не имеет целочисленного решения.

 

Разработаем целочисленную  математическую модель информационной системы и определим оптимальное  решение методом Гомори.

Математическая модель формулируется  следующим образом: из числа фирм, предоставляющих услуги спутникового Internet на территории Российской Федерации, требуется выбрать провайдера спутникового Internet с максимальной величиной чистого приведенного эффекта (NPV) и удовлетворяющих финансовым ограничениям [3, c. 58].

Пусть   — доля финансирования проекта “НТВ-Плюс”,   — доля финансирования проекта EuropeOn Line,   — доля финансирования проекта Astra Network,   — доля финансирования проектаSatpro,   — доля финансирования проекта Network Service.

Целочисленная математическая модель имеет вид

при ограничениях (1)

 Решим непрерывную задачу. Приведем к стандартной форме  и составим исходную Жорданову таблицу (табл. 1).

при ограничениях (4)

(2)

Таблица 1

Начальная Жорданова  таблица

БП	1	-	-	-	-	-
=	6,5	5,4	3,2	2,931	6,286	5,9
=	3,0	2,006437	1,5	3,000547	3,000575	3,2
=	3,0	0,0	2,5	2,0	0,0	1,6
=	1,5	0,0	0,881832	0,0	0,0	1,186
Z=	0	-1,52727	-0,741239	-1,374394	-0,14511	-0,530312

 

В табл.2 приведена первая итерация.

Таблица 2

Первая итерация

БП	1	-	-	-	-	-
=
=	0,58484	-0,371563	0,311	1,911498	0,664934	1,007782
=	3,0	0	2,5	2,0	0	1,6
=	1,5	0	0,881832	0	0	1,186
Z=	1,83838	0,282827	0,16381	-0,545426	1,632745	1,138371

 

В табл.3 приведено оптимальное  решение непрерывной задачи.

Переход ко второму этапу  алгоритма Гомори.

Выбирается базисная переменная   с наибольшей дробной частью:  ,  ,  . Для переменной   составляется уравнение.

В табл. 4 и табл. 5 представлены расширенная задача и 3 итерация.

Таблица 3

Оптимальное решение  непрерывной задачи. Вторая итерация

БП	1	-	-	-	-	-
=	1,037635	0,290692	0,504283	-0,283954	0,975263	0,806429
=	0,305961	-0,194383	0,1627	0,52315	0,34786	0,527221
=	2,388078	0,388766	2,174601	-1,0463	-0,69572	0,545558
=	1,5	0	0,881832	0	0	1,186
Z=	2,00526	0,176807	0,252551	0,28534	1,822477	1,425931

 

Таблица 4

Расширенная задача с первым дополнительным ограничением

БП	1	-	-	-	-	-
=	1,037635	0,290692	0,504283	-0,283954	0,975263	0,806429
=	0,305961	-0,194383	0,1627	0,52315	0,34786	0,527221
=	2,388078	0,388766	2,174601	-1,0463	-0,69572	0,545558
=	1,5	0	0,881832	0	0	1,186
=	-0,305961	0,194383	-0,1627	-0,52315	-0,34786	-0,527221
Z=	2,00526	0,176807	0,252551	0,28534	1,822477	1,425931

 

Таблица 5

Третья итерация

БП	1	-	-	-	-	-
=	0,569642	0,588017	0,25542	-1,084156	0,443182	1,529584
=	0	0	0	0	0	1
=	2,071475	0,58991	2,006242	-1,587645	-1,055679	1,034781
=	0,811731	0,437271	0,515833	-1,176842	-0,782522	2,249531
=	0580328	-0,368694	0,308599	0,992278	0,659799	-1,896738
Z=	1,177753	0,702539	-0,18749	-1,129581	0,881649	2,704617

 

В табл.6 приведено оптимальное  нецелочисленное решение.

В табл.7 представлена расширенная  задача со вторым дополнительным ограничением.

 

Таблица 6

Оптимальное нецелочисленное  решение

БП	1	-	-	-	-	-
=	1,203704	0,185185	0,592593	1,09259	1,164074	-0,542779
=	0	0	0	0	0	1
=	3	0	2,5	1,6	0	-2
=	1,5	0	0,881832	1,186	0	0
=	0,584844	-0,371563	0,311001	1,007782	0,664934	-1,911499
Z=	1,838386	0,282829	0,16381	1,13837	1,632745	0,545424

 

Таблица 7

Расширенная задача со вторым дополнительным ограничением

БП	1	-	-	-	-	-
=	1,203704	0,185185	0,592593	1,09259	1,164074	-0,542779
=	0	0	0	0	0	1
=	3	0	2,5	1,6	0	-2
=	1,5	0	0,881832	1,186	0	0
=	0,584844	-0,371563	0,311001	1,007782	0,664934	-1,911499
=	-0,203704	-0,185185	-0,592593	-0,09259	-0,164074	0,542779
Z=	1,838386	0,282829	0,16381	1,13837	1,632745	0,545424

 

В табл.8 приведена четвертая  итерация. В табл.9 и табл.10 представлены расширенная задача и оптимальное целочисленное решение. Оптимальный целочисленный план  =   (табл. 10). Значение целевой функции Z=1.52728.

Результаты проведенных  исследований позволили сделать  следующие выводы.

1. Разработана целочисленная математическая модель оптимизации информационных систем, позволяющая сократить затраты и сроки проектирования информационных систем и повысить обоснованность принимаемых решений.
2. Найдено оптимальное решение целочисленной задачи оптимизации информационной системы методом Гомори.

 

Таблица 8

Четвертая итерация. Отсечение дробной части переменной 

БП	1	-	-	-	-	-
=	1	0	1	1	1	0
=	0	0	0	0	0	1
=	2,14062	-0,781249	4,21875	1,20939	-0,692187	0,289847
=	1,19687	-0,275572	1,48809	1,04822	-0,244157	0,807704
=	0,477937	-0,468751	0,524814	0,959189	0,578826	-1,62664
=	0,34375	0,312499	-1,6875	0,156246	0,276875	-0,915939
Z=	1,78208	0,231638	0,276429	1,11278	1,58739	0,695464

 

Таблица 9

Расширенная задача с третьим дополнительным ограничением

БП	1	-	-	-	-	-
=	1	0	1	1	1	0
=	0	0	0	0	0	1
=	2,14062	-0,781249	4,21875	1,20939	-0,692187	0,289847
=	1,19687	-0,275572	1,48809	1,04822	-0,244157	0,807704
=	0,477937	-0,468751	0,524814	0,959189	0,578826	-1,62664
=	0,34375	0,312499	-1,6875	0,156246	0,276875	-0,915939
=	-0,34375	-0,312499	0,68785	-0,156246	-0,276875	0,915939
Z=	1,78208	0,231638	0,276429	1,11278	1,58739	0,695464

 

Таблица 10

Оптимальное целочисленное  решение

БП	1	-	-	-	-	-
=	1	0	1	1	1	0
=	0	0	0	0	0	1
=	3	-2,5	2,5	1,60001	0	-2
=	1,5	-0,881833	0,88183	1,186	0	0
=	0,993565	-1,50001	-0,506442	1,19356	0,994141	-3,00056
=	0	1	-1	0	0	0
=	1,1	-3,20001	-2,20001	0,499989	0,886003	-2,93101
Z=	1,52727	0,741244	0,786034	0,996964	1,38216	1,3744