Модели и инструментальные средства исследования операций
 Скачать 0.87 Mb.
|
|
Дисциплина МОДЕЛИ И ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ИССЛЕДОВАНИЯ ОПЕРАЦИЙ Кафедра математических методов в экономике ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Постановка задачи целочисленного программирования Полностью целочисленная ЗЛП: Постановка задачи целочисленного программирования Частично целочисленная ЗЛП: Задачи, сводящимся к ЗЦЛП • задача о ранце (задача о загрузке), • задача о назначениях, • задача коммивояжера, • задача оптимального раскроя, • задача о распределении капитальных вложений, • задача формирования портфеля инвестиционных проектов для предприятий. Методы решения задач целочисленного линейного программирования • методы отсечений; • комбинаторные методы; • комбинированные методы. Методы отсечений К этой группе методов относят методы отсекающих плоскостей Гомори, которые разработаны для решения как частично, так и полностью целочисленных задач. Идея методов заключается в следующем. Сначала решается задача ЦЛП как задача ЛП без учёта целочисленности, а затем вводятся дополнительные ограничения, которые отсекают от ОДР части, не содержащие целочисленных значений переменных. Комбинаторные методы К этой группе методов относят метод ветвей и границ. Методом ветвей и границ удобно решать такие ЗЦЛП, в которых число неизвестных невелико либо требования целочисленности относятся не ко всем неизвестным. Суть метода состоит в том, что для тех неизвестных, к которым относится требование целочисленности, нужно определить границы, в которых могут находиться значения этих неизвестных. Затем решаются соответствующие задачи линейного программирования. Комбинированные методы Используются только тогда, когда целочисленные переменные являются булевыми. К этой группе методов относят метод частичного перебора. Метод Гомори для полностью целочисленных задач линейного программирования Напоминалка Целой частью числа a называется наибольшее целое число, не превосходящее а. a b a b a a a Алгоритм метода Гомори для полностью целочисленных задач 1. Решается задача линейного программирования без учёта целочисленности. 2. Среди дробных чисел выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение. 3. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной. 4. Полученная задача решается двойственным симплексным методом. Если в процессе решения в симплексной таблице появится уравнение с нецелым свободным членов b i и целыми коэффициентами a ij , то данная задача не имеет целочисленного оптимального решения. Как составлять дополнительное ограничение (п.2 алгоритма) См. следующие слайды. Если найдено нецелочисленное решение, то вводят дополнительные ограничения, которые 1) отсекают уже найденное нецелочисленное решение и 2) не отсекают все целочисленные решения. 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 n n n n m m mn n m a x a x a x b a x a x a x b a x a x a x b 1 1 2 2 ( ) max n n L x c x c x c x Пусть найдено решение * * * * 1 1 1 1 1 1 1 2 1 2 1 * * * * 2 2 2 1 2 1 2 2 2 2 2 * * * * , 1 , 1 , 2 , 2 m m m m n n m m m m n n m m m m m m m m m m mn n x b a x a x a x x b a x a x a x x b a x a x a x Если все , то решение найдено, если не целые решения, то для решения у которого дробная часть самая большая введем дополнительные ограничения. Пусть это k-я строка в системе т.е. (**) Введем следующее ограничение: * * * 1 2 , ,....., m b b b * * * , 1 1 , k k k m m k n n x b a x a x * * * * , 1 1 , 2 2 , 0 k k m m k m m k n n b a x a x a x Сокращённо Данное ограничение удовлетворяет всем правилам правильного отсечения. (*) * * 1 0 n k kj j j m b a x Как неравенство преобразуется в уравнение (п.3 алгоритма) Следует преобразовать полученное неравенство в уравнение путём введения дополнительной переменной : 1 0 n x * * 1 1 n k kj j n j m b a x x Пример 1 Решите методом Гомори следующую ЗЦЛП. Решение. 1 2 ( ) 3 2 max L x x x 1 2 1 2 1 2 0 2 6, 4 5, , x x x x x x 1 2 3 4 ( ) 3 2 0 0 max L x x x x x 1 2 3 1 2 4 1 2 3 4 0 2 6, 4 5, , , , x x x x x x x x x x Из табл. 3 находим оптимальный план X=(19/7;4/7;0;0). Этот оптимальный план не удовлетворяет условию целочисленности нужно составить дополнительное ограничение. Дробной частью координаты x₁=19/7 является число 19/7-[19/7]=19/7-2=5/7, дробной частью координаты x₂=4/7 является число 4/7-[4/7]=4/7-0=4/7. Сл-но, max({x₁}; {x₂})={x₁}. Первое уравнение на основании таблицы запишется так: Определив дробные части коэффициентов при неизвестных и свободных членов, получаем следующее дополнительное ограничение: или, введя добавочную переменную , 1 2 3 4 19 4 1 0 7 7 7 x x x x 3 4 5 4 6 0, 7 7 7 x x 5 0 x 3 4 5 5 4 6 7 7 7 x x x Получаем новую строку в симплексной таблице, полученной из табл. 3 и добавления коэффициентов из только что полученного уравнения: Совершаем шаг симплексного метода и получаем таблицу. Получили оптимальный план X=(17/6;1/3;0;5/6;0). Он также не удовлетворяет условию целочисленности нужно снова составить дополнительное ограничение. {x₁}= 17/6-[17/6]=17/6-2=5/6; {x₂}= 1/3-[1/3]=1/3-0=1/3; {x 4 }= 5/6-[5/6]=5/6-0=5/6. Max({x₁}; {x₂}; {x 4 })=5/6. Сл-но, можно использовать первое или третье уравнение. Используем 3-е. Введя добавочную переменную , получим дополнительное ограничение 6 0 x 3 5 6 5 2 5 6 3 6 x x x Составляем таблицы Оптимальный план X=(3;0;0;2;1;0). Он удовлетворяет условию целочисленности. Координаты x 5 и x 6 можно не учитывать, так как начальные условия задачи содержит лишь четыре неизвестные. Поэтому окончательный оптимальный план запишется так: X=(3;0;0;2), а максимум функции цели равен 9. Графический метод решения ЗЦЛП Пример 2. Найти максимальное значение целевой функции Z=2x 1 +4x 2 заданных ограничениях: Решение примера 2 Построим ОДР без условия целочисленности переменных. Условию целочисленности удовлетворяют лишь 12 точек, отмеченных на рисунке. Заменим многоугольник ОАВС многоугольником OKEMNF, содержащим все допустимые точки с целочисленными координатами. Для определения максимального значения целевой функции на многоугольнике OKEMNF построим вектор градиент с(2;4) и прямую 2x 1 +4x 2 =const . Построенную прямую передвигаем в направлении вектора градиента до тех пор, пока она не пройдет через последнюю общую точку с этим многоугольником. Координаты полученной точки Е(1;3) и являются оптимальным решением задачи, а значение целевой функции в ней Zmax=Z(1;3)=14 является максимальным. |