MBA《运筹学》讲义课件

MBA《运筹学》讲义

运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析

的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。

运筹学的核心思想是建立在优化的基础上。

例如，在线性规划中体现为两方面：

(1)对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完

成？

(2)在给定的一定数量的资源条件下，如何合理安排，使完成的任务

最多？

运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问

题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科

学依据。

随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解

已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进

行，这样可以节省大量的人力和时间。

第一部分线性规划内容框架

LP问题

L1基本概念一数学模型「可行解、最优解

实际问题*LP问题I解的概念一基本解、基可行解

煽本最优解

提出

一基本方法

图解法

「原始单纯形法

单纯形法一r大M法

L人工变量法一

对偶单纯形法L两阶段法

偶理论

一进一步讨论

'灵敏度分析——参数规划*

经济管理领域内应用

—「运输问题(转运问题)

特殊的LP问题整数规划

、多目标LP问题*

第一部分线性规划(LinearProgramming)

及其应用

第一章LP问题的数学模型与求解

§1LP问题及其数学模型

(-)弓I例1(生产计划的问题)

某工厂在计划期内要安排生产I、H的两种产品，已知生产单位产品

所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表

所示。问应如何安排计划使该工厂获利最多？

1II资源限量

设备128（台时）

原材料A4016(kg)

原材料B0412(kg)

单位产品利润（元）23

该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的

生产计划方案。

解：设xi,X2分别表示在计划期内生产产品I、n的产量。由于资源的

限制，所以有：

机器设备的限制条件：XI+2X2W8I、

原材料A的限制条件：4xW16（称为资源约束条件）

原材料B的限制条件：4x2^12—

同时，产品I、II的产量不能是负数，所以有

xi20,X2»0（称为变量的非负约束）

显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有

许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产

量X”X2以得到最大的利润，即使目标函数

Z=2X,+3X2的值达到最大。

综上所述，该生产计划安排问题可用以下数学模型表示：

maxz=2x1+3x2

x]+2X2<8

4%]<16

s.t.

4X2<12

%1•%NO

引例2.（营养配餐问题）

假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质

和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和

营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使

购买食品的费用最小？

序号食品名称热量（卡路里）蛋白质（克）钙(mg)价格（元）

1猪肉10005040010

2鸡蛋800602006

3大米900203003

4白菜200105002

解:设Xj（j=l,2,3,4）为第j种食品每天的购买量，则配餐问题数学模型为

minz=1Ox16x28x32x4

lOOOOX1+800々+900x,+200x4>3000

X

50x,+60X2+203+10x4>55

400x,+200X2+3OOX3+500》42800

Xj>0(J=1,2,3,4)

（-）LP问题的模型

上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使

线性目标函数值最大或最小的问题。它们具有共同的特征。

（1）每个问题都可用一组决策变量（X1,X2,…Xn）表示某一方案，其具体

的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对

变量的取值加以约束，如非负约束。

(2)存在一组线性等式或不等式的约束条件。

(3)都有一个用决策变量的线性函数作为决策目标(即目标函数),

按问题的不同，要求目标函数实现最大化或最小化。

满足以上三个条件的数学模型称为LP的数学模型，其一般形式为：

max(或min)z=ciXi+C2X2+…+CnXn

(1.1)

+/2%2+…+<(=,>)/?,

a2ix2+a22x2+---+a2nxn<(=,>)b2

s.t.......(1.2)

—+%%+…<(=，之电(1.3)

_X.-x2---x>0

或紧缩形式

max(或min)z=ZCX

j=iJJ

才4'W(=,2)〃(i=1,2,…,M

j=1(1.4)

x>0

_J

或矩阵形式

max(或min)z=cx

NX<(=>)/?

(1.5)

X>0

或向量形式：

max(或min)z=cx

£p产jW(=,N)b

(1.6)

X/>O=1,2,.••,//)

其中C=(C],C2,…,品)，称为价值系数向量；

a、]，，…Qi

2w

A=222称为技术系数矩阵(并称消耗系数矩阵)

，。帆2,…"〃皿_

