Метод Гомори для частично целочисленных задач

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

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

L1*W1 + L2*W2 + … +Ln*Wn ≥ {Bi}, где

Aij, если Aij≥0 и Wj может быть дробной, (1)

({Bi}*Aij)/({Bi}-1), если Aij<0 и Wj может быть дробной, (2)

Lj = {Aij}, если {Aij}£{Bi} и Wi должна быть целой, (3)

{Bi}*(1-{Aij})/(1-{Bi}), если {Aij}>{Bi} и Wi должна быть целой, (4)

j=1,…,n

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

Bi - базисная переменная, имеющая максимальную дробную часть (дробная часть числа – это разность между этим числом и максимальным целым числом, не превосходящим его);

Aij – коэффициент, стоящий на пересечении строки i-ой базисной переменной и столбца j-ой небазисной переменной;

Далее полученное ограничение приводится к стандартному виду:

-L1*W1 - L2*W2 - … -Ln*Wn + Sr = -{Bi}

где r – номер итерации алгоритма.

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

В нашем случае переменная, имеющая максимальную дробную часть – это Х4 ({2,67}=0,67), она должна быть целой, переменные Х7 и Х8 могут быть дробными, переменные Х1 и Х2 должны быть целыми, поэтому, согласно выше приведенной формуле, составим новое дополнительное ограничение. Так как все коэффициенты на пересечениях базисной переменной Х4 и небазисных переменных Х1, Х2, Х7, Х8 ≥ 0 (0,44≥0, 0,11≥0, 0,17≥0), токоэффициенты при переменных Х1 и Х2 рассчитали по формуле (3): L1={0,44}=0,44, L2={0,11}=0,11, а коэффициенты при переменных Х7 и Х8 рассчитали по формуле (1): L3=0,17, L4=0,17. {В4}={Х4} = {2,67} = 0,67. Ограничение будет иметь вид:

0,44 Х1 + 0,11 Х2 + 0,17 Х7 + 0,17 Х8 ≥ 0,67

Можно убедиться, что это ограничение сделало наше оптимальное решение недопустимым (если подставить Х1=0, Х2=0, Х7=0, Х8=0, - значения переменных, полученных в оптимальном нецелочисленном решении, то получим 0≥0,67 – неверно).

Приведя ограничение к стандартному виду, имеем:

-0,44 Х1 - 0,11 Х2 - 0,17 Х7 - 0,17 Х8 + Х9 = - 0,67

Добавим к нашей финальной симлекс-таблице строку и столбец, соответствующие построенному ограничению и новой базисной переменной Х9:

Таблица 8. Симплекс-таблица №7.

Как видно, полученная симплекс-таблица содержит недопустимое решение (переменная Х9 имеет отрицательное значение). Произведем дальнейший пересчет таблицы, причем ведущую строку определяем максимальным по модулю отрицательным элементом столбца решений, а ведущий столбец – минимальным по модулю отношением элемента Е- строки к отрицательным элементам ведущей строки. Пересчет симплекс-таблицы осуществляется на основе стандартных процедур симплекс-метода.

Итак, переменная, исключаемая из базиса – это X9, т.к. ее значение –0,67 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X1, т.к. |1,67/(-0,44)|=3,8, |1,67/(-0,11)|=15,2, |2,5/(-0,17)|=14,7, 3,8 – минимальное по модулю отношение элемента Е- строки к отрицательным элементам ведущей строки. Ведущий элемент равен –0,44. Получим новую симплекс-таблицу:

Таблица 9. Симплекс-таблица №8.

Все значения базисных переменных стали неотрицательными, это означает остановку вычислительного процесса на данной итерации и анализ полученных результатов. Как видно из таблицы, в базис вошла новая переменная Х1, переменные Х3, Х4 и Х5 уменьшили свое значение, а переменная Х6 увеличилась. Значение целевой функции уменьшилось и стало равно 37,5, что объясняется тем, что оптимальное нецелочисленное решение было отсечено нашим дополнительным ограничением, и для поиска оптимального целочисленного решения мы ушли вглубь области допустимых решений, где значение целевой функции меньше оптимального. Наше решение все еще нецелочисленное, поэтому составим новое ограничение.

