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

杨利霞

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

* P" q. ]+ e. T% w2.1 基本概念

% Y, `* d7 d7 _# }$ O整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
0 h1 f3 M1 t8 Y/ n整数规划的解有如下三种情况：
. D8 g! X  r0 D* b5 s* _- _
没有可行解（最优解不是整数）
( a- e8 \0 s* N- B& ~; Y9 H存在最优解（最优解为整数）
有可行解（最优解值变差）
1 [: Z* F$ b7 m6 o0 Y2.2 0-1整数规划

定义：变量x仅取值0或1，即0-1变量
3 a- X- \7 b, ^8 ~
# ]7 Z% V: I6 I  t9 s+ K2.2.1 相互排斥的约束条件

% T$ M) T0 w% B9 ~0 G! e) O' t7 G) n引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
若有m个互相排斥的约束条件

0 y$ h: i% Z. L2 [& G
需保证只有一个起作用，则引进m个0-1变量：

, `# M! a4 D( n) R8 f* t/ |
- w6 p/ P. G9 M! X' G# u8 f1 q! F和一个充分大的常数M，则有：

* l+ Q5 m" S; `2.2.2 混合整数规划（固定费用）

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

1 _5 g3 A4 n! A7 t1 J$ Q5 u: ^" M
y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
9 r* B5 X/ M" n+ u4 V1 Y
5 J( i* z* f- E. o

2.2.3 指派问题

关键：给出系数矩阵C
( J& E# [8 g. L+ H4 X) z! ~$ j规划模型为：（x为引入的0-1变量）

7 ^$ X! M8 S. u6 j; _- o
) d$ N: D$ I, h
2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
2 {# E" ?6 `1 R  定义目标函数 f 和约束向量函数 g

7 A0 L. x, f' R7 a! I+ j求解问题
+ z; J& o( [: m2 s$ O

- o* }; U- L# ^) S. A2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
1 b/ t8 o% D) q; Q8 j1 j8 t# A. @3 C  标准形式为：

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

; p( ^5 G. A' b# N+ u% g版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
+ [2 j$ e  c" n' }% c

% N7 Z% Z# f; C  _————————————————
/ t4 O9 C" X  z8 g2 k9 j+ Q原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

1 k/ ]  V. j, S! N