经济学运筹学

1三、课堂教学内容章次内容总学时数绪论1一线性规划及单纯形法16/2二对偶理论与灵敏度分析12/2三运输问题6/1四整数规划6/1五动态规划5/1六动态规划应用举例4七图与网络分析10/1八网络计划2九排队论10总学时数72/82运筹学的工作步骤明确问题建立模型设计算法整理数据求解模型评价结果简化？YesNoNo明确问题建立模型设计算法整理数据求解模型评价结果结束Yes满意？3

数学规划是管理科学中求最优或最有效使用有限资源的方式以达到既定目标的一个领域，又称为最优化。有限的资源：从地下抽出的原油、倾倒垃圾和有害废物的场地、企业招聘的人员、餐馆放座位的空间、一个人每天工作活动的时间，做某件事情需要花的钱……1、确定产品组合：多数企业可以生产多种产品，但不同产品所需的原材料和工时不同，类似地，它们产生的利润也不同，管理者必须决定每种产品产量以使利润最大或以最小成本满足需求。2、选路与物流：许多零售公司在各地都有提供商店货物的仓库，仓库可供的货物数量和各商店所需的货物数量是不同的，需要确定从仓库运送到商店的货物所需成本最低的方法。4

线性规划

(LinearProgramming——LP)是数学规划的一个分支，是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。一般可以表达成以下两个问题中的一个：

当资源给定时，要求完成的任务最多；当任务给定时，要求为完成任务所消耗的资源最少。数学规划中的模型都是线性函数时，称线性规划。5第一章线性规划及单纯形法

第一节线性规划问题及数学模型（P8）III设备原材料A原材料B单件利润140220438台时16kg12kg6设X1﹑X2为工厂1﹑2的日处理量

MinZ=1000X1+800X2

X1≥1(1)0.8X1+X2≥1.6(2)X1≤2(3)X2≤1.4(4)X1﹑X2≥0环保要求：(污水量/河水量)≤0.2%，河流自净力：20%500万m3200万m31.4万m3，800元/万m3

o工厂2例2（P9）

2万m3

，1000元/万m3

o工厂17

LP问题的共同特征：每一个问题变量都用一组决策变量（x1,x2,…,xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。

存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化或最小化。

目标：objective,goal,target8LP模型一般形式目标函数Max(Min)Z=C1X1+C2X2+...+CnXn

a11X1+a12X2+...+a1nXn≤(=,≥)b1约束条件a21X1+a22X2+...+a2nXn≤(=,≥)b2

┆┆am1X1+am2X2+...+amnXn≤(=,≥)bm

非负条件X1﹑X2...Xn≥(=,≤)0或无约束94x1=164x2=12x1+2x2=8x1x248430Q(4,2)Z=2x1+3x2最优生产计划为：生产I产品4件，生产II产品2件。三、两变量线性规划问题的图解法作出LP问题的可行域作出目标函数的等值线移动等值线到可行域边界得到最优点图解法步骤（图解法意义不大，但可直观揭示有关概念）10有可行解有最优解唯一解无穷多解无最优解（可行域为无界）无可行解（无解）LP解的可能情况：

若LP问题有最优解，则要么最优解唯一，要么有无穷多最优解。

110 48 12 x1963x2①③②可行域Z=364,6多重解举例

MaxZ=3X1+4X2

X1≤8①2X2≤12②3X1+4X2≤36③X1﹑X2≥0此线段上的点均为最优点12-1 01 2 3x121x2可行域无界解举例MaxZ=3X1+2X2

-2X1+X2≤2①X1-3X2≤3②X1﹑X2≥0①②Z增大方向130 24 6 8x1x2无可行解举例：

MaxZ=2X1+3X2

X1+2X2≤8①4X1≤16②4X2≤12③

-2X1+X2≥4④X1﹑X2≥0①③

6 420

④无公共区域(可行域)②14

四、线性规划问题的标准型15线性规划标准形矩阵描述(A,C,b,X均为矩阵)：X—决策变量列向量。b—约束条件右端常数（资源）列向量。C—目标函数价值系数行向量。Amxn—约束条件左端系数矩阵。

a11a12...a1na21a22...a2nA=┆┆┆am1am2...amn

=[P1，P2...Pn]C=[c1c2...cn]

b1x1b2x2b=┆X=┆bmxnMaxZ=CX|AX=b，X≥016非标准形LP问题化为标准形：1）若目标函数为MinZ，令Z'=-Z，则MinZ等价于MaxZ'2）

