Ograniczenia logiczne
Analityka łańcucha dostaw w Pythonie
Aaren Stubberfield
Supply Chain Analytics Mgr.
Przykładowy problem
Maksymalna waga: 20 000 funtów
| Produkt | Waga (funty) | Zysk (USD) |
|---|---|---|
| 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 |
- Wybrać najbardziej opłacalne produkty do wysyłki bez przekraczania limitu wagi
- Zmienne decyzyjne:
- X$_{i}$ = 1, jeśli produkt _i_ jest wybrany, w przeciwnym razie 0
- Cel:
- Maksymalizacja z = $\sum$ Zysk$_{i}$X$_{i}$
- Ograniczenie:
- $\sum$ Waga$_{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))
Wynik przykładu
Maksymalna waga: 20 000 funtów
| Produkt | Załadować? |
|---|---|
| A | Nie |
| B | Nie |
| C | Nie |
| D | Tak |
| E | Tak |
| F | Tak |
Wynik
- Zysk: 230 307 USD
- Waga produktów: 15 700 funtów
Przykład ograniczenia logicznego 1
Wybrany jest produkt E lub produkt D, ale nie oba jednocześnie.
- X$_{E}$ = 1, jeśli produkt _i_ jest wybrany, w przeciwnym razie 0
- X$_{D}$ = 1, jeśli produkt _i_ jest wybrany, w przeciwnym razie 0
- Ograniczenie
- X$_{E}$ + X$_{D}$ ≤ 1
Przykład kodu – ograniczenie logiczne 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))
Wynik – ograniczenie logiczne 1
Maksymalna waga: 20 000 funtów
| Produkt | Załadować? |
|---|---|
| A | Nie |
| B | Nie |
| C | Tak |
| D | Tak |
| E | Nie |
| F | Tak |
Wynik
- Zysk: 228 916 USD
- Waga produktów: 15 800 funtów
Przykład ograniczenia logicznego 2
Jeśli wybrano produkt D, to musi zostać wybrany również produkt B.
- X$_{D}$ = 1, jeśli produkt _i_ jest wybrany, w przeciwnym razie 0
- X$_{B}$ = 1, jeśli produkt _i_ jest wybrany, w przeciwnym razie 0
- Ograniczenie
- X$_{D}$ ≤ X$_{B}$
Przykład kodu – ograniczenie logiczne 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))
Wynik – ograniczenie logiczne 2
Maksymalna waga: 20 000 funtów
| Produkt | Załadować? |
|---|---|
| A | Nie |
| B | Tak |
| C | Nie |
| D | Tak |
| E | Nie |
| F | Tak |
Wynik
- Zysk: 228 901 USD
- Waga produktów: 15 300 funtów
Inne ograniczenia logiczne
| Ograniczenie logiczne | Warunek |
|---|---|
| Jeśli element _i_ jest wybrany, to element _j_ jest również wybrany. | x$_{i}$ - x$_{j}$ ≤ 0 |
| Wybrany jest element _i_ lub element _j_, ale nie oba jednocześnie. | x$_{i}$ + x$_{j}$ = 1 |
| Jeśli element _i_ jest wybrany, to element _j_ nie jest wybrany. | x$_{i}$ - x$_{j}$ ≤ 1 |
| Jeśli element _i_ nie jest wybrany, to element _j_ również nie jest wybrany. | -x$_{i}$ + x$_{j}$ ≤ 0 |
| Co najwyżej jeden z elementów _i_, _j_ i _k_ jest wybrany. | x$_{i}$ + x$_{j}$ + x$_{k}$ ≤ 1 |
1 James Orlin, and Ebrahim Nasrabadi. 15.053 Optimization Methods in Management Science. Spring 2013. Massachusetts Institute of Technology: MIT OpenCourseWare. License: Creative Commons BY-NC-SA.
Podsumowanie
- Omówiono przykłady ograniczeń logicznych
- Przedstawiono tabelę innych ograniczeń logicznych
Czas na ćwiczenia!
Analityka łańcucha dostaw w Pythonie
