Целочисленное программирование. Решение задач

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

Задача о рюкзаке

Задача о назначении: имеется  n исполнителей, которые могут выполнять n различных работ. Известна полезность cij, связанная с выполнением i-м исполнителем j-ой работы j=1..n, i=1..n. Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплен только один исполнитель.
Математическая модель задачи имеет вид:
F=∑∑cijxij → max
Каждый исполнитель назначается только на одну работу: ∑xij = 1
На каждую работу назначается только один исполнитель: ∑xij = 1
Условие неотрицательности и целочисленности:
xij ≥ 0, xij = {0,1}, i=1..n, j=1..n
Для решения задачи о назначении используется сервис Задача о назначении.

Задача коммивояжера: коммивояжер должен посетить один и только один раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарное пройденное расстояние.
F=∑∑cijxij → min
∑xij = 1
∑xij = 1
Условие неотрицательности и целочисленности:
xij ≥ 0, xij = {0,1}, i=1..n, j=1..n
Добавляется условие прохождения маршрута через все города, т.е. так называемое условие цикличности. Иначе, маршрут должен представлять собой замкнутую ломаную, без пересечений в городах-точках.
Для решения задачи коммивояжёра используется сервис Задача коммивояжёра.

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

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

Графический метод
При наличии в задаче линейного программирования двух переменных, задача может быть решена графическим методом.
В системе координат X10X2 находят область допустимых решений, строят вектор С и линию уровня. перемещая линию уровня по направлению С для задач на максимум, определяют наиболее удаленную от начала координат точку и ее координаты.
В случае, когда координаты этой точки нецелочисленные, в области допустимых решений строят целочисленную решетку и находят на ней такие целые числа x1 и x2, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному нецелочисленному решению. Координаты такой вершины являются целочисленным решением.
Аналогично решается задача на минимум. Целочисленному минимуму целевой функции будет соответствовать координаты вершины целочисленной решетки, лежащей в области допустимых решений, наиболее близкой к началу координат в направлении вектора С.
Для решения задачи графическим методом используется сервис Графический метод. Целочисленное программирование.

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

  1. либо меньше или равно ближайшему меньшему целому числу Ki*.
  2. либо больше или равно ближайшему большему целому числу Ki*.

Определяя эти числа симплексным методом решения двух задач линейного программирования:
1) F=∑cjxj → max
∑aijxj ≤ bi
xi ≤Ki*
xj≥0, xj – целые, j=1..n

2) F=∑cjxj → max
∑aijxj ≤ bi
xi ≥Ki*+1
xj≥0, xj – целые, j=1..n
Возможны четыре случая при решении этой пары задач:
1) Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции и дают решение исходной задачи.
2) Одна из задач неразрешима, а другая имеет нецелочисленный оптимальный план. Тогда рассматривается вторая задача и в ее оптимальном плане выбирается одна из компонент, значение которой равно дробному числу и строятся две новые задача, аналогично предыдущим.
3) Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи  есть дробные числа. Тогда вычисляем значение целевой функции от планов и сравниваем их между собой. Если на целочисленном оптимальном план значение целевой функции больше или равно ее значению в плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и дает искомое решение.
4)Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда рассматриваем ту из задач, для которой значение целевой функции является наибольшим. Строятся новые две задачи.

Алгоритм метода ветвей и границ

  1. Находится решение задачи линейного программирования без учета целочисленности
  2. Составляется дополнительные ограничения на дробную компоненту плана.
  3. Находится решение двух задач с ограничениями на компоненту.
  4. Строятся в случае необходимости дополнительные ограничения, согласно возможным четырем случаям. Определяется оптимальный целочисленный план, либо устанавливается неразрешимость задачи.

Для решения задачи целочисленного программирования методом ветвей и границ используется сервис Метод ветвей и границ.
загрузка...