若为不等式约束：若为≤，在方程左边加一非负新变量，称松弛（Slack）变量若为≥，在方程左边减一非负新变量，称剩余（Surpius）变量或松弛变量四个特点：极大化目标﹑等式约束﹑约束右端常数bi≥0﹑决策变量Xj≥0。17非标准形LP问题化为标准形：3）

若bi<0,方程两边同乘（-1）4）

若变量不满足非负：若xK≤0，令xK=-xK',xK'≥0，用此式替换模型中xk

若xK无约束，令xK=xK'-xK'',xK'﹑xK''≥0，用此式替换模型中xk18例1可化为例4MinZ=-1X1+2X2-3X3X1+X2+X3≤7X1-X2+X3≥2-3X1+X2+2X3=5X1﹑X2≥0﹑X3无约束MaxZ'=X1-2X2+3（X4-X5）+0X6-0X7X1+X2+（X4-X5）+X6=7X1-X2+（X4-X5）-X7=2-3X1+X2+2（X4-X5）

=5X1﹑X2﹑X4﹑X5﹑X6﹑X7≥0191.4LP问题解的概念（可行解﹑基﹑基可行解﹑可行基）MaxZ=2X1+3X2+4X3+7X42X1+3X2-X3-4X4=8X1-2X2+6X3-7X4=-3X1﹑X2﹑X3﹑X4≥020X1=(1,14/7,0,0);X2=(45/13,0,-14/13,0)X3=(34/5,0,0,7/5);X4=(0,45/16,7/16,0)X5=(0,68/29,0,-7/29);X6=(0,0,-68/31,-45/31)基可行解X1﹑X3﹑X4,最优解X3，Z=117/5思考：X=(-9/7,27/7,1,0)、X=(7,1,1,2)是何解？21例1

MaxZ=2x1+3x2

s.t.x1+2x2≤84x1≤164x2≤12

x1,x2

≥0

可行解、基解和基可行解举例非基变量基变量图中的点x4,x5x1=4x2=3x3=-2A基解x3,x5x1=2x2=3x4=8B基可行解x3,x4x1=4x2=2x5=4C基可行解x2,x4x1=4x3=4x5=12D基可行解x2,x3x1=8x4=-16x5=12E基解x1,x5x2=3x3=2x4=16F基可行解x1,x3x2=4x4=16x5=-4G基解x1,x2x3=8x4=16x5=12H基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH标准型22线性规划标准型问题解的关系约束方程的解空间基解可行解非可行解基可行解23MaxZ=3X1+5X2+0X3+0X4+0X5系数矩阵:X1+X3=8① 10100

2X2+X4

=12②020103X1+4X2+X5

=36③ 34001X1,X2,,X3,X4,X5≥0C=（35000）令x1,x2=0，得：X=(0081236)z=0

1令x2,x3=0，得：X=(8001212)z=24

2

保留的变量称基变量，由解方程求得。移到右边并令为零的变量称非基变量。相应于基变量的系数列称基。24令x4,x5=0，得：X=(46400)z=425令x2,x5=0，得：X=(120-4120)z=366令x1,x4=0，得：X=(068012)z=303令x3,x5=0，得：X=(83060)z=39425令x1,x5=0，得：X=(098-60)z=45

7令x3,x4=0，得：X=(8600-12)z=54

8∵000210=0401

∴无解9

∵110000=0301

∴无解10

26小结

本例3阶系数行列式共有10个，其中有8个行列式≠0，它们称为基，其中的每一列Pj(j=1,2,…,m)称基向量，另2个行列式=0，无意义。与基向量Pj对应的变量xj称为基变量，记为XB

，其余变量称为非基变量，记为XN

根据基求出的解称基解，本例有8个基解，其中有5个解的所有变量都≥0(即可行)，这5个解称基可行解，给出这5个可行解的基称为可行基。在5个可行解中，第5个解的目标函数值最大，故又称这个解的可行基为最优基。27

线性规划解的概念与定理

可行解：满足约束方程组和非负条件的解。基(B)：约束方程系数矩阵Am*n(m为方程个数，n为变量个数)中满足行列式≠0的m阶方阵。对应于基系数列的变量称基变量 XB，非基系数列对应变量称非基变量XN

。基解：根据某个基，令非基变量=0而求出的解。28线性规划解的概念与定理

