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

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

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

Ограничения составляются по финальной симплекс-таблице, в которой получено оптимальное нецелочисленное решение. При этом на первоначальную систему ограничений накладывается новое ограничение по следующей формуле L1W1 L2W2 LnWn Bi, где Aij, если Aij0 и Wj может быть дробной, 1 BiAijBi-1, если Aij 0 и Wj может быть дробной, 2 Lj Aij, если AijBi и Wi должна быть целой, 3 Bi1-Aij1-Bi, если Aij Bi и Wi должна быть целой, 4 j1 n где Wn небазисная переменная Bi - базисная переменная, имеющая максимальную дробную часть дробная часть числа это разность между этим числом и максимальным целым числом, не превосходящим его Aij коэффициент, стоящий на пересечении строки i-ой базисной переменной и столбца j-ой небазисной переменной Далее полученное ограничение приводится к стандартному виду -L1W1 - L2W2 - -LnWn Sr -Bi где r номер итерации алгоритма. Здесь Sr неотрицательная остаточная переменная, не имеющая никакого содержательного смысла в оптимальном целочисленном решении эта переменная оказывается равной нулю. В нашем случае переменная, имеющая максимальную дробную часть это Х4 2,670,67, она должна быть целой, переменные Х7 и Х8 могут быть дробными, переменные Х1 и Х2 должны быть целыми, поэтому, согласно выше приведенной формуле, составим новое дополнительное ограничение.

Так как все коэффициенты на пересечениях базисной переменной Х4 и небазисных переменных Х1 , Х2 , Х7 , Х8 0 0,440, 0,110, 0,170, то коэффициенты при переменных Х1 и Х2 рассчитали по формуле 3 L10,440,44, L20,110,11, а коэффициенты при переменных Х7 и Х8 рассчитали по формуле 1 L30,17, L40,17. В4Х4 2,67 0,67. Ограничение будет иметь вид 0,44Х1 0,11Х2 0,17Х7 0,17Х8 0,67 Можно убедиться, что это ограничение сделало наше оптимальное решение недопустимым если подставить Х10, Х20, Х70, Х80 значения переменных, полученных в оптимальном нецелочисленном решении, то получим 00,67 неверно.

Приведя ограничение к стандартному виду, имеем -0,44Х1 - 0,11Х2 - 0,17Х7 - 0,17Х8 Х9 -0,67 Добавим к нашей финальной симлекс-таблице строку и столбец, соответствующие построенному ограничению и новой базисной переменной Х9 БПX1X2X3X4X5X6X7X8X9БРE1,671,6700002,52, 5040X31110001008X6-0,67-0,670001-0,50,50 0X40,440,1101000,170,1702,67Х50,220,5500 100,330,3305,33X9-0,44-0,110000-0,17-0,1 71-0,67Таблица 8. Симплекс-таблица 7. Как видно, полученная симплекс-таблица содержит недопустимое решение переменная Х9 имеет отрицательное значение.

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

Итак, переменная, исключаемая из базиса это X9, т.к. ее значение 0,67 - это максимальный по модулю отрицательный элемент столбца решений.

В базис включаем переменную X1, т.к. 1,67-0,443,8, 1,67-0,1115,2, 2,5-0,1714,7, 3,8 минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки. Ведущий элемент равен 0,44. Получим новую симплекс-таблицу БПX1X2X3X4X5X6X7X8X9БРE01,2500001,8751,8 753,7537,5X300,7510000,625-0,3752,256,5X 60-0,50001-0,250,75-1,51X40001000012Х500 ,500100,250,250,55X110,250,3750,375-2,25 1,5Таблица 9. Симплекс-таблица 8. Все значения базисных переменных стали неотрицательными, это означает остановку вычислительного процесса на данной итерации и анализ полученных результатов. Как видно из таблицы, в базис вошла новая переменная Х1, переменные Х3, Х4 и Х5 уменьшили свое значение, а переменная Х6 увеличилась.

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

