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

杨利霞

数学建模算法与应用第二章：整数规划
" W3 S' x/ z/ Z& [
, ?  z4 Y! B) ^0 }2.1 基本概念
3 d/ m. R7 k* v
整数规划：数学规划中的变量（部分或全部）限制为整数
$ n3 @4 X+ d5 [; G  Q1 c目前只能求解整数线性规划
整数规划的解有如下三种情况：

没有可行解（最优解不是整数）
存在最优解（最优解为整数）
有可行解（最优解值变差）
4 z6 ^: Z  w3 V2.2 0-1整数规划

( {/ m( G4 E: w定义：变量x仅取值0或1，即0-1变量

2.2.1 相互排斥的约束条件

1 c. t% a8 m: J2 H; g  `7 K. T* j3 U引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
* c: `; B) @* k- S, f若有m个互相排斥的约束条件
* T1 R0 y# T( Q2 S5 J7 h
  u, _2 \+ n% x7 K
! Q7 `% ^$ G7 ?+ l1 s$ \需保证只有一个起作用，则引进m个0-1变量：
+ }; F# x* K4 t- B, U, u

. M+ q" ], ?; J" A& \和一个充分大的常数M，则有：
# ]. u/ U4 r/ G; [7 o. `
2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
% p) M( J7 J  |可用约束条件：

; Q8 L4 q7 D9 B. V
, w# J8 Z- }' q7 p  I8 r1 m0 Fy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：



! Y& l$ L* V, T$ \4 B% B2.2.3 指派问题

关键：给出系数矩阵C
+ J" ]: Z! d1 N+ M* o规划模型为：（x为引入的0-1变量）

" A1 q% E+ r5 u* G. b* w2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
2 Z  n. o7 J. C9 R( jmatlab程序如下：
5 ]  L/ m5 _7 N+ r( D) d# s  定义目标函数 f 和约束向量函数 g

求解问题

. e: I7 i. U$ a7 J
* A* m* \5 t9 Q& ~  Z5 U4 L4 T7 c2.4 整数线性规划的计算机求解

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

  Y" W; N* [0 k# Q% T

# B4 c7 S* \) t4 W
0 O; q; z' D" X! p6 d" H
0 @: E* B3 I) }————————————————
5 G, o/ y( \4 D1 q
* e- I. Y) ~" f版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
# y: |; U( U0 W7 s' R+ u- b
. U7 P+ Q' `. |2 T, m6 \$ l
————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
& L# C8 B* }. G5 c% T, E
5 |/ T0 x6 A0 m
6 C  h8 J7 X7 t0 X6 Q& P