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

杨利霞

数学建模算法与应用第二章：整数规划
: F2 M0 b0 f+ u- q% N9 U
: ]9 ]; S! Z! i( Q2.1 基本概念
; Z9 o* y, k* T7 U4 I4 ~
: T. @, {3 X/ b) l整数规划：数学规划中的变量（部分或全部）限制为整数
0 M' @$ C3 p. n: k目前只能求解整数线性规划
整数规划的解有如下三种情况：

没有可行解（最优解不是整数）
存在最优解（最优解为整数）
& u3 h8 U" o1 u3 Q  |+ H, S有可行解（最优解值变差）
2.2 0-1整数规划

" H9 ?! K% ~, _  ^( N, ?" l定义：变量x仅取值0或1，即0-1变量

2.2.1 相互排斥的约束条件
$ k; ?: \" t% S! b% p5 M; y& v1 v
引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
5 j$ o" u  M$ n8 {7 }* q3 {" f若有m个互相排斥的约束条件


/ ]8 U% m1 |- p* i8 n4 y6 [5 V需保证只有一个起作用，则引进m个0-1变量：

3 Y! K) \& [% t; v( s
和一个充分大的常数M，则有：

; G+ C$ f. i( f9 O% y# E4 E2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
6 B* \: m# E9 }0 j4 I9 E! d可用约束条件：

6 C$ b2 J4 }6 l$ |
( t  U  R2 a, p$ k* F4 Wy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
0 Y) V) S1 [9 z9 n7 H
, J9 I% _( t$ w' z2 B$ q) q' m$ @8 Y
, c% h1 B3 Z1 Q
2.2.3 指派问题

关键：给出系数矩阵C
! B- A) m& K7 x$ _$ [. w* J3 {规划模型为：（x为引入的0-1变量）

, k: A) F6 |: V3 S9 M! I
2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
  定义目标函数 f 和约束向量函数 g

求解问题
7 U- ], T" m. M

2.4 整数线性规划的计算机求解

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

0 i$ h$ g9 D$ L, V/ z: u
9 K* ?) T$ G8 _


————————————————
0 @! r3 ~' p& O! B: K
版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
) U- ?% X5 K* a原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231


9 g" k; q. h* y, W# ]  g————————————————
3 [+ _6 g( q' l! b$ t- w; F原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
9 V# S* j: O" Q3 ]: [4 J8 E% x0 C
( z7 h3 p& T, {