管理运筹学（第2版）课件全套 管理运筹学-开场-第八章：对策论

管理运筹学(ManagementOperationalResearch)2026年7月13日协作创造奇迹2

定量优化的决策科学2026年7月13日协作创造奇迹3一、运筹学的起源与发展1.30年代末：英国军事需要----OperationsResearch

2.二次大战后：除了军事应用外，还广泛应用于工业、农业、经济和社会问题各个领域。

3.1948年：英国成立运筹学学会。

4.50年代：中国引入OperationsResearch，翻译为运筹学。

5.1959年：英、美、法三国成立国际运筹学联合会（FORSO）。

6.1980年：中国成立运筹学学会，1982年加入FORSO。二、运筹学的性质和特征1.以数学为工具。

2.研究问题从系统的观点出发。

3.应用具有多学科交叉的特点。

4.强调科学方法。三、工作步骤1.提出并且形成问题。

2.建立模型。

3.求解：可以是最优解、次优解、满意解。

4.检验：解是否反映现实问题。

5.解的实施。四、学习方法：着重培养3个方面的能力1.善于运用所学知识，为各种实际问题建立数学模型。

2.掌握各种模型的优化方法。

3.正确理解和应用各种参数的经济意义。4第一章：线性规划1.1线性规划(LinearPrograming---L.P.)概述一、L.P.概念：

L.P.是目前应用最广泛的一种系统优化方法。其理论已十分成熟，广泛应用于工农业生产和经济管理等领域。以数学为工具，在一定资源条件下，如何合理安排，取得最大经济效果。二、发展史：

30年代末(苏)康特罗维奇书“生产组织与计划中的数学方法”，为L.P.建立数学模型和求解奠定了基础。

1、(美)库普曼(T.C.Koopmans)建立了L.P.数学模型，获诺贝经济奖。

2、(美)丹泽(G.B.Dantzig)在1947年提出求解L.P.数模的通用方法---单纯形法。

1946年，世界上第一台计算机问世，使单纯形法处理大规模L.P.数模成为可能。三、L.P.问题的求解过程

1、将实际问题转化为数学模型(数学公式)：建模。

2、求解数学模型：

图解法：适合于2个变量的L.P.数学模型。

单纯形法：适合于任意个变量的L.P.数学模型。

3、利用数学模型的最优解获得原问题的最优决策方案。51.2线性规划问题及其数学模型一、L.P.问题

例：某厂生产甲、乙两种产品，均需在A、B、C三种不同的设备上加工，产品加工所需工时、销售后能获得的利润及设备有效工时数如下表。问：如何安排生产计划，才能使该厂获得总利润最大？

解:①设甲、乙产品产量分别为x1、x2公斤———决策变量，简称变量②设总利润为Z，则

MaxZ=70x1＋30x2———目标函数③设备可用工时数限制———约束条件

s.t.3x1+9x2≤540A设备可用工时约束

5x1+5x2≤450B设备可用工时约束

9x1+3x2≤720C设备可用工时约束

x1,x2

≥0非负约束

设备产品

ABC利润(元/公斤)

甲(x1公斤)乙(x2公斤)3955937030限制工时

5404507206二、L.P.数学模型的经济含义1、数学模型的三要素:

①.有一组待确定的决策变量。如(x1,x2)为一个具体行动方案。

②.有一个明确的目标要求(Max或Min)。如要求利润最大。

③.存在一组约束条件。如设备A、B、C三种资源的约束。

2、数学模型中系数的含义:

①.目标函数中决策变量的系数70,30------叫价值系数，表单位产品提供的利润(元/件)；

②.约束条件左边决策变量的系数------叫约束条件系数或单耗(台时、kg、kg/件)；

③.约束条件右边常数540,450,720------叫限制常数，表现有的资源限量。

三、线性规划数学模型的解

1、可行解：满足约束条件②、③、④、⑤的所有解。

2、可行解域：所有可行解的集合，上图阴影部分。

3、最优解：满足目标函数①的可行解。

4、基本解：所有约束条件直线的交点对应的解，即上图所有的实心点和空心点对应的解。

5、基本可行解：位于可行解域边界上的约束条件直线的交点对应的解，即上图所有的实心点对应的解。它满足两个条件：其一是约束条件直线的交点对应的解；其二是可行解，即满足所有的约束条件，在可行解域内。

oX1X2

