Перейти к содержанию

Примеры

Задача о ранце

В качестве первого примера рассмотрим решение задачи о рюкзаке. Пусть \(I\) - набор предметов, каждый из которых имеет вес \(w_i\) и предполагаемую ценность \(p_i\). Требуется выбрать подмножество с максимальной ценностью таким образом, чтобы сумма весов выбранных предметов была меньше или равна вместимости рюкзака \(c\).

Пусть переменными задачи являются \(x_i\), которые принимают значение 1, если выбран \(i\)-й элемент, или 0, если нет. Формулировка задачи математического программирования имеет вид:

\[ \begin{split}\textrm{Maximize: } & \\ & \sum_{i \in I} p_i \cdot x_i \\ \textrm{Subject to: } & \\ & \sum_{i \in I} w_i \cdot x_i \leq c \\ & x_i \in \{0,1\} \,\,\, \forall i \in I\end{split} \]
import arhiplexpy

v = [360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28,
87, 73, 78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276,
312]
w = [7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9, 0,
42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71,
3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13]
c = 850
I = range(len(w))

model = arhiplexpy.Model()
model.set_dbl_param("time_limit", 90)

x = [model.add_variable(0, 1, v[i], arhiplexpy.variable_type.binary, f'x_{i}') for i in I]

# Ограничение на суммарный вес предметов
model.add_constraint(sum([x[i] * w[i] for i in I]) <= c, 'total_weight')

# Направление оптимизации
model.set_objective_sense(arhiplexpy.objective_sense.maximize)

# Решение задачи
result = model.solve_remote("mapping.map")

# Выбранные предметы
selected = [i for i in I if result.get_variable_value(x[i]) >= 0.99]
print("Выбранные предметы: {}".format(selected))

В результате решения задачи имеем следующее решение:

Запуск ArhiCloud
Права на использование (c) 2024 Arhitex

Параметры запуска:
presolve : on
problem_type : max
time_limit : 90
abs_gap : 1e-06
gap : 0.0001
primal_feasibility_tolerance : 1e-06
mip_feasibility_tolerance : 1e-06
remote_timeout : 300
Отправка запроса на расчет . . . успешно
UID: 
Начало загрузки модели . . . успешно
Ожидание начала расчета .Запуск ArhiPlex 2.0.11.123984
Права на использование (c) 2024 Arhitex
Процессор Intel Xeon Processor (Icelake) [ AVX512, AVX2 ], физических ядер CPU: 26

Параметры запуска:
        time_limit =    90.00000000

Оригинальная задача MILP temp.mps содержит ограничений: 1, переменных: 50 (дробных: 0, бинарных: 50, целых: 0)

Отчет
  Статус               : Оптимально
  Первичная граница    : 7534
  Двойственная граница : 7534
  Отклонение           : 0%
  Статус решения       : Достижимо
  Время                : 0.0 с.
  Ноды(листья)         : 0
  LP итераций          : 8
Выбранные предметы: [0, 1, 3, 4, 6, 10, 11, 12, 14, 15, 16, 17, 18, 19, 21, 22, 24, 27, 28, 29, 30, 31, 32, 34, 38, 39, 41, 42, 44, 47, 48, 49]

Оптимизация инфраструктуры

Рассмотрим произвосдтво, которое отгружает свою продукцию с 5 цехов на 4 склада. Рассматривается возможность прекращения поставок с одного или или нескольких заводов и перераспределения потоков продукции в целях сокращения затрат. Требуется определить, какой завод (или несколько заводов) следует закрыть (и следует ли), чтобы минимизировать суммарные затраты, состоящие из постоянных затрат на обеспечение производства и затраты на транспортировку продукции.

Множество заводов - \(N\), складов - \(M\). Значения фиксированной стоимости обслуживания заводов описываются параметром \(fixed_i, i \in N\), спрос на складах на продукцию - параметром \(demand_j, j \in M\), стоимость транспортировки единицы продукции со склада \(i \in N\) на склад \(j \in M\) - значениями \(tc_{ij}, i \in N, j \in M\).

