运筹学与效益管理课件

运筹学与效益管理绪论运筹学与效益管理绪论1本章是绪论，介绍运筹学的释义，重点是运筹学的基本特征与方法，使学生了解运筹学主要分支，明确计算机专业学习运筹学的目的，掌握学习运筹学的方法。本章是绪论，介绍运筹学的释义，重点是运筹学的基本特征与方法，2第一节

运筹学释义与发展简史

大英百科全书：运筹学是一门应用于管理有组织系统的科学，运筹学为掌管这类系统的人提供决策目标和数量分析的工具。英：Operationalresearch美：Operationsresearch第一节

运筹学释义与发展简史

大英百科全书：运筹学是一门应用3发展简史

朴素运筹学：齐王赛马、丁渭修皇宫。起源：1938年，英国研究雷达站的配置协调问题。发展：45-50，创建、线性规划50年代，使用计算机、快速成长发展60年代，应用普及、快速发展当代，广泛应用，尤其在经济领域发展简史

朴素运筹学：齐王赛马、丁渭修皇宫。4第二节

基本特征与方法

系统的整体观念：协调部分、整体最优多学科的综合：交叉学科，吸收多学科多领域的经验和技能模型方法的应用：建立数学和模拟的模型，抽象研究。第二节

基本特征与方法

系统的整体观念：协调部分、整体最优5模型方法分析和表述问题：定性分析,决定决策目标，识别关键因素，列出控制变量。建立模型：抽象规范，找出本质规律，分析因果关系，研究算法。求解：求出可行解，满意解，最优解检验解建立对解的控制方案的实施模型方法分析和表述问题：定性分析,决定决策目标，识别关键因素6第三节

运筹学主要分支线性规划非线性规划动态规划图与网络分析存贮论排队论对策论决策论第三节

运筹学主要分支线性规划7第四节

运筹学与管理科学马克思：一门科学只有成功地应用数学时，才算达到了完善的地步。运筹学实际上是数学应用于管理计算机专业为什么学运筹学效率与效益复杂计算机算法需要运筹学将来从事管理工作第四节

运筹学与管理科学马克思：一门科学只有成功地应用数学时8如何学好运筹学多动脑筋多做题多理论联系实际如何学好运筹学多动脑筋9本章介绍的线性规划及单纯形法是运筹学的基础和核心，重点是线性规划数学模型，从图解法开始，引入单纯形法的原理，使学生了解单纯形法计算步骤，通过对一些实例的分析，使学生掌握建立数学模型的方法。本章的难点是单纯形法计算步骤，必须通过大量的习题练习，本章共布置15道习题。

本章介绍的线性规划及单纯形法是运筹学的基础和核心，重点是线性10第一章

线性规划及单纯形法

第一节线性规划问题及数学模型第一章

线性规划及单纯形法11例产量Ix1IIx2每天可用能力设备A(h)y1设备B(h)y2调试工序(h)y306152115245利润(元)21例12目标函数maxz=2x1+x2约束条件5x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0目标函数13目标函数max(min)z=c1x1+c2x2+…+cnxn约束条件a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2……am1x1+am2x2+…+amnxn≤(=,≥)bmx1,x2,…,xn≥0目标函数14标准化步骤当bi≤0时，等式两边同乘-1。约束条件为不等式，添加松弛变量。

当“≤”，加+xk,使约束条件为等式。

当“≥”，加-xk,使约束条件为等式。X取值无约束，令x=x’–x’’,x’≥0,x’’≥0。当x≤0时,令x=-x’,x’≥0。minz=cx改为max(-z)=-cx。标准化步骤当bi≤0时，等式两边同乘-1。15标准形式maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=bmx1,x2,…,xn≥0b1,b2,…,bm≥0标准形式16线性消元法(1)两边同乘非零。(2)交换两行。(3)将一行的倍数加到另一行。10…0c1r+1…c1nd101…0c2r+1…c2nd2…00…1crr+1…crndr00…00…0dr+100…00…0dm

线性消元法17若dr+1,…,dm不全为零，方程组无解。若r=n，方程组有唯一解。若r<n，任取(xr+1,…,xn)=(tr+1,…,tn),x1=d1-c1r+1tr+1-…-c1jtj-c1ntn

x2=d2–c2r+1tr+1-…-c2jtj–c2ntn……xr=dr-crr+1tr+1-…-crjtj–crntn

xr+1=tr+1

…xn=tn若dr+1,…,dm不全为零，方程组无解。18第二节图解法

步骤画直角坐标系（x1,x2)画约束条件，找出可行域图示目标函数最优解的确定第二节图解法

步骤画直角坐标系（x1,x2)19解的情况：唯一最优解；无穷个最优解；无界解；无可行解。存在可行域，则它是一个凸集。若存在最优解，则它在可行域凸集上的某个顶点。解题思路：先找出凸集的一个顶点，计算它的目标函数值，比较周围顶点的目标函数值，如果值更优，转到新顶点。重复过程，直至找到目标函数值取得最优的顶点。解的情况：唯一最优解；无穷个最优解；无界解；无可行解。20第三节单纯形法原理解的概念：可行解：满足约束条件的解，组成可行域。基：约束方程组的系数矩阵中一个满秩子矩阵。基向量，基变量。基解：令非基变量取0，求出的唯一解。基可行解：非负基解。基解可能取负值，就不满足约束条件。第三节单纯形法原理解的概念：21凸集：集合中任意两点的连线上的点都在集合中。对于X1,X2C,a[0,1],aX1+(1-a)X2C顶点：不在集合中任意两个不同点的连线上的点。不X1,X2C,X1X2,a(0,1),使得X=aX1+(1-a)X2C凸集：集合中任意两点的连线上的点都在集合中。22定理1：若线形规划问题存在可行解，则它的可行域是一个凸集。引理：可行解为基可行解的充要条件是它的正分量对应的系数列向量线性独立。定理2：基可行解对应可行域（凸集）的顶点。定理3：若线形规划问题存在最优解，则存在一个基可行解是最优解。讨论问题：找出书上证明中的逻辑错误定理1：若线形规划问题存在可行解，则它的可行域是一个凸集。23引理：若C是有界凸集，则C中任一点都可表示为C的顶点的凸组合。定理4：若线形规划问题的解有界，则存在一个基可行解是最优解。证：设X(0)是最优解,CX(0)最大。如果它不是顶点，由引理，X(0)可表示为顶点的凸组合，X(0)=∑kiX(i)。∑ki=1,ki

