运筹学第三版（刁在钧）光盘中的内容

mnpfc

第二章 线性规划

本章, 我们介绍三种解决线性规划问题的软件:

第一种: 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 =
- N, h% p* x4 R. Y0 j-2

-1

3

-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 =
1
2
5 \. k1 i2 k( D' X% ]4
* Z' S* L4 H- p. D# D& U-1

2
3
-1
1

+ S4 V. l. X- q! Q7 E6 f1
0
1
9 o1 P6 I' Q3 b' H# O# x3 z1

1 G4 y* |5 s  \3 n& A-1
0 t7 {7 ^2 F3 d$ K2 O: H( F$ |0
$ Z. F0 [' ~$ q& @2 `# A0
8 a- @, N0 M/ P  {0

5 b' M/ N" k! k7 Q4 U% e! k4 P5 G* r& l0
-1
0
6 ^6 o/ G  J; O5 b. f- c' [0

- z& K; s6 f- G' n0
1 G9 v! @1 i; L  r& y% P9 s2 z: y& W0
. D2 j0 D) d, c9 I0 H, E' p. R2 d-1
0

0
0
5 b) u- _& p0 [' G0 ?8 U9 w* g; B2 \0
-1

Please input the resource array of the program b(m)_T=[6,12,4,0,0,0,0]'

b =
6

12

, V$ D2 A1 Z  J; V( e' l4

2 ]% l, ^+ c( o* M0

0

; ?+ q5 J+ e% _1 M0

. a- d' E$ m. r5 Q0

Optimization terminated successfully.

The optimization solution of the programming is:

x =
4 L; v8 o+ x0 M$ o3 s1 q! i0.0000

, t7 m0 t* b; b* S# ?; F  n& }1 e2.6667

% ~- T9 H( ~# B( @-0.0000

3 d6 \( i0 x' n3 W: u. l4.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
& c" X2 G5 z8 Q9 j2 R) S( w" i5 K！注释符号; 系统默认为自变量>0, 若不要求用free命令.

！在出来report windows之前可选择显示对此规划进行灵敏度分析等

按solve键, 在reports window中出现以下内容:

LP OPTIMUM FOUND AT STEP
, u" ~" q% w% E9 `6 H! }/ U2

5 |8 v, ~6 {8 `% a* n3 q  a8 ~OBJECTIVE FUNCTION VALUE

1)
* U2 F' x# i8 I0 q/ n* E6 }145.0000

VARIABLE
3 t) _) k# @5 ?4 hVALUE
; @& [3 R( C( c  t) yREDUCED COST

X
10.000000
0.000000

; Y8 d* A) E" P3 ~Y
3.000000
0.000000

/ {! V: L3 U8 ~& \8 t# qROW
SLACK OR SURPLUS
DUAL PRICES

2)
) @) b4 u" h" V) D0.000000
0 a- K" A" w: A) s* B9 u2.500000

9 H4 u" G& _  D+ D" o% X$ x3)
9.000000
1 R- v, I4 t9 j+ _2 P0.000000

) ^9 |& [0 z9 q4)
0.000000
  i& Z$ s  o6 }7.500000

NO. ITERATIONS=
2

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE
CURRENT
5 t: R+ y) s/ }$ P- C. E: e+ kALLOWABLE
3 Y9 h! K# w8 b3 Z; cALLOWABLE

COEF
8 E" P7 p; U$ H1 C% M7 V7 i( |INCREASE
( J% {7 n  f3 M$ w, S8 q" m8 U! zDECREASE

X
10.000000
INFINITY
2.500000

Y
8 Q/ X# P. {; w1 ?1 Z& A, ]# B15.000000
8 h  I7 F$ M6 e- }7 F+ l5.000000
15.000000

: i6 }, B( ]: DRIGHTHAND SIDE RANGES

ROW
4 s3 |3 C2 d* E  n! _CURRENT
7 F3 y& Z, T3 o5 _ALLOWABLE
ALLOWABLE

RHS
INCREASE
DECREASE

$ N0 b5 ]7 X4 I- w; `- o% K" i
2
10.000000
6.000000
9 w$ h' a" T, L6 G$ B/ {0 F10.000000

) m9 A2 h9 ?) B8 D3
; J) }0 i) h2 Z7 y0 o12.000000
, R+ A- d' X0 }$ a! P$ XINFINITY
9.000000

& u( _% p7 U+ a5 L1 p( u, H1 u9 w4
16.000000
* G3 G) ]/ r/ F18.000000
5 S! k" R$ |1 C' b. [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;

按运行按钮在solution
6 j( d* O. K  q' L; B- rreport 窗口得到以下结果：

Global optimal solution found at iteration:
) W9 f3 c+ p0 m& p! h( Z* \  ~2

Objective value:
7.750000

& Z8 L7 X. ^: V& l5 v5 I- d* h: P$ LVariable
% _# W6 n; R" k1 }# {, k4 A# zValue
Reduced Cost

. {4 J" o/ M7 c  R# I; r3 KX1
/ j, l7 ~  N8 ~" g8 N& a0.5000000
0.000000

0 I) i7 v9 d& Z8 G9 ]- i. k5 ZX3
; g) v0 v  E9 Z: i0 a0.2500000
0.000000

/ h0 \$ @% ]" {: D/ u/ a8 L
' \; W8 }. n7 l) N% q' _X2
8 M0 m' m) `+ M* }5 e8 |0 u0.000000
4 s) g- W/ h) a" D/ C) r5 R0 ~0.5000000

X4
, z/ ^+ l8 S; Z9 ]0 [- k0.000000
" ?3 D# P% W' @( t8 ]; j: ]2.750000

% C* S: w. M, sX5
0.000000
7 ~$ g8 G. M- W& m% ~2 Q2.250000

Row
, b/ c( f% `) i0 i$ i! rSlack or Surplus
Dual Price

1
7.750000
& a# R9 R- p" i' I7 B9 l-1.000000

2
; M! ?; R* _! _) _' y( T0.000000
5 T# F6 v' {$ \# C7 p$ o-2.750000

3
0.000000
-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;
! this is a commnent;

x<=100;

y<=120;

x+2*y<=160;

按运行按钮在solution report 窗口得到以下结果：

  Global optimal solution found at iteration:
$ a) h! c9 \( f& S/ Q+ E1 F2

, |: w( K' J  L1 G" TObjective value:

: J' C0 [8 m, s$ x6 \  j: o% x14500.00

Variable
) q0 F) o( r6 d( C# }2 vValue
Reduced Cost

( e/ o5 v' d: W4 k1 PX
100.0000
. I3 q. v$ A8 s( }, m) T0.000000

Y
0 T$ l. ~0 E8 a& k8 B# I30.00000
# X) K. C: R" |5 `5 b: N4 i9 G0.000000

! @7 ~! a, h" _/ @, [1 d% HRow
% ?3 n7 f2 j% jSlack or Surplus
5 f/ G! C+ w) oDual Price

1
14500.00
& p1 O  i# R) D6 U+ d1 L1.000000

2
. X: J% ?) m; ~, H+ D# Q0.000000
4 o$ a4 P1 q& Q3 M: a1 ?25.00000

: X" T6 _/ U# n$ C* v; i6 _3
90.00000
0.000000

4
0.000000

9 M+ s3 @. ]) ^9 s" M75.00000

loooog12

先下下来看看