=(Pl,P2,'",Pn)

飞「

b、

b=：称资源限制向量

_bm_

X=(X1,X2,…,Xn)T称为决策变量向量。

(三)LP问题的标准型

1.为了讨论LP问题解的概念和解的性质以及对LP问题解法方便，必须

把LP问题的•般形式化为统一的标准型：

maxz=VCX；

Jjj

maxz=cx

=h(i=1,2,…,⑼[AX=h

./=1或C

X.>0(；=1,2,•••,«)l_X20

maxz=cx

EPjXj=b

或J=1

X>0(J=1,2,­••,«)

标准型的特点：

①目标函数是最大化类型

②约束条件均由等式组成

③决策变量均为非负

④bi(i=l,2,…,n)

2.化一般形式为标准型

①minz—>max(-z)=-cx

②“4"f左边+松驰变量；f左边一“松驰变量”

③变量XjWOf-XjNO变量Xj无限制一令Xj=x：—x丁

④卜<0一等式两边同乘以(-1)。

3.模型隐含的假设

①比例性假定：决策变量变化的改变量与引起目标函数的改变量成比

例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假

定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是

一个常数。

②可加性假定：每个决策变量对目标函数和约束方程的影响是独立于

其它变量的。

③连续性假定：决策变量应取连续值。

④确定性假定：所有的参数®j,bi,卬均为确定，所以LP问题是确定型问

题，不含随机因素。

以上4个假定均由于线性函数所致。在现实生活中，完全满足这4个假

定的例子并不多见，因此在使用LP时必须注意问题在什么程度上满足这些

假定。若不满足的程度较大时，应考虑使用其它模型和方法。如非线性规

划，整数规划或不确定型分析方法。

对LP标准型，我们还假定r(A)=m<n。

(四)LP问题的解的概念

设LP问题

maxz=Zc.X.(1.7)

>1

£%吃=2"=1,2,...,八)(1.8)

>=|

%.>0(J=1,2,--•,?!)(1.9)

1.从代数的角度看：

可行解和最优解满足约束条件(L8)和(1.9)的解X=(X1,X2,…,Xn)T称为

可行解。所有可行解构成可行解集，即可行域3={X|A'=〃,％20}。

而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最

优值。

求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难

的。

2.从LP角度看：

基:设人为11^11矩阵,r(A)=m,B是A中的mxm阶非奇异子矩阵(即IBIM),

则称B是LP问题的一个基。

若B是LP问题的一个基，则B由m个线性独立的列向量组成，即

B=(Pr|,Pr2,…,Prm)，其中Prj=(airj,a2中…,am寸)\0=1,2,…,m)称为基向理。与其

向量Prj相对应的变量Xg称为基变量，其它变量称为非基变量。显然，对应

于每个基总有m个基变量，n—m个非基变量。

基本解与基可行解设B是LP问题的一个基，令其n—m个非基变量均

为零，所得方程的解称为该LP问题的一个基本解。显然，基B与基本解是

一一对应的，基本解的个数WC'、。在基本解中，称满足非负条件的基本解

为基可行解，对应的基称为可行基。

退化解如果基解中非零分量的个数小于m,则称此基本解为退化

的，否则是非退化的。

最优基如果对应于基B的基可行解是LP问题的最优解，则称B为LP

问题的最优基，相应的解又称基本最优解。

3.LP问题解之间的关系如图所示

（五）两个变量LP问题的图解法

LLP问题解的几何表示。以引例为例说明

maxz=2xi+3x2

$+2X2<8①

4x,<16②

4X2<12③

A：,>0,x2>0④

按以下顺序进行：

解：（1）画出直角坐标系；

（2）依次做每条约束线，标出可行域的方向，并找出它们共同的

可行域；

（3）任取一目标函数值作一条目标函数线（称等值线），根据目标

函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数

线接触的最终点即表示最优解。

图1

一21

其中，将目标函数Z=2XI+3X2改写为=---X.H—Z，因此，它可

-33

以表示为：以z为参数，以一2为斜率的一族平行线。位于同一条直线上的

3

点具有相同的值。

解的几种情况：

（1）此例有唯一解Q2，即X|=4,X2=2,Z=14

（2）有无穷多最优解（多重解），若将目标函数改为Z=2XI+4X2则线段

Q2,Q3上的点均为最优解。

（3）无界解

可行域与最优解间的关系：

可行域最优解

空集------------＞无最优解（无可行解）

有界集唯一最优解

无界集-------------＞无有限最优解（无界解）

结论：（1）LP问题的可行域是凸集（凸多边形，凸多面体，…）;

(2)LP问题最优解若存在，则必可在可行域的顶点上得到；

(3)LP问题的可行域的顶点个数是有限的；

(4)若LP问题有两个最优解，则其连线上的点都是最优解。因

此，求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最

优的点的问题。

2.基可行解的几何意义

对例1LP问题标准化为maxZ=2x1+3x2

$+2X2+工=8

4xt+乙=16

4%+4=12

_再,…,％5之0

可求得所有的基本解：

x⑴=(0,0,8/6,12)T(0^),X(2)=(4,0,4,0,12)1QI点)

x°)=(4,2,0,0,4尸92点),x«)=(2,3,0,8,0)T(Q3点)

