管理运筹学教案1-绪论及线性规划模型复习过程

管理运筹学教案1-绪论及线性规划模型大西洋反潜战（1942年）

应英国要求，美国派MORSE率领一个小组去协助。MORSE经过多方实地考察，最后提出了两条重要建议：将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由100米左右改为25米左右。即当潜艇刚下潜时攻击效果最佳。(提高效率4-7倍)运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（25%下降到10%）丘吉尔采纳了MORSE的建议，最终成功地打破封锁，并重创了德国潜艇。MORSE同时获得英国和美国的最高勋章。6/10/20262管理运筹学课程组英国战斗机中队援法决策（40年代）第二次世界大战后，德国军队突破了法国的马奇诺防线，法军节节败退。英国为了对抗德国，派遣了十几个战斗机中队，在法国上空与德国军队作战，并且指挥、维护均在法国进行。英国运筹人员得知此事后，进行了一项研究，其结果表明：在当时情况下，当损失率、补充率为现行水平时，仅仅再进行两周时间左右，英国的援法战斗机就连一架也不存在了。运筹学家以简明的图表、明确的分析结果说服了丘吉尔，丘吉尔最终决定：不仅不再增加新的战斗机中队，而且还将在法国的英国战斗机中队大部分撤回英国本土，以本土为基地，继续对抗德国。局面有了很大的改观。6/10/20263管理运筹学课程组重要事件:古代朴素的运筹思想1917年爱尔朗的排队论公式。1939年英国成立第一个运筹学工作小组，从事防空预警系统的研制（研究如何合理运用雷达），使原先平均击落一架敌机要发2万发炮弹改善为只要发4千发炮弹。1939年前苏联的康托洛维奇提出类似线性规划模型，1960年《最佳资源利用的经济计算》,获诺贝尔奖。1942年美国成立运筹学工作小组,研究战斗行动效能,行动方式。1947年美国数学家，提出线性规划模型及单纯形算法战争结束，Mores和Kimball合著第一部专著“运筹学的方法”。战后，运筹学的应用领域从军事扩展到其它各领域。6/10/20264管理运筹学课程组学会组织1948年英国成立运筹学学会

1952年美国成立运筹学学会

1956年法国成立运筹学学会

1959年英、美、法成立运筹学联合会

我国50年代引入运筹学，1982年加入世界运筹学联合会(1956年时曾使用“运用学”，57年定名为“运筹学”)6/10/20265管理运筹学课程组§2运筹学的性质和内容

由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。——钱学森

运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物资、资金等大型系统的指挥或管理中所出现的复杂问题的一门学科。其目的是“帮助管理者以科学方法确定其方针和行动”——英国运筹学会

运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。——近代运筹学工作者1.运筹学的定义

“运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。”——P.M.Morse与G.E.Kimball6/10/20266管理运筹学课程组2.特点(1)运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，故其应用不受行业、部门之限制；(2)运筹学既对各种经营进行创造性的科学研究，又涉及到组织的实际管理问题，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效；(3)它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解，寻求最佳的行动方案，所以它也可看成是一门优化技术，提供的是解决各类问题的优化方法。6/10/20267管理运筹学课程组规划论——线性规划、目标规划、非线性规划、

整数规划、动态规划、组合规划等

图与网络存储论排队论

对策论决策论仿真

·马尔科夫过程·可靠性多目标规划

6/10/20268管理运筹学课程组§3运筹学的工作步骤

1.提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；

2.建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来；3.求解。用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出；

4.解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题； 5.解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。6/10/20269管理运筹学课程组§4本课程的要求本课程的授课对象是管理科学与工程类及交通运输类专业本科生，属管理类专业技术基础必修课。

学生通过学习该课程，应了解管理运筹学对优化决策问题进行定量研究的特点，理解线性规划、整数规划、动态规划、图与网络、排队论等分支的基本优化原理，掌握其中常用的模型和算法，具有一定的建模能力。

先修课程主要为线性代数和概率统计，学生对它们的掌握程度直接影响本课程的学习，所以要求学生课前要做必要的复习。

学习方法：理解、掌握基本理论和方法的基础上，适当作些习题。

参考书：其他版本的《管理运筹学》

6/10/202610管理运筹学课程组二.线性规划(LP)

(LinearProgramming)本部分是课程的最重要部分§1线性规划问题及其数学模型第一章线性规划与单纯形法6/10/202612管理运筹学课程组1.1问题的提出例1．某工厂计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时和A、B两种原材料的消耗、以及可获利润如表所示，问应如何安排计划使该工厂获利最多？6/10/202613管理运筹学课程组利润最大目标函数maxz=2x1+3x26/10/202614管理运筹学课程组例2:某工厂用钢与橡胶生产3种产品A、B、C，有关资料如下表404524332231ABC单位产品利润单位产品橡胶量单位产品钢消耗量产品已知每天可获得100单位的钢和120单位橡胶，问每天生产A、B、C各多少使总利润最大？解：设x1，x2，x3分别为A、B、C日产量，则有

