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

杨利霞

数学建模算法与应用第二章：整数规划
. m0 Y1 R' c  S6 K% S! F
& C' U6 U; H' h- e" o  Z2.1 基本概念

6 \% G( |3 [1 J$ x9 b) i# S5 c( T整数规划：数学规划中的变量（部分或全部）限制为整数
, |& s' V# [% j  @目前只能求解整数线性规划
整数规划的解有如下三种情况：
2 j& W* l5 a3 w* f
没有可行解（最优解不是整数）
2 K2 t' Y: D- ^存在最优解（最优解为整数）
8 G* v6 v: o: r8 Y# T- Z! {' k有可行解（最优解值变差）
2.2 0-1整数规划
' U6 }2 ~. c$ ~: m: a' j5 F
, |  r$ L5 i( ~8 X定义：变量x仅取值0或1，即0-1变量

* n: _  S1 O  ~* \2.2.1 相互排斥的约束条件

引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
若有m个互相排斥的约束条件


( j! D8 }$ B( Z4 I$ T9 X& k  `+ X需保证只有一个起作用，则引进m个0-1变量：


$ S/ U2 e( K$ l! ]' h' v和一个充分大的常数M，则有：
$ ~5 m; V5 }: x4 g9 |+ F8 i: q
2.2.2 混合整数规划（固定费用）

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

y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：
4 l' u3 s* Z+ F" {

1 C. c5 a) K& j' }5 C
2.2.3 指派问题

关键：给出系数矩阵C
9 d: e: g" V, Y" x/ j规划模型为：（x为引入的0-1变量）

- B) q! v$ ?) @- b

; p3 c1 i. ~. a3 n0 F1 J* o2 f2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
' i0 ~7 N. M% T* C9 w$ K, r* l/ R, V3 Y  定义目标函数 f 和约束向量函数 g

7 ]* t3 M' B7 Q& a
" B+ X1 ~) z( D, C- M$ i) }求解问题

' b5 k! T# }+ h( ?
$ D9 {4 \+ i% {2.4 整数线性规划的计算机求解

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

# _9 Z( t  a! D. v

5 L- z- D  u5 R$ ?
* e" s' X3 U+ T$ u$ {
0 p* Z2 I* c% y! ?( L* f9 D6 N& z————————————————

+ o) ?6 p/ I$ ~0 v0 n5 Q1 w8 d版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231


————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231