数学建模社区-数学中国
标题:
数学建模：matlab解决线性规划问题
[打印本页]
作者:
zhangtt123
时间:
2020-5-28 15:56
标题:
数学建模：matlab解决线性规划问题
在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效
# w& X+ p- X7 E* y
益的问题。此类问题构成了运筹学的一个重要分支一数学规划,而线性规划(Linear
% Z* S) d5 Q; \( Z3 `
Programming, LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线
9 ^# a3 b- K6 O' E
性规划的单纯形方法以来,线性规划在理论上趋向成熟,在实用中日益广泛与深入。特别
8 l6 I V. ?7 p% q" M5 m# Z1 Q
是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适
5 |5 |3 I9 E. }5 f
用领域更为广泛了,已成为现代管理中经常采用的基本方法之一。
, F# v/ W1 r% c
" {) j3 @6 _( @3 C8 M- Z9 T
例如，给定m个数据点(xi,yi),i=1,2,…,m，拟合一条直线y=ax+b(即确定参数a、b)，使得所有数据点(xi,yi)和拟合直线上对应的点(xi,axi+b)之间距离的最大值rmax最小。也就是说，对整个这组数据点而言，最大绝对偏差r=max{ | yi-y(xi) | }最小。这种准则实际上定义了如下优化问题：
' `# {2 I8 J: X) G! Y' S( C
2020-5-28 15:58 上传
下载附件
(6.42 KB)
+ j3 r! a8 [9 p- w
这是一个线性规划问题，具有很广泛的应用。
+ e3 {* W8 M$ a* E
! i5 f9 ^- A( u) e* F* ]
木匠问题
% C/ U6 O% O* F) \8 g! r( _
木匠销售桌子和书架的单位净利润分别为25美元和30美元，他希望确定每周生产的桌子数量x和书架数量y。他每周最多有690 张木板和120小时的劳动时间可以利用，如果木板和工时不用于生产桌子和书架，他能够将它们有效地使用在其他方面。他估计，生产一张桌子需要20张木板和5小时劳动时间，生产一个书架需要30张木板和4小时劳动时间。模型为
8 j( o! G7 @3 d0 L a
2020-5-28 15:58 上传
下载附件
(11.62 KB)
' X4 j: `( D$ P; k% F4 {/ L
6 ~" Y5 Z! \, x% y" s
木匠问题中的约束所代表的凸集在图中用多边形ABCD表示。请注意，约束所代表的直线有6个交点，但只有四个交点（即A—D）满足所有约束从而属于该凸集。点A—D是该多边形的极点。
, Z8 c* N. R) t- ]4 Q' @7 v7 V
如果一个线性规划存在最优解，它必然也会出现在约束所形成的凸集的某个极点上，极点上目标函数的值（木匠问题的利润）是
! M4 Q% g x' _ R5 m7 a
5 r1 J3 ?2 r$ M. U) P
2020-5-28 15:53 上传
下载附件
(6.63 KB)
7 H w/ l8 _+ e3 O% F6 d8 s- K" d5 U
: D% K+ `- ~% _8 B5 y% F
! z1 D/ k: ?/ N2 m' a7 _2 n0 ?
因此，木匠每周应该制作12张桌子和15个支架，每周最大利润为750美元。
. o! I r# P" Q! u) V3 X
2 u0 ^$ p6 q N9 a: B
木匠问题(线性规划)的matlab解法
( G) i# h- j8 y0 e7 {
& N( c9 ~" K7 L6 C
线性规划的目标函数可以是求最大值,也可以是求最小值,约束条件的不等号可以是
% _" A5 I {1 x6 s) r9 ?
小于等号也可以是大于等号。为了避免这种形式多样性带来的不便, Matlab中规定线性
" p; I% F7 L+ H6 |' c
规划的标准形式为
" D4 y1 P$ ^4 @+ r* [9 f! @
2020-5-28 15:55 上传
下载附件
(6.74 KB)
. A+ d3 Y8 {3 W7 v) L6 x, Z6 g
( w7 K8 n- h7 a! P$ ?$ v
式中:f,x ,b ,beq,lb, ub为列向量,其中f称为价值向量,b称为资源向量;A , Aeq为矩阵。
, k% a$ r; ?) {. i; Y0 y1 R
Matlab中求解线性规划的命令为
+ `; E. B6 m2 @4 } _
[x,fval] = linprog(f,A,b)
" ?" c7 n% N* W3 p9 ^
[x,fval] = linprog( f,A,b,Aeq, beq)
: Q* R& Y# V( @; q$ S
[x,fval] = linprog( f ,A, b,Aeq , beq,1b,ub)
* C, H. c2 V( H% u; p7 G; }4 e
式中:x返回决策向量的取值;fval返回目标函数的最优值;f为价值向量;A和b对应线性
% A, f+ Q/ ~! F$ | ~8 q& I
不等式约束;Aeq和beq对应线性等式约束;lb和ub分别对应决策向量的下界向量和上
H0 w: b* c" o0 ]9 g# c
界向量。
8 L3 z5 r- s J& w) n/ v8 O
例如,线性规划
% \; s3 C, I+ S' A- ?
2020-5-28 15:59 上传
下载附件
(2.61 KB)
4 f! [, T! `$ g1 ~
的matlab标准型为
& T4 B/ _) b. x; Y8 h
2020-5-28 15:59 上传
下载附件
(2.96 KB)
1 R* p: J% M% a- O+ f3 Y2 }
9 A4 ]/ S3 B! h% o+ O
& x5 H5 c8 k- F7 |. u' J4 q
附上木桶问题的matlab代码
4 Y' ~9 ~( ?. P V% z
2020-5-28 15:56 上传
下载附件
(10.68 KB)
, w1 H' g7 S* p$ L$ l
2 z- J6 e+ n& a' B
————————————————
6 g4 b9 w' G& k4 A! T5 D5 q1 R+ f
版权声明：本文为CSDN博主「板砖大的砖头」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
b% J/ u" S9 P8 I
原文链接：https://blog.csdn.net/qq_44953660/article/details/104227831
, j' N) k4 i6 H% n) I, I& {
2 G* H+ G- J8 X3 F
- f" ^# g3 ~: x$ [# n3 o7 k* q
, W9 Q. D: c% H' V& I
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