*°)=(0,3,2,16,0,((24点)46)=(4,3,-2,0,0)19点)

x⑺=(8,0,0,-16,12)T(人点)小岱)=(0,4,0,16,-4)T(B点)

但A、B、C三点是非可行域上的点,即非可行解。因此，x⑴,x⑵，X。),

x(%,x⑸才是基可行解，它们与可行域的顶点相对应。于是还有

结论：(5)对于标准型的LP问题，X是基可行解的充要条件是X为可行

域的顶点。

(6)LP问题可行域顶点的个数=基可行解的个数W基的个数

3.图解法只适用于两个变量(最多含三个变量)的LP问题。

4.求解LP问题方法的思考：

①完全枚举法，对m、n较大时，C')是一个很大的数，几乎不可能；

②从可行域的一个顶点(基可行解)迭代到另一个顶点(基可行解)。

§2单纯形法与计算机求解

1.解LP问题单纯形法的基本思路：

2.单纯形法的计算步骤(表格形式)

(1)建立初始单纯形表，假定B=I,b'O

设maxZ=c1x1+C2X2+…+cnxn

%+4",+1

々+a2m+]xm+l+---a2nx„=b2

X；>0(J=l,2,•••,«)

将目标函数改写为：-Z+C1X1+C2X2+…+CnXn=0

把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组,

并写成增广矩阵的形式:

-zX|X2""XmXm+1…Xnh

「010…0alm+1…五In

001…0a2m+1…汀2nb2

...1

000〃mm+1…m

l-l0J

ClC2""CmCm+1'・・Cn

=。一七%%,代入Z中的基变量，有

以非基变变量量表表示示基基变变量量形形式式X七,.=〃-当代入Z中的基变量，有

7j==1l

Z=-E%Xj)+»jXj

/=1j=ni+\j=m+]

/〃_，n〃.

=EcA-EE(函M+YCJXJ

i=li=\j=m+}j=m+\