②③④⑤⑤ahbkMaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤71、线性规划：如果以上数学模型中的方程均是线性方程，则该数模称为线性规划数学模型。

2、非线性规划：如果以上数学模型中的方程至少有一个方程是非线性方程，则该数模称为非线性规划数学模型。

四、L.P.的一般形式

Max(Min)Z=c1·x1+c2

·x2+---+cn

·xn

a11·

x1+a12

·x2+---+a1n

·xn≤(≥,=)b1

a21·

x1+a22

·x2+---+a2n·xn≤(≥,=)b2s.t.-------------------------------------------------

am1

·

x1+am2·x2+---+amn·xn≤(≥,=)bmxj≥0,j=1,～,n

81.3线性规划问题的建模

确定决策变量；确定目标函数；列出约束条件。

一、运输问题建模:编制最优运输计划,使总运费最少

例：某地有三个有色金属矿A1、A2、A3，生产同一种金属矿石，A1矿的年产量为100万吨，

A2矿为80万吨，A3矿为50万吨。矿石全部供应四个冶炼厂，B1厂的全部需求量为50万吨，

B2厂70为万吨，B3厂为80万吨，B4厂为30万吨。产量恰好等于总需求量，矿石由各矿山运到冶炼厂的单位运价已知，如下表。问如何安排运输，使各矿山的矿石运到冶炼厂，满足各厂的需要，且运输费用最小，试建立该问题的数学模型？

.确定决策变量:设

xij

为从第i个矿山到第

j

个冶炼厂的矿石运输量(万t)..确定目标函数:设总运费为Z,则

MinZ=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24+1.2x31+0.3x32+2x33+2.5x34

.确定约束条件:

x11+x12+x13+x14=100s.t.x21+x22+x23+x24=80x31+x32+x33+x34=50x11+x21+x31=50x12+x22+x32=70x13+x23+x33=80x14+x24+x34=30xij≥0,i=1~3;j=1~4.9

二、合理下料问题建模:寻求最佳下料方式,使余料最少.

例有一批长度为180公分的钢管,需截成70、52和35公分三种管料。它们的需求量应分别不少于

100、150和100个。问应如何下料才能使钢管的余料为最少?

解:

.确定决策变量:

设xj

为第j种下料方式所用的钢管根数..确定目标函数:设总余料为Z,则

MinZ=5x1+6x2+23x3+5x4+24x5+6x6+23x7+5x8(公分).确定约束条件:

2x1+x2+x3+x4≥100s.t.2x2+x3+3x5+2x6+x7≥150x1+x3+3x4+2x6+3x7+5x8≥100xj≥0,且为整数.

10

三、分派问题建模:合理分派人员,使总效率最大.

例：设有四件工作分派给四个人来做，每项工作只能由一人来做，每个人只能做一项工作。希望适当安排人选，发挥各人特长又能使总的效率最大(或完成最快,或费用最少)。表1.5表示各人对各项工作所具有的工作效率。.确定决策变量:设xij

为分派第i个人从事第

j

项工作,xij=1,0(分派与否).确定目标函数:设总效率为Z,则

MaxZ=0.6x11+0.2x12+0.3x13+0.1x14+0.7x21+0.4x22+0.3x23+0.2x24

+0.8x31+1.0x32+0.7x33+0.3x34+0.7x41+0.7x42+0.5x43+0.4x44

.确定约束条件:

x11+x12+x13+x14=1s.t.x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1xij=1,0,i=1~4;j=1~4.11

四、投资方案选择问题建模:合理选择方案,使总收益最大.

例：某炼油公司为提高炼油能力和增加企业经济效益,经研究有五种技术改造的投资方案可供选择，它们所需的投资费用年收益如下表所示。其中:方案1和方案2只能选择其中一种，不能兼而实现，并且，如选择方案2，则方案3必须同时选择，或者都不选择。

现该公司可供支配的资金总额为：第一年有650万元，第二年仅有460万元。技术改造的结果要求至少应增加出油能力500桶/天，但又不得超过1100桶/天，试确定该公司总经济效益最大的投资方案。12.确定决策变量:设xj

为第j方案的取舍，

xj=1,0(取舍).确定目标函数:设总经济效率为Z,则

MaxZ=100x1+200x2+50x3+30x4+20x5(万元).确定约束条件:

200x1+300x2+150x3+100x4+50x5≤650s.t.200x1+150x2+50x3+70x4+40x5≤460500x1+1000x2+100x3+50x4+20x5≥500500x1+1000x2+100x3+50x4+20x5≤1100x1+x2≤1-x2+x3=0xj=0,1,j=1~5.131.4线性规划图解法

一、适用范围：

二个变量的数学模型。

二、求解步骤：

MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤

oX1X2

②③④⑤⑤ahbk7030(75,15)最优解为：X*=(75，15)TZ*=5700

第二步：确定可行解域，即所有约束方程图形的公共部分；

第三步：绘出目标函数直线，根据目标函数的要求以及与决策变量的关系，找出直线移动方向P。

第五步：确定最优解及最优目标函数值。

第一步：将所有约束方程用图形绘出；

第四步：目标函数直线沿着方向P向可行解域的边界平行移动，直至与可行解域相切为止，这个切点就是最优点，对应的解就是最优解。

14

三、LP几何意义

oX1X2

②③④⑤⑤ahbk1、闭合的可行解域是凸多边形(凸集)。

2、可行解域有若干个顶点：O、a、h、k、b。对应的解叫基本可行解。

3、最优解若唯一存在，则必是顶点中的某一个。15

四、特殊的数学模型

1、有无穷多个最优解：若有两个最优解，则必有无穷多个最优解。如下例数学模型：MaxZ=x1＋2x2s.t.x1+x2≤6x1+2x2≤8x2≤3x1,x2

≥0

OX1X2Q1Q2Q3Q4

此线性规划问题的最优解在Q2Q3线段上，如上图所示，即线段Q2Q3上任意一点都使Z取得相同的最大值，这个线性规划问题有无穷多最优解。因此，若有两个最优解，则必有无穷多个最优解。

16

四、特殊的数学模型

2、解无界：可行解域无界，目标值无限增大。如下例数学模型：

MaxZ=x1＋x2s.t.-2x1+x2≤4x1-5x2≤2x1,x2

≥0

OX1X2用图解法求解结果见上图所示，从图中可以看到，该问题可行解域无界，目标函数值可以增大到无究大，称这种情况为无界解或无最优解。

17

四、特殊的数学模型

3、无可行解域：约束条件相互矛盾。如下例数学模型MaxZ=3x1＋4x2s.t.x1+x2

≥6x1≤2x2≤3x1,x2

≥02OX1X2636该问题可行解域为空集，如上图所示，即无可行解域，当然也无最优解。181.5线性规划单纯形法

一、适用范围

任意个变量的数学模型。

二、原理从一初始顶点(初始基本可行解)出发，沿可行解域的边缘逐个验算遇到的顶点(基本可行解)，直至找最优点(最优解)为止。MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤

oX1X2

②③④⑤⑤ahbk最优解为：X*=(75，15)TZ*=5700

19

三、LP数模的标准型条件一:具有等式约束方程组；条件二:右边常数非负；条件三:变量非负；条件四:目标函数为Max型。MaxZ=70x1＋30x2…①s.t.3x1+9x2≤540…②5x1+5x2≤450…③9x1+3x2≤720…④x1,x2

≥0…⑤对设备A：3x1+9x2

≤540，引入非负松弛变量x3，加到不等式的左边得

3x1+9x2+x3

=540

实际使用的

空闲工时(≥0)限制工时

工时数

(起松弛作用,叫松弛变量)

MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720xj

≥0，j=1,～,5

则原数模的标准型为：对设备B：5x1+5x2

≤450，引入非负松弛变量x4，加到不等式的左边得

5x1+5x2+x4

=450

实际使用的

空闲工时(≥0)限制工时

工时数

(起松弛作用,叫松弛变量)

对设备C：9x1+3x2

≤720，引入非负松弛变量x4，加到不等式的左边得

9x1+3x2+x5

=720

实际使用的

空闲工时(≥0)限制工时

工时数

(起松弛作用,叫松弛变量)

20

四、LP数模的规范型条件一:具有标准型；条件二:约束方程组系数矩阵中含有至少一个单位子矩阵(对应的变量叫基变量)；条件三:目标函数中不含基变量。MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720xj

≥0，j=1,～,5；x3,x4,

x5为基变量

则原数模的规范型为：MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720xj

≥0，j=1,～,5

x3x4x539100100A=55010中有B=010=（

3、

4、

5）=E93001001一组基

1

2

3

4

5

x1x2x3x4x5

非基变量基变量

