整数规划 python

2744557306

整数规划是线性规划的一个扩展，其中变量被限制为整数。在Python中，你可以使用多种库来解决整数规划问题，包括：
3 H  ~* C$ B4 m; d3 R
2 F' b) y1 e+ C8 s* {2 x1.PuLP：PuLP是一个优化建模库，可以用于线性规划、整数规划和混合整数规划。它提供了一种直观的方式来定义优化问题，并支持多种优化算法。

1.   from pulp import LpMaximize, LpProblem, LpVariable+ `9 d8 \7 X& J\" y( J( d
   
2. : i/ F& r% Y6 V* Q- o5 U+ }
   
3. 
     o/ G5 g, y/ A) D; {0 ?  m
4. ( b5 g3 m- M% g1 x7 [5 {6 O
   
5.    # 创建问题) j: l0 Z2 W. p. s+ e' i0 E+ {
   
6. ' M* U+ L; ^2 Q- e$ r+ \
   
7.    prob = LpProblem("Integer programming problem", LpMaximize)
   4 @% m. s  [  G: v1 y% m
8. - q' w' Y: J& N9 M' o
   
9. 
   ; O9 g* ^5 `7 w) [; i' F\" \
10. 
    ) Z, `5 d) `* _$ z7 c( \
11.    # 定义变量
    , ?! K3 _; b\" D4 H
12. - e8 U1 Z' j7 F$ e% |2 M6 ^\" d
    
13.    x = LpVariable("x", lowBound=0, cat="Integer"): t$ b6 j# H, w/ u2 C5 S* q0 I
    
14. 
    . {& o) N, ], o, H  j$ R) a- o