-E(ZMLX

i=ly=m+li=l

_，n__，〃

令Zo=£c及Zj=£q%

i=lf=l

于是Z=Z0+Z(ZJ-cj)Xj

j=m+\

因此，上述的增广矩阵就可写成:

h

zX|X2…XmXm+1…Xn

<010…0aim+i**•aIn

001…0了2m+la2nb2

000…1Qmm+lQmnbm

11inin

00...oZq”而+i-Cm+i

i=i1=1

再令bj=C,-Z,=c「£c%

1=1

则上述增广矩阵可写成下面表格形式：即初始单纯形表T(B)

CiGCmCm+1品

Oi

bXix

CBXBmXm+IXn

c.X|b।1........0aim+ia〔n

b20........0^2m+1a2n

c2X2

:.:::

CmXmbm0........1^mm+1^mn

zZo0........0Om+1...........On―g检验数行

上述初始单纯形表可确定初始可行基和初始基可行解:

B=(P1,P2,…,Pm)=I,X=(bi,b2,…,bm,0……0)T

从初始单纯形表建立的过程可以看到以下事实：

(1)凡LP模型中约束条件为“W”型，在化为标准型后必有B=L如

果b20,则模型中约束方程的各数据不改变符号照抄在表中相应的位置。

目标函数非基变量的系数则以相反数填入检验数行各相应位置。

(2)在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应

的检验数均为零。

(3)20=工(:也,2=2广5=工生为一的(/=机+1/一〃)

i=li=l

更好表现一般规律的在矩阵形式的单纯形表中

设MaxX=CXMaxZ=CX+OXL

「

AX<bA+ixL=b

其标准型为

x>0x,xL>0

将系数矩阵(A,I)分划为(B,N,I),其中B为可行基，对应于基变量向量

XB,N对应于XN，I对应于XL,(XN,XL)为非基变量向量。于是

TT

(X,L)=(XB,XN,XL),(C,0)=(CB,CN,0)O因此，矩阵形式的LP模型改写为：

MaxZ=(C^,CA.,O)XNMaxZ=CBXB+CNXN+0XL

1X」

XN=h\'BXB+NXN+IXL=h

XLTLXB，X.,,X二。

_xs,xN,xt>o

用非基变量向量表示基变量向量，有

ll1

XB=Bb-BNXN-BXL

代入目标函数中有

Z=CB(B"b-BTNXN-B-1XL)+CNXN+OXL

=CBB』b-CBB"NXN-CBB/XL)+CNXN

^BB-^-CCBB^N-C^XN-CBB-'XL

将

Z+(CKB-'N-CJXN+CKB"'x,=CKB''b

XB+BtNXN+B~'XL=B一%

写成对应于基B的矩阵形式的单纯形表T(B)：

N

CBCCL

bXBXNXL

B'b

B-1

XB1B'N

ZCBBI0CBB'N-CNCBB-1

例如将例1化成标准型后如下表T(B)：

Ci23000

6i

CBXBbXlX2X3X4X5

0X3812100

0X41640010

0X51204001

-z0-2-3000一0j

初始可行基B=(P3HR)=I,X=(o,0,8,16,12)T

(2)判别最优解

1°在T(B)中，若所有的检验数。j2O0=1,2,…,n)

贝UB为最优基，相应的基可行解为最优解，停止计算。

2°在T(B)中，若有。k<0(l4k«n),且Xk的系数列向量PkWO,则该问题

无界，停止计算。否则转入(3)

(3)换基迭代(基变换)

10先确定入基变量Xk：k=min{jloj<0}

2°按最小比值原则确定出基变量XL：

0=min1aik>0=

_纵电

3°以瓦,为主元，进行初等行变换(又称旋转变换)即将列向量区变

换为单位列向量：

返回(2)o

换基迭代的关键在于将换入变量对应的列向量区用初等行变换方法

变换成单位列向量。其中主元瓦K变成1。即

品0

aik0

Pk=->f第L个分量

a\k1

0

如果在最终表中有非基变量的检验数为0,则该问题有多重最优解。

3.单纯形法的进一步讨论——用人工变量法求初始基可行解

（■■）人工变量法

若对LP模型标准化后，不具有B=I时，如何办？此时可采用人工变量

法得到初始基可行解。

所谓人工变量法是在原问题不含有初始可行基B=I的情况下，人为的对

约束条件增加虚拟的非负变量（即人工变量），构造出含有B=I的另一个LP

问题后求解。当增加的人工变量全部取值为。时，才与原问题等价。这样，

新问题将有一个初始基可行解（以人工变量为基变量），可用单纯形法进行

迭代。经迭代后，若人工变量全部被换成非基变量，则原问题的约束条件

被恢复，同时也得到一个基可行解。在最终表中若不能全部被换出，则说

明原问题无可行解。

因此，该法的关键在于将人工变量全部换出。

人工变量法常见的有大M法和两阶段法。

（1）大M法（通过下例简略介绍其方法与步骤）

例，用大M法求解

MinZ=xi+1.5x2

xx+3X2>3

%1+x2>2

xpx2>0

解：MinZ=xi+1.5x2+0.xs+0.X4+Mx5+Mx6

%14-3X2-x3+x5=3

X1+x2-x4+4=2

_XpX2>0,x3,x4>0,x5,x6>0

其中X3,X4为松驰变量，X5,X6为人工变量，M为任意大的正数。

注意到：①分别在约束条件增加人工变量X5,X6是为了构成“人工基”

②对于Min的目标函数采用（+M）,而对于Max的目标函数则采

用（-M）作为人工变量的系数，是强加于人工变量的一种惩罚,其目的是为了

强制人工变量由变量转为非基变量，使之恢复原问题，或与原问题等价。

③对于minZ判别最优性准则应是Cj—ZjWO。

④大M法适合于手算，不适用于计算机求解。

（2）两阶段法

第一阶段：不考虑原问题是否存在基可行解；给原LP问题的约束条件

加入人工变量，构造仅含人工变量的目标函数并要求实现最小化（即使原

LP问题目标函数是求最大化）的辅助问题：

MinW=Xn+1+…+Xn+m

"%阳+…+册,/+%用二4

生西+…+”2户“+Z+2=b2

王，....工…之0

然后用单纯形法求解（Do若WM,则原问题无可行解，停止计算。

若w=o,且所有的人工变量均为非基变量，则去掉人工变量后可得到原问

题的基可行解；如果人工变量中含有为0的基变量时（即退化解），则可再

进行初等行变换将其换出，从而获得原问题的基可行解。

第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人工

变量列删去，同时将人工目标函数行换入原问题的目标函数作为第二阶段

计算的初始表。

仍以上例为例用两阶段法求解。

MinZ=Xi+l.5x24-0x3+0x4

X]+3々-X3=3

原I可题：*+/—x4=2

_x,,x2>0,x3,x4>0

MinW=X5+X6

/+3X2-X3+x5=3

辅助问题：X]+—x4+x6-2

x,,x2>0,x3,x4>0,x5,x6>0

书中第19页表2.9和表2.10的说明：（1）第一阶段的初始表中非基变量

的检验数=人工变量所在行的非基变量相应系数之和，目标函值值=人工变

量所在行相应常数之和。

（2）第二阶段单纯形表中目标函数系数应将非基变量表示基变量后所

得结果填入，或先直接填入原系数，再通过初等行变换使基变量的检验数

为0。

（3）若maxZ,则可转化为minZ^Zk-Z）

（二）退化

单纯形法计算中用。规则决定换出变量时，有时出现两个以上相同的最

小比值，这样在下一次迭代中就有一个或几个基变量等于0,出现退化解，

如某个最大化问题的单纯形表为：

G403000

0i

BbXl

cBXX2X3X4X5X6

0X562010103

0X43[1]-101003

0X651110015

z0-40-3000-5

0X500[2]1-2100

4Xl31-10100/

0X63021-1011

z120-4-3400-5

在出现退化解后的继续迭代中，有可能出现基循环:

B]—>B2f...—>Bj

