【数学建模】线性规划

佛自业障

1.线性规划简介

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

+ m" ^0 |. S! w$ {# U& E0 m
x1,x2为决策变量，约束条件记为s.t.（subject to）。
( z: F. H0 ~9 e1 K0 T& S5 N: ^

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

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

2 N4 ^! d* @/ m# l: ~
其中c和x均为n维列向量，A、Aeq为适当维数（列数与x维数相同，行数与约束条件数相同）,b、beq为适当维数的列向量（维数与约束条件数相同）。
# P; M: ?+ H3 j: g! F
例如：
; {! F( z5 |+ I: kmax  cTx  s.t.   Ax≥b max  cTx  s.t.   Ax≥b
/ `$ M: Z+ f' U! s+ X4 Hmatlab中为：
min  −cTx  s.t.   −Ax≤b min  −cTx  s.t.   −Ax≤b
  H7 Y$ [3 P# u  y4 I: ^' J) J2 X3.线性规划中解的概念
% Y- s. u2 s8 A; C- O& z. i
" x$ d* n5 R+ ?可行解：满足约束条件的 解x = （x1,x2…xn），称为线性规划问题的可行解，从而使目标函数达到最大值或者最小值的可行解称为最优解。
- [' C9 O5 v" y- @2 A( g可行域：所有可行解构成的集合称为问题的可行域，记为R。

4.一般的线性规划问题

在一般的n维空间中，满足 ∑ni=1aixi = b∑i=1naixi = b 的点集称为一个超平面，而满足 ∑ni=1aixi ≥ b∑i=1naixi ≥ b （或者∑ni=1aixi ≤ b∑i=1naixi ≤ b ）的点集称为一个半平面，若干个半平面的交集称为多胞形，有界的多胞形称为多面体。因此线性规划的可行域必定为多胞形（空集也视为多胞形）。若该区域R为凸集，则凸集中的任意两点的连线必然在该凸集中，若x为区域R的极点，则x不能位于R中的任意两点的连线上。

7 z8 B6 F$ s" k+ I% Y5.matlab中线性规划求解过程
+ @! i* D7 k5 n3 D) w) w, |
① 利用linprog函数返回最小值解向量。
8 Q# p& n9 y. W* a" J! E( E② value = c’ * x求最小值。
) V3 X( B2 m9 B9 g
基本函数形式是 linprog(c,A,b) , c用于确定等值线（列向量），返回值为向量x。
/ c& T  T1 B+ y- d! _* h# Q其他的函数形式：
[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,x0,OPTIONS)
4 j/ W  `8 U6 ^x0为向量x的初始值，一般使用zeros()函数 初始化，LB和UB分别是向量x的下界向量和上界向量。返回值为fval（目标函数c’ * x的值）。

/ S) N' v% g0 W4 {# m( r6.常见技巧
, f6 S2 k7 S" T! D% P7 O
问题为：

min|x1|+|x2|+…+|xn|  s.t.  Ax≤b min|x1|+|x2|+…+|xn|  s.t.  Ax≤b  
& d0 s6 q% K5 B9 h* O% B" s事实上，对于任意的xixi，存在ui,viui,vi满足：
7 F" _* q4 S2 f% B) Lxi=ui−vi  ,  |xi|=ui+vixi=ui−vi  ,  |xi|=ui+vi
令 ui=(xi+|xi|2),vi=(|xi|−xi2)ui=(xi+|xi|2),vi=(|xi|−xi2)即可满足。
! \* a2 D) c5 t/ `" X( K+ Y5 g
转换为：
min  ∑ni=1(ui+vi)min  ∑i=1n(ui+vi)
! H/ s: I5 j! D5 y# p( us.t.{A(ui−vi)≤b,u,v≥0,s.t.{A(ui−vi)≤b,u,v≥0,
- i2 Z# c: Z- @) N  k/ a7 z7.运输问题（产销平衡）
, p1 F5 b# i$ O6 X

+ y& u8 B& Q: ?7 |( O8 n

8.指派问题

1.数学模型
" s3 a. E+ [# D, b: W+ y

1 \- G* u' b8 p
$ J3 L1 N" `( g% \' C! b. |- s2.利用匈牙利算法
8 r, z$ z6 R& r$ Q2 @' i/ G算法主要思想：如果系数矩阵中C=(cijcij)一行（或一列）中每一个元素都加上或减去同一个数，得到新矩阵B，则以B或C为系数矩阵的指派问题具有相同的最优指派。
最优指派的结果是一个2行n列的行列式，第一行为第i人，第二行为被指派的地点。
求解中心：变换出n个不同行不同列的零元素。

2 U" s" R6 b1 G- [% ?$ e8 Y