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

杨利霞

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

2.1 基本概念
3 r5 e9 r5 N; L
( Y, ]/ J& w3 f' O1 p3 X! C7 s( t& k整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
整数规划的解有如下三种情况：

没有可行解（最优解不是整数）
5 Z" ^7 T7 O% E& B/ c: W存在最优解（最优解为整数）
7 l* y5 ^& V* m9 E; r: r) `有可行解（最优解值变差）
2.2 0-1整数规划
  _' g2 N0 @( U* i5 T* q7 V
0 H9 i$ c7 _: v" S  n, f6 T9 f定义：变量x仅取值0或1，即0-1变量
" y+ p2 |$ F; v/ E/ f2 I
5 ]. D% q/ B* m* G0 L3 t2.2.1 相互排斥的约束条件
4 _  Z: u- R, F, |& x9 r
引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
' u3 J; I! H) w; Y' z. p9 s若有m个互相排斥的约束条件


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


9 ?# J' e/ }! ?) ]) n和一个充分大的常数M，则有：

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

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

0 y$ b6 r3 h& g4 j  d" D
* z2 `. l! R* ^% t4 x% v# ?9 F: {6 Cy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
+ O$ P  @4 [1 T9 t

9 a% F/ P9 m# O
2.2.3 指派问题

关键：给出系数矩阵C
% F0 a+ ?, f/ k5 s/ q规划模型为：（x为引入的0-1变量）

( K  f, h2 B+ N  o  L, M' u' v" y
2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
  Z4 d! _3 ~' o# \4 I0 rmatlab程序如下：
6 A; |, ]" G" q! |& D3 E& @  定义目标函数 f 和约束向量函数 g

. s, U( Y1 Q8 z  }- S
求解问题


1 y. @/ t' Z* X( V  g  l1 J( {2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
) O" F7 v! |+ H" c) ~$ `  标准形式为：

7 Y. F, P0 S1 T/ u" V8 s
8 G  H: q6 Q* ]
( Y' f3 l: c- J" [" N/ l: `

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

9 v$ j3 R5 Z& T( _( i! X4 s+ L版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

' u! l2 U+ Y" J# e& E
5 H1 r& g, {- W" C# N————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
# U! i0 B* C" _3 G& y; t
2 h0 n2 H- D  ]% J  x3 d7 @
0 r- T, ~  _# H