这样迭代下去便永远得不到最优解。

解决基循环的方法很多，如“摄动法”、“字典序法”等等。

在计算机上常采用“Bland规则”：

(1)取表中下标最小的非基变量Xk为换入变量，即

k=min{jIOj>0}

(2)按。规则计算，若存在两个相同以上最小比值时，选取下标最小

的基变量为换出变量XL，即

b

L=minr\3r=min{—Iajk>0}

值得庆幸的是出现基循环是罕见的。

§3对偶理论与灵敏度分析

一、LP的对偶问题

1.引例前已述引例1是一个在有限资源的条件下，求使利润最大的生

产计划安排问题，其数学模型为：

maxZ=2xi+3x2

（设备）

X]+2X2<8

（原材料A）

4X2<16

（原材料B）

4X2<12

xt,x,>0

现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的设备台

时和购买工厂的原材料A、B,为其加工生产别的产品，由客户支付台时费

和材料费，此时工厂应考虑如何为每种资源的定价问题？

解：设yi,y2,y3分别表示出租单位设备台时的租金和出售单位原材料A、

B的价格（含附加值）

工厂决策者考虑：

（1）出租设备和出售原材料应不少于自己生产产品的获利，否则不如

自己生产为好。因此有

~yt+4y2>2

_2y,+4y3>3

工厂的总收入为W=8yi+16y2+12y3

（2）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底

价）

租赁者考虑：希望价格越低越好，否则另找他人。

于是，能够使双方共同接受的是

MinW=8yi+l6y2+12y3

一%+4乃之2

s.t2yl+4y3>3

J•%•”20

上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下

产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。

称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶

问题。

2.从矩阵形式讨论互为对偶LP问题

由例1有maxZ=cx

~YX<b

X>0

由矩阵形式的单纯形表中可知：

