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

杨利霞

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

# G1 j3 k. T. d- G3 {2.1 基本概念
) W; r* [6 x( p8 J% P& Q) o! A8 s
* N# s7 W, o' k# S整数规划：数学规划中的变量（部分或全部）限制为整数
目前只能求解整数线性规划
. f& U! F( x2 r2 x3 {整数规划的解有如下三种情况：
# y: m" N$ t7 W  v! b4 c  O
3 h! x0 O# g  J% J; M$ |* w没有可行解（最优解不是整数）
存在最优解（最优解为整数）
2 o" [5 c9 _; l有可行解（最优解值变差）
$ H, W* k' j8 g7 Z4 ~2.2 0-1整数规划

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

' w$ w: F! X9 W# k+ T2.2.1 相互排斥的约束条件
  z2 `. n; x6 N; U
8 l7 e6 Z! u& R% O7 L引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
若有m个互相排斥的约束条件
- j: Y2 j6 x8 t8 m2 @2 V, O: ]4 Y
3 Y6 f' c9 J- j5 z. G: ~
; Q5 Y2 n8 f$ u2 `/ n7 u$ L需保证只有一个起作用，则引进m个0-1变量：


6 v  y- \1 _2 p3 x和一个充分大的常数M，则有：

; ~* R% s: v  N8 w8 v2.2.2 混合整数规划（固定费用）

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

7 T1 M. d- `* s9 `, z8 U5 {' Z# [
# f0 V2 N) U  b8 Ry为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：



2.2.3 指派问题

关键：给出系数矩阵C
' N8 k9 X7 I- ]# b8 Z' g规划模型为：（x为引入的0-1变量）

+ T) E. l' W% x. W3 {5 G! h7 i0 ?

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

目的：求解非线性整数规划
: M- O& q+ T7 Y( d3 D+ n& y' smatlab程序如下：
  定义目标函数 f 和约束向量函数 g

5 ?4 l) A! {( B! ]$ \求解问题
* L! W' W9 j: J& m/ x

3 h7 G5 `, p& G" s. n4 [2.4 整数线性规划的计算机求解

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

" y% h5 c5 p: s. m5 e
, m* P& x( b; ^
# H: I5 p. {) O1 Z, A, ?# T
/ @0 g9 k  L; Y
7 M5 U3 L; D" b% f9 x. t3 u% H————————————————
/ H, L9 F1 ?5 x' }( b3 ^/ c; {$ q3 O/ a
8 k' B3 z, v0 N& @8 `8 d5 \& m% l版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
* c* ^7 `  h2 R* c, U原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231


! K. I7 N- ~" ^————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

- I! \6 g( N5 ~" K/ A) N, {: i3 `