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

杨利霞

数学建模算法与应用第二章：整数规划
) J/ e. Z* Q" `) f- U7 t+ w$ z3 y$ P
2 O4 E# b, U" j# f* E2.1 基本概念
6 @) o  r5 x7 j( A8 I- ^
5 E0 E7 ?/ X; \  a/ O整数规划：数学规划中的变量（部分或全部）限制为整数
9 J" ~2 O. Z, d/ }+ U目前只能求解整数线性规划
整数规划的解有如下三种情况：
# Y; m1 r7 N( v8 M& @+ h
没有可行解（最优解不是整数）
存在最优解（最优解为整数）
# n( X; ^0 U% [5 d) o8 h有可行解（最优解值变差）
4 X& Y) q) a! z' F2.2 0-1整数规划

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

- s" E/ J: _6 i4 R1 l8 I0 Z2.2.1 相互排斥的约束条件

& B: f9 @/ R" Q* B  N引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
5 T# t! t" m, U1 o改为普通的约束条件（不常用）
若有m个互相排斥的约束条件
" c8 e( f, a/ A2 v! B2 L1 b6 I
4 j7 M% N& u; W5 k% v/ R/ g
5 v1 N4 k% p% r* X需保证只有一个起作用，则引进m个0-1变量：
4 \% v/ p0 ]/ |- h: v- m7 ?2 X
/ k" M) }' j1 I. R6 c" T3 h" u! [& j
) O8 O) H! d: o% o- v+ n) J0 q和一个充分大的常数M，则有：

3 M% C/ W  [) M$ w1 F- V/ ~  L$ `2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
7 \* S$ ?6 V0 c9 e" k( N* g可用约束条件：

3 b$ n& {  A* {
6 g4 N8 q2 P0 M8 Q7 n8 x2 W, \! _y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
- m; Q9 Y  \0 w( ~上式即代替了该分段函数：
- H, Q. N" g/ C  i5 v4 t9 B& V

6 D# Z- \5 B% j2 F
& W) v$ r+ |5 e! r7 J2.2.3 指派问题

关键：给出系数矩阵C
8 @7 t' w6 J4 Q& }+ j; B' o规划模型为：（x为引入的0-1变量）

7 M0 |' O+ v8 O) Y' \
8 K+ R8 ]. N& l( E% e
2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
  定义目标函数 f 和约束向量函数 g

# K9 z: v3 z6 L3 v# X
求解问题


2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
7 r( M7 b. u% l& w$ |1 j  标准形式为：

& o" T2 H6 n& Z3 n( W) D- S
4 V- ~+ ~: z0 ]" m8 Q+ K+ c+ I
" r' W, U9 i2 D2 X2 v

————————————————
) I4 p8 U7 N, m1 a1 X" Y& v8 [
版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231


! c' p) M2 q  R. L6 ?/ `& E1 l3 N& P————————————————
) }  ^/ T! o: N+ Y/ U7 W原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
0 t) I/ l0 G5 }