|
第二章 线性规划 本章, 我们介绍三种解决线性规划问题的软件: 第一种: MATLAB软件中的optimization toolbox中的若干程序; 第二种: LINDO软件; 第三种: LINGO软件. 1. MATLAB程序说明程序名: lprogram执行实例:file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image002.gif 在命令窗口的程序执行过程和结果如下:the program is with the linear programming Please input the constraints number of the linear programming m=7 m =7 Please input the variant number of the linear programming n=4 n =4 Please input cost array of the objective function c(n)_T=[-2,-1,3,-5]' c =; y6 g' I+ u8 w e9 {
-2 & {" v2 m, T1 x* u3 Z0 Q; n
-1 ' e0 c' W. r i, {, \ R2 i
3 % x. l3 _/ {) ?, n
-5 Please input the coefficient matrix of the constraints A(m,n)=[1,2,4,-1;2,3,-1,1; 1,0,1,1;-1,0,0,0;0,-1,0,0;0,0,-1,0;0,0,0,-1] A =6 y( d, j) M& P( P$ }( k) I8 U
1$ X" t) F& w5 }9 e# g0 e$ n
2% j {9 B- h+ B- Y) s
43 [5 X1 t9 P( |
-1
/ E+ G; e7 R5 T' I! h0 {3 A3 }29 A, f# S0 I0 i) ]2 k5 h
39 }+ X* U- ~$ e/ T
-1
4 e# X8 D& D, L, W" [) o5 j1
/ a/ X' F E o0 a4 s0 c
1
8 B: H4 @8 U7 O! r! r0 q01 g: Q' E. R% v+ X* p# r8 [
1
0 u8 V; J w% A+ d8 _7 B1
; J( s4 V9 M) o% |# R) K-17 x {! E0 m* Y; I, ^
0
# @: e, P+ g" I# j7 o& O: ]" n3 M0
# G7 Z: e- h, Y0
# Q' f2 v2 m9 S8 [- w
09 @) d8 a! k2 x0 x$ t) @
-16 B4 a, q' U0 S. u, y h
0
' L# w, g. H' ]' }+ x: p$ R0 4 i4 g( {) W8 C$ }0 d. K
0: C. a9 x+ m% \) B
0) P! H% r1 n, F! ]+ Z: I( w
-1: g9 M1 o/ J* Z5 z k
0
: b+ _/ Z% F3 }6 E) b07 r6 ?* x( w0 {( J7 n, |( f5 O/ x
0* q( u2 F9 }. |
0
: M$ z. Y3 ~% h: @7 s& Y0 h! R) [-1
Please input the resource array of the program b(m)_T=[6,12,4,0,0,0,0]' b =
: d( ~" N; n6 p N6
! f% A: ~+ b9 G. N. V12
B8 A7 i- G1 ~3 ~4
) S$ v+ A! Z8 }0
! _: W5 ^9 v- y7 X6 E0
, E/ m4 J$ w" g( |, E8 J
0
4 G" v" u! x$ s; h5 P- z* o& K0
Optimization terminated successfully. The optimization solution of the programming is: x =7 {% c R6 V7 [% M
0.0000 " v. X6 X/ |& ]9 _: t
2.6667
- [0 Q" Y5 }! [-0.0000
) F# ?! ^4 f0 f1 c. U4.0000
The optimization value of the programming is: opt_value = -22.6667 注: 红色字表示计算机的输出结果. 程序的相关知识:Solve a linear programming problem file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image003.gif where f, x, b, beq, lb, and ub are vectors and A and Aeq are matrices. 相关的语法:x = linprog(f,A,b,Aeq,beq) x = linprog(f,A,b,Aeq,beq,lb,ub) x = linprog(f,A,b,Aeq,beq,lb,ub,x0) x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) [x,fval] = linprog(...) [x,fval,exitflag] = linprog(...) [x,fval,exitflag,output] = linprog(...) [x,fval,exitflag,output,lambda] = linprog(...) 解释:linprog solves linear programming problems. x = linprog(f,A,b) solves min f'*x such that A*x <= b. x = linprog(f,A,b,Aeq,beq) solves the problem above while additionally satisfying the equality constraints Aeq*x = beq. Set A=[] and b=[] if no inequalities exist. x = linprog(f,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, x, so that the solution is always in the range lb <= x <= ub. Set Aeq=[] and beq=[] if no equalities exist. x = linprog(f,A,b,Aeq,beq,lb,ub,x0) sets the starting point to x0. This option is only available with the medium-scale algorithm (the LargeScale option is set to 'off' using optimset). The default large-scale algorithm and the **x algorithm ignore any starting point. x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) minimizes with the optimization options specified in the structure options. Use optimset to set these options. [x,fval] = linprog(...) returns the value of the objective function fun at the solution x: fval = f'*x. [x,lambda,exitflag] = linprog(...) returns a value exitflag that describes the exit condition. [x,lambda,exitflag,output] = linprog(...) returns a structure output that contains information about the optimization. [x,fval,exitflag,output,lambda] = linprog(...) returns a structure lambda whose fields contain the Lagrange multipliers at the solution x. 2.LINDO 程序说明程序名:linear执行实例:file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image005.gif 在命令窗口键入以下内容:max 10x+15y !也可以直接解决min问题 subject to x<10 y<12 x+2y<16 end
% {9 I7 C$ |* i!注释符号; 系统默认为自变量>0, 若不要求用free命令. 0 i5 @5 [! P: q# ]
!在出来report windows之前可选择显示对此规划进行灵敏度分析等 按solve键, 在reports window中出现以下内容:LP OPTIMUM FOUND AT STEP
% ]: U5 r \3 t4 c4 t2
4 ^8 @- S2 I( r3 |7 oOBJECTIVE FUNCTION VALUE
% h: o1 u# C$ b3 M( `
1)) t! K0 i ~( G; [
145.0000
5 m4 [$ t; D8 S2 N/ l6 }! [7 dVARIABLE
' B ]8 L b* q$ K; FVALUE
' u$ Q1 z! {( n; qREDUCED COST
2 M }1 T( c4 l2 U5 |X0 E: P. l' z0 F) v$ d t
10.0000000 l) t8 |3 N6 J) D
0.000000
: z. f: N5 h. v$ _3 Y- ^ f
Y) Z# f* |5 S. T% N& \4 Z' ~- t
3.000000
" d4 x( }! b" u& _0.000000 8 v+ \$ g% Y! }, ^* t7 c" k
ROW
7 ?/ F. Z l% m$ S3 ySLACK OR SURPLUS
! K( n$ X, M9 G# { IDUAL PRICES $ {# E4 n) Y {9 a% a
2)9 ^2 J, G5 I, a+ r) ?/ B
0.000000( ?0 m5 L/ c9 r; J2 M# b
2.500000
; y8 Q% b" v9 h3)" i/ Y- v3 P$ A7 ~# A/ D. \
9.000000
( Z5 Z. i7 t3 T0 g7 d$ B0 a1 C1 {0.000000
' _, O/ Z) z) s+ H% d
4)( y: ^2 a5 b* _4 x$ _0 V1 K2 F) A
0.000000. }0 R# n8 D5 r
7.500000 # J, I" b2 {$ o+ s5 x' y
NO. ITERATIONS=
- y, g9 p. p; V! _5 }2 1 M/ P1 J2 S& {( `6 X$ a- [
RANGES IN WHICH THE BASIS IS UNCHANGED: 6 l! `. D2 C$ u) g0 k }& {2 D* |- |
OBJ COEFFICIENT RANGES ; Q$ d2 t! G7 M/ q# C
VARIABLE
; Y( M# d3 ~- I2 [9 ^8 `) HCURRENT
: K/ S7 s+ L( N$ x5 FALLOWABLE
" c$ l* ?' o& F q. SALLOWABLE
5 _$ I2 m8 ~3 ^COEF N4 G! V# l% f. A; R/ h
INCREASE
9 f! K. i7 M/ I0 gDECREASE
/ Q3 I5 L5 |! U( y* O
X: _' e1 U6 |/ D$ }
10.000000
% m4 Q# Q7 T1 K" b" Z, vINFINITY6 C' Z( n5 q) `7 T% }5 X C W+ W3 M
2.500000
" j0 S( g( X: zY2 B9 p8 W2 |1 Z" n* b |' u0 q
15.000000
r( y& W' ~; q) z% F$ x& \' r5 ]4 A! J5.000000
2 p U' }0 n& u( b) d15.000000
: q2 v! ^' n# O2 d5 z
RIGHTHAND SIDE RANGES
' y8 \2 O& s- _. h" m/ K9 MROW
7 `* F/ S0 Z/ ?9 DCURRENT
/ l6 M. O1 w% ]ALLOWABLE
$ h5 d& z s: `ALLOWABLE
' D" y3 N" m# Y- h: S- j+ W5 SRHS
% x7 ~$ a+ U. q* _. |" Q, VINCREASE) ]! Y2 N$ ]7 z, L. h) Q
DECREASE
# A0 g, f! u/ A: [) T
3 h6 o/ D! R$ K. T4 q- V2
! P$ } p6 t3 ?% R; w7 n) l10.000000" D8 O7 ^) Z. a% m) Z3 R
6.000000
\3 Q5 C/ j- t8 G9 g& e/ e) L) t10.000000
) n4 A/ g7 d, m' |6 l3# t/ \* `" }2 k6 Q- a
12.000000
* V( E8 J' k0 B2 m2 PINFINITY( R/ |, ^3 @( \- H, _; L
9.000000
2 N8 a) x- q3 C: ?
4
# {- D9 A. J2 ]16.000000' \! W- V, Z# l8 _) Y8 J4 R
18.000000
! ]5 P4 [9 i2 `. S9 y/ L& Y6.000000 3.LINGO 程序说明3.1 程序名: linearp1(求极小问题)linearp1运行实例:file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image007.gif 在model window中输入以下语句:min=5*x1+21*x3; x1-x2+6*x3-x4=2; x1+x2+2*x3-x5=1; 按运行按钮在solution
4 c6 V) f3 x9 ?/ C$ Dreport 窗口得到以下结果: & f- D: Y+ M3 C( M) T
Global optimal solution found at iteration:
# f1 Y+ z2 Y" K& W" }3 M9 X2 ) J# _4 E2 t# P
Objective value:
: t9 y8 e% D$ E6 ]7.750000
1 g2 O/ D' b2 T. L7 lVariable
( ?5 B' V+ c9 f9 i2 |8 r" R" mValue7 w' Q9 g$ |9 F. s* g/ r k
Reduced Cost
& {& m6 y! g% ^, z3 ]8 g
X1- q% g+ l( X* k; z: m5 M+ D1 `( _
0.5000000) O% v" T- G- u: Z' L
0.000000
( z9 p. {5 @; y `X3
b& I9 U, H! _8 z, q& F) I0.2500000
- _/ c/ ?, u( @0 ~& {0.000000
8 Q) Z3 j/ `; |, I& g
4 ~* F6 _ Q* t* N7 }X2/ _. a) W" Z- e+ Z; v" Y1 Y. ]
0.000000: v. X9 ^# R$ o
0.5000000
9 O1 u2 H( V$ N2 yX4) V4 `1 ~) f" M" [. O5 c x
0.000000
1 S" i5 s: l9 h1 A( z* K2.750000
9 ?( ~5 ?! Y1 G. hX5: e, u* a9 T1 t! U7 W
0.0000002 ~3 C7 m. G3 k9 c' \' {! E# y
2.250000
# S( d" o8 j9 T+ `4 ~Row1 E5 C# O/ z, U4 S
Slack or Surplus
+ x7 r' h* C; h9 s' h) [# T HDual Price
3 a2 p3 @" N4 m5 @2 [
1# ?& [% J6 B6 {* g6 H% q
7.750000
) d4 T1 T. V+ H-1.000000
, ]. W; s2 ?" r- y0 c8 u2( [' K4 J+ `' ]2 ^ Y
0.000000
3 P( H1 O( a! O4 G& {; Z1 J-2.750000
4 G1 t' y5 \# z2 E6 v" p3+ q" n8 w" F* j' P6 [6 j1 l
0.000000
, o8 s) @- `: s9 N6 L-2.250000
3.2 程序名: linearp2(求极大问题)linearp2运行实例:file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image009.gif 在model window中输入以下语句:max=100*x+150*y;) [& ^ { D, K0 n4 H% w; C' R; u0 h# Z
! this is a commnent; x<=100; y<=120; x+2*y<=160; 按运行按钮在solution report 窗口得到以下结果: Global optimal solution found at iteration:! v' o2 i% l% w6 A
2 ! ?- l6 U4 o5 m. F5 B6 e" L
Objective value:! S5 c3 w |( \, w ~7 k% P3 c. ]: W
2 H; G* x& I7 ~# { }9 t14500.00
% T: v* A& x( P* p0 \* H2 a+ hVariable0 ^, z V7 q/ n( m/ u* s3 \" q9 C
Value
; S' j8 R. A2 ]! P$ o: w/ z' SReduced Cost
) T& z A6 K: O& O- hX6 I/ V. S( y( i/ _( j6 [
100.0000. e) [8 z. V% Q- b& z
0.000000
5 y g; u. B+ i* ?" \
Y; R4 D1 ^, W. M% I+ s
30.00000
J5 O( y% k/ g; [5 Q0.000000 4 R3 z$ D7 w( W3 [" |0 W7 d
Row
! |; q8 {/ u3 n- {2 bSlack or Surplus
" `/ A E4 O# |! [# v/ `, U- eDual Price & q8 i4 `" f2 K6 B
1
) y4 P# G2 i# R, J# v14500.00
" Y! i& Z" v, R$ [: U2 [$ b1.000000
o0 W$ c; T9 U: c' q& \9 U9 k9 N2
0 _+ B& K( s U7 s+ R3 `( F0.000000% t: z+ ]: E( T$ F
25.00000
$ x. L! ?( D. P Q7 f9 Z
3
9 \& q8 f. E6 f; F7 q8 P; c* x90.00000
h; r( m: I# }/ F5 ]! x0.000000 4, T9 G4 f/ H. d
0.000000
; ~* c$ P& \! p* M2 S" p, Z0 `4 z! K* {0 V
75.00000 |