Метод Гомори. Целочисленное решение

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

Задача целочисленного программирования формируется так же, как и задача линейного программирования, но включает дополнительное требование, состоящее в том, что значения переменных должны быть целыми неотрицательными числами, например, Метод Гомори. Целочисленное решение - student2.ru станков, Метод Гомори. Целочисленное решение - student2.ru самолетов, Метод Гомори. Целочисленное решение - student2.ru человек.

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

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

а) оно должно быть линейным;

б) должно отсекать найденный оптимальный нецелочисленный план;

в) не должно отсекать ни одного целочисленного плана.

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

Алгоритм Гомори, основанный на симплексном методе, имеет простой способ построения правильного отсечения и содержит следующие этапы.

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

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

Дополнительное ограничение выписывается в том случае, когда значение базисной переменной в оптимальном плане Метод Гомори. Целочисленное решение - student2.ru дробное число. Тогда некоторые элементы Метод Гомори. Целочисленное решение - student2.ru в Метод Гомори. Целочисленное решение - student2.ru ой строке симплексной таблицы также дробные числа. Обозначим через Метод Гомори. Целочисленное решение - student2.ru и Метод Гомори. Целочисленное решение - student2.ru целые части чисел Метод Гомори. Целочисленное решение - student2.ru и Метод Гомори. Целочисленное решение - student2.ru , т.е. наибольшие целые числа, не превышающие Метод Гомори. Целочисленное решение - student2.ru и Метод Гомори. Целочисленное решение - student2.ru . Величины дробных частей Метод Гомори. Целочисленное решение - student2.ru и Метод Гомори. Целочисленное решение - student2.ru определяются как разности следующим образом: Метод Гомори. Целочисленное решение - student2.ru и являются положительными числами.

Тогда неравенство Метод Гомори. Целочисленное решение - student2.ru , сформированное по Метод Гомори. Целочисленное решение - student2.ru ой строке симплексной таблицы, обладает всеми свойствами правильного отсечения.

3. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной и включается в оптимальную симплексную таблицу.

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

Если в процессе решения в симплексной таблице появится уравнение с нецелым свободным членом Метод Гомори. Целочисленное решение - student2.ru и целыми коэффициентами Метод Гомори. Целочисленное решение - student2.ru , то данная задача не имеет целочисленного оптимального решения.

Пример.Маркетинговые исследования указали на необходимость освоения выпуска новой продукции. Поэтому на предприятии решено установить новое технологическое оборудование на освободившейся площади Метод Гомори. Целочисленное решение - student2.ru . На приобретение оборудования двух видов выделено 6 млн. руб. Комплект первого вида оборудования стоимостью 1 млн. руб. устанавливается на площади Метод Гомори. Целочисленное решение - student2.ru и позволяет увеличить доход предприятия на 8 млн. руб. Комплект второго вида оборудования занимает площадь Метод Гомори. Целочисленное решение - student2.ru и обеспечивает увеличение дохода предприятия на 5 млн. руб. Определить, какое количество технологического оборудования каждого вида следует закупить, чтобы обеспечить максимальное увеличение дохода предприятия от продажи продукции, выпускаемой новым оборудованием.

Решение. Обозначим через Метод Гомори. Целочисленное решение - student2.ru и Метод Гомори. Целочисленное решение - student2.ru количество комплектов технологического оборудования соответственно первого и второго видов, через Метод Гомори. Целочисленное решение - student2.ru доход предприятия от продажи продукции, изготовленной новым оборудованием. Тогда математическая модель задачи имеет вид:

Метод Гомори. Целочисленное решение - student2.ru ,

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

Метод Гомори. Целочисленное решение - student2.ru

Приведем задачу к каноническому виду, для чего введем дополнительные неотрицательные переменные Метод Гомори. Целочисленное решение - student2.ru и решим ее симплексным методом.



Метод Гомори. Целочисленное решение - student2.ru Б Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru -8 -5 -32 -30
Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru  
Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru  
Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru

На третьей итерации получен оптимальный план задачи без учета условия целочисленности Метод Гомори. Целочисленное решение - student2.ru , так как Метод Гомори. Целочисленное решение - student2.ru .

По первому уравнению с переменной Метод Гомори. Целочисленное решение - student2.ru , получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью Метод Гомори. Целочисленное решение - student2.ru , составляем дополнительное ограничение:

Метод Гомори. Целочисленное решение - student2.ru

Метод Гомори. Целочисленное решение - student2.ru

Метод Гомори. Целочисленное решение - student2.ru

Метод Гомори. Целочисленное решение - student2.ru

Метод Гомори. Целочисленное решение - student2.ru

Метод Гомори. Целочисленное решение - student2.ru .

Дополнительное ограничение имеет вид:

Метод Гомори. Целочисленное решение - student2.ru .

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

Метод Гомори. Целочисленное решение - student2.ru

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

Тогда получим:

Метод Гомори. Целочисленное решение - student2.ru Б Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru Метод Гомори. Целочисленное решение - student2.ru
Метод Гомори. Целочисленное решение - student2.ru -1
Метод Гомори. Целочисленное решение - student2.ru -1
Метод Гомори. Целочисленное решение - student2.ru -3
Метод Гомори. Целочисленное решение - student2.ru

Применяя алгоритм двойственного симплексного метода (ключевой строкой является третья с отрицательным значением базисной переменной, а ключевым столбцом – столбец Метод Гомори. Целочисленное решение - student2.ru с наименьшим по абсолютной величине значением частного от деления коэффициентов индексной строки на отрицательные коэффициенты ключевой строки), проводим одну итерацию, в результате которой получим оптимальное целочисленное решение:

Метод Гомори. Целочисленное решение - student2.ru .

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

Следует заметить, что Метод Гомори. Целочисленное решение - student2.ru площади останется неиспользованным, а деньги, выделенные на приобретение оборудования, будут полностью израсходованы.

Наши рекомендации