15.    y = LpVariable("y", lowBound=0, cat="Integer")) ?( l/ B$ x# {
    
16. \" t. P, x* E$ \1 L* o1 P8 m; E
    
17. 7 o* N( j1 A; t/ R, S: Z
    
18. ; ~* V* `8 W6 y
    
19.    # 定义目标函数9 n8 R! Z2 n7 E$ F( {
    
20. $ T% ^: z1 y8 H* x4 @/ o
    
21.    prob += 3 * x + 2 * y; J\" d& F% |, M. C
    
22. 
    ) Z8 K3 C9 D! m
23. & P  E( H/ U% |+ T1 p+ v- L- q
    
24. 
    % s& ^2 m$ |# O1 l2 R0 v/ G6 p- Q6 ]
25.    # 添加约束条件1 ~4 n\" V; E' W6 n
    
26. 
    2 c0 n9 Z: Q% N7 E9 p& B% ~
27.    prob += 2 * x + y <= 6! K8 s; C( Y2 h# A- _  p6 K/ u
    
28. 2 U) A% k* A. ]) C
    
29.    prob += x + 2 * y <= 8
    ) h2 d4 |6 P\" M! r. y  w0 ]
30. 
    3 o% q2 P( _& y' Z/ K
31. 
    # X( K0 G$ m5 e- O* E5 g
32. 
    # ?/ h; X- ?$ Y  D6 g
33.    # 求解问题; v7 _& K& Q; x: e
    
34. 
    : r: u  d% F: W- C- N# U
35.    prob.solve()! F  o) f% j& m/ D$ \( \9 x2 p( [
    
36. 
    5 \! k2 w3 a4 z7 l% |: B( e' d
37. 2 J% h6 N\" i/ ^
    
38. / x' v/ v9 {  S8 W9 Q1 E  l
    
39.    # 输出结果
    # t8 d5 T0 P: K; j  e1 z8 @! x
40. 
    2 q: I3 d% H5 k. @* i
41.    print("Optimal value:", prob.objective.value())
    , ^5 {9 \# C+ \, p/ W
42. 
    ' R4 k\" B7 j; X
43.    for var in prob.variables():
    , Z4 V6 x- w- ?. `6 a
44. - x( j/ C7 f& Q1 R7 o9 v
    
45.        print(var.name, "=", var.value())

复制代码

2.Pyomo：Pyomo是一个用于优化建模的Python库，可以处理线性规划、整数规划、混合整数规划等问题。它提供了一种声明式的建模语言，可以方便地定义优化问题。

1.   from pyomo.environ import ConcreteModel, Var, Objective, Constraint, SolverFactory) b3 r' w6 w3 Z
   
2. 
   . D* W) `4 ^, `. ^# Y5 j
3. 
   9 O3 j6 r9 K# O$ S; f
4. & U( A0 a$ k: X7 P
   
5.    # 创建模型; l6 T+ g, d: f! C\" e
   
6. ( k! z' G( f) \3 e' x2 |- O4 K' B# Z; T
   
7.    model = ConcreteModel()) Z2 m3 t7 h/ N. C0 H4 O% w* i
   
8. 6 b( U+ Y$ R* a8 N$ j1 [
   
9. , M! \\" E. Q0 I) C
   
10. ; y$ W. [5 f  e+ }( q\" [
    
11.    # 定义变量1 i% v3 e8 y' [! w
    
12. 
    , @4 A8 \\" R# U* S# ~' I
13.    model.x = Var(within=NonNegativeIntegers)5 c1 f# ?5 @\" l. {, X% g* _
    
14. ) p/ j& L- q8 o, X2 [1 w2 w- K
    
15.    model.y = Var(within=NonNegativeIntegers), T  ^# o: P. H, g! R2 a/ E2 V
    
16. 4 C3 ?! w0 W0 ~, s
    
17. 
    3 O# O! y  k\" L4 Y
18. # g, r, ~- s/ u1 ]- K1 Z  s5 _2 \) ?6 k
    
19.    # 定义目标函数
    5 Q! }! l/ ^# C1 t/ v
20. 3 x' P  p' @  j. f, x3 r5 ^
    
21.    model.obj = Objective(expr=3 * model.x + 2 * model.y, sense=maximize)
    \" D: O+ a, y4 A  N# c
22. 7 g4 g  T! ]' Y4 D0 F
    
23. 
    5 U9 F# a5 m( V& Y/ S
24. 8 _& |\" U( P. j; l  w
    
25.    # 添加约束条件# {( J& w; D& u) v
    
26. * V! x+ M! K  T) t' v' s4 o  y  e
    
27.    model.con1 = Constraint(expr=2 * model.x + model.y <= 6)3 e  v! G2 [2 p/ K1 q
    
28. & t; Z8 L: Q, U  m+ ]! N7 F
    
29.    model.con2 = Constraint(expr=model.x + 2 * model.y <= 8)$ K+ N, g7 |0 a
    
30. / w% ^9 D' }$ R: b# ?
    
31. ( u- J! |! t- D- i$ O7 x+ b
    
32. 4 V0 G\" ?  L) E0 e0 I4 `7 [0 ]5 q5 D  w
    
33.    # 求解问题  n3 r* J- \+ ?: {, ], I; D
    
34. % Y: ]' J\" ?$ G
    
35.    solver = SolverFactory('glpk')
    * f8 `( `( ?' O* e4 @! _5 u
36. 
    - _5 W0 |1 J; Y+ D\" m# K
37.    solver.solve(model)
    6 A& @3 T# d5 T2 P6 s  k1 O
38. / K6 I, I4 ~/ [3 S\" z; g
    
39. 
    , [* Z  f: f* k  V+ m
40. ( C' z) h4 p, u( G& H
    
41.    # 输出结果# f% R( ^: `8 e# J& I
    
42.   R9 C& Z6 I. r( e( o
    
43.    print("Optimal value:", model.obj())
    & S7 J; i( i. B4 O8 Y  Q+ i3 L
44. 8 l7 U; O( O: B. v% F$ u. e. y
    
45.    print("x =", model.x())
    , V$ m- C' {% T( L5 ~# a0 j: ^' X7 V
46. 
    7 \1 N' @, Z6 `- g7 Q+ Q  ?0 O
47.    print("y =", model.y())

复制代码