基可行解：满足非负条件的基解。可行基：对应于可行解的基。最优基：给出最优目标函数值的可行基。定理：若线性规划问题存在最优解，则必定能在其基可行解中得到。从图形上看，也就是说最优解一定能在其可行域的顶点处得到。29第2节LP理论基础：(凸集、凸组合、顶点）凸集：设K为En的一点集，若对于任意X(1)﹑X(2)€K，都有αX(1)+（1-α）X(2)

€K，（0≤α≤1）；则称K为凸集。凸组合：设X(1)﹑X(2)…

X(k)为En的

K个点，若存在μ1、μ2…

μk，且0≤μi≤1，i=1，2…k;使X=μ1X(1)+μ2X(2)

…

+μkX(k)则称X为X(1)，X(2)

…

X(k)的凸组合。顶点：设K为凸集，X€K，若X不能用不同的两点X(1)﹑X(2)€K的线性组合表示为αX(1)+（1-α）X(2)

（0≤α≤1）；则称X为K的一个顶点。30第2节LP理论基础：(定理1、2*、3）证明：设X(1)﹑X(2)为LP可行域D内任意两点，X(1)≠X(2)

，则AX(1)=b，AX(2)=b，X(1)≥0，X(2)≥0令X为X(1)﹑X(2)

连线上任意一点，即X=αX(1)+（1-α）X(2)

，（0≤α≤1）代入约束AX=αAX(1)+（1-α）AX(2)=αb+（1-α）b=b，又∵α≥0，（1-α）≥0，∴X≥0，即X(1)﹑X(2)

连线上任意一点也在D内，由凸集定义，D为凸集。定理1：若LP问题存在可行域，则其可行域D={X|}是凸集。31证明：设X(1)﹑...﹑X(k)为可行域顶点，相应目标值Z(1)﹑...﹑Z(k)

，其中第m个顶点X(m)处目标值最大，记为Z(m)

，若X(0)

不是顶点但其目标值最优，则：X(0)=αiX(i)

，αi≥0，αi=1CX(0)=αiCX(i)=αiZ(i)≤αiZ(m)=Z(m)

据假使CX(0)

为最优值，∴X(m)处也能达到最优。定理3：若可行域有界，LP问题的目标函数一定可以在其可行域的顶点上达到最优。32第3节单纯形法(GeorgeDantgig于1947年提出)

由线性代数知，对标准形LP问题，理论上可以求出所有基解（枚举法），再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法.33

为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是，停止。二是若不是最优，要保证下一步得到的解不劣于当前解。基于线性代数原理，并将上述功能贯穿于算法过程，这就是线性规划的单纯形法。

第3节单纯形法(GeorgeDantgig于1947年提出)34Z=2X1+3X2,C1=2>0,C2=3>0,∴此解非最优,选X2进基.

令X1,X2=0,称非基变量

X1+2X2+X3

=84X1+X4

=164X2+X5=12X=(0081612),Z=0MaxZ=2X1+3X2+0X3+0X4+0X5X1+2X2+X3

=84X1+X4

=164X2+X5

=12X1,X2,X3,X4,X5

≥0X3812100X41640010X51204001X1+2X2+X3

=84X1+X4

=164X2+X5=12用表表示：35当X2=min(8/2,-,12/4)=3时,X5=0,∴X5出基。X1+2X2+X3

=84X1+X4

=16

4X2+X5=128/2-12/4X1+2X2+X3

=84X1+X4

=164X2+X5=12X1+2X2+X3

=84X1+X4

=164X2+X5=12X1+2X2+X3

=84X1+X4

=164X2+X5=12基变换36X1+X3

-X5/2=2①’=①-2*③’4X1+X4

=16

②’=②

X2

+X5/4

=3③’=③/4

解基变量并保持右端常数是其值的形式,对系数作如下变换：X1+2X2+X3

=84X1+X4

=164X2+X5=12

①’=①-2*③’：X1+2X2+X3

=82（X2

+X5/4

=3）=X1+X3

-X5/2=2

204001X321010-1/2X41640010X2301001/4用表表示：X2X537X3812100X41640010X51204001X321010-1/2X41640010X2301001/4X1+X3

-X5/2=24X1+X4

=16

X2

+X5/4

=3X1+2X2+X3

=84X1+X4

=164X2+X5=12

令X1,X5=0,得X=(032160),将X1、X2代入目标函数，并写成只含非基变量形式得：Z=2X1+3(3-X5/4)=9+2X1-3X5/4。∵X1

系数C1=2>0,∴此解非最优,选X1进基。和前一步对比：38当X1=min(2/1,16/4,-)=2时,X3=0,∴X3出基。

X1

+X3

-X5/2=24X1

+X4

=16

X2

+X5/4

=32/116/4-

X1

+X3

-X5/2=24X1

+X4

=16

X2

+X5/4

=3X1+X3

-X5/2=24X1+X4

=16

X2

+X5/4

=3

X1

+X3

-X5/2=24X1

+X4

=16

X2

+X5/4

=3基变换39

解基变量并保持右端常数是其值的形式,对系数作如下变换：

②’=②-4*①

：

4X1+X4

=164（X1+X3-X5

/2=2)=-4X3+X4+2X5

=8

140100X121010-1/2X4800-412X230100-1/4用表表示：

X1

+X3

-X5/2=2①4X1

+X4

=16②

X2

+X5/4

=3

③X1X3X1

+X3

-X5/2

=2①’=①

-4X3+X4+2X5=8

②’=②-4*①

X2

-X5/4

=3③’=③40

令X3,X5=0,得X=(23080),将X1、X2代入目标函数，并写成只含非基变量形式得：

Z=2(2-X3+X5/2)+3(3-X5/4)=13-2X3+X5/4

。∵X5

系数C5=1/4>0,∴此解非最优,选X5进基。和前一步对比：X1

+X3

-X5/2

=2

-4X3+X4+2X5=8

X2

+X5/4

=3X121010-1/2X4800-412X230100-1/4X3210101/2X41640010X2301001/4X1+X3

-X5/2=24X1+X4

=16

X2

+X5/4

=341当X5=min(-,8/2,3*4)=4时,X4=0,∴X4出基。-8/23*4基变换X1

+X3

-X5/2

=2

-4X3+X4+2X5

=8

X2

+X5/4

=3X1

+X3

-X5/2

=2

-4X3+X4+2X5

=8

X2

+X5/4

=3X1

+X3

-X5/2

=2

-4X3+X4+2X5=8

X2

+X5/4

=3X1

+X3

-X5/2

=2

-4X3+X4+2X5

=8

X2

+X5/4

=342

解基变量并保持右端常数是其值的形式,对系数作如下变换：

①’=①+②’/2：

X1+X3-X5/2

=2+(-2X3+X4/2+X5=4)/2=X1+X4/4

=4

-1/221/4010X141001/40X5400-21/21X22011/2-1/80用表表示：X5X4X1

+X3

-X5/2

=2①

-4X3+X4+2X5

=8②

X2

+X5/4

=3③X1+X4/4

=4①’=①+

②’/2-2X3+X4/2+X5

=4

②’=

②/2X2

+X3/2-X4/8

=2

③’=③-②’/4

③’=③-②’/4

：

X2+X5/4

=3-(-2X3+X4/2+X5=4)/4=X2+X3/2-X4/8

=2

43

令X3,X4=0,得X=(42004),将X1、X2代入目标函数，并写成只含非基变量形式得：

Z=2(4-X4/4)+3(2-X3/2+X4/8)=14-3X3/2-X4/8

。和前一步对比：X1+X4/4

=4-2X3+X4/2+X5

=4X2

+X3/2-X4/8

=2X141001/40X5400-21/21X22011/2-1/80X1

+X3

-X5/2

=2

-4X3+X4+2X5=8

X2

+X5/4

=3X121010-1/2X4800-412X230100-1/444∵目标函数中所有变量的系数均<或=0,∴得最优解：

X*=(42004),Z*=14

答：该厂生产I产品4件，II产品2件，可获最大利润14元。

将上述方程组求解过程，用列表形式表达，即为线性规划单纯形法。Z=2(4-X4/4)+3(2-X3/2+X4/8)=14-3X3/2-X4/8

。45

x3x4x2←表1-3表1-421010-1/2301001/4

检验行

j2000-3/42/1=2

16/4=4-↓↓←8/2=4

-12/4=31640010

00346表1-521010-1/2800-412301001/4

x1x4x2

203检验行

j00-201/4

x3x4x2

00321010-1/21640010301001/4

检验行

j2000-3/42/1=2

16/4=4-↓←-8/2=43*4=12↓←表1-447301001/421010-1/2800-412

x1x4x2

203检验行

j

00-201/4-8/2=43*4=12↓←

20341001/40400-21/212011/2-1/80

检验行

j00-1.5-1/80

x1x5x2表1-5表1-6最优解：x1=4x2=2x3=0x4=0x5=4z=14484x1=164x2=12x1+2x2=8x1x2484O三、单纯形表与图解法的对应关系X1=(0,0)T,Z1=0X2=(0,3)T,Z2=9X3=(2,3)T,Z3=13X4=(4,2)T,Z4=14Q1Q2QQ3基可行解基可行解迭代

顶点相邻的顶点迭代

图解法：单纯形表算法：49第4节单纯形步骤1.化标准形2.在系数矩阵中找出（构造）m（方程个数）阶单位矩阵，以其为初始基，对应变量为基变量，画初始单纯形表；3.计算检验数

j，若所有

j≤0，得最优解，否则转4；50第4节单纯形步骤4.若某个

j>0，其对应列系数均≤0，得无界解，停止，否则转5；5.选最大

j(>0)对应变量进基，最小比值

对应变量出基（这种做法称

规则），标出主元(进基变量和出基变量交叉处元素)；6.将主元变为1，主元列(主元所在列)其它元素变为0，得新表，返回3。51检验数

j算法：

基变量检验数总是0，只需求非基变量检验数。方法是：将左列基变量价值系数与所求非基变量系数列分别相乘再相加，然后被该非基变量价值系数减去。

最小比值算法：

以b列为分子，主元列元素(>0)为分母,计算各行比值，其最小者为。

52

j算法公式推导：

设前m个为基变量，则xi=bi-aijxj(i=1…m)代入目标函数

Z=cixi+cjxj=ci(bi-aijxj)+cjxj=cibi-ciaijxj+cjxj=cibi+(cj-ciaij)xj53Z=cibi-ciaijxj+cjxj=cibi+(cj-ciaij)xj令Z0=cibi，Zj=ciaij,则Z=Z0+(cj-Zj)xj令

j=cj-Zj=cj-[c1a1j+c2a2j+…+cmamj]，则Z=Z0+

jxj54例8MinZ=-3X1+X2+X3

X1-2X2+X3≤11-4X1+X2+2X3≥3

-2X1+X3=1X1,X2,X3≥0化标准形：MinZ=-3X1+X2+X3+0X4+0X5

X1-2X2+X3+X4

=11-4X1+X2+2X3-X5=3

-2X1+X3=1X1,X2,X3,X4,X5

≥0

系数矩阵：1-2110-4120-1-20100系数矩阵：1-211000-4120-110-2010001加人工变量：MinZ=-X1+X2+X3+0X4+0X5+MX6+MX7

X1-2X2+X3+X4

=11-4X1+X2+2X3-X5+X6

=3

-2X1+X3+X7

=1X1,X2,X3,X4,X5,X6,X7

≥055松弛变量(X4,X5)是化不等式为等式而添加的变量,其意义表示约束两边不等的部分。

人工变量(X6,X7)

是在标准化以后，为了凑成单位矩阵而添加的变量。只有在最优解中人工变量=0，所得解才是原问题解，若最优解中含有人工变量，原问题无解。在迭代过程中，为尽快剔除基变量中的人工变量，将目标函数中人工变量系数赋以无穷大数M(对Max，则为-M)，使其对目标函数构成惩罚，也就是说，只有人工变量=0，才有可能实现目标最优。这就是大M法基本思想。56用大M法求解MinZ=-3X1+X2+X3+0X4+0X5+MX6+MX7

X1-2X2+X3+X4=11-4X1+X2+2X3-X5+X6=3

-2X1+X3+X7=1X1,X2,X3,X4,X5,X6,X7≥0系数矩阵：1-211000-4120-110-2010001

Cj-31100MMCBXBbX1X2X3X4X5X6X70X4111-211000MX63-4120-110MX71-20100016M-31-M1-3M0M00↑113/21

1-2010001103-20100-1

10100-11-2X4X6X30M1

-11-M00M03M-1↑-1-←←57X4X6X3←10100-11-21-2010001123001-22-5X4X2X3011↑12/3--←41001/3-2/32/3-5/310100-11-290012/3-4/34/3-7/30001/31/3M-1/3M-2/3X1X2X3-10001M-1M+1-311最优解：X*=(4190000)最优（小）值：Z*=-2Cj-31100MMCBXBbX1X2X3X4X5X6X7

1-2010001103-20100-1

10100-11-2

-11-M00M03M-1↑0M158l

两阶段法(将LP问题分成两个阶段来考虑)第I阶段:不考虑原问题是否存在可行解，给原LP问题加入人工变量，构造仅含人工变量的目标函数w并要求最小化；然后用单纯形法求解，若得w=0，则进行第二阶段计算，否则无可行解。第II阶段：除去第一阶段最终表中的人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表，继续用单纯形法求解。

59cj0000011CBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011σj6-1-301000x4103-20100-1-1x610100-11-210x31-2010001-σj0-1001030x4123001-22-540x210100-11-2-0x31-2010000-σj0000011此时，达到第一阶段的最优解，W=060

二、单纯形法遗补1.存在两个以上的最大正检验数时，任选一个最大正检验数对应变量作为进基变量。2.最小比值相同（退化）：当最小比值不止1个时，在下一步迭代中就有1个或几个基变量等于0，这种现象称退化。当出现退化时，有可能使计算进入死循环。为避免死循环，应选择下标最小的基变量出基。

出现死循环的例子

MaxZ=3