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

杨利霞

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

2.1 基本概念
, a: a9 f4 f0 [. [( t# ^9 t- f
整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
整数规划的解有如下三种情况：

没有可行解（最优解不是整数）
存在最优解（最优解为整数）
8 F# w2 b# S, h" t+ L0 v: R3 n有可行解（最优解值变差）
; {5 r/ X  G0 S3 Y, y. b- l2.2 0-1整数规划
$ ^& o$ _6 Y/ P- @& t+ q1 C
1 Y. l# P- G6 `/ E* l定义：变量x仅取值0或1，即0-1变量
1 g1 U: F4 Z3 B" K
% _( d  v' ?8 g: ~  |+ O2.2.1 相互排斥的约束条件

9 W: u3 }5 ^; u3 s引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
/ W8 t& Q: f2 z# W, {改为普通的约束条件（不常用）
' W+ @- M! l* B0 A0 {若有m个互相排斥的约束条件
7 l. M9 B# E; l, U4 q

8 o; J1 K) L5 P  L需保证只有一个起作用，则引进m个0-1变量：


" K+ N2 J* k, R5 x$ {和一个充分大的常数M，则有：

2.2.2 混合整数规划（固定费用）

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

8 C: y4 k5 y( j/ l# b' Q3 j
6 P) ?/ L9 i) v- X/ D: ^y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
$ V( C/ B& o$ O0 E* w! v

  T$ ?" i. m" ?% f
2.2.3 指派问题

关键：给出系数矩阵C
, j$ c  |, k+ ?( m6 m; j" n规划模型为：（x为引入的0-1变量）

' l+ c* ]& |, ^4 U2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
2 D% g5 ]* ]% E: c& L9 ?! c' }1 h  定义目标函数 f 和约束向量函数 g

- z% T8 A$ K. P, L0 @  _6 g3 D
% S) c) v7 X5 a求解问题


/ n/ V% _8 C5 S& ~( F2.4 整数线性规划的计算机求解

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

6 K4 p2 V7 i# o0 b2 c: }) d
, y5 V" n, m- R) g
( \4 ^( O. V. r/ i( \  F& K& @
. Z1 @: c; U2 `( Y. l  V# w
————————————————
. x9 t& h9 m! A* @, h. G, R1 B
版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
, w. C/ h' i' M0 C7 x3 e原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
$ o2 _9 A/ N" e6 k7 q+ m) `; m9 N* Q

4 @# }  V, r8 J) |$ A————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
7 R+ N! Q# S* k) ^3 x  o
1 p( S) W- V0 l