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

杨利霞

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

2.1 基本概念
& [! a1 E1 {( e1 R
整数规划：数学规划中的变量（部分或全部）限制为整数
0 a2 `4 H' n# K' R: f' K& D7 X% E; _目前只能求解整数线性规划
* |9 @7 B! i  l! ]整数规划的解有如下三种情况：

- t9 S1 u- n5 b8 U+ p. B没有可行解（最优解不是整数）
存在最优解（最优解为整数）
" ]8 A4 A) o5 J; y有可行解（最优解值变差）
2.2 0-1整数规划

定义：变量x仅取值0或1，即0-1变量
! ^3 Q6 u9 i* H
. ~0 Z4 n! A, @0 S# i1 L' W  O# W2.2.1 相互排斥的约束条件
. O" U6 ~5 B$ C, a( C
3 U8 i5 Q: U* U& R引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
$ {6 |( l" N! Q. G3 y' H改为普通的约束条件（不常用）
若有m个互相排斥的约束条件


需保证只有一个起作用，则引进m个0-1变量：
, f+ u6 I  m& |+ I9 g1 \6 R! m

  s$ B, P. u' ]0 h和一个充分大的常数M，则有：

2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
9 e+ U. X7 G2 I$ J4 B' _6 f$ K可用约束条件：

y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
  B0 p# A: h' `9 C0 i: P9 r7 A
$ R) y& C0 U9 M" q. o
% h8 f; V; o" k) |$ R' _" {
2.2.3 指派问题

关键：给出系数矩阵C
1 R; J' x4 t6 p  Z5 ]规划模型为：（x为引入的0-1变量）

+ T# ]) f( L/ Z9 q2 W% p" Z

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

目的：求解非线性整数规划
# _& C! ~; m7 i& l, y3 J; ematlab程序如下：
$ G5 \& i% z9 e5 ^3 r  定义目标函数 f 和约束向量函数 g

- `# L1 Q+ o  d1 ^* @求解问题
# W' S6 a9 ]/ n- O/ k# G

+ e( V0 X5 U5 _$ L$ ]2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
- A7 }6 ~. J1 e- ~. i9 f( J$ k% h  标准形式为：

- G4 M: ^% w7 g+ b0 |

; J9 D1 s; N7 R* m. }
( [! S6 x6 x9 ]- G6 \; ~$ U- p5 h
————————————————
3 M8 x1 }/ ~# z$ x( J
+ P' R9 o$ Z3 R* O版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
/ j/ l9 D5 M7 \$ |. f9 L原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

' ?  ]1 ?8 o" n( t* P# z; n6 Y; i
7 p8 U  j+ m( l; V) d————————————————
7 s9 W$ D: p7 f# T6 O原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231