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

杨利霞

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

- [, j; g% @- `  f! V: F  o2.1 基本概念

整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
整数规划的解有如下三种情况：

$ ~9 m0 c1 \; H5 u没有可行解（最优解不是整数）
8 i% H' b% R; _% F/ @; t! C存在最优解（最优解为整数）
( x' E+ B' f9 W" O5 V$ r' ?$ Z: G有可行解（最优解值变差）
, V' `0 l/ [6 |1 M, v5 q2.2 0-1整数规划

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

2.2.1 相互排斥的约束条件
0 u+ h6 n; h% e7 R
0 j% O* `+ E3 i+ x/ j! I/ p引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
8 a  ^: W1 D  S3 u若有m个互相排斥的约束条件

' _, y0 i; A2 W& d8 l: ?6 w
& z( C; p$ o' p8 ^: h6 S8 i需保证只有一个起作用，则引进m个0-1变量：
2 A3 g3 [& r! f) Y6 E  {2 _, M# K
8 O/ e; p( ^: r  j* X
6 m2 @% o% s  {) W8 {和一个充分大的常数M，则有：
& j0 P+ Y9 j2 v+ h: M$ ?
4 u- k9 a1 j; {) X; v7 [4 ?2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
) ^( T& p; |  b% E$ d7 D5 Y4 ?可用约束条件：

- [! S6 {7 j! c$ d5 R6 j& H! C$ v
1 m3 g( a3 Y& B9 E4 l% \y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：



0 K5 O2 L: j$ c6 M5 q; [; T2.2.3 指派问题

关键：给出系数矩阵C
: Z5 s! F+ ^6 v! K规划模型为：（x为引入的0-1变量）

+ r; r, B" v- m

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

目的：求解非线性整数规划
matlab程序如下：
  S! T+ {1 o4 V  定义目标函数 f 和约束向量函数 g

6 A$ \& \5 F8 S  U0 _' T7 c求解问题

( W+ n+ a7 K. T0 m3 o9 p  L5 `
2.4 整数线性规划的计算机求解

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

9 Y1 e: s* S- \* ^————————————————

版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
0 _. }% c$ p& Q# k& V+ t' C# b
1 [' F% i8 r2 `/ [7 P9 L' p
————————————————
, L4 A$ V7 T; k) h/ L& S原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
+ h: {3 x$ h3 _5 `