Переменная, имеющая максимальную дробную часть – это Х3 ({6,5}=0,5) (Х1 имеет такую же дробную часть, поэтому выбрали любую из них, например, Х3), она должна быть целой, переменные Х7, Х8 и Х9 могут быть дробными, переменная Х2 должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение. Так как коэффициенты на пересечениях базисной переменной Х3 и небазисных переменных Х2, Х7, Х9 ≥ 0 (0,75≥0, 0,625≥0, 2,25≥0), токоэффициент при переменной Х2 рассчитаем по формуле (3): L1={0,75}=0,75, коэффициенты при переменных Х7 и Х9 рассчитаем по формуле (1): L3=0,625, L4=2,25. Так как коэффициент на пересечении базисной переменной Х3 и небазисной переменной Х8<0, то коэффициент при переменной Х8 рассчитаем по формуле (2): L2=({6,5}*(-0,375))/({6,5}-1)=0,375. {В3}={Х3} = {6,5} = 0,5. Ограничение будет иметь вид:

0,25 Х2 + 0,625 Х7 + 0,375 Х8 + 2,25 Х9 ≥ 0,5

Или, после приведения к стандартному виду, получим:

-0,25 Х2 – 0,625 Х7 – 0,375 Х8 – 2,25 Х9 + Х10 = -0,5

Добавим это ограничение к нашей предыдущей симплекс-таблице:

Таблица 10. Симплекс-таблица №9.

Переменная, исключаемая из базиса – это X10, т.к. ее значение –0,5 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X9, т.к. |3,75/(-2,25)|=1,67, |1,25/(-0,25)|=5, |1,875/(-0,375)|=5, 1,67 – минимальное по модулю отношение элемента Е- строки к отрицательным элементам ведущей строки. Ведущий элемент равен –2,25. Получим новую симплекс-таблицу:

Таблица 11. Симплекс-таблица №10.

Решение все еще не целочисленное, поэтому переходим к следующей итерации. Переменная, имеющая максимальную дробную часть – это Х5 ({4,89}=0,89), она должна быть целой, переменные Х7, Х8 и Х10 могут быть дробными, переменная Х2 должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение. Так как коэффициенты на пересечениях базисной переменной Х5 и небазисных переменных Х2, X7, X8, Х10≥0 (0,44≥0, 0,17≥0, 0,22≥0), токоэффициент при переменной Х2 рассчитаем по формуле (3): L1={0,44}=0,44, коэффициенты при переменных Х7, Х9 и Х10 рассчитаем по формуле (1): L2=0,17, L3=0,17, L4=0,22. {В5}={Х5} = {4,89} = 0,89. Ограничение будет иметь вид:

0,44 Х2 + 0,17 Х7 + 0,17 Х8 + 0,22 Х10 ≥ 0,89

Или, после приведения к стандартному виду, получим:

-0,44 Х2 – 0,17 Х7 – 0,17 Х8 – 0,22 Х10 + Х11 = -0,89

Добавим это ограничение к нашей предыдущей симплекс-таблице:

Таблица 12. Симплекс-таблица №11.

Переменная, исключаемая из базиса – это X11, т.к. ее значение –0,89 - это максимальный по модулю отрицательный элемент столбца решений. В базис включаем переменную X2, т.к. |0,83/(-0,44)|=1,9, |1,25/(-0,17)|=7,4, |1,67/(-0,22)|=7,6, 1,9 – минимальное по модулю отношение элемента Е- строки к отрицательным элементам ведущей строки. Ведущий элемент равен –0,44. После пересчетов получим получим новую симплекс-таблицу:

Таблица 13. Симплекс-таблица №12.

Столбец решений не содержит отрицательных элементов, все переменные X1, X2, X3, X4, X5, X6 приняли целочисленные значения, значит, оптимальное целочисленное решение найдено, оно равно: (X1,X2,X3,X4,X5,X6)=(1,2,5,2,4,2), целевая функция при этом принимает максимальное значение: Е=35.