В качестве переменных определим значения факта работы завода (\(open_i \in \{0,1\}\)), а также объёма транспортируемой продукции с каждого из заводов на каждый из складов (\(vol_{ij} \ge 0\))

Целевая функция - суммарные затраты, состоящие из стоимости транспортировки всей продукции с заводов на склады, а также из фиксированных затрат на производство.

В задачу вводятся два ограничения:

  1. Суммарный объём поставленной на склад продукции не превышает производительности цеха, а если цех не работает, то равен нулю.
  2. Суммарный объём поставленной на склад продукции полностью удовлетворяет заданный спрос.

В результате математически задача описывается следующим образом:

\[ \begin{split}\textrm{Minimize: } & \\ & \sum_{i \in N} open_i \cdot fixed_i + \sum_{i \in N} \sum_{j \in M} tc_{ij} \cdot vol_{ij} \\ \textrm{Subject to: } & \\ & \forall i \in N: \sum_{j \in M} vol_{ij} \le open_i \cdot capacity_i \\ & \forall j \in M: \sum_{i \in N} vol_{ij} \ge demand_{j} \\ & open_i \in \{0,1\} \,\,\, \forall i \in N\ \\ & vol_{ij} \ge 0, \forall i \in N, j \in M \end{split} \]

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

import arhiplexpy as ap

# Спрос на продукцию с каждого из складов
demand = [15, 18, 14, 20]

# Вместимость хранения для каждого из цехов производства
capacity = [38, 22, 17, 19, 18]

# Фиксированные расходы каждого из производственных цехов
fixedCosts = [12000, 15000, 17000, 13000, 16000]

# Стоимость транспортировки с каждого склада на каждый из цехов
tc = [
    [4000, 2000, 3000, 2500, 4500],
    [2500, 2600, 3400, 3000, 4000],
    [1200, 1800, 2600, 4100, 3000],
    [2200, 2600, 3100, 3700, 3200],
]

# Списки идентификаторов
plants = range(len(capacity))
warehouses = range(len(demand))

# Создание экземпляра модели и установка параметров
m = ap.Model("facility")
m.set_dbl_param("time_limit", 120)

# Переменные решения open_i
open = {}

for plant in plants:
    open[plant] = m.add_variable(
        var_type=ap.variable_type.binary, 
        var_name=f'open_{plant}',
        obj_value=fixedCosts[plant]
    )


# Переменные решения vol_ij - количество перемещаемого продукта с цеха i на склад j
vol = {}

for w in warehouses:
    for p in plants:
        vol[w, p] = m.add_variable(
            var_type=ap.variable_type.continuous,
            var_name=f'vol_{w}_{p}',
            obj_value=tc[w][p]
        )

# Целевая функция - минимизация суммарных расходов
m.set_objective_sense(ap.objective_sense.minimize)

# Ограничения на производство. Если производство в цехе не осуществляется - 
# Суммарный объём доставки равен нулю

capacity_constraints = {}

for p in plants:
    capacity_constraints[p] = m.add_constraint(
        constr=sum(vol[w, p] for w in warehouses) <= capacity[p] * open[p], 
        constr_name=f'capacity_constraint_{p}'
    )

demand_constraints = {}

# Ограничения спроса - спрос должен быть удовлетворен

for w in warehouses:
    demand_constraints[w] = m.add_constraint(
        constr=sum(vol[w, p] for p in plants) == demand[w],
        constr_name=f'demand_constraint_{w}'
    )

# Решение задачи
result = m.solve_remote('mapping.txt')

for k, v in open.items():
  if result.get_variable_value(v) > 0.99:
      print(f'Цех {k} открыт')
      for k1, v1 in vol.items():
          if k1[1] == k and result.get_variable_value(v1) > 0.01:
              print(f"Транспортировка из цеха {k1[1]} на склад {k1[0]} объёма {result.get_variable_value(v1)}")
  else:
      print(f'Цех {k} закрыт')