In mbich/combinatorics: An implementation algorithm of discrete optimization

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

| № | Название мероприятия | Описание мероприятия | Затраты, тыс.руб.| Прибыль в год, тыс.руб. | | - |------------------|---------------------|----------:|----------:| | 1 | Станок - А | Покупка станка марки «А» | 350 | 117 | | 2 | Станок - Б | Покупка станка марки «Б» | 420 | 125 | | 3 | Аренда - А | Аренда станка марки «А» | 330 | 105 | | 4 | Оборудование к А | Покупка дополнительного оборудования к станку марки «А» | 77 | 83 | | 5 | Оборудование к Б | Покупка дополнительного оборудования к станку марки «Б» | 75 | 81 |

Из приведенных вариантов мероприятий проистекает следующий набор логических связей между мероприятиями:

• [1,2,3] - мероприятие № 1, мероприятие № 2, мероприятие № 3 взаимно друг друга исключают
• {1,2,3} - какое-либо из мероприятий № 1, № 2, или № 3 обязательно должно быть исполнено;
• (1)->(4), (3)->(4) - если будет исполнено мероприятие № 1 или мероприятие № 3 то может быть исполнено и мероприятие № 4;
• (2)->(5) - если будет исполнено мероприятие № 2 то может быть исполнено и мероприятие № 5.

Общая сумма средств на покупку станка и оборудования не должна быть более, чем 700 т.руб. Задача в том, чтобы получить максимальную прибыль.

Загрузим пакет combinatorics

library(combinatorics)

Создадим новую модель и заполним её данными. В качестве целевого параметра укажем - "Прибыль", в качестве ограниченного ресурса - "Затраты" и зададим лимит ограниченного ресурса в размере 700.

model <- combinatorics.model(name="Пример")
model <- combinatorics.add.parameter(model, "Затраты",  "тыс.руб.", 700)
model <- combinatorics.add.parameter(model, "Прибыль в год",  "тыс.руб.")
model <- combinatorics.set.target(model, "Прибыль в год", TRUE)
model <- combinatorics.add.arrangement(model, "Станок - А", c(350.0, 117.0))
model <- combinatorics.add.arrangement(model, "Станок - Б", c(420.0, 125.0))
model <- combinatorics.add.arrangement(model, "Аренда - А", c(330.0, 105.0))
model <- combinatorics.add.arrangement(model, "Оборудование к А", c(77,83))
model <- combinatorics.add.arrangement(model, "Оборудование к Б", c(75,81))
model <- combinatorics.add.logicconnection(model, "[1,2,3]")
model <- combinatorics.add.logicconnection(model, "{1,2,3}")
model <- combinatorics.add.logicconnection(model, "(1)->(4)")
model <- combinatorics.add.logicconnection(model, "(3)->(4)")
model <- combinatorics.add.logicconnection(model, "(2)->(5)")
model

Выполним расчёт на максимум

combinatorics.calculate(model)

Увеличим значение ограниченного ресурса "Затраты" до 900 тыс.руб. и повторно выполним расчёт на максимум

model <- combinatorics.set.limit(model, "Затраты", 900)
combinatorics.calculate(model)

Для просмотра названий в списке оптимальных мероприятий нужно добавить параметр nameArrangment

out <- combinatorics.calculate(model) 
print(out, nameArrangment=TRUE)

График зависимости Прибыль в год от Затраты и Прибыль в год/Затраты от Затраты

  plot(out, type="o")
  plot(out, type="o", TargetDivLimit=TRUE)

Предположим, что предприятие может использовать заёмные средства объемом 345 тыс. рублей, которые распределяются следующим образом:

| № | Название мероприятия | Заём, тыс.руб. | | - |------------------|----------:| | 1 | Станок - А | 150 | | 2 | Станок - Б | 310 | | 3 | Аренда - А | 65 | | 4 | Оборудование к А | 25 | | 5 | Оборудование к Б | 35 |

Добавим ограниченный ресурс и повторно выполним расчёт

   model <- combinatorics.set.limit(model, "Затраты", 700)
   model <- combinatorics.add.parameter(model, "Заём", "тыс.руб", 345, c(150, 310, 65, 25, 35))
   combinatorics.calculate(model)

Результатом решения задачи с несколькими ресурсными ограничениями является единственная оптимальная выборка.

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

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

mbich/combinatorics documentation built on May 22, 2019, 12:42 p.m.