【数学建模】线性规划

佛自业障

1.线性规划简介

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

2 I: |, y6 @! Q. J0 W! w$ x
6 r2 K* z( W2 y8 M9 v* Q2 _x1,x2为决策变量，约束条件记为s.t.（subject to）。

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

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

' @2 e$ b1 c$ L( S6 m8 j$ l4 o- r
其中c和x均为n维列向量，A、Aeq为适当维数（列数与x维数相同，行数与约束条件数相同）,b、beq为适当维数的列向量（维数与约束条件数相同）。
. D9 z& Z! f' \: z
- p  I4 d  L8 z$ Z例如：
max  cTx  s.t.   Ax≥b max  cTx  s.t.   Ax≥b
4 }; V" m  u' ?( g5 L( f6 u) ^: qmatlab中为：
min  −cTx  s.t.   −Ax≤b min  −cTx  s.t.   −Ax≤b
0 v; l% a$ c, s4 r1 J5 w3.线性规划中解的概念

: r+ Z( K  q1 i0 u! z可行解：满足约束条件的 解x = （x1,x2…xn），称为线性规划问题的可行解，从而使目标函数达到最大值或者最小值的可行解称为最优解。
可行域：所有可行解构成的集合称为问题的可行域，记为R。
8 q) T. ~0 i( d5 }% `( u( G
4.一般的线性规划问题
* o: g& l! |1 p- c5 @
在一般的n维空间中，满足 ∑ni=1aixi = b∑i=1naixi = b 的点集称为一个超平面，而满足 ∑ni=1aixi ≥ b∑i=1naixi ≥ b （或者∑ni=1aixi ≤ b∑i=1naixi ≤ b ）的点集称为一个半平面，若干个半平面的交集称为多胞形，有界的多胞形称为多面体。因此线性规划的可行域必定为多胞形（空集也视为多胞形）。若该区域R为凸集，则凸集中的任意两点的连线必然在该凸集中，若x为区域R的极点，则x不能位于R中的任意两点的连线上。
8 t3 N2 B$ A3 v
5.matlab中线性规划求解过程

* X3 o5 a" f+ [7 o5 R! J; P% G① 利用linprog函数返回最小值解向量。
② value = c’ * x求最小值。
8 P) L0 h3 F1 h& W$ Z
& C  ^5 ^" N) T: O基本函数形式是 linprog(c,A,b) , c用于确定等值线（列向量），返回值为向量x。
- I  @7 y- {& L- K" Y/ \其他的函数形式：
[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,x0,OPTIONS)
3 B4 i% P3 g- ]3 }# \x0为向量x的初始值，一般使用zeros()函数 初始化，LB和UB分别是向量x的下界向量和上界向量。返回值为fval（目标函数c’ * x的值）。
; J+ t) I' E7 E% o+ d5 ^$ E$ [
6.常见技巧

) \9 x& H8 E# @8 ^2 |问题为：

  j6 s* E3 `7 {/ kmin|x1|+|x2|+…+|xn|  s.t.  Ax≤b min|x1|+|x2|+…+|xn|  s.t.  Ax≤b  
+ H5 n- \' U: A* L, D0 n! d) @5 p1 T事实上，对于任意的xixi，存在ui,viui,vi满足：
xi=ui−vi  ,  |xi|=ui+vixi=ui−vi  ,  |xi|=ui+vi
2 B! B# E# W$ z1 E7 m! K令 ui=(xi+|xi|2),vi=(|xi|−xi2)ui=(xi+|xi|2),vi=(|xi|−xi2)即可满足。
$ v+ V7 e) O( Z
9 _' o$ ?0 K1 L: S$ r0 ]& u2 j. ?转换为：
2 F" n( r; z5 W! l) b$ H. smin  ∑ni=1(ui+vi)min  ∑i=1n(ui+vi)
( E2 K4 q& U% K# U8 }* n; ]: r$ Qs.t.{A(ui−vi)≤b,u,v≥0,s.t.{A(ui−vi)≤b,u,v≥0,
7.运输问题（产销平衡）

8.指派问题

1.数学模型

2.利用匈牙利算法
6 E& ^! j$ ^" Q9 L算法主要思想：如果系数矩阵中C=(cijcij)一行（或一列）中每一个元素都加上或减去同一个数，得到新矩阵B，则以B或C为系数矩阵的指派问题具有相同的最优指派。
最优指派的结果是一个2行n列的行列式，第一行为第i人，第二行为被指派的地点。
求解中心：变换出n个不同行不同列的零元素。
" L& L) R7 t/ Q: j! X
6 L+ B& G6 L  V" W& v2 a4 q
: m& G  Y" h* p9 r# d7 ~& G
# E7 m. l8 Y8 `/ j- _7 x+ ]! T