数学建模算法与应用第二章：整数规划

杨利霞

数学建模算法与应用第二章：整数规划

& ?9 }; v/ B! {4 S. W! Z2.1 基本概念

8 X' A5 m5 P4 V整数规划：数学规划中的变量（部分或全部）限制为整数
: `: r/ R, ]6 E9 r0 f9 G7 S. K! n4 [目前只能求解整数线性规划
; S  o" I/ l1 z* L. O整数规划的解有如下三种情况：

没有可行解（最优解不是整数）
+ o1 V3 a4 x5 R/ N8 {8 I6 r% k6 ]8 h存在最优解（最优解为整数）
有可行解（最优解值变差）
2.2 0-1整数规划

定义：变量x仅取值0或1，即0-1变量

2.2.1 相互排斥的约束条件

引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
若有m个互相排斥的约束条件

$ B# q! ?  q7 o- x8 z
需保证只有一个起作用，则引进m个0-1变量：
% f+ L" e' z. A

2 u  \! r# }! v$ d7 `. n和一个充分大的常数M，则有：
) g6 j# b1 e* X# O
2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
9 j8 L4 J+ U! G- Z0 d/ @& o可用约束条件：

& p9 ^, }) w4 |4 `: u  H- `0 q, |6 yy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
/ y" `* h/ A! x5 r& Y上式即代替了该分段函数：
' s. f% d- h# j" q
( W8 v* N- W$ G' d/ o0 J: p, v
, q7 o' Y$ o/ Z5 F9 x6 t  K
2.2.3 指派问题

关键：给出系数矩阵C
规划模型为：（x为引入的0-1变量）

* \2 h. `1 D+ o
2 v* A  Y4 z1 \  q8 E* a( G+ k2 |
- c1 W! d: s, l( A2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
$ j5 T4 G9 M: L  [- }  ^( {matlab程序如下：
  定义目标函数 f 和约束向量函数 g

求解问题
" i" o: e0 Y  Q9 G! g9 S
3 [& ^' _1 {& `3 u: I
3 C# G8 h8 ]% W" k& r0 U/ m6 y/ g2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
  标准形式为：

8 [7 n, q4 X/ q- O) r/ ?- T


9 a. H9 [3 z8 u+ D" b9 ~% \1 Y
————————————————

7 t1 [  l' @1 f+ l/ g版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
0 ^, ^3 I$ W( N! ]. _, R. J原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
9 F) H  E  ]$ W- m/ f+ j! b% I3 k
! a4 u+ \1 J5 O$ l- ?
7 ~; y6 W; ?8 L" s————————————————
, o( Y( m8 B4 u/ n原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
+ W5 Q6 p4 G' K% r. i! Y

- H/ v" `1 ]& K# c2 J  r6 B