Целочисленные модели исследования операций

Для изучения данного раздела дисциплины необходимо умение решать задачи графическим и симплекс-методом.

Изучив данную тему, студент должен:

– знать методы решения ЗЦЛП;

- уметь решать ЗЦЛП методом ветвей и границ;

- уметь решать задачу коммивояжера

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

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

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

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

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

Методы решения задач целочисленного линейного (ЗЦЛП) программирования можно классифицировать как (1) методы отсечений и (2) комбинаторные методы.

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

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

5.1. Метод ветвей и границ решения целочисленных задач линейного
программирования (ЦЗЛП)

Пример 5.1:

F() = 3x₁ + 2x₂ ® max

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

x₁ + x₂ £ 3,5;

x₁ £ 2;

x₂ £ 2;

x₁, х₂ ³ 0, целые.

Начальный шаг решения этой задачи состоит в нахождении решения задачи ЛП, получаемой при отбрасывании условия целочисленности х₁ и х₂. Обозначим эту задачу через ЛП-1. На рис. 5.1 представлено графическое решение задачи ЛП-1.

Рис. 5.1. Решение задачи ЛП-1

Оптимальное решение задачи ЛП-1 имеет вид: х₁ = 2, х₂ = 1,5, оптимальное значение целевой функции F() = 9. Поскольку х₂ принимает дробное значение, найденное решение не может быть оптимальным решением исходной задачи ЦЛП. Но найденное значение F() представляет собой верхнюю границу истинного оптимального целочисленного значения, поскольку при выполнении требования целочисленности х₂ значение F() может лишь уменьшиться.

Следующий шаг метода ветвей и границ состоит в просмотре целочисленных значений х₂, больших или меньших 1,5. Это делается путем добавления к задаче ЛП-1 либо ограничения x₂ £ 1, х₂ ³ 2. Таким образом, из задачи ЛП-1 получаются две задачи следующего вида (ЛП-2 и ЛП-3):

ЛП-2 ЛП-3

F() = 3*x₁ + 2*x₂ ® max F() = 3*x₁ + 2*x₂ ® max

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

x₁ + x₂ £ 3,5 x₁ + x₂ £ 3,5

x₁ £ 2 x₁ £ 2

x₂ £ 2 x₂ £ 2

x₂ £ 1 х₂ ³ 2

x₁, х₂ ³ 0. x₁, х₂ ³ 0.

На рис. 5.2 и 5.3 изображены допустимые области задач ЛП-2 и ЛП-3 соответственно. (Заметим, что допустимая область задачи ЛП-3 представляет собой просто отрезок АВ).

Рис. 5.2. Решение задачи ЛП-2

Рис. 5.3. Решение задачи ЛП-3

Оптимальное решение задачи ЛП-2 (рис. 5.2) – точка х₁ = 2, х₂ = 1, где F() = 8. Таким образом, получено допустимое (целочисленное) решение исходной задачи ЦЛП. Зафиксируем это целочисленное решение. Пусть Z ₀ = 8. Даже если ЛП-2 имеет другие целочисленные решения, значение целевой функции в них не может быть больше 8. Таким образом, значение Z ₀ = 8 представляет собой текущую нижнюю границу максимального значения F . Поскольку ранее была получена верхняя граница, равная 9, нельзя утверждать, что решение ЛП-2 оптимально для исходной задачи. Следовательно, необходимо также рассмотреть задачу ЛП-3.

Оптимальное решение задачи ЛП-3 (рис. 5.3): х₁ = 1,5; х₂ = 2; F() = 8,5. Для исходной задачи ЦЛП это решение недопустимо, поскольку х₁ принимает дробное значение. Оптимальное значение F() = 8,5 задачи ЛП-3 больше ранее полученной нижней границы = 8, поэтому необходимо проверить существование в допустимой области задачи ЛП-3 целочисленного решения, дающего значение целевой функции F > 8. Для этого рассматриваются задачи ЛП-4 и ЛП-5, получающиеся при добавлении к ЛП-3 ограничений х₁ £ 1 и х₁ ³ 2 соответственно.

ЛП-4 ЛП-5

F() = 3*x₁ + 2*x₂ ® max F() = 3*x₁ + 2*x₂ ® max

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

x₁ + x₂ £ 3,5 x₁ + x₂ £ 3,5

x₁ £ 2 x₁ £ 2

x₂ £ 2 x₂ £ 2

х₂ ³ 2 х₂ ³ 2

x₁ £ 1 х₁ ³ 2

x₁, х₂ ³ 0. x₁, х₂ ³ 0.

Допустимая область задачи ЛП-4 состоит из отрезка ДЕ, показанного на рис. 5.4; задача ЛП-5 не имеет допустимых решений.

Рис. 5.4. Решение задачи ЛП-4

Оптимальное решение задачи ЛП-4 имеет вид: х₁ = 1, х₂ = 2; F() = 7, следовательно, для любого целочисленного решения в допустимой области ЛП-3 значение целевой функции не превосходит 7. Так как F() меньше ранее полученной нижней границы, то = 8 не изменяется. Таким образом, точка х₁ = 2, х₂ = 1 (решение задачи ЛП-2) представляет собой оптимальное целочисленное решение исходной задачи; оптимальное значение целевой функции в этой точке равно = 8.

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

ЛП-1 = (2; 1,5) F() = 9

x ₂ £ 1 x ₂ ³ 2

= (2; 1) ЛП-2 ЛП-3 = (1,5; 2)

F() = 8 = F() = 8,5 >

x ₁ £ 1 x ₁ ³ 2

= (1; 2) ЛП-4 ЛП-5 P = Æ

F() = 7 <

Рис. 5.5

Каждая вершина представляет собой либо начальную, либо конечную точку некоторой ветви. Вершина 1 на рис. 5.5 соответствует задаче ЛП-1, получаемой при отбрасывании требования целочисленности переменных. Ветвление в вершине 1, определяемое целочисленной переменной х₂ с помощью ограничения х₂ £ 1, приводит к вершине 2 (ЛП-2). Поскольку задача ЛП-2 имеет оптимальное целочисленное решение, нет необходимости производить ветвление в вершине 2. В этом случае говорят, что рассматриваемая вершина прозондирована. Ветвление в вершине 1 по ограничению х₂ ³ 2 дает ЛП-3 (вершина 3). Поскольку оптимальное решение ЛП-3 является дробным и F() > , происходит дальнейшее ветвление в вершине 3 по целочисленной переменной х₁. Таким образом, появляются вершины 4 и 5. Эти вершины являются прозондированными, поскольку ЛП-4 обладает целочисленным решением, а задача ЛП-5 не имеет допустимых решений. Наилучшее решение из полученных в прозондированных вершинах представляет собой оптимальное решение исходной задачи.

Дата добавления: 2014-12-29