|
第二章 线性规划 本章, 我们介绍三种解决线性规划问题的软件: 第一种: 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 =
2 J% K9 X6 e1 e) }2 Y-2
) g; I% p' H& z% ?! t1 @# p-1
- e' ]1 e, J/ }5 v8 l) w1 s% D! \
3 ' y( i4 I% A/ e3 Q
-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 =5 b6 s3 G. d8 V8 z Y* F& S/ s' q: i
1
^# c. w' [- `: V% `, o2
% ^9 _% N- l6 ?, @$ l! K1 i$ N4* {! g& x* s( ]' F1 x2 J$ O
-1 + |4 p1 v& H5 H
2# A, \+ S/ I' X/ l* [
3( f* d$ s9 n% ~8 ~! I
-1/ w* ^/ W+ r. z/ u6 e
1 - N$ @! b3 A2 w
1' b* P4 J5 k3 c
0
4 Y# T0 N8 @" e: d( Z1
7 a+ b+ w7 k' q1 ! P4 h& I! O) q+ u
-13 R5 g+ Z1 E& v
0
( N* R' ^! ]* R" \, {0
4 ^9 ^2 I+ Y7 T& G) ~0 " h/ r) F2 S8 d( b0 k8 S
0
! E2 ]4 u% b" U: s, s7 x-12 W3 _; X8 f0 E' h6 o: Z# Y" G
0. D9 ^7 [* \, h7 z
0
2 H7 z6 V. @. Q2 t7 l: T9 [) i! s0
" q4 B4 J: C5 X* p1 @0
F+ S' t1 m. K( T-1 @) k8 j+ k3 Y; z! u, S
0
# C# t! E( a" q, d1 J0 o% H02 ]5 M ^ o- q
0) A. N+ r! f! b$ A* d
0
: o% q2 V7 l' w" `" A0 b-1
Please input the resource array of the program b(m)_T=[6,12,4,0,0,0,0]' b =
# n; q- I* F6 K* } M" N# A& e. x6
3 E+ r8 `# u* n3 \, U9 j/ q12
' |- ~: }5 x/ u3 H" L4
2 s: r, G# U u1 D% W" C0
* d. L0 e# ?1 w. K; A/ R V
0
& `5 C' U. D) q* a+ H0
?5 i/ d4 }6 e; M" K& f4 u& Y; ]0
Optimization terminated successfully. The optimization solution of the programming is: x =
6 ~+ s& ]* Q$ o( R4 I0.0000 . X: `" L3 |- L" m. g4 h
2.6667
3 f' i6 y- ^1 A B2 q0 P-0.0000
9 Z9 m b8 W- @, e2 I6 o* y
4.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( i V/ e. ]) j3 N
!注释符号; 系统默认为自变量>0, 若不要求用free命令. ( U, s" \. T5 E2 d/ B+ v& M- K
!在出来report windows之前可选择显示对此规划进行灵敏度分析等 按solve键, 在reports window中出现以下内容:LP OPTIMUM FOUND AT STEP0 l1 ^1 y0 u" G: v$ C1 c, D( [" I
2
5 m0 S" D y- m" ^OBJECTIVE FUNCTION VALUE
# k& p ?4 @$ `5 c" L( u$ z1 `% ^
1)3 f/ N& ^! e9 H0 w. d* o
145.0000 ' `1 G' r S7 _) T: n
VARIABLE
4 U/ D* F2 K$ W* w& d2 F- vVALUE
! |, b; u) T# |2 Q$ XREDUCED COST
" }, |! K* n+ T0 `" kX
# L- }+ B. Y7 K4 s- N/ n10.000000
1 a& }, |3 I8 L- F* x5 G. E) Z u0.000000
2 f6 m+ C; O8 l' W5 p1 C9 n
Y% A9 H$ b1 X0 f$ o* W5 R
3.0000009 O: T1 [. {5 \8 S
0.000000 8 S% c( A H/ V+ c& ~9 S
ROW
0 j9 `# t& ^- k* [6 }- RSLACK OR SURPLUS/ o2 |# H. ^7 f6 ~ ~! a
DUAL PRICES
9 p. x5 R/ M: n( N4 X9 E1 L2)2 ^7 R0 u, W$ F+ Q8 c! f, I
0.000000
& s7 Z* u" t4 B8 l2.500000
0 Z4 Y9 }8 D" w& b" h
3)
9 E, u$ H3 F4 @5 _; |; _7 r4 a9.000000, G$ ^3 _9 U3 n: [9 b
0.000000
' D) l9 p4 j8 f. ]; A4)
6 V; e9 m0 _ Z1 ^0.000000
0 K" K+ f5 t: R+ F6 M5 ?7.500000
U; }$ s; g! U3 R/ iNO. ITERATIONS=
6 C: Z {2 ~$ {, Y! u& k3 v2
3 s3 V$ Q& j/ l9 w
RANGES IN WHICH THE BASIS IS UNCHANGED:
/ f7 Y a3 n0 G( p7 i, BOBJ COEFFICIENT RANGES
& A" o% j6 |0 I% |+ O( JVARIABLE% B* V4 U. m; I6 l$ w
CURRENT) O5 u! a- ^/ f3 ]/ M8 Q
ALLOWABLE6 z4 R! h# [6 F3 W. k: h
ALLOWABLE
# p( F- }$ y4 [. X! Z
COEF
& D3 v! ?* U7 q8 m! EINCREASE
& m6 V: z. t9 l$ Y; xDECREASE
) ~/ C6 E$ e0 y- m0 DX
( l" {8 }0 m4 W" A, C+ e7 C+ ?10.000000
% t2 d& M) x' `0 D, s: ?6 N8 FINFINITY
; S) ]0 n4 X' F: N# [0 g, b: h2.500000
- O, \; ?& a) s' @; a( EY
! b G' m0 \" D. t* g' p7 [15.000000; w* r. ~- F. U* n% s6 o) P. ]
5.000000
+ X: h1 E/ S/ h7 {: f15.000000
4 J( l" `$ x) U6 LRIGHTHAND SIDE RANGES
3 K" [5 A# Y+ N& j& b X/ @: I1 OROW7 S% R0 z& ^5 e) N
CURRENT, z. j4 |4 A/ k- e9 z6 E
ALLOWABLE8 y8 e, Y: H; T& o" j) ?" l, P
ALLOWABLE
) ]: K2 \4 _/ S) R6 v
RHS& l: g/ m8 g6 H6 y9 i o
INCREASE
2 t% w7 {9 R- I5 q% zDECREASE $ g" @' M* r! b' H1 ]; {
5 T0 H% u! e# L( s8 r
2
# _1 F3 v: }) }0 b2 ~+ T10.000000
& T$ ~# l, u- g$ L$ a6.000000
7 K6 H- t! |- z8 K5 [7 K10.000000 . ~% Z' G/ m3 _6 ^! @4 P H
3
( e2 |7 S8 E& |, k9 w12.000000
: `+ B0 \ z Z* v0 ]INFINITY
% Y; X/ i) n: ]- O9.000000 3 ^! ~' v9 A$ b5 z- v6 o7 G8 R
4, d" S8 t, C" l* Q% J
16.000000; l3 ^9 f) z3 L% r/ j2 [# H3 o# `7 w/ j
18.000000
3 T- D$ J1 U+ r; o# _- v6.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
& ]! y D( T% F3 I. r9 ]" h: k( Ereport 窗口得到以下结果: + o- N& e# n Z2 ]8 _8 _
Global optimal solution found at iteration:2 m8 e4 f/ d3 n" b8 M( ?; t8 T
2 # S8 X) ^2 m W. i
Objective value:
T0 P% h8 L( Y- J! d: R( i7.750000 9 Y0 j, S5 J& K+ I% c- g; c7 J
Variable/ W0 t0 ^; w6 Z
Value
( l R6 K9 \& P1 \# S% bReduced Cost
! J8 n! w, i5 Y6 F+ ?7 K7 kX1
) E1 B; A# s5 r2 b" n0.50000008 L5 ^" o( @. l. ^) x6 D
0.000000
! `8 _7 `5 u. _1 U6 j" \+ {/ HX3
- Y0 ~: S4 L1 D- T0.2500000* o- F+ w! T! @+ x' @/ S* ^
0.000000
( x$ m" T4 |6 n+ N: y
8 X& S5 F5 V# `X2
2 ]) y9 i0 ]/ s2 s; l+ a/ p0.000000* V) c' v& f2 k' h" c" b
0.5000000
$ _- U. M, s$ R7 }" X! h! C
X4
& u0 _1 C. g$ U; ~, w3 S7 g [0.000000
. d) {; b4 x% R& J# _9 X H2.750000 : [4 m7 A, i: A& U
X5! F7 G5 T2 _- S! t. Q
0.000000
( {9 f/ e9 t9 C. {7 Z2.250000
% w, P3 D' o' ~, YRow I6 e a: \% ~+ Q4 k2 z* w
Slack or Surplus- G# I# s E( j c: l0 I
Dual Price
7 {9 `/ }6 ~, G6 h" D: u1
) G. H8 Y6 [( A+ v7.750000
\9 }" r+ J" k& D-1.000000
* Z" ~1 A: M, y% W/ U8 o! {
2
0 W5 _; v7 F# k& D# n7 c0.000000
- x$ t; i& z/ a6 w$ A" o8 D-2.750000 2 ~* Y) k6 Z! }1 f0 @
3' M* |# d7 ~5 D5 I3 T U, q% t \
0.000000
" n5 ]* w, I2 z5 ~-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;7 o( }7 @: W/ E: A! k+ L9 m7 H$ U$ K
! this is a commnent; x<=100; y<=120; x+2*y<=160; 按运行按钮在solution report 窗口得到以下结果: Global optimal solution found at iteration:
+ ~6 _/ s9 ~ r" M2 \7 Q6 \$ L; ^2 + y! |9 q4 \1 S) X4 y
Objective value:0 m+ M9 t2 O* {3 b4 z
3 P& O" w$ X; v0 _/ {; u
14500.00 + Z1 o1 i" V8 Y% i( L2 t
Variable! P5 Y7 C: [( M7 j8 [/ D2 P
Value
+ S; g% }! }4 o' l4 ~8 }Reduced Cost
+ ^( v) W: j5 m6 i- W, XX9 t& y5 p2 }! q A+ _' X
100.0000
@- z5 `$ r& q% f9 c0.000000
0 Y/ g; j3 X1 x% V! D- kY+ W$ k( ^6 h+ A8 X5 L1 M- g
30.00000 s9 f5 v& O& W& Y5 `. D- Z# G
0.000000
. U: ]9 \: s7 T3 H" m# H0 k
Row
: C+ u) X2 f. T* X0 J# @ f0 V* g/ H( zSlack or Surplus
, a+ E! x4 @# {# d5 E0 i8 _/ S' @Dual Price $ v$ X, H5 i/ R% _, }/ t
1
0 {3 F2 @2 R- X, F14500.00: q6 b* _6 V; a
1.000000
4 Y9 @# P; V2 n7 p+ \2 t2
2 d7 E! r: V0 [/ D3 h0 Z0.0000006 i ]7 W2 |# h8 f; u7 Z. s3 u
25.00000
& t6 _# \7 o" d5 |3 E0 q3
( ^# Z; m" C! j8 X' }) d g2 s. F90.00000
8 ~* K- |: ^; b! N4 S' g0.000000
4
3 G0 ?- J8 S! ^* r/ ~0.000000
, e* {, |, }9 y) L4 A( A
3 G- Y! i* [* ]) G* a, o; F# r+ `75.00000 |