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

杨利霞

数学建模算法与应用第二章：整数规划
' [1 I9 t$ @3 k; T. g2 u
2.1 基本概念

整数规划：数学规划中的变量（部分或全部）限制为整数
2 F# D5 G0 U0 T* V& n9 l3 U/ ^目前只能求解整数线性规划
: P+ W  O) L* w整数规划的解有如下三种情况：
4 y* c! |  K4 |, K
# D- I0 O1 {1 M$ W# I* T没有可行解（最优解不是整数）
5 Q$ {2 @0 s9 W; w存在最优解（最优解为整数）
有可行解（最优解值变差）
2 A% Q+ A: w1 r+ a) E2 z2.2 0-1整数规划

* `. N# s" U) ~2 A- p* w- \7 C定义：变量x仅取值0或1，即0-1变量
! P% H) [6 F1 {2 o
2.2.1 相互排斥的约束条件

引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
" A! j& L  V$ g: u2 Z$ W) M若有m个互相排斥的约束条件
2 d. @1 Q7 }' G% L5 e3 _

# P4 ^2 h& |7 S2 C* Z$ Z需保证只有一个起作用，则引进m个0-1变量：
% B% Q6 T. h; F8 |  j

和一个充分大的常数M，则有：

; c' S# P( l: h- U2.2.2 混合整数规划（固定费用）

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

. [/ i3 o! X, U7 `% c1 u& G' v
y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：

6 P$ [8 {' L( n; g8 ]* d, a7 F$ Z

2.2.3 指派问题

关键：给出系数矩阵C
3 _3 j4 T! E# c规划模型为：（x为引入的0-1变量）

, }- j, K7 W3 a7 {$ y! A
( U2 q: n# S# h$ \, Y7 s, C0 @, i& h
0 j8 @7 o5 j# l9 n- H9 I2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
- l1 Z" }6 v: e! B% w3 Q$ Q) u; S4 h1 \matlab程序如下：
* D" H6 v- \- x( s) ?; |  定义目标函数 f 和约束向量函数 g

- J8 b! E' l0 W! @1 Q求解问题
6 R1 g) M+ K  }6 R  Q+ [
+ A) H# G# [* u) {- X) O9 \
2.4 整数线性规划的计算机求解

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

1 S# G1 w& V; y1 A
6 [/ T9 Q, j& T5 X# m# u

4 e' i: j; R* U7 j. a
) M; _7 o) N7 a, k————————————————
9 _+ U+ o/ v9 ?4 k7 O2 N  O
8 Y9 d/ V! t# U2 z: A  g) \. B版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

6 G( c+ j8 K6 i
9 L: d" Q# o0 M————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

. _& y, k1 _" C
+ u7 b; ?" O% p# T4 X3 O