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

杨利霞

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

2.1 基本概念

8 b; }2 `3 X1 r3 }% P5 k3 N1 _" u整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
, p$ g1 Q  G' ]; p* V整数规划的解有如下三种情况：

+ H7 A& @$ m" f' x6 B" n没有可行解（最优解不是整数）
7 @. }3 [2 Z& W9 a* i4 M存在最优解（最优解为整数）
& V+ x( ^! K: X$ {1 B* g有可行解（最优解值变差）
2.2 0-1整数规划

定义：变量x仅取值0或1，即0-1变量
6 q' r) L  l3 Z+ Z
2.2.1 相互排斥的约束条件
6 }& s6 u7 ?3 Z, X0 r
# N7 j: |6 o2 g) q% @8 S; K/ w引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
# A7 s, L6 ?1 t, @改为普通的约束条件（不常用）
若有m个互相排斥的约束条件

3 D4 e% }# j+ X
需保证只有一个起作用，则引进m个0-1变量：
7 J3 W9 S3 S: }3 M1 \
2 b5 `; P% |7 J
和一个充分大的常数M，则有：
: X& g( O5 Z( U$ W
2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
& X% U! t* J# E& G! E* M可用约束条件：

5 F/ R) U) g+ |y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：


; Y5 }" E0 U" f0 d( y* K1 K
4 ~$ @* d( c" H: A2.2.3 指派问题

关键：给出系数矩阵C
% y7 H7 m: H- n规划模型为：（x为引入的0-1变量）

! o* `! c6 g0 F
2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
" [7 ^' @* v+ C  定义目标函数 f 和约束向量函数 g

/ I" x. d+ t* h# z. P' P+ x
求解问题
; H+ Z8 R: J8 R( ?
1 x5 q: }+ s) q* V- ^6 R. p& B' i4 L
, z! ^( P8 P( x8 ]9 h8 p9 d: u2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
8 o1 }0 I2 \+ P" `4 G9 P* g' @% L  标准形式为：

0 y. ^' V0 M" c, Q6 `2 P

' B: r0 A4 g. M. T% K* h4 l4 Q% I

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

版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
9 M4 ~) W+ Z  D原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
8 W8 O; ^0 @0 D1 i: u

$ z* M2 @$ e5 M: `1 r/ |————————————————
' e% b& W  X. x  [8 E# F原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231