基的作用是：可得到初始基本可行解(即初始顶点--通常是原点O),是单纯行迭代的基础。21五、最优解寻求步骤第一步、确定初始基本可行解：利用规范型数模，令非基变量x1、x2=0，求出基变量x3、x4、x5。得初始基本可行解为：

X(1)=（

x1,x2,

x3,x4,x5）T=(0,0,

540,450,720

)T

甲乙设备A设备B设备C→空闲工时

Z(1)=0，利润为0未生产，资源全部闲置(对应原点O)(x1、

x2

为非基变量，x3、x4、x5为基变量)

第二步、判断X(1)是否最优：检查用非基变量表达的目标函数中非基变量前的系数(叫检验数)。

MaxZ=70x1+30x2

因为检验数70、30>0，所以当x1

和x2从0增大时，Z也会增大。故当前解非最优。当前解须改进，寻求更好的解。

oX1X2

②③④⑤⑤ahbkMaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720xj

≥0，j=1,～,5；x3,x4,

x5为基变量22第三步、确定改进的非基变量及其上界:

选择使目标Z值改变得最快的

非基变量优先改进。(1)、确定非基变量

x1优先改进：因为从目标函数MaxZ=70x1+30x2可以看出

x1增加1，可使目标Z增加70；x2增加1，目标Z能增加30。

(2)、x1增加的上界是80：因为从约束方程组可以得出(从资源最优利用考虑，令x3、x4、x5

=0)x1=180-3x2-(1/3)x3=180---目前可用的设备A台时数最多可生产甲产品180Kg。

x1=90-x2-(1/5)x4=90---目前可用的设备B台时数最多可生产甲产品90Kg。

x1=80-(1/3)x2-(1/9)x5=80---目前可用的设备C台时数最多可生产甲产品80Kg。取最小值即非基变量x1增加的上界是80-----最小比值规则。此时x2=0。第四步、确定新解：将x1=80，

x2=0代入约束方程组中求出x3、x4、x5的值。得新基本可行解为：

X(2)=（x1,x2,

x3,x4,x5）T=（80,0,300,50,0）T

甲乙设备A设备B设备C→空闲工时(对应点a)

Z(2)=5600，利润为5600(x2、

x5

为非基变量，x1、x3、x4为基变量)MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720xj

≥0，j=1,～,5；x3,x4,

x5为基变量

oX1X2

②③④⑤⑤ahbk23第五步、判断X(2)是否最优：检查用非基变量表达的目标函数中非基变量前的系数(叫检验数)。

MaxZ=70x1+30x2=70[80-(1/3)x2-(1/9)x5]

+30x2=5600+(20/3)x2-(70/9)x5

因为检验数20/3>0，所以当x2

从0增大时，Z也会增大。故当前解非最优。当前解须改进，寻求更好的解。第六步、确定改进的非基变量及其上界:选择使目标Z值改变得最快的非基变量优先改进。

(1)、确定非基变量

x2改进：因为目标函数中只有一个正检验数。

(2)、x2增加的上界是15：因为从约束方程组可以得出(从资源最优利用考虑，令x3、x4、x5

=0)x2=60-(1/3)x1-(1/9)x3=60-(1/3)x1→x2=37.5

x2=90-x1-x4=90-x1→x2=15

x2=240-3x1-(1/3)x5=240-3x1→

x1=80-(1/3)x2代入上面二式取前二式的最小值即非基变量x2增加的上界是15-----最小比值规则。此时x1=75。MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720xj

≥0，j=1,～,5；x3,x4,

x5为基变量

oX1X2

②③④⑤⑤ahbk24第七步、确定新解：将x1=75，

x2=15代入约束方程组中求出x3、x4、x5的值。得新基本可行解为：

X(3)=（

x1,x2,

x3,x4,x5）T=（75,15,

180,0,0）T

甲乙设备A设备B设备C→空闲工时

Z(3)=5700，利润为5700(x4、

x5

为非基变量，x1、x2、x3为基变量)(对应点h)第八步、判断X(3)是否最优：检查用非基变量表达的目标函数中非基变量前的系数(叫检验数)。

MaxZ=70x1+30x2=

5700-2x4-(20/3)x5

由5x1+5x2+x4

=4509x1+3x2+x5

=720

解得x1=75+(1/10)x4-(1/6)x5，x2=15-(3/10)x4+(1/6)x5，代入目标函数中得

