Пример: «Задача о распределение инвестиций»

И меется n проектов и для любого j-ого проекта определен эффект от реализации γ_j при необходимых объемах инвестиций g_j, т.е. γ_j g_j.

Общий объем инвестиций не превышает В. Определить, какие проекты нужно реализовать, чтобы суммарный эффект был максимальным.

Х = 0 если Р_j не реализуется

1. если Р_j реализуется

Тогда при ограничениях

Первый алгоритм Гомори (аддитивный)

Идея: задача решается симплекс-методом «с ослабленными ограничениями» (без условия целочисленности на переменные). Затем подбирается дополнительное линейное ограничение, обеспечивающее за конечное число шагов получение оптимального целочисленного решения или установление факта его отсутствия.

Г

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

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

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

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

Для изложения вводим следующие понятия:

Пусть а - действительное число. Целой частью числа а – [a] – есть максимальное целое, не превосходящее данного числа. Дробная часть числа а – q_a- разность между числом и его целой частью: q_a= а-[a]; 0≤ q_a≤1

Основным понятием в методе отсечения является понятие «правильного отсечения».

Определение: пусть Х^*- оптимальный нецелочисленный план (ослабленной задачи). Неравенство  х< называется правильным отсечением (отсечением Гомори), если оно удовлетворяет следующим условиям:

1. условие отсечения: Х^* не удовлетворяет этому ограничению  х^*≥

2. условие правильности: для всякого произвольного целочисленного плана Х`  Х<sup>`</sup><

Необходимым условием применения первого алгоритма Гомори (аддитивного) является целочисленность всех коэффициентов и элементов правых частей.

Алгоритм Гомори состоит из двух шагов:

1. Решается ослабленная задача симплекс-методом. Если оптимальный план целочисленный, то он является решением исходной задачи, в противном случае переходим к пункту № 2.

2. Вводится дополнительное линейное ограничение - правильное отсечение и переходим к пункту № 1, решая ослабленную задачу с дополнительным ограничением.

Процесс присоединения дополнительных ограничений продолжается до тех пор, пока:

• Либо не будет найдено целочисленное решение задачи

• Либо не будет установлено, что такого решения нет.

Условие неразрешимости целочисленной задачи:

Это возможно, если для дробного значения переменной задачи x_j (которая не является недобавочной, неизбыточной переменной) все коэффициенты a_ij в данной строке симплекс-таблицы оптимального решения окажутся не целыми.

Схема алгоритма

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

Замечание: 1-й алгоритм Гомори решает только полностью целочис­ленные задачи, поэтому результатом его решения может быть опти­мальный план только с целочисленными компонентами.

2. В симплекс-таблице оптимального решения выбираем значение базисной переменной задачи Х^*_j с наибольшей дробной частью. Если таких переменных несколько, то выбираем любую.

Этой переменной соответствует строка симплекс-таблицы, на­зываемая строкой, производящей отсечение (производящей стро­кой).

Выписывается уравнение

(полагая, что первые m перемен­ных базисные для данного оптимального решения).

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

Представим каждый коэффициент данной строки в виде целой и дробной частей.

Тогда 0<q_j<1

0≤q_j<1

q_j - положительная дробь

q_ij - неотрицательная дробь

Переносим все целые части коэффициентов в одну сторону, ос­тавляя все дробные в другой:

Так как все переменные x_m+1,...,x_n принимают целочисленные значения и силу их небазисности, то правая часть уравнения является целочисленной. Сле­довательно, в силу неотрицательности дробных частей и переменных зада­чи и левая часть должна быть неотрицательна:

, следовательно,

Так как q_j<1, заменяя в правой части q_j, получим строгое нера­венство

Так как левая часть неравенства должна принимать целые зна­чения, то, следовательно, необходимое условие ее целочисленности можно записать только в следующем виде:

Вводя остаточную переменную S_j (переменную Гомори), получим

Где S_j – неотрицательная добавочная переменная, которая по определению должна принимать целочисленное значение, что для данной системы ограничений при x_j=0 имеет вид:

Следовательно, она принимает отрицательное значение, т.е. является недопустимой, и, таким образом, полученное ранее решение ослабленной задачи не удовлетворяет данному ограничению. В этой ситуации обычно используют двойственный симплекс-метод или М-метод.

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