【数学建模】线性规划

佛自业障

1.线性规划简介

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

1 a! G) U+ z" R+ o5 K! c& O& u" x
; A6 H6 r, w" u) Ox1,x2为决策变量，约束条件记为s.t.（subject to）。
3 q: h1 V# J+ ]4 j5 T6 A8 o* K' R

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

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

其中c和x均为n维列向量，A、Aeq为适当维数（列数与x维数相同，行数与约束条件数相同）,b、beq为适当维数的列向量（维数与约束条件数相同）。

" r/ ~; ~0 |; b例如：
2 u$ [; m& k' U2 p, Y' ]/ }0 V1 Imax  cTx  s.t.   Ax≥b max  cTx  s.t.   Ax≥b
% y% T' w3 R5 q9 Pmatlab中为：
; u1 @0 ^  U: dmin  −cTx  s.t.   −Ax≤b min  −cTx  s.t.   −Ax≤b
5 T8 J1 \' `5 z* O- a3.线性规划中解的概念

, H  L; _# E& W可行解：满足约束条件的 解x = （x1,x2…xn），称为线性规划问题的可行解，从而使目标函数达到最大值或者最小值的可行解称为最优解。
: n$ K( J3 a% b' t$ p7 N可行域：所有可行解构成的集合称为问题的可行域，记为R。
+ |$ z3 e. q  K8 G$ n
3 [- o3 ]0 Y5 s( B! a/ I4.一般的线性规划问题
5 y8 r0 R5 a8 V% f4 L! S
在一般的n维空间中，满足 ∑ni=1aixi = b∑i=1naixi = b 的点集称为一个超平面，而满足 ∑ni=1aixi ≥ b∑i=1naixi ≥ b （或者∑ni=1aixi ≤ b∑i=1naixi ≤ b ）的点集称为一个半平面，若干个半平面的交集称为多胞形，有界的多胞形称为多面体。因此线性规划的可行域必定为多胞形（空集也视为多胞形）。若该区域R为凸集，则凸集中的任意两点的连线必然在该凸集中，若x为区域R的极点，则x不能位于R中的任意两点的连线上。
! X( G+ O2 `" n
5.matlab中线性规划求解过程

① 利用linprog函数返回最小值解向量。
4 f5 l9 t6 C$ e- h② value = c’ * x求最小值。
" j& g9 n$ m2 ]. M' a
- B0 D' Q- a: m4 Z8 Q/ G基本函数形式是 linprog(c,A,b) , c用于确定等值线（列向量），返回值为向量x。
其他的函数形式：
- z! g7 d' ?$ @' {- ]/ q$ W[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,x0,OPTIONS)
x0为向量x的初始值，一般使用zeros()函数 初始化，LB和UB分别是向量x的下界向量和上界向量。返回值为fval（目标函数c’ * x的值）。
5 p9 @* `% f4 m/ l4 ~# U$ [
6.常见技巧

: W, r. v4 {  j" }问题为：
$ |, P, q7 h1 d+ d, ~5 I
2 L0 y3 Y2 k+ ~5 J+ m# r7 {, n) Jmin|x1|+|x2|+…+|xn|  s.t.  Ax≤b min|x1|+|x2|+…+|xn|  s.t.  Ax≤b  
' g5 ^7 i& o. Y+ y事实上，对于任意的xixi，存在ui,viui,vi满足：
xi=ui−vi  ,  |xi|=ui+vixi=ui−vi  ,  |xi|=ui+vi
7 U. b( v$ [2 j/ t- s8 ?令 ui=(xi+|xi|2),vi=(|xi|−xi2)ui=(xi+|xi|2),vi=(|xi|−xi2)即可满足。

转换为：
* g0 C+ H: R  x6 T+ t! gmin  ∑ni=1(ui+vi)min  ∑i=1n(ui+vi)
$ l; ^1 X4 l: ]s.t.{A(ui−vi)≤b,u,v≥0,s.t.{A(ui−vi)≤b,u,v≥0,
7.运输问题（产销平衡）
0 v) N6 N0 ^& j6 y6 q/ x

5 n$ E! A8 @* u

8.指派问题

1.数学模型
) v1 M3 J' d' _/ K" ~6 `

$ _" T! r( m2 t# M' T% v2.利用匈牙利算法
算法主要思想：如果系数矩阵中C=(cijcij)一行（或一列）中每一个元素都加上或减去同一个数，得到新矩阵B，则以B或C为系数矩阵的指派问题具有相同的最优指派。
7 |& e4 G3 h: B- R6 n5 O最优指派的结果是一个2行n列的行列式，第一行为第i人，第二行为被指派的地点。
求解中心：变换出n个不同行不同列的零元素。
8 @! f, F6 X; Q; M1 Y( m4 G
8 @1 g( \6 s3 `0 T

; u* x& k5 _: J$ i4 W! a