MaxZ=70x1+30x2=70[75+(1/10)x4-(1/6)x5]

+30[15-(3/10)x4+(1/6)x5]=

5700-2x4-(20/3)x5

因为检验数-2、-20/3<0，所以当前解最优。最优解为：

X*=（75,15,

180,0,0）T，Z*=5700

所以，产品甲、乙分别安排产量75Kg、15Kg，可使工厂获利最大为5700元。MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720xj

≥0，j=1,～,5；x3,x4,

x5为基变量

oX1X2

②③④⑤⑤ahbk25

将数模写成如下形式：

3x1+9x2+x3

=540

5x1+5x2+x4

=450

9x1+3x2+x5

=720-Z+70x1＋30x2=0

列出以下单纯形表进行旋转运算

：

六、单纯形法表格化-----单纯形表MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720xj

≥0，j=1,～,5；x3,x4,

x5为基变量

oX1X2

②③④⑤⑤ahbk26基x1x2x3x4x5b

x339100540x455010450x593001720-Z70300000

70300000001809080x3x4x1-Z11/3001/9800810-1/3300010/301-5/950020/300-70/9-560037.515240x3x2x1-Z0103/10-1/615001-12/51180100-1/101/675000-2-20/3-5700基本可行解X(1)=(0，0，540，450，720)TZ(1)=0对应原点OX(2)=(80，0，300，50，0)TZ(2)=5600对应顶点aX(3)=(75，15，180，0，0)TZ(3)=5700对应顶点h最优解为：X*=X(3)=(75，15，180，0，0)TZ*=Z(3)=

5700

00700307027

问题一：若最大检验数有两个或两个以上并且相等，应如何确定入基变量(可任选)。

问题二：若最小比值有两个或两个以上并且相等，应如何确定出基变量(可任选)。

问题三：原问题无解的判断：入基列元素全部非正。基x1x2x3x4x5b

1

2x33910054018060x4550104509090x59300172080240-Z70700000基x1x2x3x4x5b

x33-9100540x450010450x59-3001720-Z70300000基x1x2x3x4x5b

x339100540180x45501045080x59300172080-Z70300000MaxZ=70x1＋30x2s.t.3x1-9x2≤5405x1≤4509x1-3x2≤720x1,x2

≥0b

935131/3028

七、单纯形的经济信息

MaxZ=70x1＋30x2s.t.3x1+9x2+x3

=5405x1+5x2+x4

=4509x1+3x2+x5

=720xj

≥0，j=1,～,5；x3,x4,

x5为基变量

1、决策变量的解：x1=75公斤,x2=15公斤，提供最优决策方案。

2、松弛变量的解：最优决策条件下，提供资源的剩余量。

x3=180,设备A的闲置台时。

x4=0,设备B的闲置台时。

x5=0,设备C的闲置台时。

3、相关价值系数：改化或约化的价值系数(新解下的价值系数---单位产品提供的利润)。

o:X(1)=(0,0,540,450,720)T；MaxZ=0+70x1+30x2+0x3+0

x4+0

x5a:X(2)=(80,0,300,50,0)T；MaxZ=5600+0x1+

(20/3)x2+0x3+0x4-(90/7)x5h:X(3)=(75,15,180,0,0)T；MaxZ=5700+0x1+0x2-0x3-2x4-(20/3)x5

反映各产品有相互制约作用，起了考虑市场信息和规划方案改变对利润的综合影响。

oX1X2

②③④⑤⑤ahbk最优解为：X*=(75，15)TZ*=5700

29

4、影子(潜在)价格⑴影子价格的概念：最优规划条件下，单位资源能够带来的目标增量。是反映资源最优利用的一种虚拟价格，也叫资源边际利润。⑵影子价格的计算：最优表中松弛变量检验数的相反数,或最优目标函数中松弛变量系数的相反数。基x1x2x3x4x5bx3001-12/51180x20103/10-1/615x1100-1/101/675-Z000-2-20/3-5700

检验数：0-2-20/3影子价格：0220/3MaxZ=5700+0x1+0x2-0x3-2x4-(20/3)x5当设备A增加1个台时，此时x3=-1，则利润Z增加0元，为5700+0元；当设备B增加1个台时，此时x4=-1，则利润Z增加2元，为5700+2元；当设备C增加1个台时，此时x5=-1，则利润Z增加20/3元，为5700+20/3元。结论：设备A的影子价格为0(元/台时)，

