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

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

* e1 Q* ]  h5 @- J2 f* P) g-1

3

# o) ~  r, D6 _# f1 R- |: {9 u( o# `-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 =
# x7 c( Y3 f6 c1
2
8 N5 @7 e: s0 }, s; _4
-1

) C/ g: |9 d# z1 x- T9 e5 f2
3
1 W! Z; x1 k, F4 a2 r' d( f-1
- u% u; s: ^4 U  f" d9 G1

1
0
0 N* x- p7 ^7 s/ ^. I6 ?1
1

5 B7 _' S% M! G-1
0
- \6 m4 L1 T2 @2 i) L0
0

3 \. U  Z. x7 W( z" K. t0
4 i: w. \" ]; E8 r/ w; R-1
0
* h; @( J" Q" @' F% q7 T+ W! s0

0
0
( I* q& k& @- n& l, _* z7 i-1
# v3 ?! S; M1 t8 J0 ^4 J0

0
0
/ H* s9 ~0 w# e) u0
+ _; o& }# P+ Z" N4 R' x! S-1

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

b =
1 T! ^( t" H+ j) b: O6

0 }. R) z# e/ H3 K& Y7 J$ C12

$ i3 N: z, l+ w0 z# X* ?4 Q4

0

( L! A( B1 X& X& `1 L' S0

" J) E, w! o- s0

0

Optimization terminated successfully.

The optimization solution of the programming is:

x =
* a0 P, {  s' E0.0000

- m* N2 h1 G/ ~; F1 p- _' v2.6667

: s- [# L$ w9 [1 p" Y-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
！注释符号; 系统默认为自变量>0, 若不要求用free命令.

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

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

LP OPTIMUM FOUND AT STEP
2

& F( e. ]( F8 z) z$ }OBJECTIVE FUNCTION VALUE

1)
/ K3 Z8 W( h: m) \7 u5 e' ]( i145.0000

: g6 c7 G3 Z* d1 R: L1 jVARIABLE
5 ^" ~5 S+ h- K: m' KVALUE
$ r) V& ?1 O( ^# k1 v- cREDUCED COST

X
10.000000
0.000000

Y
3.000000
0.000000

6 J* ^# e2 v& G7 ]  OROW
SLACK OR SURPLUS
DUAL PRICES

2)
0.000000
2.500000

( j! w3 Z. K! O9 ^3)
9.000000
0.000000

4)
0.000000
7.500000

3 J  x! \5 ^# n4 T/ W. S3 p5 E0 ^NO. ITERATIONS=
2

RANGES IN WHICH THE BASIS IS UNCHANGED:

) P: g/ L) d# j& r7 l, l; @! ^OBJ COEFFICIENT RANGES

VARIABLE
& i( i4 Y( r1 t; `, }CURRENT
ALLOWABLE
9 D& c# d9 {$ p$ RALLOWABLE

" I! I' h- I4 a) I* H# `7 DCOEF
- O. F3 }! _7 @" ]- X+ NINCREASE
DECREASE

X
10.000000
INFINITY
% U8 f' P3 X" C% K+ t3 g# ^" x2.500000

Y
6 Q* X. `3 J: D$ n" E  o2 G15.000000
5.000000
, u1 z( z" k+ |; _! M8 H% g15.000000

RIGHTHAND SIDE RANGES

4 a4 [" p8 d3 M. o; K! IROW
  e% y9 J6 F5 \* OCURRENT
ALLOWABLE
ALLOWABLE

RHS
INCREASE
DECREASE

9 C2 K! c5 i% X% ~0 h  `
. {, N! `' J- C* e$ w5 f. G+ H2
10.000000
- k2 U% ^' Y+ Y6 A7 Z6 z- a6.000000
0 O2 e" C5 j9 G; K! A, u10.000000

3
8 j* q3 e$ B: Y& |' |12.000000
INFINITY
9.000000

4
1 `' a5 m% z( e( z0 j5 i  u- Z16.000000
2 P9 _! B. ]% s. h  ?7 Z2 l  Q18.000000
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
# }4 ?4 K% k, g  N$ Mreport 窗口得到以下结果：

Global optimal solution found at iteration:
4 z9 m$ S8 R& I8 _" `2

Objective value:
! E! _, P0 k# P; M( R( c7.750000

Variable
Value
Reduced Cost

9 L) y$ V8 A5 A$ }" v, wX1
/ s2 X6 r; P4 b: m, W& O0.5000000
0.000000

X3
0.2500000
- y$ [) i% {5 B! C! k2 L6 y2 i0.000000

X2
- N* ~6 s! X5 e" X% O, \  c6 [0.000000
% U- J, n% R4 Z' D  G1 j! F0.5000000

8 f# v+ U- E- F- a: WX4
0.000000
2.750000

* x) y7 H' {: I8 C9 f5 W7 F) u# zX5
% ^; S( P' b" o9 G% a4 {  J& W" b* y) E0.000000
% a  Z8 \: i; j/ W3 `& G2.250000

5 d+ ~4 X7 `0 B: s) M9 YRow
Slack or Surplus
Dual Price

1
7.750000
8 |" o, B2 ~- l) w- {% m# m-1.000000

  O/ r1 w# K  W& I7 n1 e) I2
7 |- \2 l% ^% W( N0.000000
-2.750000

3 |3 o/ R0 e/ ~' ]! h3
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;
4 e. b( r  C2 Z. t, I9 T8 ^2 |7 F& W! this is a commnent;

x<=100;

y<=120;

x+2*y<=160;

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

  Global optimal solution found at iteration:
! _  p8 b6 m6 G+ {( ^2 o5 o# M' D2

/ q3 Q: B0 u& B! S. \* O5 \! L0 u0 VObjective value:

14500.00

Variable
Value
Reduced Cost

& s* ^: [/ K! q. d7 f0 qX
8 ?+ A5 G% Q: s& u8 F3 N. g9 L100.0000
0.000000

7 \- g6 I! R$ W7 q* QY
* q4 h$ N8 T: X30.00000
0.000000

Row
% x- {- e9 h0 kSlack or Surplus
Dual Price

  }( ~0 M, v. ]7 ^9 d+ v1
14500.00
8 W; d, v) S+ [- L1.000000

2
0.000000
. X: \: o% V$ v25.00000

3
6 d0 V* v) e0 x4 `& Y( G) g# m90.00000
0.000000

4
/ W& f/ m0 f, I# |) Q$ @2 l0.000000

75.00000

loooog12

先下下来看看