Целочисленное программирование
Раздел математического программирования, в котором на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений, называется дискретным программированием. При наличии условия целочисленности имеется в виду подраздел дискретного программирования – целочисленное программирование.Задача о назначении: имеется 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 целые числа,
Методы отсечений
Методы отсечений относятся к численным методам решения дискретных задач оптимизации (методам дискретного программирования). Они предназначены для решения целочисленных задач линейного программирования (ЛП).Идея методов отсечения состоит в следующем. Первоначально решается обычная ("непрерывная") задача ЛП, полученная из исходной задачи отбрасыванием требования целочисленности. Если полученное решение является целочисленным, то оно будет также решением исходной задачи. Если нет, то к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее двумя свойствами:
- полученное нецелочисленное решение ему не удовлетворяет;
- все целочисленные точки допустимого множества исходной задачи ему удовлетворяют.
Такое ограничение называется правильным отсечением.
Затем решается расширенная непрерывная задача ЛП, т.е. непрерывная задача с добавленным ограничением. Если полученное решение не является целочисленным, добавляется новое правильное отсечение и т.д. Процесс повторяется до тех пор, пока решение очередной расширенной непрерывной задачи ЛП не окажется целочисленным. Таким образом, решение целочисленной задачи ЛП сводится к решению некоторой последовательности обычных задач ЛП.
Геометрически добавление каждого такого линейного ограничения означает проведение гиперплоскости, отсекающей от многогранника допустимых решений очередной непрерывной задачи ЛП оптимальную точку с нецелочисленными координатами, но не затрагивающей ни одной из целочисленных точек этого многогранника. Поэтому методы, опирающиеся на эту идею, получили название методов отсечений.
Пример №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 - целые числа.
Далее задача решается методом ветвей и границ или методом отсечений.