【数学建模】线性规划

佛自业障

1.线性规划简介

线性规划（LP）是数学规划的一个分支。

. n5 ^! r/ S: r8 \* i" ]
8 D* m6 \3 c4 I& @, B* x# H  Gx1,x2为决策变量，约束条件记为s.t.（subject to）。
1 G# s( {! e: Y1 D

2.线性规划的matlab标准形式

线性规划的目标函数可以求最大值也可以求最小值，约束条件的不等号可以是小于号也可以是大于号，因此在matlab中给出了统一形式

+ d9 A9 \: w1 F: ]4 F$ Z其中c和x均为n维列向量，A、Aeq为适当维数（列数与x维数相同，行数与约束条件数相同）,b、beq为适当维数的列向量（维数与约束条件数相同）。

/ ]  g5 V6 {9 ]6 ?( Y" A, D例如：
3 K! x1 C+ K/ R" S: ~3 u. p9 y8 tmax  cTx  s.t.   Ax≥b max  cTx  s.t.   Ax≥b
( s( T; ?$ O3 J3 dmatlab中为：
& q# F4 _; H% ]min  −cTx  s.t.   −Ax≤b min  −cTx  s.t.   −Ax≤b
3.线性规划中解的概念

: ~; W; O4 @" j+ q7 X3 d可行解：满足约束条件的 解x = （x1,x2…xn），称为线性规划问题的可行解，从而使目标函数达到最大值或者最小值的可行解称为最优解。
$ n+ n3 q  f4 O, y, c6 }: M可行域：所有可行解构成的集合称为问题的可行域，记为R。
3 G( T7 O  j! K. {2 k: h# r  {
9 @3 B7 p8 `) y) L% _- X4.一般的线性规划问题
: ?- I" M; ^* `+ c3 c3 R( g8 J
2 I1 @1 `- J+ M5 l* [# w在一般的n维空间中，满足 ∑ni=1aixi = b∑i=1naixi = b 的点集称为一个超平面，而满足 ∑ni=1aixi ≥ b∑i=1naixi ≥ b （或者∑ni=1aixi ≤ b∑i=1naixi ≤ b ）的点集称为一个半平面，若干个半平面的交集称为多胞形，有界的多胞形称为多面体。因此线性规划的可行域必定为多胞形（空集也视为多胞形）。若该区域R为凸集，则凸集中的任意两点的连线必然在该凸集中，若x为区域R的极点，则x不能位于R中的任意两点的连线上。
% E5 d) D7 k4 R" U8 U
5.matlab中线性规划求解过程

① 利用linprog函数返回最小值解向量。
② value = c’ * x求最小值。
) a1 [: {! F8 i& \; {" I* G
: ?0 S% {. Z% U6 ^2 @. @3 H- M基本函数形式是 linprog(c,A,b) , c用于确定等值线（列向量），返回值为向量x。
) e# X! ?) o  D& V% d6 n; L9 Z其他的函数形式：
[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,x0,OPTIONS)
6 P) T4 ^& ]4 ~6 Y+ Xx0为向量x的初始值，一般使用zeros()函数 初始化，LB和UB分别是向量x的下界向量和上界向量。返回值为fval（目标函数c’ * x的值）。

6.常见技巧
- X: h8 E' C6 M! v
1 b$ E7 {* s7 I问题为：

min|x1|+|x2|+…+|xn|  s.t.  Ax≤b min|x1|+|x2|+…+|xn|  s.t.  Ax≤b  
+ j! M8 O  F0 J" o- c* r9 T事实上，对于任意的xixi，存在ui,viui,vi满足：
1 [) X+ Y+ q! U3 Z8 H- [7 exi=ui−vi  ,  |xi|=ui+vixi=ui−vi  ,  |xi|=ui+vi
( {& ]* Y5 t- I令 ui=(xi+|xi|2),vi=(|xi|−xi2)ui=(xi+|xi|2),vi=(|xi|−xi2)即可满足。

转换为：
6 A( Z' ]2 [- L1 q3 o- o+ G/ _min  ∑ni=1(ui+vi)min  ∑i=1n(ui+vi)
8 F0 x9 A  G2 K; w3 M- g/ Js.t.{A(ui−vi)≤b,u,v≥0,s.t.{A(ui−vi)≤b,u,v≥0,
; ?; v) \$ o: ]7 `5 g7 [% m7.运输问题（产销平衡）
0 ?$ J; j/ Z5 m

# H* D& K. c  H$ x! O, F. j

8.指派问题

1.数学模型
0 y% R- U& _" }# E( \

  m. `2 y7 x8 c6 f3 r
. g4 t0 _, a* t0 X; z. M0 |2.利用匈牙利算法
算法主要思想：如果系数矩阵中C=(cijcij)一行（或一列）中每一个元素都加上或减去同一个数，得到新矩阵B，则以B或C为系数矩阵的指派问题具有相同的最优指派。
最优指派的结果是一个2行n列的行列式，第一行为第i人，第二行为被指派的地点。
求解中心：变换出n个不同行不同列的零元素。
- X" o* X) u8 {4 s* `1 F


% r0 v. w- x- ]/ H3 i