检验数的表达式为：CBB“N-CN和CBB"

当—C“NO①

CBB120②

表示LP问题已得到最优解

☆Y=CBB」,且②有Y20

由于基变量XB的检验数为0,可改写成CBB"B-CB=0

因此，包括基变量在内的所有检验数可写成

(CBB」B-CB,CBBN—CN)=(CBB」A—C)=YA—CNO

即YA2C

又对②Y=CBBL两边右乘b,有

Yb=CBB'b=Z

由于Y无上界，所以只有最小值，因此有

MinW=Yb

~YA>C

r>o

它是原问题（maxZ=CXIAX<b,X>0）的对偶问题

于是，对称形式下两个互为对偶LP问题的数学模型为：

MaxZ=CXMinW=Yb

~YX>b「E4"

与

X>0丫20

任何一个LP问题均有一个对偶LP问题与之匹配。

对偶理论就是研究LP问题及其对偶问题的理论，它是LP理论中的重要

内容之一。

二、对偶理论

1.原问题与对偶问题的关系如下表所示

原始对偶表

原问题Max（对偶问题）对偶问题Min（原问题）

约束条件数=m变量个数=111

第i个约束条件为第i个变量20

第i个约束条件为“2”第i个变量W0

第i个约束条件为“=”第i个变量无限制

变量个数=01约束条件个数=n

第i个变量N0第i个约束条件为

第i个变量W0第i个约束条件为

第i个变量无限制第i个约束条件为“=”

第i个约束条件的右端项目标函数第i个变量的系数

目标函第i个变量的系数第i个约束条件的右端顶

2.对偶问题的基本性质

MaxZ=CXMinW=Yb

'YX<b「E4”

设

_x>o[_r>o

（i）（对称性）对偶问题的对偶是原问题；

（2）（弱对偶性）若又是原问题的可行解，「是对偶问题的可行解；

则。又（再；

（3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原

问题）无可行解；

（4）（最优性准则），若又、「分别是互为对偶问题的可行解，且

CX=Yb,则又、「分别是它们的最优解；

（5）（对偶定理）若互为对偶问题之一有最优解，则另一问题必有最

优解，且它们的目标函数值相等。

从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一：

①原问题与对偶问题都有最优解，且CX=Yb；

②一个问题具有无界解，则它的对偶问题无可行解；

③两个问题均无可行解。

（6）（互补松驰性），若X*、Y*分别是原问题的对偶问题的可行解，则

X*、Y*是最优解的充要条件是：Y*Xs=0,YsX*=0（其中Xs,Ys分别是原问题和

对偶问题的松驰变量向量）。或，X*、Y*分别是原问题和对偶问题最优解的

充要条件是：

①若y*i>0,则ZaijX：=bi

②若ZaijX*j<b,则y*i=0

③若X；>0,则£aijy*i=Cj

④若2aijy*i>Cj,则X：=0

三、对偶单纯形法

1.单纯形法的重新解释

X*是最大化原LP问题最优解的充要条件是同时满足

6-%20①（称为原始可行条件）

CBB~'N-CN>0②（称为对偶可行条件）

因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶可行,

达到求出最优解的过程。

根据对偶问题的对称性，也可以在保持对偶可行下，经过迭代，逐步

实现原始可行，以求得最优解。对偶单纯形法就是这种思想所设计的。

2.对偶单纯形法的计算步骤:

举例说明

3.对偶单纯形法与单纯形法的不同之点:

①不要求模型中b20

②先确定换出变量XL，再确定换入变量XK

③，=min,'\arj<0=

）%Jark

4.对偶单纯形法适用对象

①maxZ=CX（CW0）②maxZ=CX

AX=bAX=b

（b无限制），Z（0

X>0X>0

③当变量个数（约束个数时，可先转化为其对偶问题，再用单纯形法

或对偶单纯形法解之

④进行灵敏度分析时，有时会用到此法

四、对偶解的经济含义和影子价格

1.对偶解Y*=CBB”的经济含义

设互为对偶的LP问题

maxZ=CXminW=Yb

AX<bYA>C

（原）（对）

X>0y>o

有Z*=CBB%=W*（其中B为最优基）

*

因此^—=CB=y*

dbB

或者说Z*=y*M+y*2b2+y*mbm

SZ*,

则-----

=y:*

dbl,

其含义是：若对原问题右端常数项向量b中的某一常数项bi增加一个单

位，目标函数的最优值Z*的变化将是Yi*。换句话说，Yi*表示当bi增加一个

单位时，目标函数最优值的相应增量。实质上丫产就是第i种资源边际价值

的种表现，也是对第i种资源的种估价。

事实上，如引例中互为对偶LP问题分别描述生产计划问题和资源的定

价问题，其数学模型分别是：

maxZ=2x1+3x2minW=8y1+16y?+l2y3

%1+2X<8

2-乂+4”之2

4x<16

(原问题)c（对偶问题）2y+4%>3

4X2<12

J，为20,>32°

xt,x2>0

对原问题用单纯形法求解所得最终表为

C23000

CBXBbXlX2X3X4X5

2X]41001/40

