Настройка линейной программы для задачи распределения / назначения

Question

У меня есть некоторые проблемы, связанные с линейной программой, которую я уже решил и использую Excel, но теперь я хочу сделать это в r / python, потому что я уже достиг превосходств и пределов решателей. Поэтому я прошу помощи по этой конкретной теме.

Я пробовал ее с помощью пакета lPsovle, также изменив функцию lp.assign, но не могу найти решение.

Проблема в том, чтоследующим образом:

Допустим, я поставляю товарный товар.

У меня есть различные склады, которые обслуживают разные области. Эти области ДОЛЖНЫ быть обслужены с их требованиями. Мои склады, с другой стороны, имеют ограничения относительно их возможностей, которые они могут обрабатывать и доставлять. Одно депо может обслуживать несколько зон, но одна зона может обслуживаться только одним депо.

У меня есть матрица расстояний / затрат для соединений между складами и районами, а также спрос на эти районы.

Целью этого решения должно быть то, что области должны обслуживаться с минимально возможным усилием.

Допустим, матрица стоимости / расстояния выглядит примерно так:

assign.costs <- matrix (c(2, 7, 7, 2, 7, 7, 3, 2, 7, 2, 8, 10, 1, 9, 8, 2,7,8,9,10), 4, 10)

Итакэто создает мою матрицу с клиентами / областями в первой строке / заголовке и депо в именах первых столбцов / строк.

Теперь спрос областей / клиентов:

assign.demand <- matrix (c(1,2,3,4,5,6,7,8,9,10), 1, 10)

Ограничения емкости, сколько может обслуживать депозит:

assign.capacity <- matrix (c(15,15,15,15), 4, 1)

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

Результат должен выглядеть примерно так:

assign.solution <- matrix (c(1,0,0,0 ,0,1,0,0, 1,0,0,0, 1,0,0,0 ,0,0,0,1), 4, 10)

Что касается ограничений, это означает, что каждый столбец должендо одного.

Я пробовал это с функциями lpsolve и lp.assign из lpSolve, но я не знаю точно, как реализовать именно такие ограничения, которые у меня есть, и я уже пытался изменить функции lp.assign с помощьюнет успехаЕсли это поможет, я также могу сформулировать уравнения для ЛП.

Спасибо всем за вашу помощь, я действительно застрял прямо сейчас: D

BR

Answer 1

Шаг 1. Разработка математической модели

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

Синие записи представляют данные икрасные указывают переменную решения. i - склады, а j - клиенты. Ship указывает, отправляем ли мы от i до j (это двоичная переменная). Первое ограничение говорит о том, что общая сумма, отправленная из склада i , не должна превышать его вместимость. Второе ограничение говорит о том, что для каждого клиента должен быть ровно один i j .

Шаг 2. Реализация

Теперь это просто вопрос точности. Я следую за моделью из предыдущего раздела как можно точнее.

library(dplyr)
library(tidyr)
library(ROI)
library(ROI.plugin.symphony)
library(ompr)
library(ompr.roi)

num_depots <- 4
num_cust <- 10

cost <- matrix(c(2, 7, 7, 2, 7, 7, 3, 2, 7, 2, 8, 10, 1, 9, 8, 2,7,8,9,10), num_depots, num_cust)
demand <- c(1,2,3,4,5,6,7,8,9,10)
capacity <- c(15,15,15,15)

m <- MIPModel() %>%
  add_variable(ship[i,j], i=1:num_depots, j=1:num_cust, type="binary") %>%
  add_constraint(sum_expr(demand[j]*ship[i,j], j=1:num_cust) <= capacity[i], i=1:num_depots) %>% 
  add_constraint(sum_expr(ship[i,j], i=1:num_depots) == 1, j=1:num_cust) %>% 
  set_objective(sum_expr(cost[i,j]*ship[i,j], i=1:num_depots, j=1:num_cust),"min") %>% 
  solve_model(with_ROI(solver = "symphony", verbosity=1))

cat("Status:",solver_status(m),"\n")
cat("Objective:",objective_value(m),"\n")
get_solution(m,ship[i, j]) %>%
  filter(value > 0) 

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

Для реализации я использовал OMPR вместо пакета LpSolve, потому что OMPR позволяет мне оставаться ближе к математической модели. LpSolve имеет матричный интерфейс, который очень сложно использовать, за исключением очень структурированных моделей.

Шаг 3: Решите это

Status: optimal 
Objective: 32 
   variable i  j value
1      ship 1  1     1
2      ship 4  2     1
3      ship 2  3     1
4      ship 1  4     1
5      ship 3  5     1
6      ship 4  6     1
7      ship 4  7     1
8      ship 2  8     1
9      ship 1  9     1
10     ship 3 10     1

Я считаю, что это правильное решение.