数学建模社区-数学中国

标题: 数学建模算法与应用第二章：整数规划 [打印本页]

---

作者: 杨利霞    时间: 2020-3-13 17:02
标题: 数学建模算法与应用第二章：整数规划
数学建模算法与应用第二章：整数规划
: m7 |, `# \# V& ~
2.1 基本概念

- H9 r4 j9 k3 S7 u9 L整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
2 ?* R' m" t: {+ S* ~整数规划的解有如下三种情况：
* |& {' e" K$ }# S6 Y
3 p, W. v5 m5 I# o' G没有可行解（最优解不是整数）
存在最优解（最优解为整数）
; n7 {$ S7 R% g+ {5 T3 M# @有可行解（最优解值变差）
$ @5 |1 Y" X4 k. b; V2.2 0-1整数规划
% l  O6 {3 r# P, D6 Q( q5 o$ u
% m' u! k8 }; u定义：变量x仅取值0或1，即0-1变量

2.2.1 相互排斥的约束条件
2 `. ~7 ^# h9 }
引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
, j7 z3 ]( v  s$ r  X5 ?  v若有m个互相排斥的约束条件
" u) Y% M& W: z
( s7 I6 ?* p/ O
) ?) j+ w( R% [8 u# _$ f% R/ J需保证只有一个起作用，则引进m个0-1变量：
6 s$ s& e  m8 J

和一个充分大的常数M，则有：

  [% {% B/ G, O, u2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
可用约束条件：

y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：

$ N/ v8 u, C. P" N. _+ f5 a

2.2.3 指派问题

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

2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
5 d4 ~0 \4 z( F; r: U; ?  定义目标函数 f 和约束向量函数 g

: P( O) F& E" d8 V7 q( Z
求解问题

2 T0 c- T7 v/ I6 a. E
* |& q$ b( U0 ^5 r: U4 Z& K0 t: m2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
8 E; s$ r* v' ^$ Z/ R  标准形式为：

2 P! F) c2 p# }

* i' m( z8 D. e5 E: }
0 R) P/ f( c% N! ^
————————————————
5 ^/ a2 I: Y( I. D* B$ L: |
! r2 Z- N9 y  d2 G版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
0 _0 d1 _) g$ p: V原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

$ d. C, N1 b; S3 _& g, i( ]
————————————————
1 H$ ~) ?2 J" R: ~原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

% B$ B- k2 m8 u; z- M# H6 ?1 \
- u' V* t$ M* b; H( [& \. p

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5