约束条件2x1+3x2+x3≤100

3x1+3x2+2x3≤120

x1≥0，x2≥0，x3≥0称x1，x2，x3≥0为决策变量

目标函数：maxz=40x1+45x2+24x36/10/202615管理运筹学课程组2万m31.4万m36/10/202616管理运筹学课程组2万m31.4万m36/10/202617管理运筹学课程组6/10/202618管理运筹学课程组6/10/202619管理运筹学课程组6/10/202620管理运筹学课程组6/10/202621管理运筹学课程组x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q24.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。

解法：6/10/202622管理运筹学课程组线性规划问题解的存在情况：(1)存在唯一最优解x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例16/10/202623管理运筹学课程组（2）有无穷多最优解

若将例1目标函数变为maxz=2x1+4x2，则问题变得存在无穷多最优解。如图x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=03Q26/10/202624管理运筹学课程组（3）有无界解(无有限最优解或无最优解)

z（4）无可行解（可行域为空集）注意：没有存在有限多个解的情况可行域有界时必有最优解，无界时不一定无最优解6/10/202625管理运筹学课程组用图解法求下面问题的解12无界不可行6/10/202626管理运筹学课程组1．3线性规划问题的标准形式

为了求解LP问题，必须统一其模型，本课程选用标准型式为maxz=c1x1+c2x2+···+cnxn (1.1)s.t.a11x1+a12x2+···+a1nxn=b1

a21x1+a22x2+···+a2nxn=b2······(1.2)

am1x1+am2x2+···+amnxn=bm

x1，x2，···，xn

0(1.3)其中bi

0，（i=1，2，···，m）一般m<n；m，n>0。6/10/202627管理运筹学课程组标准型的简写形式:maxz=c1x1+c2x2+···+cnxn (1.1)s.t.a11x1+a12x2+···+a1nxn=b1

a21x1+a22x2+···+a2nxn=b2······(1.2)

am1x1+am2x2+···+amnxn=bm

x1，x2，···，xn

0(1.3)用求和符号表示6/10/202628管理运筹学课程组用矩阵描述为：

maxz=CXAX=b X

0=(P1，P2，···，Pn)；a11

…

a12…a1na21

…

a22…a2n……am1

…

am2…amnA=称A为约束条件的m

×n阶系数矩阵，一般A的秩为m。0=00…06/10/202629管理运筹学课程组用向量表示：X=x1x2…xnPj=a1ja2j…amjb=b1b2…bm向量Pj对应的决策变量为xj。6/10/202630管理运筹学课程组b1

b2

bm

(p1,p2,…,pn)ΣPjxj=b

a11a12

…a1n

a21a22…a2n

………

am1am2

…amn

x1

x2

xn

=xj≥0j=1,…,nx1

x2

xn

Maxz=x1

x2

xn

(c1,c2,…,cn)=Σcjxj=CX=Σaijxj=bi

i=1,…,mAX=bX

≥0

b6/10/202631管理运筹学课程组6/10/202632管理运筹学课程组

x1+2x2

84x1

164x2

12x1，x2

0

maxz=2x1+3x2+0x3+0x4+0x5标准型：例3．将例1的数学模型化为标准型。

maxz=2x1+3x2

所加松弛变量x3，x4，x5表示没有被利用的资源，当然也没有利润，在目标函数中其系数应为零；即c3，c4，c5=0。

x1+2x2+x3=84x1+x4=164x2+x5

=12x1，x2，x3，x4，x5

06/10/202633管理运筹学课程组

x1+x2+x3

7x1

–x2+x3

2–3x1+x2+2x3=5x1，x2

0，x3为无符号约束例4．将下述线性规划问题化为标准型

minz=–x1+2x2–3x3解：用x4-x5

替换x3

，令z’=-z

x1+x2+(x4-x5)+x6=7x1

–x2+(x4-x5)-x7=2–3x1

+x2+2(x4-x5)=5x1，x2，x4，x5，x6，x7

0maxz’=x1–2x2+

3(x4-x5)+0x6+0x7用标准型求最优解后，再回到原变量。6/10/202634管理运筹学课程组复习线性代数内容:列向量x=(x1，x2，…，xn）T为n维列向量。xRn行向量x=(x1，x2，…，xn）为n维列向量。xRn矩阵(向量)运算规则加减乘、求逆运算

结合律分配律交换律乘法无交换律线性相关一组向量v1,…,vn,如果有一组不全为零的系数α1,…,αn,使得:α1v1+…+αnvn=0

则称v1,…,v