Алгоритм метода Гомори


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

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

3. Вводим дополнительную неотрицательную целую переменную и получаем новое уравнение

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

Замечание. - дробная часть числа .

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

Пример. Решить задачу в целых числах.

Приведем задачу к каноническому виду:

Построим симплекс-таблицу

 

Базис Свободный Переменные Оценочные
  член           отношения
   
17/2
О -2 -3  

 

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

Базис Свободный Переменные Оценочные
  член           отношения
     
-5 20/3
-4 2/3
-2  

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

Базис Свободный Переменные Оценочные
  член   отношения
     
-1 -1  
2/3 1/3 -4/3  
 
76/3 2/3 1/3  

 

Полученное решение оптимально, но не является цело

численным .

Построим правильное отсечение из условия:

Найдем дробные части от чисел стоящих в фигурных скобках:

Получим неравенство

Введем дополнительную целую переменную

Полученное уравнение необходимо добавить в систему ограничений и решить

симплекс-методом новую задачу.

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

 

Базис Свободный Переменные Оценочные
  член             отношения
     
-1 -1
2/3 1/3 -4/3
2/3 1/3 2/3 -1
76/3 2/3 1/3  

 

Полученное базисное решение не допустимо

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

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

 

Базис Свободный Переменные Оценочные
  член             отношения
     
-1/2 -2/3  
-2  
-1/2 3/2  
1/2 3/2  
1/2 1/2  

 

Полученное решение является оптимальным. Найденный план целочисленный

 



Дата добавления: 2017-04-05; просмотров: 1845;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.011 сек.