设备B的影子价格为2(元/台时)，

设备C的影子价格为20/3(元/台时)。

30⑶影子价格的应用①在企业内部：指出挖潜方向。原理：影子价格高的资源潜力大，影子价格低的资源潜力小。设备A的影子价格为0元/台时：已有180台时剩余，缺少180台时不会造成任何损失，增加数量

也不会增加利润，为非关键资源，不应对此花费代价。设备B的影子价格为2元/台时：缺少

1台时将造成

2元的损失，增加1

台时将增加

2元的利润。

为关键资源，应重点挖潜(比如增加数量)，其重要程度次之。设备C的影子价格为20/3元/台时：缺少

1台时将造成

20/3元的损失，增加1

台时将增加

20/3

元的利润。为关键资源，应重点挖潜(比如增加数量)，其重要程度最高。②在企业外部：制定外单位来料加工时的收费用标准：合计收费0+900+4800=5700元。设备A的收费用标准为0元/台时，现有540台时，共收费0×540=0元(不考虑收费)；

设备B的收费用标准为2元/台时，现有450台时，共收费2×450=900元；

设备C的收费用标准为20/3元/台时，现有720台时，共收费20/3×720=4800元；

衡量资源的使用是否合理：同一种资源在不同的地方和不同的时期，其影子价格不相同。影子价格高的说明使用合理，否则说明使用不合理。应建立动态影子价格体系，物尽其用。

31

例2：求解数模：所以x1、x3、x6

为基变量。用非基变量表达目标函数：将x1

=5-2x2+2x4

x3

=6-x2+x4-2x5代入目标函数中得：MinZ=2(5-2x2+2x4)

-x2-(6-x2+x4-2x5)

-3

x5=11-4x2+3x4-5x5令Z=-D，原目标函数等价于：MaxD=-11+4x2-3x4+5x5从而原数模的规范型数模为：32解：用单纯形表迭代计算如下基x1x2x3x4x5x6b

x1120-2005---x3011-12063x602013188/3-D040-35011基本可行解X(1)=(5,0,6,0,0,8)TD(1)=-11x1120-20055/2x30-1/31-5/30-2/32/3---x502/301/311/38/34-D02/30-14/30-5/3-7/3X(2)=(5,0,2/3,0,8/3,0)TD(2)=7/3x21/210-1005/2x31/601-20-2/33/2x5-1/300111/31-D-1/300-40-5/3-4X(3)=(0,5/2,3/2,0,1,0)TD(3)=4X*=(0，5/2，3/2，0，1，0)TZ=-D(3)=-433

八、单纯形的理论分析

1、L.P.数模的标准型⑴一般式：⑵求和式：

MaxZ=c1·x1+c2

·x2+---+cn

·xn

a11·

x1+a12

·x2+---+a1n

·xn=b1

a21·

x1+a22

·x2+---+a2n·xn=b2s.t.------------------------------------------

am1

·

x1+am2·x2+---+amn·xn=bmxj≥0,j=1,～,n

34⑶向量式：⑷矩阵式：

352、L.P.数模的规范型

⑴s.t.方程组中含一组基：XB=(x1，x2，---，xm)Tx1+a1,m+1

xm+1+---+a1n

xn=b1x2+a2,m+1

xm+1+

---+a2,n

xn=b2s.t.···································································xm+am,m+1xm+1+---+

am,nxn=bm

⑵目标函数中不含基变量x1，x2，---，xm

：

363、L.P.数模的单纯形表

MaxZ=c1x1+c2

x2+

···+cn

xnx1+a1,m+1

xm+1+---+a1n

xn=b1x2+a2,m+1

xm+1+

---+a2,n

xn=b2s.t.--------------------------------------------------xm+am,m+1xm+1+---+

am,nxn=bm

xj≥0，j=1~m

374、单纯形法求解步骤

第一步：将原问题的数学模型化为规范型，列出初始单纯形表。第二步：确定入基变量：选择最大的正检验数对应的非基变量入基。第三步：确定出基变量：选择最小的正比值对应的基变量出基。第四步：确定主元素：入基列和出基行的交叉元素为主元素。第五步：以元素为中心进行旋转运算(即将入基列变为单位向量列)，得一新表。第六步：重复以上步骤直至最优表。381.6人造基下的单纯形法---两阶段法和大M法