Переменная, имеющая максимальную дробную часть это Х3 6,50,5 Х1 имеет такую же дробную часть, поэтому выбрали любую из них, например, Х3, она должна быть целой, переменные Х7 , Х8 и Х9 могут быть дробными, переменная Х2 должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение. Так как коэффициенты на пересечениях базисной переменной Х3 и небазисных переменных Х2 , Х7 , Х9 0 0,750, 0,6250, 2,250, то коэффициент при переменной Х2 рассчитаем по формуле 3 L10,750,75, коэффициенты при переменных Х7 и Х9 рассчитаем по формуле 1 L30,625, L42,25. Так как коэффициент на пересечении базисной переменной Х3 и небазисной переменной Х8 0, то коэффициент при переменной Х8 рассчитаем по формуле 2 L26,5-0,3756,5-10,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 Добавим это ограничение к нашей предыдущей симплекс-таблице БПX1X2X3X4X5X6X7X8X9X10БРE01,2500001,875 1,8753,75037,5Х300,7510000,625-0,3752,25 06,5X60-0,50001-0,250,75-1,501X400010000 102X510,500100,20,250,505Х110,250,3750,3 75-2,2501,5X100-0,250000-0,375-0,375-2,2 51-0,5Таблица 10. Симплекс-таблица 9. Переменная, исключаемая из базиса это X10, т.к. ее значение 0,5 - это максимальный по модулю отрицательный элемент столбца решений.

В базис включаем переменную X9, т.к. 3,75-2,251,67, 1,25-0,255, 1,875-0,3755, 1,67 минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки.

Ведущий элемент равен 2,25. Получим новую симплекс-таблицу БПX1X2X3X4X5X6X7X8X9X10БРE00,8300001,251 ,2501,6736,67Х300,510000,25-0,75016X60-0 ,330001010-0,671,33X400,1110100-0,17-0,1 700,441,78X500,44400100,170,1700,224,89Х 110,50,750,750-12X900,110,170,171-0,440, 22Таблица 11. Симплекс-таблица 10. Решение все еще не целочисленное, поэтому переходим к следующей итерации.

Переменная, имеющая максимальную дробную часть это Х5 4,890,89, она должна быть целой, переменные Х7 , Х8 и Х10 могут быть дробными, переменная Х2 должна быть целой, поэтому, согласно формуле, составим новое дополнительное ограничение.

Так как коэффициенты на пересечениях базисной переменной Х5 и небазисных переменных Х2, X7, X8, Х100 0,440, 0,170, 0,220, то коэффициент при переменной Х2 рассчитаем по формуле 3 L10,440,44, коэффициенты при переменных Х7, Х9 и Х10 рассчитаем по формуле 1 L20,17, L30,17, L40,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 Добавим это ограничение к нашей предыдущей симплекс-таблице БПX1X2X3X4X5X6X7X8X9X10Х11БРE00,8300001, 251,2501,67036,67Х300,510000,25-0,750106 X60-0,30001010-0,6701,33X400,110100-0,17 -0,1700,4401,78X500,4400100,170,1700,220 4,89Х110,50,750,750-102Х900,110,170,171- 0,4402X110-0,440000-0,17-0,170-0,221-0,8 9Таблица 12. Симплекс-таблица 11. Переменная, исключаемая из базиса это X11, т.к. ее значение 0,89 - это максимальный по модулю отрицательный элемент столбца решений.

В базис включаем переменную X2, т.к. 0,83-0,441,9, 1,25-0,177,4, 1,67-0,227,6, 1,9 минимальное по модулю отношение элемента Е-строки к отрицательным элементам ведущей строки.

Ведущий элемент равен 0,44. После пересчетов получим получим новую симплекс-таблицу БПX1X2X3X4X5X6X7X8X9X10Х11БРE0,9380,9401 ,251,8935Х30010000,063-0,93800,751,1255X 6010,1251,1250-0,5-0,752X4000100-0,125-0 ,12500,5-0,252X500001014Х110,5630,5630-1 ,251,1251Х90,1250,1251-0,50,250X2010,375 0,37500,5-2,252Таблица 13. Симплекс-таблица 12. Столбец решений не содержит отрицательных элементов, все переменные X1, X2, X3 , X4 , X5 , X6 приняли целочисленные значения, значит, оптимальное целочисленное решение найдено, оно равно X1,X2,X3,X4,X5,X61,2,5,2,4,2, целевая функция при этом принимает максимальное значение Е35.