|
第二章 线性规划 本章, 我们介绍三种解决线性规划问题的软件: 第一种: 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 = W, R* d+ S0 D
-2 & P: D" s- b8 d6 j8 i3 W
-1
) ]$ K$ F9 R, m, h7 p3
4 J) b8 O1 x6 \/ p+ k
-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 =
+ ~; k7 E( b, W4 m' N1
7 ?1 Q# r/ j" t q% A6 l* c* A$ H2& |. ]3 }) n9 Q9 }* [
49 z/ J+ F) `) ~, ~; O
-1 ' \; a# k3 Z& X6 }' s
2
1 m! K$ z1 p0 V" e! K. B3
! B h4 p* j8 K) h" H! G-1! v4 a# h, v5 P
1 2 f; d! `6 b0 l9 p! O' n0 [
1
" R2 s0 k" x1 x" }/ Y; d$ ^" {9 K: {0* u8 J; x0 V1 G5 j& L
1
. w& l9 n" \( r) ]' R# `1 " P6 f5 ]( r! X
-1
+ E2 ?- ?) }) R; G( r+ O04 S9 P4 T7 L8 S
0
`: V0 d4 h+ Y' z. T& g5 Z/ z5 c0
2 A' u" B0 ~; Q0 u5 ^09 {5 e7 S6 l* k# }; G
-1
, ~* S" v8 {: I/ d/ J) a% {0
0 o$ f" B. M. I( w0 U0
5 ?: V2 l o+ H/ A6 Q0
. y# e1 U7 B1 e# V( c06 a, M/ a9 k% O8 z6 I0 ~9 C- [5 j
-1
4 W1 @! ] \& Z# D) z3 N& e0
1 B5 e, a0 L8 O/ F, u' w3 n& Y5 {( M
0# W) f$ Z* `+ L5 T5 k
0$ H: n! A. @) R+ m$ E3 ]/ f D
0
1 ]; H! H8 V" w a9 d! [' Z-1 Please input the resource array of the program b(m)_T=[6,12,4,0,0,0,0]' b =
, j4 J/ b* |& p( `6 9 |4 u3 m5 H# C! I, k; I {! Z5 d/ `
12 ! B; d. w- \* T) d# g5 ~3 ^) M z. s
4
+ [4 L) |2 \1 [7 [3 A6 v" L0
# H6 {, P% V4 z3 ~; U0 k0 \
0
- U l) M9 D6 C+ A2 ]( S4 o9 ]0
; I# }: \3 R* x* z" N; u0
Optimization terminated successfully. The optimization solution of the programming is: x =$ u8 d6 S; R) L8 ^1 ]0 ?
0.0000
: u3 K1 P3 L8 z; ^$ [7 k; W2.6667
0 h& ?* c) z8 J-0.0000
$ {) p! Z8 o5 Y3 b: d4.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
% o; E- w1 ]% ~& e! y& `!注释符号; 系统默认为自变量>0, 若不要求用free命令.
7 a: Z7 T6 n- ?: V+ v( [!在出来report windows之前可选择显示对此规划进行灵敏度分析等
按solve键, 在reports window中出现以下内容:LP OPTIMUM FOUND AT STEP* h7 P. p7 M& E& }. }
2 2 J) ]! J. ^1 r, K0 ^
OBJECTIVE FUNCTION VALUE $ b. C, P5 t! _; h& o9 H3 Z6 S
1) b& O( X- C* L* ^
145.0000
; r/ b/ l8 ~, xVARIABLE
+ N* Q7 n7 O+ {VALUE. p7 s N. J7 ]' M( t
REDUCED COST
& ~2 t. ]+ [. {# b; s& e- y
X- n9 i+ w7 d; e- i, s% P& k; y
10.000000
; o c0 P, P$ _6 i; v4 x0.000000 9 N4 y. e: b+ w( Z9 ^
Y' e5 N6 h4 P4 w: a+ O( E% b
3.000000
" v* s J! W. }. f0 @2 H; ~! e2 g0.000000 9 V3 w. w4 L( b: ?7 [1 H0 F& J
ROW
* S; s0 h0 M/ ]- ?& U. V0 g5 ySLACK OR SURPLUS8 J9 i, {2 Q' \# c4 G
DUAL PRICES \ T2 m% ?+ ]4 X4 r
2)( D4 h) R ?8 Z) N9 j5 j% A) z
0.000000$ H, h7 J3 X; s
2.500000
/ ~ b( H* R3 e! ^" y* H9 t3): H0 H# Y B9 _$ U$ V# v& y, L( F
9.000000
$ i/ |0 a2 w z# F+ F- {0.000000
3 P9 G( U g$ C4 S
4)
. B8 ~+ r7 X2 ?) s9 Y9 p' t; [! X0.000000
9 \ F- d6 p! h; x/ Y7.500000 4 `" }0 T' P8 B- G' ?; ]
NO. ITERATIONS=
7 f1 ?+ M8 k% h9 x2
- {% u! T/ C, pRANGES IN WHICH THE BASIS IS UNCHANGED:
# }8 o& f3 ~7 y: \' |0 I6 t8 B4 d e7 r
OBJ COEFFICIENT RANGES % `* M; r' o( S ~; m4 C
VARIABLE# I, R! O) q5 X6 W. n+ P
CURRENT
1 M! Y5 j( p; g5 [7 l" o: \ALLOWABLE+ K9 M$ w: i9 ?( y6 J
ALLOWABLE
3 O( Z( p* e+ C0 Q1 i8 j+ hCOEF# \! c, b3 @ D
INCREASE
0 S8 W: n6 p- h5 Z5 O( r) @DECREASE
; J8 E$ ^- O' V
X
% c) ~0 N+ M6 u; ~. {) T10.000000: n$ g/ q1 P7 }. _! a( Z) w
INFINITY$ V9 X- l0 U2 n4 A. n0 d
2.500000
! Y* d- z: |7 J% W# ZY% t. r9 Q3 h! R/ c1 b
15.000000
, n+ \* B. A- F& Z/ v' D5.000000
( N- V- J* @& K15.000000
/ Y/ C6 B& w5 `) @' gRIGHTHAND SIDE RANGES
6 W% n3 z7 ~# M8 f, T, H
ROW
7 q' w) f7 g0 K) D' B" @CURRENT8 }6 J0 k: K! R) p
ALLOWABLE
. `+ w0 _* j+ s9 I! Z: |: l) QALLOWABLE , b1 B i- Y1 L! E5 X" ^
RHS
[) ]. u: A* T3 D, S' I9 _INCREASE' I1 K$ V# P. G# P; g/ X
DECREASE
2 P# {; D/ F* x( g1 _" |& _& m) O4 N, x; |8 ]8 H
2
* Q7 F$ g; y" D10.000000
V9 N4 T% u$ |0 N6 d3 g( `6.000000
8 P1 i' A- \5 N! N5 j' H. E0 A1 k10.000000
5 D, |& o+ t7 H5 T$ s o
3& w9 E$ a& X2 O1 H" {1 O
12.000000
1 ]' j8 n% L: ^7 FINFINITY/ {5 t4 K! ~+ f; D8 v* u
9.000000 ' {- P6 \4 y4 n7 e# _, r
4+ k0 v& j' r4 i6 m+ K/ p
16.000000
* \$ b7 `/ S9 K4 \' k18.0000008 W/ t1 I6 f6 d* n3 x Q5 _9 e
6.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; 按运行按钮在solution6 ?, B4 i# X* ` U( Y" v
report 窗口得到以下结果:
; _, |& F" A9 s9 M XGlobal optimal solution found at iteration:
" {0 q7 d( \* N8 b+ M: Y1 n2
+ D: l9 i1 j A6 H; X; ?$ ]0 SObjective value:
& Q) P5 }7 B# P, l, T7.750000
/ w1 U+ ~ z# H( Y8 m2 w
Variable
' {+ v2 S& a9 Q2 f+ WValue
8 k1 M# S# L0 EReduced Cost $ Z5 P) J! N$ A+ U4 n
X1
6 }0 E7 K8 d- j' h0.5000000
$ ~# x1 J+ N5 `. r9 C0.000000 + C2 w! s8 s, f# v
X3
$ A6 c6 h6 T, B/ d8 a6 ^5 t0.2500000( @, [4 p9 B3 q, X+ v
0.000000
$ q: R! G$ d# P: G' r9 E. ^
9 I. D9 ?. f1 r T9 u- UX2
! d0 N, m4 Y4 R0.000000
9 r2 r: [+ D2 f" L0.5000000
% k- q0 f2 f* F- w5 R3 |. V1 I7 TX4
& N- C; ^- t. W( U- H$ @# v0.000000
" A1 A m0 Q* q6 L0 A! K2.750000
2 G5 q7 `! C, g2 ~- sX5( o# ^( E+ ?6 s
0.000000; |$ h2 k; E5 h6 O2 A$ O) p; B
2.250000
! C2 G1 A' B4 a# v3 X' {5 u
Row
3 y2 P3 a& R9 I" m3 lSlack or Surplus
, b9 z+ ^$ }6 _Dual Price ) E5 r* g7 h y1 V/ o& Q
13 d r" |6 G& x+ e# C" g- ^
7.750000
4 }" ^# v1 W( }. f. s* G' q-1.000000 5 J# q" A- D& }8 d1 s- J
2
, \+ p7 h6 c4 ^0 P6 f% G' s& N# ^0.000000. K' R, \" J8 P+ A/ p, C7 g# G0 R
-2.750000
8 O# d* g& t+ @ A7 ?) t2 d! m3
+ T- Q7 A: m$ K0 a X3 q0 `5 j0.000000! t* a3 z ~# ? m4 K
-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;" x, o1 f+ Q( I4 m( l5 Y! i
! this is a commnent; x<=100; y<=120; x+2*y<=160; 按运行按钮在solution report 窗口得到以下结果: Global optimal solution found at iteration:0 i8 m; B3 ?' S" h/ J& B! m
2
# w* `2 }3 A' JObjective value:$ |! i$ K- m5 M E6 }: s# W
# h4 Y7 b& v6 a
14500.00
6 x, e) Q# g$ u5 R+ @/ L: c; [# BVariable* k: q5 }' r I9 U1 L* N4 y, j8 `3 J
Value0 K g: g. [" C+ [ F# I) ^
Reduced Cost
G0 N) L% T+ A: R- E' I8 gX+ P! P8 i3 S1 n$ G+ D" W' J, w
100.0000$ q( a" @9 _( A: C/ L# G7 f3 v
0.000000
8 C6 H8 o" p% v
Y
2 b/ r; E' B9 x+ L7 v, }. K30.00000 a- ~! ]1 W" T1 B
0.000000
" l, p0 x" o/ b7 v. p& o4 ]* ]Row
1 ?( X( v9 z5 PSlack or Surplus
6 {$ m; W/ E3 k v/ ~. }3 eDual Price
0 p+ P' ?/ ?4 S3 r& Q! \1$ ^( }: ?; x9 l1 N* \
14500.00
; W0 ] V. j/ p% R2 z2 t1.000000
: n9 e8 n. L" V6 s4 `2
! ^) J# L" N" b/ N J, H0.000000 F" c+ a9 @, u+ x
25.00000
2 ~8 t: ]9 B, ?' U3 U2 J6 M7 I8 K7 |! z
90.000005 V1 c) Q0 W- ~ z- X
0.000000
4
$ [+ V7 e- h6 u. i0.000000
+ W9 u% j1 N) n" X$ O6 `
, r& s R U0 x1 x# {& J- p75.00000 |