≥0CX(0)=∑CkiX(i)=

∑kiCX(i)≤∑kiCX(0)=

CX(0)，因此，CX(0)=CX(i)。引理：若C是有界凸集，则C中任一点都可表示为C的顶点的凸组24单纯形法原理确定初始基可行解：系数矩阵中找或引进一个单位矩阵从一个基可行解转换为相邻的基可行解。

最优性检验和解的判别

检验数单纯形法原理25解的判别当所有的σj≤0,顶点为最优解。当所有的σj≤0,还有非基变量的σk=0，表明引入对应顶点仍为最优解，从而有无穷个最优解。当某个σj>0,又Pj≤0,则当θ→∞，z→∞,即有无界解。无可行解：找不到初始基可行解。解的判别当所有的σj≤0,顶点为最优解。26直接观察x1=b1-a1m+1xm+1-…-a1jxj-a1nxn

x2=b2–a2m+1xm+1-…-a1jxj–a2nxn……xm=bm-amm+1xm+1-…-amjxj–amnxn当xj增加1，则目标函数增加cj，然而xi减少aij，目标函数减少ciaij，i=1,2,…,m.合计变动，直接观察27当σj≤0，为了得到最大，xj越小越好，xj=0。当σj>0，为了得到最大，xj越大越好，因此把xj>0，即取作基变量。但是xj增大，会使xj<0。然而当pj≤0时，xj增大会使xj也增大，因此目标函数无限增加，达到无界解。当σj≤0，为了得到最大，xj越小越好，xj=028第四节计算步骤求初始基可行解，列出初始单纯形表

计算各列的检验数：第四节计算步骤求初始基可行解，列出初始单纯形表

计算各列的29单纯形表Cjc1…cm…cj…cnCB基Bx1…xm…xj…xnc1c2cm…x1x2xmb1b2bm100………001………a1ja2jamj………a1na2namnσj0…0…σj…σn单纯形表Cjc1…cm…cj…cnCB基Bx1…xm…xj…302最优性检验，确定解的类型从一个基可行解转换为相邻的目标函数值更大的基可行解

（1）确定换入基变量：

σk=max{σj|σj>0}

