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

杨利霞

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

2.1 基本概念
; c) k$ E+ m1 U7 Z1 m$ _$ y; }  M
整数规划：数学规划中的变量（部分或全部）限制为整数
! r9 z2 X- g  R) U" h. K1 b目前只能求解整数线性规划
整数规划的解有如下三种情况：
% _' P& h- u5 X3 m4 K, P: n
没有可行解（最优解不是整数）
& \$ W( A; S4 {! p9 O存在最优解（最优解为整数）
8 J4 T# D2 F3 o" \2 H+ K* Q8 `  F有可行解（最优解值变差）
% N. x( G& K7 @2.2 0-1整数规划
) j; j. l8 s. L( a) c! P
! W) P( e2 P- z4 j* u定义：变量x仅取值0或1，即0-1变量

0 `  M% X: D2 E9 p2.2.1 相互排斥的约束条件

7 n+ M! u; X# S! x7 ?6 i引进一个充分大的数，削弱取一种情况时另一种情况下的约束条件
( ~- H4 s$ M% s# `8 j; m改为普通的约束条件（不常用）
& B8 t% _) @8 @" z( n" W若有m个互相排斥的约束条件


1 ^/ @" a8 w2 @, k! U$ P% q需保证只有一个起作用，则引进m个0-1变量：
) ]- A- z% p# e+ L

# W3 c4 }# t) D6 j% O7 n, Y; O5 c和一个充分大的常数M，则有：

! s# c$ t( ^1 P9 M2.2.2 混合整数规划（固定费用）

定义：变量部分限制为整数
9 L: w$ b: f7 u# h, A可用约束条件：

, u+ r. N4 ^& n4 uy为引入的0-1变量，ε \varepsilonε为充分小的正常数，M为充分大的正常数
2 g+ }$ ?  Q, Q  i$ b2 j上式即代替了该分段函数：


2 ?1 O1 a* p) W4 K" _2 m
2.2.3 指派问题

关键：给出系数矩阵C
规划模型为：（x为引入的0-1变量）

  K' v6 @. M- w9 V1 \. y. n! W; y
; b# s2 c7 O' U& K2 M/ w0 o( w2.3 蒙特卡洛法（随机取样法）

目的：求解非线性整数规划
) `  ]. T0 z/ G6 tmatlab程序如下：
  定义目标函数 f 和约束向量函数 g

' c' _* G! t& t- i0 R) b
求解问题
6 y0 X. L; Q" t7 M: e3 b
) W" H( [. |7 I7 h2 d  k) g" q
2.4 整数线性规划的计算机求解

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

# }0 i* A: {- |4 r* T$ D

8 I9 m" G  T7 ]
————————————————

3 X6 l) Z( H' i% E3 b8 I版权声明：本文为CSDN博主「victor_cs_bit」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231

( j- U9 I$ V6 ^( q! A
0 [, j% h, c) I9 l% k————————————————
原文链接：https://blog.csdn.net/qq_41000485/article/details/96478231


5 C5 V- G( y7 J, h0 \; R3 i% J$ ^