Логические ограничения

Аналитика цепочек поставок на Python

Aaren Stubberfield

Supply Chain Analytics Mgr.

Пример задачи

Максимальный вес: 20 000 фунтов

Товар	Вес (фунты)	Рентабельность ($США)
A	12 800	77 878
B	10 900	82 713
C	11 400	82 728
D	2 100	68 423
E	11 300	84 119
F	2 300	77 765

Выбрать наиболее рентабельный товар для отправки, не превысив лимит веса
Переменные решения:
- X$_{i}$ = 1, если товар _i_ выбран, иначе 0
Целевая функция:
- Максимизировать z = $\sum$ Рентабельность$_{i}$X$_{i}$
Ограничение:
- $\sum$ Вес$_{i}$X$_{i}$ < 20 000

prod = ['A', 'B', 'C', 'D', 'E', 'F']
weight = {'A':12800, 'B':10900, 'C':11400, 'D':2100, 'E':11300, 'F':2300}
prof = {'A':77878, 'B':82713, 'C':82728, 'D':68423, 'E':84119, 'F':77765}

# Initialize Class
model = LpProblem("Loading Truck Problem", LpMaximize)

# Define Decision Variables
x = LpVariable.dicts('ship_', prod, cat='Binary')

# Define Objective
model += lpSum([prof[i]*x[i] for i in prod])

# Define Constraint
model += lpSum([weight[i]*x[i] for i in prod]) <= 20000

# Solve Model
model.solve()
for i in prod: print("{} status {}".format(i, x[i].varValue))

Результат примера

Максимальный вес: 20 000 фунтов

Товар	Отправить?
A	Нет
B	Нет
C	Нет
D	Да
E	Да
F	Да

Результат

Рентабельность: $230 307
Вес товаров: 15 700 фунтов

Пример логического ограничения 1

Выбирается либо товар E, либо товар D, но не оба одновременно.

X$_{E}$ = 1, если товар _i_ выбран, иначе 0
X$_{D}$ = 1, если товар _i_ выбран, иначе 0
Ограничение
- X$_{E}$ + X$_{D}$ ≤ 1

Пример кода — логическое ограничение 1

model += x['E'] + x['D'] <= 1

prod = ['A', 'B', 'C', 'D', 'E', 'F']
weight = {'A':12800, 'B':10900, 'C':11400, 
          'D':2100, 'E':11300, 'F':2300}
prof = {'A':77878, 'B':82713, 'C':82728, 
        'D':68423, 'E':84119, 'F':77765}

# Initialize Class
model = LpProblem("Loading Truck Problem",
                   LpMaximize)

# Define Decision Variables
x = LpVariable.dicts('ship_', prod, 
                      cat='Binary')

# Define Objective
model += lpSum([prof[i]*x[i] for i in prod])

# Define Constraint
model += 
  lpSum([weight[i]*x[i] for i in prod]) <= 20000
model += x['E'] + x['D'] <= 1

# Solve Model
model.solve()
for i in prod:
  print("{} status {}".format(i, x[i].varValue))

Результат примера с логическим ограничением 1

Максимальный вес: 20 000 фунтов

Товар	Отправить?
A	Нет
B	Нет
C	Да
D	Да
E	Нет
F	Да

Результат

Рентабельность: $228 916
Вес товаров: 15 800 фунтов

Пример логического ограничения 2

Если выбран товар D, то товар B также должен быть выбран.

X$_{D}$ = 1, если товар _i_ выбран, иначе 0
X$_{B}$ = 1, если товар _i_ выбран, иначе 0
Ограничение
- X$_{D}$ ≤ X$_{B}$

Пример кода — логическое ограничение 2

model += x['D'] <= x['B']

prod = ['A', 'B', 'C', 'D', 'E', 'F']
weight = {'A':12800, 'B':10900, 'C':11400, 
          'D':2100, 'E':11300, 'F':2300}
prof = {'A':77878, 'B':82713, 'C':82728, 
        'D':68423, 'E':84119, 'F':77765}

# Initialize Class
model = LpProblem("Loading Truck Problem", 
                   LpMaximize)

# Define Decision Variables
x = LpVariable.dicts('ship_', prod,
                      cat='Binary')

# Define Objective
model += lpSum([prof[i]*x[i] for i in prod])

# Define Constraint
model += 
 lpSum([weight[i]*x[i] for i in prod]) <= 20000
model += x['D'] <= x['B']

# Solve Model
model.solve()
for i in prod:
  print("{} status {}".format(i, x[i].varValue))

Результат примера с логическим ограничением 2

Максимальный вес: 20 000 фунтов

Товар	Отправить?
A	Нет
B	Да
C	Нет
D	Да
E	Нет
F	Да

Результат

Рентабельность: $228 901
Вес товаров: 15 300 фунтов

Другие логические ограничения

Логическое ограничение	Ограничение
Если выбран элемент _i_, то выбран и элемент _j_.	x$_{i}$ - x$_{j}$ ≤ 0
Выбирается либо элемент _i_, либо элемент _j_, но не оба.	x$_{i}$ + x$_{j}$ = 1
Если выбран элемент _i_, то элемент _j_ не выбран.	x$_{i}$ - x$_{j}$ ≤ 1
Если элемент _i_ не выбран, то элемент _j_ также не выбран.	-x$_{i}$ + x$_{j}$ ≤ 0
Выбран не более одного из элементов _i_, _j_ и _k_.	x$_{i}$ + x$_{j}$ + x$_{k}$ ≤ 1

¹ James Orlin, Ebrahim Nasrabadi. 15.053 Optimization Methods in Management Science. Spring 2013. Massachusetts Institute of Technology: MIT OpenCourseWare. Лицензия: Creative Commons BY-NC-SA.

Итоги

Рассмотрены примеры логических ограничений
Приведена таблица других логических ограничений

Давайте потренируемся!

Аналитика цепочек поставок на Python