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

杨利霞

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

2.1 基本概念
! @: l3 I1 O; _
* E+ f! t, n) R8 m整数规划：数学规划中的变量（部分或全部）限制为整数
& M6 \  _; `2 z3 ^/ P目前只能求解整数线性规划
8 b: I5 O8 n' ^整数规划的解有如下三种情况：
/ Q5 R, o* }+ u7 t+ w+ `% K: D
没有可行解（最优解不是整数）
9 Z4 Q6 l5 j  ?: z  ^; o( @存在最优解（最优解为整数）
0 G2 k6 L; X3 t8 c1 t8 M; v; T有可行解（最优解值变差）
7 z. G2 J$ n9 u& e2.2 0-1整数规划

0 f8 b; s, P4 c! F3 w定义：变量x仅取值0或1，即0-1变量
2 u2 ^# x2 }5 l+ o
2.2.1 相互排斥的约束条件

引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
若有m个互相排斥的约束条件
5 L# R0 K$ b8 ]0 B, _/ w
$ M" v8 i6 ~) U1 H% t
1 S* `1 d' a; \$ q8 s需保证只有一个起作用，则引进m个0-1变量：

  V7 T5 n, F, {8 H# J
和一个充分大的常数M，则有：
: H" L* A: f4 r' n8 y% j+ K
2.2.2 混合整数规划（固定费用）

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

; F- B* z- X( P. a
y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：



9 h% J& _* e- U5 J2 K4 O8 c5 V$ V2.2.3 指派问题

关键：给出系数矩阵C
% v4 G# a% @) w6 m规划模型为：（x为引入的0-1变量）

0 q$ [% B3 w( H

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

目的：求解非线性整数规划
8 P" \' C/ W7 Z  w- q$ w8 ?matlab程序如下：
  定义目标函数 f 和约束向量函数 g

求解问题

# S$ }( T7 s. z
2 X6 I$ T1 ~9 J4 H2.4 整数线性规划的计算机求解

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

; v4 {  ?* P- }( {: C7 R



————————————————
6 A( z" [2 y9 Z: r- |; v3 N
版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
( K; F$ J, k0 v: v: m- `8 O; Q3 G4 M原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

# [+ c$ f' ?4 j! C- j$ O6 e
' R2 ?/ j" Z  r/ n9 I————————————————
# |- b) U# p3 f9 t- {4 M, O: L- h- @/ R原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
0 ?' W( `9 o0 I! H$ _7 t1 z
1 c: o6 s' l/ j7 x9 V