|
第二章 线性规划 本章, 我们介绍三种解决线性规划问题的软件: 第一种: 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 =$ h, \& q) Y: W9 k
-2
6 e; \% }2 T$ l) x-1
) p1 c5 z" F- h+ m% [7 D3
# _' \ M8 T- s0 m6 a/ v
-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 z5 e' _# C( } x& W1
* s2 B( ], p' h6 D" x2
+ G B1 i+ C' l% A( |% u5 j4
& E& v$ U. \& B- b-1
' Q% ]1 w' Q4 T, W# |2
) [7 @7 @4 R# d3
5 V9 X _. o) n0 y" H; Q9 v9 h0 T-10 s( G' n* c3 ~8 h
1
" V" J; }; w* b( h" w- {# C& F19 R3 B7 ~- D- O# S2 [( j" u, U( u
03 q& B4 ^* ~9 N, V
1 }+ ` M- R1 D+ Y- o% c* @
1
7 `9 U9 h% ]+ x
-1: V9 n( g) L: p8 C* g" B
0
/ |) e" b9 @* y9 g$ [06 M n( z; }3 R7 o' l j3 L" Z
0
; V* K7 j, R' B4 V9 ?( B0
7 N9 ~7 t7 s0 }% U2 B" a6 X-1
7 _/ X3 [* R; X9 D/ r0, O0 o0 M G1 N% t& l, p; u1 w5 R, G
0
, J6 U* H) u8 g05 t+ ~; d6 ~2 c+ }, p+ N4 w
0
* I& H% R4 f% H" }3 a0 m5 r-1
% P2 ]% L, }( D& e, B+ c0
3 t& Q9 R0 y3 T3 }: u# n0
( K1 a6 F" N! B+ Y/ F: @0
. X5 d) W+ ?; ]0$ c& ^ m% P# C* W% f- ]1 \
-1
Please input the resource array of the program b(m)_T=[6,12,4,0,0,0,0]' b =
7 d! |& [: N% y2 j6
D" \+ r9 E0 p12
4 j V' r5 v* q& l
4 , h% O% x$ x8 j5 ~
0 6 r( Y# g6 _4 H3 d# [9 ]
0
- q$ e. i0 _5 H+ \5 y0
1 W9 a% t+ ]7 \! U) p/ J- C, Z+ q
0 Optimization terminated successfully. The optimization solution of the programming is: x =
$ N, v, ?8 J, c% y4 B: p3 f0.0000
& z" C: Q+ }! i p, r- y4 b" f, M2.6667
5 q& x/ X: J+ u) Z. d" g
-0.0000 3 z1 n( \, D9 W5 }, `- u
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
# N$ X' T4 P* ?6 O7 |' ^6 G!注释符号; 系统默认为自变量>0, 若不要求用free命令.
& I* n. l6 h1 M0 Q3 {5 n!在出来report windows之前可选择显示对此规划进行灵敏度分析等
按solve键, 在reports window中出现以下内容:LP OPTIMUM FOUND AT STEP* Z" @# A2 d& k$ v$ B+ n
2 & f) V, k9 }, ^: b! l G) ]
OBJECTIVE FUNCTION VALUE
6 _' `7 B8 _! V1): B- `8 ^( {' |; v9 v& d+ c
145.0000
0 e6 G- F' S2 l% NVARIABLE
% w1 C( b( L8 F' V! A% {VALUE
! o( R0 j$ o0 a# d. uREDUCED COST
! _' D' d" e' I, ?7 d: _. J4 pX
! n5 l" `. T) ^6 @! m- U10.000000
7 }" ]" E: l* A, t& r/ r. S0.000000
5 D2 y0 w7 W, u% n- o% H! t
Y
8 [$ W* A5 t' B$ Y3.0000004 Y p, r: v# }/ M% A) X- Z
0.000000
6 c* ]! M; g1 o0 AROW% V c5 Q- v' O. E5 t
SLACK OR SURPLUS c# i U. \6 M& s4 B8 C) p: ?
DUAL PRICES
2 C$ j, U7 K" d9 ~2)) O0 e% D M4 A0 G
0.000000
" } G) ~! W& |" r2.500000
n1 V& V. H4 Q/ J6 G1 U3)/ L+ E( \6 j4 V# I$ p
9.000000- p; U9 T4 |: O
0.000000
# l( `: D6 k# |
4)+ O- S! T7 h& I3 v2 g/ s
0.000000
* O2 `& W8 t8 A6 }! {7.500000
* [$ w U: I/ }9 V% DNO. ITERATIONS=2 W; f6 \$ B+ \' o8 ?3 Q' \
2
# e% I. M4 `1 W: M
RANGES IN WHICH THE BASIS IS UNCHANGED: 1 A' T# H! [& ]& f% `0 ?& t
OBJ COEFFICIENT RANGES 7 m! x! G, R& c
VARIABLE/ U7 n& I4 Y4 e3 f( u7 ]
CURRENT
% J6 C* s0 d( GALLOWABLE
# U. _/ T J V7 g& n: q5 ^ALLOWABLE
) S" p2 x# u6 D7 Z& N1 X% wCOEF
/ Y8 p7 l6 c* M( A9 P* _8 S, ~INCREASE
0 U8 y* J0 e( b% a7 a( A nDECREASE
% E/ i) ^) S; D) [) ~
X$ \+ v; U0 p. \4 A
10.000000: r+ Z9 o. r% T) F( i2 a
INFINITY
0 K u' P$ f3 Q9 G2.500000 / `* D( p' p0 Q* ?
Y8 p: ]! a/ r7 U8 G* V4 i$ _
15.0000006 W% K: ]6 @6 w7 o0 l o
5.000000
, A3 [$ r0 u( H15.000000
. U6 R" h' E+ c6 n: |5 z# M; @RIGHTHAND SIDE RANGES
7 i1 d; H* t2 J' ]; _
ROW
$ A# {; \ U1 L6 o7 t, z3 c6 |* CCURRENT( J9 a' j+ c& a2 l5 r& I4 v5 a
ALLOWABLE
# c& c, f; h; N$ O: LALLOWABLE
. g8 D( x9 p3 p# FRHS) G/ s D2 U w k Z9 e$ x
INCREASE
$ H2 q; C6 j1 x: \DECREASE
: k8 i; a. f1 I8 P) o3 f( X
8 g7 `% ^. {. }7 y0 Y9 z; d- ~2
( v' S# n' R/ M& P$ v10.000000" Y1 d" Q& E8 N: ^: @9 ]
6.000000
; i% U N$ s* j6 G- n1 _10.000000
& n6 `1 b2 \; J* o
3
2 v( j0 l- u# o2 s12.0000000 Y) ~" g+ _" \9 B \% N
INFINITY
, r4 }) G. t5 @- ?9.000000 - j, P* G2 A8 a
4
5 L( `- g+ c/ P3 p( Y3 I* X16.000000
, C M, f: x3 u& j( l5 p18.000000
0 T8 [; _, Y. D, K! y# |2 D7 F/ a6.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+ _/ o0 e- \: ^& S
report 窗口得到以下结果:
. F- N5 d0 k' N0 q) y1 mGlobal optimal solution found at iteration:- r& X( [% M. ]' h& Q$ x4 h. O2 F4 T
2 2 f, d8 D) F3 c) V E6 T
Objective value:0 o( u% `& W u/ j( r
7.750000 3 [$ U2 ]5 v$ m0 ?4 P5 V- t
Variable
# D1 `% F; N9 i8 `5 u& t9 TValue1 `7 N( @* F5 H6 t
Reduced Cost 9 `- K/ X( B2 p2 g, L: H* ^8 A' l
X1
1 A& P0 F' U' _0.5000000
( G, v& s& y' q% D3 C. k; e0 N0.000000
6 z) p0 j8 q1 s4 Q+ q5 \* E2 SX3
* {7 u! u# z. M- O$ R6 y0.2500000
" p4 {# N# M; P. m0.000000
- m- m) y% ?% l" L1 g
9 ~) i( ?5 e. V* K. AX2
4 M& A$ q$ m7 R- H& I7 R0.000000
, A, p6 w* K" m; {0.5000000
& }& E- A. M) E0 d& IX4 K7 V. l. K7 @+ ~9 [
0.000000& o( U/ R2 n6 o: h
2.750000
# ?9 m N {- ^4 ^X54 \+ h. ?9 c! S
0.000000
6 J1 Y! i: G9 V% L- M# O" v2.250000
! a) M" r* A' }) w
Row' x7 E" C; u# O& b+ x
Slack or Surplus ]7 E( H! u+ Y8 T3 {( M; Q0 F
Dual Price " d8 I0 A4 J0 h7 b; }* l( n* L
1
# u5 u+ e; A) Y" D7.750000" x) S+ S8 I$ [$ y4 U
-1.000000
: `- Q; C+ f% F+ m2- u0 a4 I& i0 c+ T$ r/ n
0.000000
' o5 v* G$ c3 V7 B n; G-2.750000
% }& u! ]- @: o% |# {: q. _
3; p% P0 B8 U8 [5 }/ {- }9 r8 l
0.000000
6 {$ q- _& X( J7 ]0 b# A-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;
+ b$ s# \3 b1 \9 l8 h4 L! this is a commnent; x<=100; y<=120; x+2*y<=160; 按运行按钮在solution report 窗口得到以下结果: Global optimal solution found at iteration:3 j3 @/ @0 G# s+ @0 J
2 ; Y, C; d7 y* x, F4 E! F# U( w
Objective value:
3 H8 v' p3 U5 J0 b, a. Q, A2 I6 n" h3 U6 k& F! ~# S# U# E2 A
14500.00
0 z' o3 j7 A- ~0 uVariable
) A0 e. @ A4 F+ M* b& i9 Q- nValue
. U+ V% T/ k* C, R7 c: jReduced Cost
! f3 f2 Y9 n3 A& JX7 U% d: R* V1 l. n9 _( O
100.0000# w }0 |1 C; Y& C) P0 a
0.000000
# _- z5 H' z& X) LY1 q6 \, i/ q/ K& G! ?
30.00000
$ ?/ H$ o- L2 @& j5 |8 c0.000000
! S9 Z* x" c, k a' F5 JRow: A$ u/ f n0 P2 r% O
Slack or Surplus, k1 Y8 n( ^& D
Dual Price
/ V) D% d7 E$ ?- y
1
+ c1 D, g% b* s5 j; f2 X* n- H14500.00
" ~7 M, j1 t3 N" G4 U/ {1.000000
: Y( h) _+ G) H2# _# H K7 |8 v$ l
0.000000
% h4 K1 V }4 b2 T25.00000
4 X! k# R9 F0 ~7 E3 \5 R2 d9 L! x% y, D
90.00000
* a' O: g3 L P0 [' Z1 J0.000000
4( z, h2 t _" ?6 ~
0.000000& E: P( E2 a& i y8 }
0 j$ U n8 t! m( V
75.00000 |