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

杨利霞

数学建模算法与应用第二章：整数规划
& [  n, O6 I4 }8 J4 c/ q2 G/ z; J
2.1 基本概念

整数规划：数学规划中的变量（部分或全部）限制为整数
9 `. j  n' R" U: Z- u! Y: H目前只能求解整数线性规划
整数规划的解有如下三种情况：

( i1 ~7 F" m" g( \没有可行解（最优解不是整数）
存在最优解（最优解为整数）
有可行解（最优解值变差）
2.2 0-1整数规划
! I5 _3 C! C/ S& A) M; [
定义：变量x仅取值0或1，即0-1变量

$ u* F5 [9 ]1 a. J2.2.1 相互排斥的约束条件

# @; q1 x8 b2 s) k8 d9 f  i$ q/ Q4 E  n引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
改为普通的约束条件（不常用）
# h/ {" h, e5 x4 m8 k; \若有m个互相排斥的约束条件


需保证只有一个起作用，则引进m个0-1变量：


. Z+ q# E- F0 \和一个充分大的常数M，则有：
5 @( E8 l. D' {6 _! f- x
7 W9 e' H1 b* Y$ ^, R2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
* I4 n7 P% L1 }( T4 k0 O可用约束条件：

3 T! o' f: U6 L3 ~9 M0 l- W
y为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
1 W1 H; l8 b) f上式即代替了该分段函数：

5 V# j1 W1 K* d8 ^% \+ O
3 U7 i2 U  M* v. r$ v( q
- s" a! E" x6 P, Z( l8 b2.2.3 指派问题

关键：给出系数矩阵C
/ Q$ z# `9 I& U7 K: @5 P4 G8 t2 ~0 S规划模型为：（x为引入的0-1变量）

/ K+ s, ]$ X7 L$ `" W

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

目的：求解非线性整数规划
0 m6 s: o2 X' h* L6 K3 J* h8 Xmatlab程序如下：
9 w) x4 }( p6 c* }) {  定义目标函数 f 和约束向量函数 g

求解问题


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

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

! B3 w! x1 G0 ]9 F! k# @# V

* H+ k* l! c5 `
0 K# v3 g$ e% O5 W————————————————
! M  L* a. \1 j% }6 D
- C0 }) R' \2 g* c9 B版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231


! |9 t0 ]# ~1 D6 S% q" d% [: W1 i————————————————
8 {  I( |6 c' C$ j. G原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231


* ?7 t8 x2 l! V; d; q3 x. Z& Q2 J