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

杨利霞

数学建模算法与应用第二章：整数规划
( ?" j0 u6 [' f( r: x( t9 P
2.1 基本概念
% j4 g& Z7 m  {; z( {" W3 q7 B6 j5 g
; J- F/ l4 h$ }& a1 N" Z整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
整数规划的解有如下三种情况：

没有可行解（最优解不是整数）
存在最优解（最优解为整数）
& u' }8 i8 Y6 y8 c有可行解（最优解值变差）
. D$ z7 h$ V& C$ f3 d* B  `* o2.2 0-1整数规划
/ k: f# D  a7 z0 n& ]
定义：变量x仅取值0或1，即0-1变量
2 n1 K0 f& V" ]- L' c+ ~. r
2.2.1 相互排斥的约束条件
# X6 @, w1 A; _- ~: @! ?
引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
0 X( r+ Z& k6 ]. m2 r6 d1 L; j改为普通的约束条件（不常用）
若有m个互相排斥的约束条件


需保证只有一个起作用，则引进m个0-1变量：


1 y' T6 x9 A( V+ e' h- b: N. j和一个充分大的常数M，则有：

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

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

0 c& q0 Z% D0 ]6 N0 Z5 M: ^
y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
4 K. \, ?" o  V6 q5 H. i' ]; z9 y' }


; T! Z- U+ I. a2.2.3 指派问题

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

9 h$ a& \) u5 x) W6 v

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

目的：求解非线性整数规划
/ C0 A7 s7 ~7 x9 _9 j, S6 |matlab程序如下：
; t; q  g5 c5 v5 G- j9 O: M  定义目标函数 f 和约束向量函数 g

, P/ l" ]( R1 i
0 C9 j& m1 {* ~/ r求解问题
+ D8 F4 ?6 D. l: ^8 c4 Y

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

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

/ N6 y3 O- [" o% ?$ z0 J, y
! F, G& w- h& w+ n: D/ y$ S; f

————————————————

- w1 I6 O+ s# {3 p9 k/ J4 X) B8 B版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
3 e4 ]8 O- |! t4 _8 V) G原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
; c0 l+ H" o4 V1 S! n/ k' n

( I8 H6 ~8 l5 B8 s7 }# V4 l————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
( |# A+ T9 C5 n; l8 [( @  Y8 ^& z