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

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

8 L9 D9 B; f5 W! `-1

3

3 B5 O* `/ u7 y# f6 x-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 =
  c' g3 X$ _) K7 x  f* [1
2
4
-1

" \( [: |# O! h0 j1 n2
9 S0 A& |5 }. s3
-1
1

2 l, @- `9 K; K" h/ Y! Y' a# [" O1
0
1
1

9 z  C) l: R  Z/ K% A( |-1
; A% {3 m4 _% L# t0
0
0

6 v% [1 j0 I) n  `7 O* Q0
-1
/ q3 t6 K3 c0 a* R! ]0
3 R* l( I6 ]7 x$ N9 j! C0

0
! t% [! I! s9 B0
2 I: v* m0 i8 X; \* l! S-1
0

0
3 @! p& W( U7 w# g! D1 t' @9 t0
, t& u- ]* I0 G0
6 [6 r( ^6 S9 O$ r8 q" d-1

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

b =
5 L, G; P) o% X' A2 u0 `0 R6

; o# A% N  K6 ]& f12

/ L) v. }" `& m/ ]" Y4

1 H. c8 T2 `+ ]0

0

  B0 R  @# e# c, L  l0

7 R: f) }$ c, L3 Q& F0

Optimization terminated successfully.

The optimization solution of the programming is:

x =
0.0000

7 n; R  ?# b! f) Y2.6667

2 \3 ^9 Q6 Q& X5 ^/ b7 z  m4 H1 Z-0.0000

" R* D8 n) Y! B) I$ ?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
* s: o1 ^" w0 J% a, |2 y) W+ F！注释符号; 系统默认为自变量>0, 若不要求用free命令.

$ ~* s  D$ K. q/ I) Z$ W2 `！在出来report windows之前可选择显示对此规划进行灵敏度分析等

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

LP OPTIMUM FOUND AT STEP
2

8 i5 L' J# M2 d/ Z4 r# R4 |+ u. SOBJECTIVE FUNCTION VALUE

4 s: L7 T1 o9 Q) V1)
145.0000

9 U+ z# G% k# n! m! gVARIABLE
7 y5 f0 X# k2 @3 h- s; V2 h7 fVALUE
REDUCED COST

# g' {1 K; G& J, d, _0 |5 yX
* S4 a! ^" r" J! s10.000000
1 b5 ]4 T% ~3 e6 D# Y$ X0.000000

Y
3.000000
* c6 a# i3 H2 c* k0.000000

+ |% c% f$ d+ s; I. r1 A# gROW
2 j8 m: b5 t, nSLACK OR SURPLUS
DUAL PRICES

2 f0 w* l6 p6 b2)
7 `1 r3 n- F4 S3 `* f3 g- u0.000000
" C# w: Z* [7 E- r1 v2.500000

8 X# o# v5 a: K* K* ?+ @- J& F3)
* }; K# Q# D3 W& A2 p( X3 {9 ^2 Z9.000000
+ y- Q! C+ X( {/ c1 v- {% g0.000000

( T; q  X% @1 g7 T9 R1 `: r, Q4)
( v5 B5 Y9 e" w" X0 A  _0.000000
7.500000

, U1 X2 c, W6 T: @) V& |NO. ITERATIONS=
; ~- v  S% s2 w$ ~2

+ F2 c, G3 f" u' G+ z- i" ]. h4 PRANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE
CURRENT
ALLOWABLE
ALLOWABLE

+ b7 j6 x6 A3 g5 k. n* rCOEF
INCREASE
! P: m$ u3 E9 Z7 MDECREASE

" R& c9 U/ m; M# P' ^" I  ?( X9 bX
9 U, O2 x5 ~; X10.000000
3 b  z/ B( y/ qINFINITY
2.500000

" m$ L' T4 a$ S9 [2 u# U. k9 KY
! M. N( X7 L7 \6 c6 n$ D15.000000
4 H0 j: u0 A0 d3 V  S5.000000
15.000000

RIGHTHAND SIDE RANGES

% |% c1 {# w7 jROW
CURRENT
% j+ W" |5 `: n5 LALLOWABLE
ALLOWABLE

0 q9 s. m2 A3 T4 O* H" z" S( ?$ i/ HRHS
+ T2 h: r) x8 T2 t+ GINCREASE
DECREASE

) O5 S+ p- B- T
9 K, l4 ?6 \7 M1 u" T: [" \2
10.000000
6 B2 ~& P( n) u6.000000
* M3 i& @' ]+ j) X. _10.000000

/ o* N. i3 Z% K0 S- @" B3
12.000000
INFINITY
2 {5 W; G8 E5 x8 N9.000000

4 r1 K$ i: m! R+ m% j. l4
' z9 w/ g% P6 V1 R16.000000
' l" ]" k, {$ P8 n: _18.000000
) K' Y5 Q+ \- N5 J$ l- s6.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
report 窗口得到以下结果：

Global optimal solution found at iteration:
# i9 k( B% Q, H2 M2

3 c3 M/ l3 _# h( T/ s8 G7 Y0 xObjective value:
7.750000

2 s3 I" D; w8 n5 \+ c! y3 Q& r4 }4 p3 LVariable
Value
% b# ]$ v" f7 \+ r* SReduced Cost

X1
" s" d7 p' f  z" g# P9 J0.5000000
0.000000

X3
0.2500000
0.000000

. M  \; T' s- D4 _
- N( ]( B: {% x2 j' mX2
0.000000
' A8 o$ u0 Q. Q9 A) N& s0.5000000

/ d  \- @9 Y3 b" ~2 xX4
0.000000
7 o" O! E7 S) R4 U* }: y2.750000

7 H9 V7 f2 R! D$ T0 zX5
/ @: f7 F$ H8 a6 X0.000000
! z8 {2 `; u/ I2.250000

# I2 ~9 I0 L8 J# Q0 URow
Slack or Surplus
/ U" G3 j" }- S1 R( x$ [1 Z. w5 |8 pDual Price

8 B' O3 @, W2 |9 Y1
7.750000
-1.000000

2
0.000000
, ^2 T, b. Z4 H& Q. K-2.750000

0 L- D! K! r- u' l' G5 S3
! M- b* P9 f# f0.000000
; C. G# S8 T" y# o$ P, m& c) v-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

Objective value:

14500.00

Variable
9 T( x/ n) o2 l$ h- e0 WValue
% {/ Y( Y7 K, m4 PReduced Cost

- w+ m) \$ D8 |/ u& k; IX
7 ]* T" v3 Y3 G" _100.0000
0.000000

4 z' Z# b  }" j/ t+ R) i' SY
0 N0 @: N4 g" o' {) o30.00000
3 H, F- T2 `3 O4 I$ Y4 c* q' J8 b9 ]0.000000

Row
Slack or Surplus
; _$ c9 n) S0 ]2 R1 hDual Price

1
14500.00
! s+ B* R% F) m3 P' C- d1 d/ E1.000000

7 l+ F- T' b1 {$ O" a  R2
0.000000
! y7 M: I. d6 J5 A25.00000

3
) O0 @0 @  ]" d/ Z/ Z3 @: `1 t" s90.00000
& o' o$ S. s1 x; P. j* O; L$ e: m0.000000

4
0.000000
( X  M! r) Y' T9 Z$ ]
9 p+ c  U5 `7 [' O75.00000

loooog12

先下下来看看