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

К методам целочисленного программирования относят:
  1. метод отсечений;
  2. приближенные методы;
  3. комбинированные методы;
  4. метод ветвей и границ;
см. решение задач целочисленного программирования

Пример №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. все целочисленные точки допустимого множества исходной задачи ему удовлетворяют.

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

Метод ветвей и границ

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

Пример №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 - количество ножек стула (кратно четырем),

загрузка...