(2）确定换出基变量：

（3）初等行变换重复第2，3步，直至所有σj≤02最优性检验，确定解的类型从一个基可行解转换为相邻的目标函31cj21000CB基Bx1x2x3x4x5000x3x4x5152450[6]1521100010001σj21000020x3x1x5154101052/6[4/6]10001/6-1/6001σj01/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2000-1/4-1/2cj21000CB基Bx1x2x3x4x50x315051032第五节单纯形法的进一步讨论人工变量法：如果标准化后，系数矩阵中没有单位矩阵，则引进单位向量，形成单位矩阵。为了在最优解中人工变量取值为零，令人工变量的价值系数为任意大的负值，“-M”。

在计算各列的检验数时，只要人工变量取值大于零，目标函数就不是最优。若最优解中，人工变量取值大于零，则原问题无可行解。第五节单纯形法的进一步讨论人工变量法：如果标准化后，系数矩阵33cj-30100-M-MCB基Bx1x2x3x4x5x6x70-M-Mx4x6x74191-201[1]31-111000-10010001σj-2M-34M10-M0000-Mx4x2x73163-2[6]0102-141001-13-11-3001σj6M-304M+103M-4M000-3x4x2x103100101001/3[2/3]100-1/201/21/20-1/2-1/21/31/6σj00303/2-M-3/2½-Mcj-30100-M-MCB基Bx1x2x3x4x5x6x7342两阶段法:相当于ci’=ci/M为了解决计算机求解时“M”的取值的麻烦（1）先求目标函数中只包含人工变量的线形规划，他们的价值系数为-1。当人工变量取值为零，目标函数值也为零。此时的最优解是原问题的基可行解。

若最优解的目标函数值不为零，则原问题无可行解。（2）若有可行解，则在原问题中除去人工变量，恢复原来的价值系数，继续寻找。2两阶段法:相当于ci’=ci/M为了解决计算机求解时35cj00000-1-1CB基Bx1x2x3x4x5x6x70-1-1x4x6x74191-201[1]31-111000-10010001σj-2400-10000-1x4x2x73163-2[6]0102-141001-13-11-3001σj60403-40000x4x2x103100101001/32/3100-1/201/21/20-1/2-½1/31/6σj00000-1-1cj00000-1-1CB基Bx1x2x3x4x5x6x7036恢复原来的目标函数cj-30100CB基bx1x2x3x4x500-3x4x2x103100101001/3[2/3]100-1/201/2σj00303/2001x4x2x305/23/20-1/23/2010001100-1/2-1/43/4σj-9/2000-3/4恢复原来的目标函数cj-30100CB基bx1x2x3x4x373。几个问题极小问题：最优标志是所有σj≥0退化：在选择换出基，有时会出现多个最小比值，表示有多余的约束条件，存在线性相关。对策：始终选择下标值最小的变量作为换出变量和换入变量。无可行解：添加人工变量后。无论人工变量法还是两阶段法，当求解出现所有σj≤0，如基变量中仍然含有非零的人工变量，表明问题无可行解。3。几个问题极小问题：最优标志是所有σj≥038第六节数据包络分析1。有关概念：数据包络分析(dataenvelopmentanalysis,DEA)是一种基于线性规划的用于评价同类型组织工作绩效相对有效性的工具。各个部门有相同的投入产出项目，如果投入产出比可以折算成同一单位，就可以进行绩效排序。2维投入可化生产前沿面，形成一条数据包络线。线上的点，表示投入的最低极限。第六节数据包络分析1。有关概念：392.线性规划的数学模型设有n个决策单元，每个决策单元有相同的m项投入和相同的s项产出。决策单元d1d2`````dn投1x11x12``````x1n2x21x22``````x2n入mxm1xm2`````xmn

y11y12``````y1n1产y21y22``````y2n2ys1ys2``````ysns出2.线性规划的数学模型40

构造由n个决策单元的线性组合1d1+2d2+`````+ndn,1+2+`````+n=1投入为：X产出为：Y现在要衡量某一个决策单元j的DEA,MinEXExjYyj1+2+`````+n=1构造由n个决策单元的线性组合1d1+2d2+````41例8分理处1分理处2分理处3分理处4职员数15202120营业面积140130120135储蓄存款18001000800900贷款200350450420中间业务1600100013001500再用4个决策单元的线性组合对每个分理处计算E，确定各分理处是否DEA有效例8分理处1分理处2分理处3分理处442第七节应用举例问题的目标能用某种指标度量大小，并能用线性函数表示。存在多种方案达到目标。受到一些条件的约束，可用线性等式或不等式表示。建立实际问题的线性规划模型，比解线性规划更有挑战性，创造性。第七节应用举例问题的目标能用某种指标度量大小，并能用线性函数43本章介绍线形规划的对偶性理论，重点是对偶性理论的意义，从对偶问题开始，引入对偶性理论，使学生从多方面了解线形规划，通过对灵敏度分析和参数线形规划的分析，使学生建立变化运动的观点，掌握辨证的思维方法。本章的难点是对偶性理论的经济意义，本章共布置12道习题。

本章介绍线形规划的对偶性理论，重点是对偶性理论的意义，从对偶44第二章

线性规划对偶性理论与灵敏度分析第一节线性规划的对偶性理论1。问题的提出：每一个线性规划问题都有对偶问题，求出一个问题，同时也给出另一个问题的解。用yi表示第i种资源的估价。第二章

线性规划对偶性理论与灵敏度分析第一节45对称条件下对偶问题的一般形式maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2……am1x1+am2x2+…+amnxn≤bmx1,x2,…,xn≥0对称条件下对偶问题的一般形式maxz=c1x1+c246对偶问题min=b1y1+b2y2+…+bmyma11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2……a1ny1+a2ny2+…+amnym≥cmy1,y2,…,ym≥0对偶问题min=b1y1+b2y2+…+bmym47Maxz=CXminw=b’Y

AX≤bA’Y≥C’

X≥0Y≥0

maxw’=(-b’)Y

(-A’Y)≤-C’

Y≥0

minw’’=(-C’)’Z

(-A’)’Z≥(-b’)’

Z≥0非对称条件下原-对偶问题关系Maxz=CXminw48原问题（对偶问题）对偶问题（原问题）AbC目标函数约束系数矩阵约束条件右端向量价格系数向量转置矩阵价格系数向量约束条件右端向量xj

≥0xj≤0xj无约束yj

≥0yj≤0yj无约束原问题（对偶问题）对偶问题（原问题）A约束系数矩阵转置矩阵x49第二节对偶问题的基本性质单纯形法的矩阵描述：

A=(B,N),X=(XB,XN)T,C=(CB,CN).

Maxz=CX+0Xs=CBXB+CNXN+0Xs

AX+IXs=b

BXB+NXN+IXs=b

BXB=b-NXN-IXs

XB=B-1b-B-1NXN-B-1Xs

代入目标函数Maxz=CBB-1b+(CN-CBB-1N)XN-CBB-1Xs

第二节对偶问题的基本性质单纯形法的矩阵描述：

A=(50CBCN0XBXNXs0XBbBNIσjCBCN0CBXBB-1bIB-1NB-1σj0CN-CBB-1N-CBB-1CBCN0XBXNXs0XBbBNIσjCBCN0CBXBB51当CN-CBB-1N≤0,-CBB-1≤

0则令XN=0，Xs=0，XB=

B-1b,Maxz=CBB-1b.(CB,CN)-CBB-1(B,N)≤0,C-CBB-1A≤0-CBB-1≤

0令Y’=CBB-1,则A’Y≥C’Y≥0Y就是松弛变量的检验数的相反数，恰好是对偶问题的可行解。w=Y’b=CBB-1b=CBXB=z当CN-CBB-1N≤0,-CBB-1≤52原问题maxz=2x1+x2+0x3+0x4+0x55x2+x3=156x1+2x2+x4=24x1+x2+x5=5对偶问题minw=15y1+24y2+5y3+0y4+0y56y2+y3-y4=25y1+2y2+y3-y5=1xi,yi≥0原问题53cj21000CB基bx1x2x3x4x5021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2σj000-1/4-1/2cjy4y5y1y2y3b基CB1524500y1y2y3y4y5245y2y31/41/2-5/415/21001-1/41/21/4-3/2σj15/2x30x40x57/2x13/2x2cj21000CB基bx1x2x3x4x50x315/20054对偶问题的基本性质1.弱对偶性：如果X是原问题的可行解，Y是对偶问题的可行解，AX≤b,Y’AX≤Y’b,

Y’A≥C,Y’AX≥CX,

则z=CX≤Y’b=w2.最优性：如果X是原问题的可行解，Y是对偶问题的可行解，且CX=Y’b，则它们都是最优解。3.无界性：如果原问题（对偶问题）具有无界解时，则其对偶问题（原问题）无可行解。注：逆命题不成立。对偶问题的基本性质1.弱对偶性：如果X是原问题的可行解，Y55如果原问题(对偶问题)有可行解,对偶问题(原问题)无可行解时，则其原问题(对偶问题)具有无界解。4.强对偶性：如果原问题和对偶问题都有可行解，则它们都有最优解，并且最优解的目标函数值相等。5.互补松弛性：最优解中，对偶变量0对应约束条件为等式。对应约束条件为不等式对偶变量=0，

CX≤Y’AX≤Y’b,CX=Y’b,Y’(AX-b)=0,(Y’A-C)X=0如果原问题(对偶问题)有可行解,对偶问题(原问题)无可行解566.原问题和对偶问题之间存在一对互补的基解，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。(1)两者都有可行解,z≤w,从而有最优解z=w。(2)两者都没有可行解。(3)一个有无界解另一个无可行解。(4)一个有可行解,另一个无可行解可行解为无界解。四种情况恰出现一次。6.原问题和对偶问题之间存在一对互补的基解，原问题的松弛变57第三节影子价格

在最优解中，bi表示资源,对偶变量yi表示对资源的估价，称为影子价格，不是市场价格。Z=CX=b’Y=w1。影子价格取决于资源的利用率。2。影子价格是边际价格，表示在最优解中bi表示每增加一个单位时目标函数的增量。第三节影子价格在最优解中，bi表示资源,对偶变量yi表示对583。影子价格是机会成本，市场价格低于影子价格，可以买进，反之则卖出。4。yi>0yi=05。σj=cj-CBB-1Pj=cj–Y’Pj=cj-

后者是生产第j种产品的隐含成本。6。线性规划的求解是资源的最优分配。对偶问题的求解是资源的恰当估价。3。影子价格是机会成本，市场价格低于影子价格，可以买进，反之59第四节对偶单纯形法

对偶单纯形法的基本思想：单纯形法的迭代中，在保持常数项非负的条件下，逐步使得检验数非正。对偶的思想是，在保持检验数非正的条件下，逐步使得常数项非负。对偶单纯形法的计算步骤：列出初始单纯形表，使得检验数都非正。如果b列都非负，即为最优解。否则，计算

br=min{bi},xr为换出变量。确定换入变量：

第四节对偶单纯形法对偶单纯形法的基本思想：单纯形法的迭代中603.以ars为主元素，xs为换入变量，消元。4.如果br<0，而对所有j=1,2,…,n，有arj≥0,原问题无可行解。使用对偶单纯形法的前提是，找到线性方程组的一个解，所有检验数都非正。单纯形法进行列操作，使得检验数逐步非正；对偶单纯形法进行行操作，使得常数项逐步非负。3.以ars为主元素，xs为换入变量，消元。61第五节灵敏度分析

研究参数发生，最优解会有什么变化，

或者参数在什么范围内变化，最优解不变。

b’=B-1b,p’=B-1p,σj重新计算

原问题对偶问题结论或继续计算的步骤可行解b≥0可行解b≥0非可行解b≤0非可行解b≤0可行解σj

≤0非可行解σj

≥0可行解σj

≤0非可行解σj

≥0表中值仍为最优值用单纯形继续迭代用对偶单纯形继续迭代引入人工变量，重新计算第五节灵敏度分析

研究参数发生，最优解会有什么变化，

或者参621.分析c的变化：只会引起检验数的变化cj1.52000CB基bx1x2x3x4x501.52x3x1x215/27/23/2010001100[5/4]1/4-1/4-15/2-1/23/2σj0001/8-9/401.52x4x1x26230100014/5-1/51/5100-610σj00-1/100-3/21.分析c的变化：只会引起检验数的变化cj1.52000C63/4-1/2≤0

1-3/2≤0

2/3≤=c2≤2cj2000CB基bx1x2x3x4x502x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2σj000/4-1/21-3/2/4-1/2≤0

1-3/2≤0

2/3≤642.分析b的变化,只会引起常数项的变化,b’=B-1bcj21000CB基bx1x2x3x4x5021x3x1x235/211/2-1/20100011005/41/4[-1/4]-15/2-1/23/2σj000-1/4-1/2020x3x1x4155201051-410000101-6σj0-100-22.分析b的变化,只会引起常数项的变化,b’=B-1bcj65

663.增加一个变量xj的分析,pj’=B-1pj

σj=cj–Y’pjcj210003CB基bx1x2x3x4x5x6021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2-70[2]σj000-1/4-1/21023x3x1x63/47/23/40107/201/21003/81/4-1/8-9/4-1/23/4001σj0-1/20-1/8-203.增加一个变量xj的分析,pj’=B-1pj

674.分析aij的变化:一般情况下，B也会发生变化，最好重新计算。如果只有一列变化，可以用增加一个变量xj的分析的方法。5.增加一个约束条件：将原来的最优解代入新增的约束条件，如满足，原来的最优解不变。否则将新增的约束条件直接加到最终的单纯形表中，继续计算。4.分析aij的变化:一般情况下，B也会发生变化，最好重新计68c210003CB基bx1x2x3x4x5x60210x3x1x2x615/27/23/2120103001210005/41/4-1/40-15/2-1/23/200001σ000-1/4-1/200210x3x1x2x615/27/23/2-3/20100001010005/41/4-1/4-1/4-15/2-1/23/2[-3/2]0001σ000-1/4-1/200210x3x1x2x515/27/23/210100001010005/41/4-1/41/6-15/2-1/23/21-5-1/31-2/3c210003CB基bx1x2x3x4x5x60x315/269第六节参数线性规划

当c或b变化时，目标函数将随之线性变化。即CC+C*,或bb+b*1。令=0，求解得最终单纯形表。2。将C*或b*项反映到最终单纯形表。3。随的增大或减小，观测原问题或对偶问题，确定原解允许的的变动范围，以及当超出变动范围后，求新解。先讨论1

≤≤2，再讨论≤1和≥2。4。重复第3步，直至解不随变动。第六节参数线性规划当c或b变化时，目标函数将随之线性变化。70Maxz()=(2+)x1+(1+2)x2

-1/4+/4≤0,-1/2-5/2≤0

推出-1/5≤≤1,z=17/2+13/2c2+1+2000CB基bx1x2x3x4x502+1+2x3x1x215/27/23/2010001100[5/4]1/4-1/4-15/2-1/23/2σ000-1/4+/4-1/2-5/2当>1,x4的检验数>0Maxz()=(2+)x1+(1+2)x2

-1/471c2+1+2000CB基bx1x2x3x4x502+1+2x4x1x2623010001[4/5]-1/51/5100-610σ001/5-/50-2-当>1,Z=7+8+当≤-1/5,x5的检验数>0c2+1+2000CB基bx1x2x3x4x50x460721/3+5/3≤0,-1/3-/6≤0推出-2≤≤-1/5,z=8+4

2+≤0,1+2≤0推出≤-2,z=0c2+1+2000CB基bx1x2x3x4x502+0x3x1x5154101051/32/31000[1/6]-1/6001σ01/3+5/30-1/3-/60000x3x4x515245061521100010001σ2+1+20001/3+5/3≤0,-1/3-/6≤0推出-73b=(15,24+,5)T,b’=B-1bc21000CB基bx1x2x3x4x5021x3x1x215/2+5/47/2+/43/2-/40100011005/41/4[-1/4]-15/2-1/23/2σ000-1/4-1/2当当-6≤≤6,>6,继续Z=对17/2+偶单/4纯形法b=(15,24+,5)T,b’=B-1bc2100074c21000CB基bx1x2x3x4x5020x3x1x4155-6+01051-410000101-6σ0-100-2021x5x1x2-1-/63+/63010001-2/15[-1/15]1/5-1/61/60100σ0-1-1/15-1/30001x5x3x2-7-/2-45-5/212+/2-2-153001010-1/2-5/21/2100σ-100-1/20c21000CB基bx1x2x3x4x50x3150510075讨论当>6，最优解不变，z=10-1-/6≥0,3+/6≥0

推出-18≤≤-6,z=9+/3-7-/2≥0,-45-5/2≥0

推出-24≤≤-18,z=12+/2当<-24,原题无意义讨论当>6，最优解不变，z=1076Maxz()=x1+2x2+3x3-1510/3x1+40/3x2+80/3x3≤300001/30x1+1/30x2+1/30x3≤100+当=0，得到最优解。劳动力的影子价格为20元，大于市场价格。2000-10≥0，1000+40≥0，推出0≤≤200，z=5000+5-200≥0，推出>200，z=9000-15Maxz()=x1+2x2+3x3-1577c12300CB基bx1x2x3x4x521x2x12000100001107/3-4/31/10-1/10-1040σ00-1/3-1/10-2021x2x12000-101000+4001107/3-4/31/10-1/10[-10]40σ0≤≤20000-1/3-1/10-2001x5x1-200900001-1/104-7/308-1/1003/1010σ2000-2-5-3/100c12300CB基bx1x2x3x4x52x2200001778本章介绍运输问题，重点是运输问题的数学模型，从简单的事例开始，引入表上作业法，使学生掌握运输问题的解题方法。本章的难点是用运输问题的方法解决一些特殊线形规划问题，本章共布置6道习题

本章介绍运输问题，重点是运输问题的数学模型，从简单的事例开始79第三章运输问题第一节数学模型第三章运输问题第一节数学模型80

产销地B1B2…Bn产量A1x11|c11x12|c12…x1n|c1na1A2x21|c21x22|c22…x2n|c2na2…Amxm1|cm1xm2|cm2…xmn|cmnam销量b1b2…bn产销地B1B2…Bn产量A1x11|c11x1281特点运输问题有有限最优解。

xij=aibj/Q是可行解,目标函数有下界0。运输问题约束条件的系数矩阵:

秩=m+n-1。

Aij=(0,…,1,0,…,0,1,0,…,0)运输问题的基可行解中非零变量的个数不能大于m+n-1个，反映m+n-1个约束条件，对应的系数列向量线性独立。特点运输问题有有限最优解。

xij=aibj/Q是可行解,82第二节表上作业法

先按某种规则找出一个初始解，然后作最优性判别。若不是最优，则在运输表上改进，迭代直至最优。一.初始基可行解：最小元素法：为了减少运费，优先考虑单位运价最小的供销业务，最大限度满足其供销量。然后再满足其次的供销业务。西北角法：优先满足运输表上西北角的供销业务。第二节表上作业法先按某种规则找出一个初始解，然后作最优性判833.沃格尔法：对每一个供应地或销售地，计算它到各销售地或供应地的最小单位运价和次小单位运价的差，称之为该地的罚数，优先考虑罚数最大的供销业务，最大限度满足其供销量。然后再满足其次的罚数最大的供销业务。沃格尔法得出的初始解的质量最好，常作运输问题最优解的近似解。3.沃格尔法：对每一个供应地或销售地，计算它到各销售地或供84二.解的最优性检验闭回路法：计算每一个空格的检验数，即给这个空格上增加一个单位运量，同时沿着一条包含它的闭回路调整相应格子的值，使其满足约束条件。闭回路经过的其余拐点都是填有数字的格子(基变量格)。闭回路上第奇数个格子的单位运价之和减去第偶数个格子的单位运价之和就是这个空格的检验数。在迭代中，不允许全部拐点都是填有数字的格子组成的闭回路，对应的列线性相关。二.解的最优性检验闭回路法：计算每一个空格的检验数，即给这个852.对偶变量法运输问题的对偶规划：Maxz’=a1u1+…+amum+b1v1+…+bnvnui+vj≤cijui,vj的符号不限。i=1,…,m,j=1,…,n由公式(2.24)知σj=cj-CBB-1Pj=cj–Y’pj

σij=cij–(u1,…,um,v1,…,vn)pij=cij–(ui+vj)2.对偶变量法运输问题的对偶规划：86设xi1j1,xi2j2,…,xisjs,(s=m+n-1)是运输问题的一个基可行解，它们对应的检验数等于零，所以ui1+vj1=ci1j1…uis+vjs=cisjs这是关于一组(m+n)个对偶变量的(m+n-1)个方程，存在多个解。令ui=0，解出方程，不妨解就是u,v…,如果它们满足约束方程σij=cij–(ui+vj)≥0设xi1j1,xi2j2,…,xisjs,(s=m+n-187则它们就是对偶问题的可行解。对于X的基变量，σj=cj–Y’pj=0，Y’A=C,Y’A-C=0对于X的非基变量,X=0。因此(Y’A-C)X=0,Y’AX=CX。另外原问题中AX=b，于是Y’b=CX，即X和Y分别为原问题和对偶问题的最优解。(Y不一定是基可行解)如果求出的解不满足约束方程：σij=cij–(ui+vj)≥0，则X不是原问题的最优解，还要继续迭代计算。则它们就是对偶问题的可行解。883.解的改进(1)如果某一个格子代表的非基变量的检验数是负数，则把检验数最小的非基变量引入基变量。(2)沿着经过它的闭回路，寻找第偶数个格子的运输量的最小值minxij作为调整量，(3)所有第偶数个格子的运输量都减去这个值，所有第奇数个格子的运输量都加上这个值，可使总运费减少σijminxij。4。几个问题：3.解的改进(1)如果某一个格子代表的非基变量的检验数是负89在最优解中，如果有非基变量的检验数是零，则说明有无穷多个解。在求初始解和迭代过程中，可能出现在某格填上一个运量后需要在运输表上同时划去一行和一列，就出现退化。为了不减少基变量，需要在同时划去一行或一列的某格填上零，表示它代表的变量是取值为零的基变量，从而使基变量恰好是m+n-1。在求初始解时，尽量减少退化。填零不可以形成闭回路。可能需要重新填零。在最优解中，如果有非基变量的检验数是零，则说明有无穷多个解。90第三节进一步讨论产销不平衡：

产量>销量：加一个假想的销地。

产量<销量：加一个假想的产地。

单位运价都是零。有转运的运输问题：

实际中常常有转运的问题，即先把物品由产地运到某个中转站（可能是产地、销地或中转仓库），然后再运到最终销地。中转要花转运费，总运费可能降低。第三节进一步讨论产销不平衡：

产量>销量：加一个假想的销地91数学模型ai:第i个产地的产量。bj:第j个销地的销量。xij:由第i个发送地到第j个接收地的数量。cij:由第i个发送地到第j个接收地的单位运价ti:第i个地点的转运量。ci:第i个地点的单位转运费。cii=-ci,xii=Q-ti数学模型ai:第i个产地的产量。92接收产地销地发送量发送1…mm+1…m+n产地1…mx11…x1m………xm1…xmmx1m+1…x1m+n………xmm+1…xmm+nQ+a1…Q+an销地m+1…m+nxm+11…xm+1m………xm+n1…xm+nmxm+1m+1…xm+1m+n………xm+nm+1…xm+nm+nQ…Q接收量Q…QQ+bm+1…Q+bm+n接收产地销地发送量发送1…mm+93接收产地销地发送量发送1…mm+1…m+n产地1…m-c1…c1m………cm1…-cmc1m+1…c1m+n………cmm+1…cmm+nQ+a1…Q+an销地m+1…m+ncm+11…cm+1m………cm+n1…xm+nm-cm+1…cm+1m+n………cm+nm+1…-cm+nQ…Q接收量Q…QQ+bm+1…Q+bm+n接收产地销地发送量发送1…mm+94第四节应用问题举例如果为了使xij=0，可令cij=M。如果为了使xij充分满足，可令cij=0。如果产量在一个区间内，可分成两个产量，一个为必需满足的，另一个为可能满足的。然后增加虚销地，必需部分的cij=M，可能部分的cij=0。第四节应用问题举例如果为了使xij=0，可令cij=M。95运筹学与效益管理绪论运筹学与效益管理绪论96本章是绪论，介绍运筹学的释义，重点是运筹学的基本特征与方法，使学生了解运筹学主要分支，明确计算机专业学习运筹学的目的，掌握学习运筹学的方法。本章是绪论，介绍运筹学的释义，重点是运筹学的基本特征与方法，97第一节

运筹学释义与发展简史

大英百科全书：运筹学是一门应用于管理有组织系统的科学，运筹学为掌管这类系统的人提供决策目标和数量分析的工具。英：Operationalresearch美：Operationsresearch第一节

运筹学释义与发展简史

大英百科全书：运筹学是一门应用98发展简史

朴素运筹学：齐王赛马、丁渭修皇宫。起源：1938年，英国研究雷达站的配置协调问题。发展：45-50，创建、线性规划50年代，使用计算机、快速成长发展60年代，应用普及、快速发展当代，广泛应用，尤其在经济领域发展简史

朴素运筹学：齐王赛马、丁渭修皇宫。99第二节

基本特征与方法

系统的整体观念：协调部分、整体最优多学科的综合：交叉学科，吸收多学科多领域的经验和技能模型方法的应用：建立数学和模拟的模型，抽象研究。第二节

基本特征与方法

系统的整体观念：协调部分、整体最优100模型方法分析和表述问题：定性分析,决定决策目标，识别关键因素，列出控制变量。建立模型：抽象规范，找出本质规律，分析因果关系，研究算法。求解：求出可行解，满意解，最优解检验解建立对解的控制方案的实施模型方法分析和表述问题：定性分析,决定决策目标，识别关键因素101第三节

运筹学主要分支线性规划非线性规划动态规划图与网络分析存贮论排队论对策论决策论第三节

运筹学主要分支线性规划102第四节

运筹学与管理科学马克思：一门科学只有成功地应用数学时，才算达到了完善的地步。运筹学实际上是数学应用于管理计算机专业为什么学运筹学效率与效益复杂计算机算法需要运筹学将来从事管理工作第四节

运筹学与管理科学马克思：一门科学只有成功地应用数学时103如何学好运筹学多动脑筋多做题多理论联系实际如何学好运筹学多动脑筋104本章介绍的线性规划及单纯形法是运筹学的基础和核心，重点是线性规划数学模型，从图解法开始，引入单纯形法的原理，使学生了解单纯形法计算步骤，通过对一些实例的分析，使学生掌握建立数学模型的方法。本章的难点是单纯形法计算步骤，必须通过大量的习题练习，本章共布置15道习题。

本章介绍的线性规划及单纯形法是运筹学的基础和核心，重点是线性105第一章

线性规划及单纯形法

第一节线性规划问题及数学模型第一章

线性规划及单纯形法106例产量Ix1IIx2每天可用能力设备A(h)y1设备B(h)y2调试工序(h)y306152115245利润(元)21例107目标函数maxz=2x1+x2约束条件5x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0目标函数108目标函数max(min)z=c1x1+c2x2+…+cnxn约束条件a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2……am1x1+am2x2+…+amnxn≤(=,≥)bmx1,x2,…,xn≥0目标函数109标准化步骤当bi≤0时，等式两边同乘-1。约束条件为不等式，添加松弛变量。

当“≤”，加+xk,使约束条件为等式。

当“≥”，加-xk,使约束条件为等式。X取值无约束，令x=x’–x’’,x’≥0,x’’≥0。当x≤0时,令x=-x’,x’≥0。minz=cx改为max(-z)=-cx。标准化步骤当bi≤0时，等式两边同乘-1。110标准形式maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=bmx1,x2,…,xn≥0b1,b2,…,bm≥0标准形式111线性消元法(1)两边同乘非零。(2)交换两行。(3)将一行的倍数加到另一行。10…0c1r+1…c1nd101…0c2r+1…c2nd2…00…1crr+1…crndr00…00…0dr+100…00…0dm

线性消元法112若dr+1,…,dm不全为零，方程组无解。若r=n，方程组有唯一解。若r<n，任取(xr+1,…,xn)=(tr+1,…,tn),x1=d1-c1r+1tr+1-…-c1jtj-c1ntn

x2=d2–c2r+1tr+1-…-c2jtj–c2ntn……xr=dr-crr+1tr+1-…-crjtj–crntn

xr+1=tr+1

…xn=tn若dr+1,…,dm不全为零，方程组无解。113第二节图解法

步骤画直角坐标系（x1,x2)画约束条件，找出可行域图示目标函数最优解的确定第二节图解法

步骤画直角坐标系（x1,x2)114解的情况：唯一最优解；无穷个最优解；无界解；无可行解。存在可行域，则它是一个凸集。若存在最优解，则它在可行域凸集上的某个顶点。解题思路：先找出凸集的一个顶点，计算它的目标函数值，比较周围顶点的目标函数值，如果值更优，转到新顶点。重复过程，直至找到目标函数值取得最优的顶点。解的情况：唯一最优解；无穷个最优解；无界解；无可行解。115第三节单纯形法原理解的概念：可行解：满足约束条件的解，组成可行域。基：约束方程组的系数矩阵中一个满秩子矩阵。基向量，基变量。基解：令非基变量取0，求出的唯一解。基可行解：非负基解。基解可能取负值，就不满足约束条件。第三节单纯形法原理解的概念：116凸集：集合中任意两点的连线上的点都在集合中。对于X1,X2C,a[0,1],aX1+(1-a)X2C顶点：不在集合中任意两个不同点的连线上的点。不X1,X2C,X1X2,a(0,1),使得X=aX1+(1-a)X2C凸集：集合中任意两点的连线上的点都在集合中。117定理1：若线形规划问题存在可行解，则它的可行域是一个凸集。引理：可行解为基可行解的充要条件是它的正分量对应的系数列向量线性独立。定理2：基可行解对应可行域（凸集）的顶点。定理3：若线形规划问题存在最优解，则存在一个基可行解是最优解。讨论问题：找出书上证明中的逻辑错误定理1：若线形规划问题存在可行解，则它的可行域是一个凸集。118引理：若C是有界凸集，则C中任一点都可表示为C的顶点的凸组合。定理4：若线形规划问题的解有界，则存在一个基可行解是最优解。证：设X(0)是最优解,CX(0)最大。如果它不是顶点，由引理，X(0)可表示为顶点的凸组合，X(0)=∑kiX(i)。∑ki=1,ki

≥0CX(0)=∑CkiX(i)=

∑kiCX(i)≤∑kiCX(0)=

CX(0)，因此，CX(0)=CX(i)。引理：若C是有界凸集，则C中任一点都可表示为C的顶点的凸组119单纯形法原理确定初始基可行解：系数矩阵中找或引进一个单位矩阵从一个基可行解转换为相邻的基可行解。

最优性检验和解的判别

检验数单纯形法原理120解的判别当所有的σj≤0,顶点为最优解。当所有的σj≤0,还有非基变量的σk=0，表明引入对应顶点仍为最优解，从而有无穷个最优解。当某个σj>0,又Pj≤0,则当θ→∞，z→∞,即有无界解。无可行解：找不到初始基可行解。解的判别当所有的σj≤0,顶点为最优解。121直接观察x1=b1-a1m+1xm+1-…-a1jxj-a1nxn

x2=b2–a2m+1xm+1-…-a1jxj–a2nxn……xm=bm-amm+1xm+1-…-amjxj–amnxn当xj增加1，则目标函数增加cj，然而xi减少aij，目标函数减少ciaij，i=1,2,…,m.合计变动，直接观察122当σj≤0，为了得到最大，xj越小越好，xj=0。当σj>0，为了得到最大，xj越大越好，因此把xj>0，即取作基变量。但是xj增大，会使xj<0。然而当pj≤0时，xj增大会使xj也增大，因此目标函数无限增加，达到无界解。当σj≤0，为了得到最大，xj越小越好，xj=0123第四节计算步骤求初始基可行解，列出初始单纯形表

计算各列的检验数：第四节计算步骤求初始基可行解，列出初始单纯形表

计算各列的124单纯形表Cjc1…cm…cj…cnCB基Bx1…xm…xj…xnc1c2cm…x1x2xmb1b2bm100………001………a1ja2jamj………a1na2namnσj0…0…σj…σn单纯形表Cjc1…cm…cj…cnCB基Bx1…xm…xj…1252最优性检验，确定解的类型从一个基可行解转换为相邻的目标函数值更大的基可行解

（1）确定换入基变量：

σk=max{σj|σj>0}

(2）确定换出基变量：

（3）初等行变换重复第2，3步，直至所有σj≤02最优性检验，确定解的类型从一个基可行解转换为相邻的目标函126cj21000CB基Bx1x2x3x4x5000x3x4x5152450[6]1521100010001σj21000020x3x1x5154101052/6[4/6]10001/6-1/6001σj01/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2000-1/4-1/2cj21000CB基Bx1x2x3x4x50x3150510127第五节单纯形法的进一步讨论人工变量法：如果标准化后，系数矩阵中没有单位矩阵，则引进单位向量，形成单位矩阵。为了在最优解中人工变量取值为零，令人工变量的价值系数为任意大的负值，“-M”。

在计算各列的检验数时，只要人工变量取值大于零，目标函数就不是最优。若最优解中，人工变量取值大于零，则原问题无可行解。第五节单纯形法的进一步讨论人工变量法：如果标准化后，系数矩阵128cj-30100-M-MCB基Bx1x2x3x4x5x6x70-M-Mx4x6x74191-201[1]31-111000-10010001σj-2M-34M10-M0000-Mx4x2x73163-2[6]0102-141001-13-11-3001σj6M-304M+103M-4M000-3x4x2x103100101001/3[2/3]100-1/201/21/20-1/2-1/21/31/6σj00303/2-M-3/2½-Mcj-30100-M-MCB基Bx1x2x3x4x5x6x71292两阶段法:相当于ci’=ci/M为了解决计算机求解时“M”的取值的麻烦（1）先求目标函数中只包含人工变量的线形规划，他们的价值系数为-1。当人工变量取值为零，目标函数值也为零。此时的最优解是原问题的基可行解。

若最优解的目标函数值不为零，则原问题无可行解。（2）若有可行解，则在原问题中除去人工变量，恢复原来的价值系数，继续寻找。2两阶段法:相当于ci’=ci/M为了解决计算机求解时130cj00000-1-1CB基Bx1x2x3x4x5x6x70-1-1x4x6x74191-201[1]31-111000-10010001σj-2400-10000-1x4x2x73163-2[6]0102-141001-13-11-3001σj60403-40000x4x2x103100101001/32/3100-1/201/21/20-1/2-½1/31/6σj00000-1-1cj00000-1-1CB基Bx1x2x3x4x5x6x70131恢复