【数学建模】线性规划

佛自业障

1.线性规划简介

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

! J* j! O6 o6 ^! e- H& y/ m4 px1,x2为决策变量，约束条件记为s.t.（subject to）。

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

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

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

例如：
7 v+ }' Z1 C0 E% `" ~% V; y$ omax  cTx  s.t.   Ax≥b max  cTx  s.t.   Ax≥b
matlab中为：
( Z8 K, [5 D# O+ S% Smin  −cTx  s.t.   −Ax≤b min  −cTx  s.t.   −Ax≤b
3.线性规划中解的概念

- C+ C/ e+ \. q# N可行解：满足约束条件的 解x = （x1,x2…xn），称为线性规划问题的可行解，从而使目标函数达到最大值或者最小值的可行解称为最优解。
可行域：所有可行解构成的集合称为问题的可行域，记为R。
. q9 w0 c  ]' L% c4 V8 M  i8 J
  s5 @. Q, L- _9 H( {2 c4.一般的线性规划问题
/ W5 a7 t8 C& J- X
在一般的n维空间中，满足 ∑ni=1aixi = b∑i=1naixi = b 的点集称为一个超平面，而满足 ∑ni=1aixi ≥ b∑i=1naixi ≥ b （或者∑ni=1aixi ≤ b∑i=1naixi ≤ b ）的点集称为一个半平面，若干个半平面的交集称为多胞形，有界的多胞形称为多面体。因此线性规划的可行域必定为多胞形（空集也视为多胞形）。若该区域R为凸集，则凸集中的任意两点的连线必然在该凸集中，若x为区域R的极点，则x不能位于R中的任意两点的连线上。

5.matlab中线性规划求解过程
! I, [1 E1 e! s& F& [" @. ^5 o; r+ P
! d, k( _. g% y- F" v5 o① 利用linprog函数返回最小值解向量。
/ L* m8 c$ N4 k$ v3 O4 R② value = c’ * x求最小值。

- F5 u* S: R1 V, u$ t: S7 ?基本函数形式是 linprog(c,A,b) , c用于确定等值线（列向量），返回值为向量x。
5 \9 R6 K8 @" v8 t9 }  U: w5 W% [其他的函数形式：
3 d: |1 G- g- e% X5 P% q+ H* [[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,x0,OPTIONS)
x0为向量x的初始值，一般使用zeros()函数 初始化，LB和UB分别是向量x的下界向量和上界向量。返回值为fval（目标函数c’ * x的值）。
8 m, W( o. J! G3 K: z
6.常见技巧

问题为：
6 w6 q" J+ H1 W1 n$ U2 M% g
min|x1|+|x2|+…+|xn|  s.t.  Ax≤b min|x1|+|x2|+…+|xn|  s.t.  Ax≤b  
事实上，对于任意的xixi，存在ui,viui,vi满足：
xi=ui−vi  ,  |xi|=ui+vixi=ui−vi  ,  |xi|=ui+vi
& {7 B. {/ P7 S# q3 b- ~' n9 O令 ui=(xi+|xi|2),vi=(|xi|−xi2)ui=(xi+|xi|2),vi=(|xi|−xi2)即可满足。
- A0 N6 L+ Z1 }; _
7 s& y% A- ?# o6 U$ ^转换为：
min  ∑ni=1(ui+vi)min  ∑i=1n(ui+vi)
2 l8 N, V% }% B- `4 As.t.{A(ui−vi)≤b,u,v≥0,s.t.{A(ui−vi)≤b,u,v≥0,
3 B3 ~  i2 p* [2 E0 b8 k" f7.运输问题（产销平衡）
4 E( Q& M& C6 ~- g3 H
  W9 C6 h  E0 S+ X$ t
4 R2 a9 E; o: K1 d# M

8.指派问题

1.数学模型

2 R9 @8 A' @8 l5 Y2 [! h: Y
/ g9 [5 v  d8 r- i$ f5 I, r2.利用匈牙利算法
算法主要思想：如果系数矩阵中C=(cijcij)一行（或一列）中每一个元素都加上或减去同一个数，得到新矩阵B，则以B或C为系数矩阵的指派问题具有相同的最优指派。
( V7 P5 B/ p3 }6 x) t$ R, C3 _- l最优指派的结果是一个2行n列的行列式，第一行为第i人，第二行为被指派的地点。
' _# }9 I  m' [求解中心：变换出n个不同行不同列的零元素。
' I( b5 [) Q( n6 Q9 J
9 f% z& v' y0 ?% l' [9 K* |: Y

0 M6 H5 L5 i' x* E" `8 t& t