数学建模社区-数学中国
标题: 【数学建模】线性规划 [打印本页]
作者: 佛自业障 时间: 2018-10-30 10:06
标题: 【数学建模】线性规划
1.线性规划简介
线性规划（LP）是数学规划的一个分支。
" _3 j" e! a- i( s3 D( u
3 q* i) K7 a* K) u# d# c- h. dx1,x2为决策变量，约束条件记为s.t.（subject to）。
& v9 H3 }3 W6 t2.线性规划的matlab标准形式
线性规划的目标函数可以求最大值也可以求最小值，约束条件的不等号可以是小于号也可以是大于号，因此在matlab中给出了统一形式
7 R& x# {" c) A4 @
7 i1 U$ m7 t" N8 S8 k& P( \其中c和x均为n维列向量，A、Aeq为适当维数（列数与x维数相同，行数与约束条件数相同）,b、beq为适当维数的列向量（维数与约束条件数相同）。+ @3 N/ Q+ `$ J4 e1 P
8 r3 Z7 S1 y! L2 o* K
例如： 9 r, q, L$ ^9 }0 D+ |# D3 i4 \& e+ ~
max cTx s.t. Ax≥b max cTx s.t. Ax≥b
7 ^2 | |# p* V$ ?matlab中为： 5 ^* ^1 t1 c- e$ b0 x7 @
min −cTx s.t. −Ax≤b min −cTx s.t. −Ax≤b
1 u9 E7 k5 k" E8 H2 X3.线性规划中解的概念
5 q7 v7 [. B* s, q+ n1 O& e6 V
, f1 |: y( F& X$ y- H可行解：满足约束条件的 解x = （x1,x2…xn），称为线性规划问题的可行解，从而使目标函数达到最大值或者最小值的可行解称为最优解。
2 S/ B/ H+ _& c/ o! }0 G可行域：所有可行解构成的集合称为问题的可行域，记为R。
" P! S# _, {' C6 ]2 o: G7 ]! o8 }: R5 l
4.一般的线性规划问题( L" \5 A, D; Y5 v) ^: m
. M; r O# g" g, n: ?" D2 g在一般的n维空间中，满足 ∑ni=1aixi = b∑i=1naixi = b 的点集称为一个超平面，而满足 ∑ni=1aixi ≥ b∑i=1naixi ≥ b （或者∑ni=1aixi ≤ b∑i=1naixi ≤ b ）的点集称为一个半平面，若干个半平面的交集称为多胞形，有界的多胞形称为多面体。因此线性规划的可行域必定为多胞形（空集也视为多胞形）。若该区域R为凸集，则凸集中的任意两点的连线必然在该凸集中，若x为区域R的极点，则x不能位于R中的任意两点的连线上。
9 D# n# \/ h* b1 L, A$ G. R0 K6 k2 l* {0 j) ]: L* r
5.matlab中线性规划求解过程
6 b* V" h5 g; K# P2 K& K! A3 Z! G( o$ Q! X6 w# \
① 利用linprog函数返回最小值解向量。
+ t* Y7 B1 n: t! I% m: f② value = c’ * x求最小值。
. B: e: y$ e6 |1 f; j# q/ g1 E% T- {- n3 D5 Z
基本函数形式是 linprog(c,A,b) , c用于确定等值线（列向量），返回值为向量x。
# h/ N" `- d3 H: w, k& x5 \; ]其他的函数形式： + N1 p4 R# O J5 ~3 B
[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,x0,OPTIONS)
8 E4 S4 S$ @% Y' ~3 Fx0为向量x的初始值，一般使用zeros()函数 初始化，LB和UB分别是向量x的下界向量和上界向量。返回值为fval（目标函数c’ * x的值）。. u. }3 o5 r$ x/ Q- v G; N/ ]
, c, Z! D0 i6 j5 J8 p4 l, A$ J ~
6.常见技巧: V$ {2 p' j& H
- s1 o P' a: `2 M0 I5 `7 u, @问题为：5 |, O8 Y* Q# h+ K9 @2 a
' `" r5 y5 O1 \3 mmin|x1|+|x2|+…+|xn| s.t. Ax≤b min|x1|+|x2|+…+|xn| s.t. Ax≤b
6 Q# n. | c1 T3 V事实上，对于任意的xixi，存在ui,viui,vi满足： " W _8 X$ I1 [$ D, j* X& l
xi=ui−vi , |xi|=ui+vixi=ui−vi , |xi|=ui+vi ) Z |8 p$ Y3 O( R5 s8 Z! ~
令 ui=(xi+|xi|2),vi=(|xi|−xi2)ui=(xi+|xi|2),vi=(|xi|−xi2)即可满足。
j/ X0 |# f4 {8 p$ L+ S- \, Q; q* M/ z
5 J# I$ R, Z) T, a+ c, h8 e转换为：
8 N+ }; q% k. e, G* @8 c! I7 |min ∑ni=1(ui+vi)min ∑i=1n(ui+vi) 2 S+ d, P) N; b3 A- Z5 b
s.t.{A(ui−vi)≤b,u,v≥0,s.t.{A(ui−vi)≤b,u,v≥0,
0 x( c% ?4 @% k% ]7 ^7.运输问题（产销平衡）
5 `7 u$ U$ d- m# c8 k8 p/ \# M4 v
9 b4 Q, W/ p" _' U
2 h1 \4 d$ i, L% h# e
8.指派问题
1.数学模型
1 l! a& T4 w5 s
; i& w- y* R( P+ l, W
4 i9 C& ]# h x/ o3 G' f: J1 O$ o
2.利用匈牙利算法 - ~8 L) R3 i, E7 X
算法主要思想：如果系数矩阵中C=(cijcij)一行（或一列）中每一个元素都加上或减去同一个数，得到新矩阵B，则以B或C为系数矩阵的指派问题具有相同的最优指派。 , q' `3 t1 N9 o3 ~# U- u
最优指派的结果是一个2行n列的行列式，第一行为第i人，第二行为被指派的地点。 & [- ]6 x- s q! ?( H
求解中心：变换出n个不同行不同列的零元素。
8 H5 o& S/ G0 t x: V8 l7 c- q$ G# G9 X7 {) _) a* j; W2 O
% p$ `% L1 W! ^2 I9 w$ }) Q/ E8 m* h$ y
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |