Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

4.2.1. Метод Р. Гомори

Этот метод применяется для решения задачи целочисленного программирования (4.1), (4.2), при условии целочисленности всех коэффициентов и правых частей ограничений задачи. Эти условия не сужают область применения метода, так как вполне выполнимы. Например, [37], ограничение

shukaev162.wmf

легко можно записать в виде неравенства

6x1 + 2x2 ≤ 39,

в которой дроби отсутствуют.

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

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

Таблица 4.1

Базисн.

перем.

x1

xi0

xm

V1

 

Vj

 

Vn

Решение

x1

1

0

0

a11

a1j

a1n

b1

...

...

                 

....

xi

0

1

0

ai1

aij

ain

bi

....

....

                 

....

xm

0

0

1

am1

amj

amn

bm

f

0

0

0

c1

cj

cn

f0

 

Здесь xi (i = 1, 2, …, m) – базисные переменные, а vj (j = 1, 2, …, n) – небазисные переменные.

Пусть i-я строка таблицы соответствует нецелому значению базисной переменной xi. Выразим эту переменную как

shukaev163.wmf (4.3)

где bi – нецелое число. Далее представим правые части в виде

bi = [bi] + di; (4.4)

aij = [aij] + dij, (4.5)

где в квадратных скобках записано наибольшее целое число, которое меньше, чем число внутри скобки. Например, если

b1 = 3/2, то [b1] = 1, а di = 1/2

или если

a11 = –5/2, то [d11] = –3, а d11 = 2/3.

После подстановки (4.4) и (4.5) в (4.3) получим

shukaev164.wmf

или

shukaev165.wmf (4.6)

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

dij ≥ 0 и Vj ≥ 0

для всех i и j, то

shukaev166.wmf

Следовательно, выполняется неравенство

shukaev167.wmf

Это означает, что

shukaev168.wmf

поскольку di < 1.

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

shukaev169.wmf

Это ограничение перепишем в виде равенства

shukaev170.wmf (4.7)

где Si – неотрицательная дополнительная переменная, которая по определению должна принимать целые значения.

Такое ограничение-равенство определяет отсечение Гомори для полностью целочисленной задачи.

Из симплексной таблицы следует, что vj = 0 и, следовательно Si = –di, то есть данная компонента решения не является допустимой. Это означает, что полученное ранее решение непрерывной задачи не удовлетворяет новому ограничению.

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

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

Таблица 4.2

Базисн.

перем.

x1

xi

xm

V1

 

Vj

 

Vn

Si

Решение

x1

1

0

0

a11

a1j

a1n

0

b1

...

...

                 

...

...

xi

0

1

0

ai1

aij

ain

0

bi

...

...

                 

...

...

xm

0

0

1

am1

amj

amn

0

bm

f

0

0

0

c1

cj

cn

0

f0

Si

0

0

0

–di1

–dij

–din

1

–di

 

Если полученное (в результате применения двойственного симплекс-метода) решение является целочисленным, то процесс решения исходной задачи завершен. В противном случае необходимо ввести новое отсечение на базе полученной табл. 4.2 и вновь воспользоваться двойственным симплекс-методом. Эта процедура повторяется до тех пор, пока не будет найдено целочисленное решение.

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

При знакомстве с методом Гомори может сложится впечатление, что размеры симплекс-таблицы неограниченно возрастают по мере добавления новых отсечений. Это не соответствует действительности. Общее число ограничений порожденной задачи не может превышать количества переменных исходной задачи [37].

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

Шаг 1. Решается исходная целочисленная задача линейного программирования с ослабленным ограничением, то есть без требования целочисленности оптимальных решений, отображаемых в итоговой симплекс-табл. 4.1.

Шаг 2. Проверяется целочисленность оптимальных решений. Если в столбце решений итоговой симплекс-таблицу (табл. 4.1) содержатся только целые числа, то получено оптимальное решение целочисленной задачи линейного программирования. В противном случае переход на шаг 3.

Шаг 3. Если в столбце решений содержаться дробные решения, то для выбранного дробного решения формируется уравнение отсечения Гомори (4.7) и это уравнение добавляется в систему ограничений исходной задачи в виде дополнительной Si – строки итоговой таблицы шага 1.

Шаг 4. С помощью алгоритма двойственного симплекс-метода осуществляется переход к следующей симплекс-таблице. Далее возврат на шаг 2.

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

Пример 4.1. Пусть необходимо максимизировать функцию

