Logiska bivillkor

Supply Chain Analytics i Python

Aaren Stubberfield

Supply Chain Analytics Mgr.

Exempelproblem

Maxvikt 20 000 lbs

Produkt	Vikt (lbs)	Lönsamhet ($US)
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

Välj den mest lönsamma produkten att skicka utan att överstiga viktgränsen
Beslutsvariabler:
- X$_{i}$ = 1 om produkt _i_ väljs, annars 0
Målsättning:
- Maximera z = $\sum$ Lönsamhet$_{i}$X$_{i}$
Bivillkor:
- $\sum$ Vikt$_{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))

Exempelresultat

Maxvikt 20 000 lbs

Produkt	Skicka eller inte
A	Nej
B	Nej
C	Nej
D	Ja
E	Ja
F	Ja

Resultat

Lönsamhet: $230 307
Produkternas vikt: 15 700 lbs

Logiskt bivillkor – exempel 1

Antingen väljs produkt E eller produkt D, men inte båda.

X$_{E}$ = 1 om produkt _i_ väljs, annars 0
X$_{D}$ = 1 om produkt _i_ väljs, annars 0
Bivillkor
- X$_{E}$ + X$_{D}$ ≤ 1

Kodexempel – logiskt bivillkor exempel 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))

Resultat – logiskt bivillkor 1

Maxvikt 20 000 lbs

Produkt	Skicka eller inte
A	Nej
B	Nej
C	Ja
D	Ja
E	Nej
F	Ja

Resultat

Lönsamhet: $228 916
Produkternas vikt: 15 800 lbs

Logiskt bivillkor – exempel 2

Om produkt D väljs måste även produkt B väljas.

X$_{D}$ = 1 om produkt _i_ väljs, annars 0
X$_{B}$ = 1 om produkt _i_ väljs, annars 0
Bivillkor
- X$_{D}$ ≤ X$_{B}$

Kodexempel – logiskt bivillkor exempel 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))

Resultat – logiskt bivillkor 2

Maxvikt 20 000 lbs

Produkt	Skicka eller inte
A	Nej
B	Ja
C	Nej
D	Ja
E	Nej
F	Ja

Resultat

Lönsamhet: $228 901
Produkternas vikt: 15 300 lbs

Andra logiska bivillkor

Logiskt bivillkor	Bivillkor
Om artikel _i_ väljs väljs även artikel _j_.	x$_{i}$ - x$_{j}$ ≤ 0
Antingen väljs artikel _i_ eller artikel _j_, men inte båda.	x$_{i}$ + x$_{j}$ = 1
Om artikel _i_ väljs väljs inte artikel _j_.	x$_{i}$ - x$_{j}$ ≤ 1
Om artikel _i_ inte väljs väljs inte artikel _j_.	-x$_{i}$ + x$_{j}$ ≤ 0
Högst en av artiklarna _i_, _j_ och _k_ väljs.	x$_{i}$ + x$_{j}$ + x$_{k}$ ≤ 1

¹ James Orlin och Ebrahim Nasrabadi. 15.053 Optimization Methods in Management Science. Våren 2013. Massachusetts Institute of Technology: MIT OpenCourseWare. Licens: Creative Commons BY-NC-SA.

Sammanfattning

Gick igenom exempel på logiska bivillkor
Presenterade en tabell med övriga logiska bivillkor

Nu kör vi en övning!

Supply Chain Analytics i Python