一、什么时候会出现人造基

例：求解下列数模

MinZ=x1－2x2s.t.x1+x2≥2-x1+x2≥1x2≤3x1,x2

≥0

当数模的约束条件出现”＝”或”≥”时，要将数模化为规范型，一般情况下就需要引入人工变量形成人造基。

标准化：引入非负松弛变量x3、x4、x5

令Z=-D,化成标准型如下

MaxD=-x1+

2x2s.t.x1+x2-x3

=2-x1+x2-x4

=

1x2+x5=3

xj≥0，j=1~5

规范化：引入非负人工变量x6、x7

化成规范型如下

MaxD=-x1+

2x2s.t.x1+x2-x3

+x6=2-x1+x2-x4

+x7=

1x2+x5=3

xj≥0，j=1~7，x5,x6,x7为基变量规范型解基的形成只要三种可能：①由决策变量自然形成的解基：由具体的物理变量组成，可含在最优解里，②由添加松弛变量形成的解基：每步迭代后的解均是可行解。③由引入人工变量形成的解基(人造基)：由虚拟人工变量组成，改变了原s.t.。39

二、两阶段法例：求解下列数模

MinZ=x1－2x2

…①s.t.x1+x2≥2

…②-x1+x2≥1

…③x2≤3

…④x1,x2

≥0

…⑤

-1o123x1-2-1123x2②③④

abch

规范化：引入非负松弛变量x3、x4、x5

和非负人工变量x6、x7

化成规范型如下

MaxD=-x1+

2x2s.t.x1+x2-x3

+x6=2-x1+x2-x4

+x7=

1x2+x5=3

xj≥0，j=1~7，x5,x6,x7为基变量

引入新目标函数MinW=x6+x7=3-2x2+x3+x4,，令W=-G，规范化得：

MaxG=-3+2x2-x3-x4第一阶段：通过单纯形迭代，将人工变量x6、x7从基中置换出来使其取值0，并得初始基本可行解。若人工变量无法全部出基，则原问题无解；若人工变量无法全部出基，但取值为0，则原问题有多余约束条件，去除多余约束条件再求解。第二阶段：通过单纯形迭代，求出最优解。40不可行解

X(1)

=(0，0，0，0，3，2，1)TD(1)=0(对应O点)G(1)=-3X(2)

=(0，1，0，0，2，1，0)TD(2)=2(对应a点)G(2)=-1

初始基本可行解X(3)

=(1/2，3/2，0，0，3/2，0，0)TD(3)=5/2(对应b点)G(3)=-0X(4)

=(0，2，0，1，1)TD(4)=4(对应C点)X(5)

=(0，3，1，2，0)TD(5)=6(对应h点)X*

=(0，3，1，2，0)TZ*=-D(5)=-641

两阶段法的作用例：求解下列数模

MinZ=-3x1+4x2

…①s.t.x1+x2≤4

…②2x1+3x2≥18…③x1,x2

≥0

…④

规范化：引入非负松弛变量x3、x4

和非负人工变量x5将s.t.化成规范型如下

s.t.x1+x2+x3

=42x1+3x2-x4

+x5=

18

xj≥0，j=1~5，x3,x5为基变量

引入新目标函数MinW=x5=18-2x1-3x2+x4，令W=-G，规范化得：

MaxG=-18+2x1+3x2-x4

⑴通过第一阶段可以判断原问题是否无解方法：人工变量无法全部出基，MinW≠0x1x2o③②④④基x1x2x3x4x5b

x3111004x5230-1118-G230-101846不可行解X(1)=(0，0，4，0，18)TG(1)=-18x2111004x5-10-3-116-G-10-3-106X(2)=(0，4，0，0，6)TG(2)=-6原问题是否无解42

⑵通过第一阶段可以发现多余的约束条件方法：人工变量无法全部出基，但取值为0。基x1x2x3x4x5b

x3111004x5230-1118-G230-101846不可行解X(1)=(0，0，4，0，18)TG(1)=-18x2111004x5-10-3-110-G-10-3-106X(2)=(0，4，0，0，0)TG(2)=-6原问题是否无解43

三、大M法例：求解下列数模

MinZ=x1－2x2

…①s.t.x1+x2≥2

…②-x1+x2≥1

…③x2≤3

…④x1,x2

≥0

…⑤

-1o123x1-2-1123x2②③④

abch

规范化：引入非负松弛变量x3、x4