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

杨利霞

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

2 H5 _9 }8 w* M" E3 P7 m2.1 基本概念

整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
整数规划的解有如下三种情况：
. X( d' P% l8 H
没有可行解（最优解不是整数）
存在最优解（最优解为整数）
. X$ U$ Z; o0 S6 k3 M* E4 h有可行解（最优解值变差）
2.2 0-1整数规划

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

2.2.1 相互排斥的约束条件

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


需保证只有一个起作用，则引进m个0-1变量：
; J+ K# i( t% U8 S$ w

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

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

定义：变量部分限制为整数
  _* y7 p9 M' b  @可用约束条件：

( m1 `7 l- ]3 }* r! D
y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：

; ~% k  ~& x" j) j$ ~5 G

2.2.3 指派问题

关键：给出系数矩阵C
; V7 U, N( }1 D规划模型为：（x为引入的0-1变量）

: Z! L+ P4 m9 L2 ]; I6 G
+ y9 t, W. _  \' F' Y
2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
. K; d' ~* {! O0 I+ F& _matlab程序如下：
  w2 R. y4 {! J' |0 S5 N  定义目标函数 f 和约束向量函数 g

* _+ w( k# I( V. a" @* P% ]
求解问题

* i* ]# ^- m5 Y- ^3 @
2.4 整数线性规划的计算机求解

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

4 @* |2 [) ^& \+ Z$ R

; d# K" e1 v3 S3 `+ f) K

————————————————
: K$ I/ m, |% Y: n( B% ^9 D
版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

: B  h  `& d; T, C- \# S$ b
7 s5 g* w, t  ]$ @) S1 i0 h: t————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
, B- b6 N* u: f- w1 b+ Y
  T1 l8 g0 L  N- U: H4 k' I0 V
# I- y) w% N/ ^" z+ t