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

杨利霞

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

2.1 基本概念
9 k5 a4 K7 ^3 L4 z
整数规划：数学规划中的变量（部分或全部）限制为整数
* u) @, w$ s9 m( A/ t3 n7 E1 W, X目前只能求解整数线性规划
整数规划的解有如下三种情况：
2 l' v+ ^4 j0 i5 f( h
没有可行解（最优解不是整数）
存在最优解（最优解为整数）
有可行解（最优解值变差）
2.2 0-1整数规划

& Q2 n6 H8 f3 i0 _6 q- X  l定义：变量x仅取值0或1，即0-1变量
" o* _* H" e" P, F$ J; H
; U& y5 p$ Z7 \, ^8 e! ]5 j% ?/ _2.2.1 相互排斥的约束条件

引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
6 R/ t3 x2 ]7 n2 I- h, M! a改为普通的约束条件（不常用）
! `7 \" q; J/ ]. P9 |& ]若有m个互相排斥的约束条件
1 ^0 L8 N, f; B# V- D8 r1 m

需保证只有一个起作用，则引进m个0-1变量：
) Q$ d  ^8 t  ~% o4 j. O3 L

, j/ f) Y' m% ^+ l) \! a- N( a. s和一个充分大的常数M，则有：

3 ?' b3 X/ y6 |/ k, Y2.2.2 混合整数规划（固定费用）

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

3 G9 z4 q" w2 k6 }) ^) p2 b; S
4 W5 Z/ T8 y# oy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
上式即代替了该分段函数：

' H3 e" l! g" p" }& J
5 N/ P0 r1 w. B$ @' L
2.2.3 指派问题

关键：给出系数矩阵C
* f$ e+ a; F8 e规划模型为：（x为引入的0-1变量）

: q/ O  X+ n! G; \8 }! P
( B2 }: X# a7 S- b* Y3 g1 H
2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
matlab程序如下：
9 ~1 F" Z: |& w  定义目标函数 f 和约束向量函数 g

求解问题

" @* M- A* z# @! K) u
! O# K" q* Q7 u2 t) @9 b2.4 整数线性规划的计算机求解

matlab求解混合整数线性规划，用intlinprog函数，但必须把所有的决策变量化成一维决策变量，即需要做变量替换。
" p4 U' Y9 I' W" ?1 k( m6 Z# M  标准形式为：

/ Y2 x+ b/ Q  a1 b
3 z6 n$ x" A* V: M  M- T9 l. S
6 z/ }. I; `1 o( G0 _$ j6 @
- U: i0 N' I* h8 r$ {
————————————————
5 m/ y  _' m  r. b
7 U: R3 }$ i" s3 E% G% d. @' R版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

5 t- S% K# d' ]( r1 g) m9 `. D
+ b0 X2 D2 {; N, T5 {6 i1 R————————————————
, |. B2 M% o3 Y7 U原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231
9 {; u9 e/ t3 ~# M% n- W