Целочисленное программирование

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

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

Задача о назначении: имеется  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, которые удовлетворяют системе ограничений и при которых значение целевой функции наиболее близко к экстремальному нецелочисленному решению. Координаты такой вершины являются целочисленным решением.
Аналогично решается задача на минимум. Целочисленному минимуму целевой функции будет соответствовать координаты вершины целочисленной решетки, лежащей в области допустимых решений, наиболее близкой к началу координат в направлении вектора С.
Для решения задачи графическим методом используется сервис Графический метод. Целочисленное программирование.

Пример №1. Решить целочисленную задачу линейного программирования методом Гомори.
В цехе размещены 100 станков 1-го типа и 200 станков 2-го типа, на каждом из которых можно производить детали А1 и А2. Производительность станков в сутки, стоимость 1 детали каждого вида и минимальный суточный план их выпуска представлен в таблице.

Детали

Производительность, деталей, сутки Стоимость одной детали, руб. Минимальный суточный план
Тип 1 Тип 2
А1 20 15 6 1510
А2 35 30 4 4500

Найти количество станков каждого типа, который необходимо выделить для производства деталей Aj, j=1,2, с таким расчетом, чтобы стоимость продукции производимой в сутки, была максимальной.

Решение.
Составим экономико-математическую модель задачи.
x1 – количество станков типа №1, выделенным для производства деталей A1
x2 – количество станков типа №1, выделенным для производства деталей A2
x3 – количество станков типа №2, выделенным для производства деталей A1
x4 – количество станков типа №2, выделенным для производства деталей A2
x1, x2, x3, x4 ≥ 0, x1, x2, x3, x4 целые числа,

Ограничения по плану
20x1 + 15x3 ≥ 1510
35x2 + 30x4 ≥ 4500

Ограничения по количеству
x1 + x2 ≤ 100
x3 + x4≤ 200

Целевая функция
6(20x1+15x3) + 4(35x2+30x4) → max`

Получим следующую систему ограничений:
20x1 + 15x3 ≥ 1510
35x2 + 30x4 ≥ 4500
x1 + x2 ≤ 100
x3 + x4 ≤ 200
120x1 + 140x2 +90x3 + 120x4 → max
x1, x2, x3, x4 ≥ 0, x1, x2, x3, x4 целые числа,

Методы отсечений

Методы отсечений относятся к численным методам решения дискретных задач оптимизации (методам дискретного программирования). Они предназначены для решения целочисленных задач линейного программирования (ЛП).
Идея методов отсечения состоит в следующем. Первоначально решается обычная ("непрерывная") задача ЛП, полученная из исходной задачи отбрасыванием требования целочисленности. Если полученное решение является целочисленным, то оно будет также решением исходной задачи. Если нет, то к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее двумя свойствами:
  1. полученное нецелочисленное решение ему не удовлетворяет;
  2. все целочисленные точки допустимого множества исходной задачи ему удовлетворяют.

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

Пример №2. Мебельная фабрика выпускает диваны, кресла и стулья. Требуется определить, сколько можно изготовить диванов, подлокотников кресел и ножек стульев при известном удельном расходе ресурсов (табл.), чтобы доход был максимальным.

Показатели Изделия Наличие ресурса
спинка дивана подлокотники кресла ножки стула  
Цена, ден. ед. 20 6 8 -
Древесина 10 5 3 206
Трудозатраты 2 7 4 100
Спрос 10 8 12 -
  x1 x2 x3 bi

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

x1 - количество спинок дивана,
x2 - количество подлокотников (кратно двум),
x3 - количество ножек стула (кратно четырем),

Целевая функция
20x1+6*2x2+8*4x3 = max
Система ограничений по ресурсам
10x1+5*2x2+3*4x3≤206
2x1+7*2x2+4*4x3≤100

Система ограничений по спросу
x1≤10
2x2≤8
4x3≤12

x1,x2,x3≥0
x1,x2,x3 - целые

Задачу можно решить либо методом Гомори, либо методом ветвей и границ (см. соответствующие калькуляторы). Оптимальный целочисленный план можно записать так:
x1 = 10
x2 = 2
x3 = 3
F(X) = 12•2 + 20•10 + 32•3 = 320

С учетом комплектации получаем:
x1 = 10 - количество спинок дивана,
x2 = 2*2=4 - количество подлокотников (кратно двум),
x3 = 3*4 = 12 - количество ножек стула (кратно четырем),

Пример №2. В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19.3 м2 - площади. На приобретение оборудования предприятие может израсходовать 10 тыс. у.е., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1000 у.е., а II вида — 3000 у.е. Приобретение одного комплекта оборудования I вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида — на3 ед. Зная, что для установки одного комплекта оборудования1 вида требуется 2 м2 площади, а оборудования II вида — 1 м2 площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Решение находим с помощью калькулятора. Составим математическую модель задачи. Предположим, что предприятие приобретет х1 комплектов оборудования 1 вида и х2 комплектов оборудованияII вида. Тогда переменные х1 и х2 должны удовлетворять следующим неравенствам:
2x1 + x2 ≤ 19/3
x1 + 3x2 ≤ 10
Если предприятие приобретет указанное количество оборудования, то общее увеличение выпуска продукции составит:
F = 2x1 + 3x2
По своему экономическому содержанию переменные х1 и х2 могут принимать лишь целые неотрицательные значения, т. е,
x1,x2 ≥ 0
x1,x2 - целые числа.

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