f = 7x1 + 9x2 → max, (4.7)

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

–x1 + 3x2 ≤ 6;

7x1 + x2 ≤ 35;

x1 ≥ 0; x2 ≥ 0, (4.8)

x1 и x2 – целые. (4.9)

Шаг 1. Решаем исходную задачу без учета ограничения (4.9). Применяя обычный симплекс-алгоритм (раздел 2.3) получим следующую итоговую симплекс-таблицу (табл. 4.3).

Таблица 4.3

БП

x1

x2

x3

x4

Решение

x2

0

1

shukaev171.wmf

shukaev172.wmf

shukaev173.wmf

x1

1

0

shukaev174.wmf

shukaev175.wmf

shukaev176.wmf

f

0

0

shukaev177.wmf

shukaev178.wmf

63

 

Шаг 2. Полученное оптимальное решение задачи линейного программирования является дробным:

shukaev179.wmf и shukaev180.wmf

Переход на шаг 3.

Шаг 3. Учитывая, что shukaev181.wmf в качестве производящей строки можно выбрать любую из двух строк таблицы. Выберем строку соответствующей переменной x2:

shukaev182.wmf

или

shukaev183.wmf

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

shukaev184.wmf

и определяет дополнительную Si – строку в новой симплекс-таблице (табл. 4.4).

Таблица 4.4

БП

x1

x2

x3

x4

S1

Правая часть

x2

0

1

shukaev185.wmf

shukaev186.wmf

0

shukaev187.wmf

x1

1

0

shukaev188.wmf

shukaev189.wmf

0

shukaev190.wmf

S1

0

0

shukaev191.wmf

shukaev192.wmf

1

shukaev193.wmf

f

0

0

shukaev194.wmf

shukaev195.wmf

0

63

Шаг 4. С помощью алгоритма двойственного симплекс-метода осуществляется переход к следующей симплекс-таблице (табл. 4.5).

Таблица 4.5

БП

x1

x2

x3

x4

S1

Решение

x2

0

1

0

0

1

3

x1

1

0

0

shukaev196.wmf

shukaev197.wmf

shukaev198.wmf

x3

0

0

1

shukaev199.wmf

shukaev200.wmf

shukaev201.wmf

f

0

0

0

1

8

59

которая также не приводит (шаг 2) к оптимальному целочисленному решению. Поэтому на шаге 3 формируем новое отсекающее уравнение Гомори. В табл. 4.5 строке с базисной переменной x1 соответствует равенство

shukaev202.wmf

порождающее отсечение

shukaev204.wmf

Добавим это отсечение к последней таблице

Таблица 4.6

БП

x1

x2

x3

x4

S1

S2

Решение

x2

0

1

0

0

1

0

3

x1

1

0

0

shukaev205.wmf

shukaev206.wmf

0

shukaev207.wmf

x3

0

0

1

shukaev208.wmf

shukaev209.wmf

0

shukaev203.wmf

S2

0

0

0

shukaev210.wmf

shukaev211.wmf

1

shukaev212.wmf

f

0

0

0

1

8

0

59

И в результате повторного использования (шаг 4) двойственного симплекс-метода получим табл. 4.7, которая дает оптимальное целочисленное решение исходной задачи:

x1 = 4; x2 = 3; f = 55.

Таблица 4.7

БП

x1

x2

x3

x4

S1

S2

Решение

x2

0

2

0

0

1

0

3

x1

1

0

0

0

–1

1

4

x3

0

0

1

0

–4

1

1

x4

0

0

0

1

6

–7

4

f

0

0

0

1

2

7

55

Геометрическая интерпретация данного примера наглядно демонстрирует (рис. 4.2) как рассмотренные выше дополнительные отсечения исключают некоторые области многогранника допустимых решений [37]. Первое отсечение

shukaev213.wmf

записанное в переменных x1 и x2, после соответствующей замены принимает следующий вид

shukaev214.wmf

или S1 + x2 = 3.

pic_4_2.tif

Рис. 4.2. Области допустимых решений непрерывной и целочисленной задач

Это уравнение эквивалентно неравенству x2 ≤ 3.

Аналогичным образом второе отсечение

shukaev215.wmf

порождает эквивалентное ограничение в переменных x1 и x2:

x1 + x2 ≤ 7.

На рис. 4.2 показано, как введение этих двух ограничений позволяет получить новую экстремальную точку с координатами (4, 3), в которой достигается оптимум исходной целочисленной задачи.


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074