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

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 =
-2

7 X- j4 E. t; _-1

$ N8 T7 Q; _) z3

) Z4 M' s" a* F/ m$ D) L-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 =
& g$ p3 e" v8 L9 n+ O" y1
" q4 M  l; C  D5 L8 D/ m2
5 y6 J  o, g8 J" u7 K4
-1

2
  s2 `2 _( b. f( l7 q) ]3
-1
1

1
; w$ c9 ?. Z+ ?" b9 l! g: e0
, a; {3 j1 Q& B: y; a2 _- F1
  |' l. X  a' t1

: B2 _! M4 s5 |% U0 g: |-1
+ X- d8 |6 v+ I+ c( F& O0
0
% p5 y. b/ \9 O& _' u- j+ T0

0
-1
- `) L4 o+ {/ Z; Q4 m0
$ l) R! k0 e7 P& T: |0

0
0
-1
& l8 M1 G+ {1 l+ u0 c/ D0

0
4 w# h. D0 ?! h" O( T5 G9 f0
0 M: `" g0 T* i: v, `' G0
-1

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

b =
7 t2 j8 C; s/ v' A& p' }' x# ?/ W6

12

4

- \* F: k$ O  a( E: O0

0

0

0

Optimization terminated successfully.

The optimization solution of the programming is:

x =
  Q! z. d* u8 z# D3 t6 V0.0000

2.6667

-0.0000

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
( p+ V$ M5 B; o3 B！注释符号; 系统默认为自变量>0, 若不要求用free命令.

% ^! h5 I: D% [& T！在出来report windows之前可选择显示对此规划进行灵敏度分析等

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

LP OPTIMUM FOUND AT STEP
2

  L  r. V7 E9 U5 X- |5 a. a0 mOBJECTIVE FUNCTION VALUE

1)
" u' [3 Q% k3 ~4 D, k4 F% m  H145.0000

0 u* F2 [6 X, `9 \VARIABLE
7 b! W5 F" D$ Z, G/ Y: H* cVALUE
  T, v5 ^, a2 k1 m" RREDUCED COST

2 y+ S; p$ Z! P6 ~/ QX
10.000000
4 Z) n+ A: c. I6 P0.000000

. u) [9 u0 S1 C2 _2 T/ C% `Y
3.000000
( V% S7 Z5 [/ F4 f6 H2 D8 C+ b0 h0.000000

ROW
* Z& m2 c4 X/ s, M: X  ZSLACK OR SURPLUS
DUAL PRICES

) y6 K* Z; c/ J' m2)
0.000000
2.500000

% Z$ Q% t. q3 m0 G3)
' V& X0 I7 \" V$ M. t2 L9.000000
0.000000

4)
0.000000
3 ~1 Q1 v/ \! E: o  M7.500000

1 B" b; N4 Q( L- ^NO. ITERATIONS=
0 @2 Q: [5 z5 h/ V9 I2 ~+ Q/ a2

RANGES IN WHICH THE BASIS IS UNCHANGED:

6 J+ t( x2 c. R  t9 ~3 Z! p- oOBJ COEFFICIENT RANGES

VARIABLE
* m8 I! ]* B& g  m6 f! Q9 W) [CURRENT
ALLOWABLE
2 n$ W& }, G/ R2 c% vALLOWABLE

COEF
& r- Q0 s+ i7 ?; k' U- X' oINCREASE
DECREASE

8 M6 |" O4 ]: m% J1 z; h! eX
( j( u  s; F  \8 {' n10.000000
- }4 @4 ^; h1 p# _INFINITY
2.500000

+ ?( W* |$ _- s+ E3 E/ J# @Y
. z+ }$ L5 _/ G, o  A& N9 p15.000000
. n( j. R0 r- [$ T5.000000
15.000000

RIGHTHAND SIDE RANGES

+ x0 k2 r# \+ a3 H  \# @ROW
CURRENT
5 H4 C$ o- r- H9 R& vALLOWABLE
) U0 s6 F% K4 _' G( rALLOWABLE

RHS
7 G4 T6 J5 P) I) G. _, Y; Q5 o; jINCREASE
DECREASE

2
7 n; k! a( s" @) @10.000000
; F; `  ^9 G4 ~8 T6.000000
/ H5 g) _8 i  x- I* x# h10.000000

' W7 t) ]- S& n- [# N$ `  I9 r+ m( ^3
12.000000
INFINITY
* I4 X* w, e, }+ b1 W. S' U. @4 b9.000000

; O0 O- f$ `7 l2 M4
! n1 M+ Y' N. a7 x4 O" z  V16.000000
18.000000
  C- p% [6 i- y4 r/ 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;

按运行按钮在solution
! p& H" o" b! o, H8 y! h. u2 Mreport 窗口得到以下结果：

. ~# J7 i  \, o/ O, ZGlobal optimal solution found at iteration:
2

3 f0 g6 v. y% J" C" D8 kObjective value:
7.750000

Variable
$ W: |0 _: D0 r6 G* ~Value
Reduced Cost

. i9 N, p. Z" n+ W9 J1 m' _X1
$ S6 S! z4 J% S$ n2 {! U0.5000000
3 b* T6 [2 i' p) d3 y( M9 i0.000000

. q0 o2 X* S& g5 e5 i* UX3
0.2500000
0.000000

; w2 b; d5 t0 J5 `5 R/ h/ ?
X2
0.000000
0.5000000

; k* r: ~" X, Z2 B# W# TX4
0.000000
0 w$ i, r9 v" e2.750000

' n+ _# \) g: h, NX5
0.000000
2.250000

Row
4 e- x7 R& F5 y+ h. cSlack or Surplus
9 v) p# }6 x" U7 X5 Q' y8 s$ @Dual Price

1
7.750000
) x* _9 c, [; V! _-1.000000

4 c0 X& y! J1 x+ ]5 q6 T4 p2
3 b3 e$ q; R4 d! W" T# I0.000000
& c" q8 Y5 ?5 C8 u, {# {3 ~, o-2.750000

' y9 k9 }: \+ P* m0 t3
; O5 T1 J' w/ D2 S- ]# d0 O0 J0.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:
2

4 T4 z8 F" ~6 d' H/ l% K5 \5 P7 iObjective value:
# s0 Q* e. a' h! A
14500.00

1 g5 k( z" r2 t% t1 DVariable
, k) @/ l; X* E. AValue
8 R* k2 P5 p3 L/ vReduced Cost

- O; _0 I: z  V, MX
100.0000
+ v8 _; O/ I6 H0.000000

: R8 _# g! B5 G0 FY
30.00000
0.000000

Row
; z* j. L1 J9 wSlack or Surplus
Dual Price

1
14500.00
1.000000

2
0.000000
& f$ ^1 P8 ]% P% c/ U/ V25.00000

. ?# V  y$ I2 z0 X2 ]3
90.00000
0.000000

4
0.000000
, W# x) S6 w, D: W& O
+ _% a; ?( B+ a, L! j* g+ r8 U' F75.00000

loooog12

先下下来看看