0X5400-21/21

3X22011/2-1/80

Z14001.50.1250

由此,它们的最优解分别是X*=(4,2)T和Y=(1.5,0.125,0)

Z*=W*=14=8Y]*+16Y2*12Y3*

上az*—,az**=经\

y*=---=1.5,y*=----=0.125,”0

12

西db2db.

其中Y|*=1.5表示单独对设备台时增加1个单位，可使Z值增加1.5个单

位的利润；丫2*=0.125表示单独对原材料A增加1个单位，可使Z值增加0.125

个单位的利润；而丫3*=0表示单独对原材料B增加一个单位，却不使Z值增

加。这是因为从最终表中可看出，在最优方案中，松驰变量X5=4,即表示

在最优生产方案中，原材料B尚有4个单位剩余被闲置，不产生任何经济效

O

2.影子价格的定义

把某一经济结构中的某种资源，在最优决策下的边际价值称为该资源

在此经济结构中的影子价格。

影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影

子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。

资源的影子价格定量的反映了单位资源在最优生产方案中为总收益应

提供的收益，因此，资源的影子价格也可称为在最优方案中投入生产的机

会成本。

3.影子价格的求法

(1)在非退化情况下：设B为LP问题的最优基，贝U

资源的影价=Y*=CBB」

(2)在退化情况下：

当对偶问题有K个最优解，则第i种资源的影价=叫11{)<">}即影价的

第i个分量等于这K个对偶解中第i个分量的最小值。

例如，设某资源利用问题为

maxZ=3xj+X2

(资源1限制)

xt+x2<2

(资源2限制)

3%]+2x,<6

阳，12之0

最终表

3100

b

XBX|X2X3X4

X121110

X400-1[-3]1

Z60230

X1212/301/3

X3001/31-1/3

Z60101

...资源1的影价

=min{yj⑴,yj⑵}

=min{3,0}=0

资源2的影价=min{丫2*"),丫2汽"}=min{0,1}=0

4.影子价格的参谋作用

-影价>0,说明伊资源已耗尽，

(1)指出企业挖潜革新的途径成为短线资源。

影价=0,说明该资源有剩余，

成为长线资源。

(2)对市场资源的最优配置起着推进作用

(3)可为企业决策者提供调整最优生产方案的信息

CBB」Pj-Cj<0说明第j种产品应投产

CBB8—Cj>0说明第j种产品不应投产

尤其对新产品是否应投产，可按以上两式考虑。

(4)可以预测产品的价格

(5)可作为同类企业经济效益评估指标之一。

五、灵敏度分析

面对市场变化，灵敏度分析的任务是须解决以下两类问题：

(1)当系数A、b、c中的某个发生变化时，目前的最优基是否仍最优

(即目前的最优生产方案是否要变化)？

(2)为保持目前最优基仍是最优基，参数A、b、c允许变化范围是什

么？

灵敏度分析的方法是在目前最优基B下进行的。即当参数A、b、c中的

某一个或几个发生变化时，考察是否影响以下两式的成立？

CBB~'N-CN>0

1.对资源数量br变化的分析

当b中某个屏发生改变时，将影响基变量的取值XB=B」b。若由的变化仍

满足B」b20,则目前的基B仍为最优基，仅在B」b和CBB-七的数量上有些改

变。若br的变化使B』b中某些分量小于0,则目前的基成为非可行