Ràng buộc logic

Phân tích Chuỗi Cung Ứng với Python

Aaren Stubberfield

Supply Chain Analytics Mgr.

Bài toán ví dụ

Khối lượng tối đa 20.000 lb

Sản phẩm	Khối lượng (lb)	Lợi nhuận ($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

Chọn tổ hợp sinh lợi cao nhất mà không vượt giới hạn khối lượng
Biến quyết định:
- X$_{i}$ = 1 nếu chọn sản phẩm _i_, ngược lại 0
Mục tiêu:
- Tối đa hóa z = $\sum$ Lợi nhuận$_{i}$X$_{i}$
Ràng buộc:
- $\sum$ Khối lượng$_{i}$X$_{i}$ < 20.0000

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))

Kết quả ví dụ

Khối lượng tối đa 20.000 lb

Sản phẩm	Giao hay không
A	Không
B	Không
C	Không
D	Có
E	Có
F	Có

Kết quả

Lợi nhuận: $230.307
Tổng khối lượng: 15.700 lb

Ví dụ ràng buộc logic 1

Chọn E hoặc D, nhưng không chọn cả hai.

X$_{E}$ = 1 nếu chọn sản phẩm _i_, ngược lại 0
X$_{D}$ = 1 nếu chọn sản phẩm _i_, ngược lại 0
Ràng buộc
- X$_{E}$ + X$_{D}$ ≤ 1

Ví dụ mã - ràng buộc logic ví dụ 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))

Kết quả ví dụ ràng buộc logic 1

Khối lượng tối đa 20.000 lb

Sản phẩm	Giao hay không
A	Không
B	Không
C	Có
D	Có
E	Không
F	Có

Kết quả

Lợi nhuận: $228.916
Tổng khối lượng: 15.800 lb

Ví dụ ràng buộc logic 2

Nếu chọn sản phẩm D thì phải chọn cả sản phẩm B.

X$_{D}$ = 1 nếu chọn sản phẩm _i_, ngược lại 0
X$_{B}$ = 1 nếu chọn sản phẩm _i_, ngược lại 0
Ràng buộc
- X$_{D}$ ≤ X$_{B}$

Ví dụ mã - ràng buộc logic ví dụ 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))

Kết quả ví dụ ràng buộc logic 2

Khối lượng tối đa 20.000 lb

Sản phẩm	Giao hay không
A	Không
B	Có
C	Không
D	Có
E	Không
F	Có

Kết quả

Lợi nhuận: $228.901
Tổng khối lượng: 15.300 lb

Các ràng buộc logic khác

Ràng buộc logic	Ràng buộc
Nếu chọn mục _i_ thì cũng phải chọn mục _j_.	x$_{i}$ - x$_{j}$ ≤ 0
Chọn một trong hai mục _i_ hoặc _j_, nhưng không đồng thời.	x$_{i}$ + x$_{j}$ = 1
Nếu chọn mục _i_ thì không chọn mục _j_.	x$_{i}$ - x$_{j}$ ≤ 1
Nếu không chọn mục _i_ thì không chọn mục _j_.	-x$_{i}$ + x$_{j}$ ≤ 0
Tối đa một trong các mục _i_, _j_, _k_ được chọn.	x$_{i}$ + x$_{j}$ + x$_{k}$ ≤ 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.

Tổng kết

Ôn lại các ví dụ về ràng buộc logic
Liệt kê bảng các ràng buộc logic khác

Đến lượt bạn!

Phân tích Chuỗi Cung Ứng với Python