《管理运筹学》复习提纲Word文档格式.doc
《《管理运筹学》复习提纲Word文档格式.doc》由会员分享，可在线阅读，更多相关《《管理运筹学》复习提纲Word文档格式.doc（38页珍藏版）》请在冰点文库上搜索。
如何在保证生产的条件下，下料最少；
配料问题：
在原料供应量的限制下如何获取最大利润；
投资问题：
从投资项目中选取方案，使投资回报最大；
产品生产计划：
合理利用人力、物力、财力等，使获利最大；
劳动力安排：
用最少的劳动力来满足工作的需要；
运输问题：
如何制定调运方案，使总运费最小。
2.线性规划的组成
目标函数：
maxf或minf；
约束条件：
s.t.（subjectto），满足于；
决策变量：
用符号来表示可控制的因素。
3.建模过程
（1）理解要解决的问题，明确在什么条件下，要追求什么目标。
（2）定义决策变量（x1，x2，…，xn），每一组值表示一个方案。
（3）用决策变量的线性函数形式写出目标函数，确定最大化或最小化
目标。
（4）用一组决策变量的等式或不等式表示解决问题过程中必须遵循的
约束条件。
一般形式
目标函数：
max（min）z=c1x1+c2x2+…+cnxn
约束条件：
s.t.
a11x1+a12x2+…+a1nxn≤（=,≥）b1
a21x1+a22x2+…+a2nxn≤（=,≥）b2
……
am1x1+am2x2+…+amnxn≤（=,≥）bm
x1，x2，…，xn≥0
对于只包含两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示
线性规划问题的有关概念，并求解。
下面通过例1详细介绍图解法的解题过程
取各约束条件的公共部分（如图2-1（f）
所示）。
目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，
直线上的每一点都具有相同的目标函数值，称之为“等值线”。
平行移动
等值线，当移动到B点时，z在可行域内实现了最大化。
A、B、C、D、E
是可行域的顶点，有限个约束条件其可行域的顶点也是有限的。
线性规划的标准化内容之一—引入松弛变量（资源的剩余量）
例1中引入s1，s2，s3，模型变化为：
4.重要结论
—如果线性规划有最优解，则一定有一个可行域的顶点对应一个最
优解；
—无穷多个最优解。
若将例1中的目标函数变为maxz=50x1+50x2，
则线段BC上的所有点都代表了最优解；
—无界解。
即可行域的范围延伸到无穷远，目标函数值可以无穷大
或无穷小。
一般来说，这说明模型有错，忽略了一些必要的约束
条件；
—无可行解。
若在例1的数学模型中再增加一个约束条件4x1+3x2
≥1200，则可行域为空域，不存在满足约束条件的解，当然也就
不存在最优解了。
5.线性规划的标准化
6.线性规划的标准形式有四个特点：
—目标最大化；
—约束为等式；
—决策变量均非负；
—右端项非负。
对于各种非标准形式的线性规划问题，我们总可以通过变换，将其转
化为标准形式。
7.为了使约束由不等式成为等式而引进的变量s，当不等式为“小于等
于”时称为“松弛变量”；
当不等式为“大于等于”时称为“剩余变量”。
如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各
个约束引进不同的松弛变量或剩余变量。
8.
9.灵敏度分析：
在建立数学模型和求得最优解之后，研究线性规划的一
个或多个参数（系数）ci,aij,bj变化时，对最优解产生的影响。
一、目标函数中的系数ci的灵敏度分析
二、约束条件中常数项bj的灵敏度分析
当约束条件中常数项bj变化时，线性规划的可行域发生变化，可能
引起最优解的变化。
A.考虑例1的情况：
假设设备台时增加10个台时，即b1变化为310，这时可行域扩大，
最优解为x2=250和x1+x2=310的交点x1=60，x2=250。
变化后的总利润−变化前的总利润=增加的利润
（50×
60+100×
250）−（50×
50+100×
250）=500，500/10=50（元）
说明在一定范围内每增加（或减少）1个台时的设备能力就可增加（或
减少）50元利润，这称为该约束条件的对偶价格。
B.假设原料A增加10千克，即b2变化为410，这时可行域扩大，但最
优解仍为x2=250和x1+x2=300的交点x1=50，x2=250。
此变化对总利
润无影响，该约束条件的对偶价格为0。
解释：
原最优解没有把原料A用尽，有50千克的剩余，因此增加10
千克只增加了库存，而不会增加利润。
在一定范围内，当约束条件中常数项增加1个单位时，
（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善
（变好）；
（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响
（变坏）；
（3）若约束条件的对偶价格等于0，则其最优目标函数值不变。
课本重点习题：
P23-26习题1268
第三章线性规划问题的计算机求解（P27-P38）
1.随书软件为“管理运筹学”2.5版（Windows版），是“管理运筹学”2.0版（Windows版）的升级版。
它包括：
线性规划、运输
2.问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。
3.“管理运筹学”软件的输出信息分析
当有多个系数变化时，需要进一步讨论。
百分之一百法则：
对于所有变化的目标函数决策系数（约束条件右端
常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过
100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）。
在使用百分之一百法则进行灵敏度分析时，要注意以下几方面。
（1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减
少量），其允许增加（减少）百分比均看作零。
（2）百分之一百法则是充分条件，但非必要条件；
也就是说超过100%，
最优解或对偶价格并不一定变化。
（3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边
常数值同时变化的情况。
这种情况下，只能重新求解。
在松弛/剩余变量栏中，约束条件2的值为125，它表示对原料A的最低需求，即对A的剩余变量值为125；
同理可知约束条件1的剩余变量值为0；
约束条件3的松弛变量值为0。
在对偶价格栏中，约束条件3的对偶价格为1万元，也就是说如果把加工时数从600小时增加到601小时，则总成本将得到改进，由800万元减少到799万元。
也可知约束条件1的对偶条件为-4万元，也就是说如果把购进原料A和B的总量下限从350t增加到351t，那么总成本将增加，由800万元增加到804万元。
当然如果减少对原料A
和B的总量的下限，那么总成本将得到改进。
在常数项范围一栏中，知道当约束条件1的常数项在300到475范围内变化，且其他约束条件不变时，约束条件1的对偶价格不变，仍为-4；
当约束条件2的常数项在负无穷到250范围内变化，且其他约束条件的常数项不变时，约束条件2的对偶价格不变，仍为0；
当约束条件3的常数项在475到700范围内变化，且其他约束条件的常数项
不变时，约束条件3的对偶价格不变，仍为1。
3.注意
（1）当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称为影子价格。
在求目标函数最大值时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，此时影子价格等于对偶价格；
在求目标函数最小值时，改进的数量就是减少的数量，此时影子价格即为负的对偶价格。
（2）管理运筹学”软件可以解决含有100个变量50个约束方程的线性规划问题，可以解决工商管理中大量的问题。
如果想要解决更大的线性规划问题，可以使用由芝加哥大学的L.E.Schrage开发的LINDO计算机软件包的微型计算机版本LINDO/PC。
P34-38习题1234
第四章线性规划在工商管理中的应用（P39-P66）
包括：
人力资源分配的问题生产计划的问题套裁下料问题
配料问题投资问题
§
1人力资源分配问题
例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数
如表4-1所示。
设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，
问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又使配备最
少司机和乘务人员的人数最少？
例2．一家中型的百货商场对售货员的需求经过统计分析如表4-2所
示。
为了保证售货员充分休息，要求售货员每周工作五天，休息两天，并
要求休息的两天是连续的。
问应该如何安排售货员的休息日期，既满足工
作需要，又使配备的售货员的人数最少？
2生产计划的问题
例3．某公司面临一个是外包协作还是自行生产的问题。
该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三道工序。
甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。
数据如表4-3所示。
问：
公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？
甲、乙两种产品的铸造中，由本公司铸造和外包协作各应多少件？
解：
设x1，x2，x3分别为三道工序都由本公司加工的甲、乙、丙三
种产品的件数，x4,x5分别为由外包协作铸造再由本公司进行机械加工和
装配的甲、乙两种产品的件数。
每件产品的利润如下：
可得到xi（i=1,2,3,4,5）的利润分别为15元、10元、7元、13元、
9元。
*该公司的最大利润为29400元
*最优的生产计划为全部由自己生产的产品甲1600件，铸造工序外包
而其余工序自行生产的产品乙600件。
例4．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。
设
有两种规格的设备A1、A2能完成A工序；
有三种规格的设备B1、B2、B3能完成B工
序。
产品Ⅰ可在A、B的任何规格的设备上加工；
产品Ⅱ可在工序A的任何一种规格
的设备上加工，但对B工序，只能在B1设备上加工；
产品Ⅲ只能在A2与B2设备上
加工。
数据如表4-4所示。
为使该厂获得最大利润，应如何制定产品加工方案？
设xijk表示第i种产品，在第j种工序上的第k种设备上加工的数
量。
建立如下的数学模型。
目标函数为计算利润最大化，利润的计算公式为：
利润=[（销售单价−原料单价）×
产品件数]之和−（每台时的
设备费用×
设备实际使用的总台时数）之和。
这样得到目标函数：
max（1.25−0.25）（x111+x112）+（2−0.35）（x211+x212）+（2.80−0.5）x312–
300/6000（5x111+10x211）-321/10000（7x112+9x212+12x312）-
250/4000（6x121+8x221）-783/7000（4x122+11x322）-200/4000（7x123）.
经整理可得：
max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-
0.5x221-0.4474x122-1.2304x322-0.35x123
*该厂的最大利润为1146.6005元。
4套裁下料问题
例5.某工厂要做100套钢架，每套用长为2.9m，2.1m，1.5m的圆钢各一根。
已知原料每根长7.4m，问：
应如何下料，可使所用原料最省？
解：
共可设计下列8种下料方案，如表4-5所示。
设x1,x2,x3,x4,x5,x6,x7,x8分别为上面8种方案下料的原材料根数。
这样我们建立如
下的数学模型。
用管理运筹学软件计算得出最优下料方案：
按方案1下料30根；
按
方案2下料10根；
按方案4下料50根。
即：
x1=30;
x2=10；
x3=0；
x4=50；
x5=0；
x6=x7=x8=0
只需90根原材料就可制造出100套钢架。
注意：
在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。
因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。
如果用等于号，这一方案就不是可行解了。
若可能的下料方案太多，可以先设计出较好的几个下料方案。
首先要求每个方案下料后的料头较短；
其次方案总体能裁下所有各种规格的圆钢，且不同方案有着不同的各种所需圆钢的比。
这样套裁即使不是最优解，也是次优解，也能满足要求并达到省料目的。
如我们用前5种下料方案供套裁用，进行建模求解，也可得到上述最优解。
5配料问题
例6．某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如表4-6和表4-7所示。
该厂应如何安排生产，使利润最大？
设xij表示第i种（甲、乙、丙）产品中原料j的含量。
这样我们建立数学模型时，要考虑：
对于甲：
x11，x12，x13；
对于乙：
x21，x22，x23；
对于丙：
x31，x32，x33；
对于原料1：
x11，x21，x31；
对于原料2：
x12，x22，x32；
对于原料3：
x13，x23，x33；
利润最大，利润=收入−原料支出
规格要求4个；
供应量限制3个。
利润=总收入-总成本=甲、乙、丙三种产品的销售单价×
产品数量−
甲、乙、丙使用的原料单价×
原料数量。
故有：
从表4-6中可知
x11≥0.5（x11+x12+x13）
x12≤0.25（x11+x12+x13）
x21≥0.25（x21+x22+x23）
x22≤0.5（x21+x22+x23）
从表4-7中可知，生产甲、乙、丙的原材料不能超过原材料的供应限额，故有
x11+x21+x31≤100
x12+x22+x32≤100
x13+x23+x33≤60
通过整理，得到以下模型：
maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33
线性规划的计算机解为x11=100，x12=50，x13=50，其余的xij=0，
也就是说每天只生产产品甲200kg，分别需要用第1种原料100kg，第2种原料50kg，第3种原料50kg。
6投资问题
例9某部门现有资金200万元，今后五年内考虑给以下的项目投资。
项目A：
从第一年到第五年每年年初都可投资，当年末能收回本利110%；
项目B：
从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；
项目C：
第三年年初需要投资，第五年末能收回本利140%，但规定最
大投资额不能超过80万元；
项目D：
第二年年初需要投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。
据测定每次投资1万元的风险指数如右表4-10所示：
（1）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本利金额最大？
（2）应如何确定这些项目每年的投资额，使得第五年年末拥有资金的本利在330万元的基础上总的风险系数最小？
②所设变量与问题①相同，目标函数为风险最小，有
minf=x11+x21+x31+x41+x51+3（x12+x22+x32+x42）+4x33+5.5x24
在问题①的约束条件中加上“第五年末拥有资金本利在330万元”的条件，于是模型如下。
minf=（x11+x21+x31+x41+x51）+3（x12+x22+x32+x42）+4x33+5.5x24
s.t.x11+x12=200
x21+x22+x24=1.1x11；
x31+x32+x33=1.1x21+1.25x12；
x41+x42=1.1x31+1.25x22；
x51=1.1x41+1.25x32；
xi2≤30（i=1，2，3，4），x33≤80，x24≤100
1.1x51+1.25x42+1.4x33+1.55x24≥330
xij≥0（i=1，2，3，4，5；
j=1、2、3、4）
运用“管理运筹学”软件求得此问题的解为：
x5A=33.5，x4B=30，x3C=80，x2D=100，
x1A=170，x1B=30，x2A=57，x2B=30，
x3A=0，x3B=20.2，x4A=7.5。
P57-61习题13456
第七章运输问题（P126-P162）
1运输模型
例1.某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表7-1所示，问：
应如何调运可使总运输费用最小？
一般运输问题的线性规划模型：
产销平衡
A1、A2、…、Am表示某物资的m个产地；
B1、B2、…、Bn表示某物质的n个销地；
si表示产地Ai的产量；
dj表示销地Bj的销量；
cij表示把物资从产地Ai运往销地Bj的单位运价。
设xij为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：
变化：
（1）有时目标函数求最大。
如求利润最大或营业额最大等。
（2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束）。
（3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。
2运输问题的计算机求解
例2.某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表7-3所示，问：
增加一个虚设的销地运输费用为0。
例3.某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表7-5所示，问：
增加一个虚设的产地运输费用为0。
3运输问题的应用
4运输问题的表上作业法
1、数学模型
在物流调运问题中，如何根据已有的交通网，制定调运方案，将货物运到各需求地，而使总运费最小，是很关键的问题。
这类问题可用如下数学语言描述。
已知有m个生产地点Ai（i=1，2…m），可供应某种物质，其供应量分别为：
ai（i=1，2，3，…m），有n个销地（需要地）Bj（j=1，2…n），其需求量分别为bj（j=1，2，…n），从Ai到Bj运输单位物资的运价为Cij。
这些数据可汇总于产销平衡表和单位运价表中，如表7-1、表7-2所示。
表7-1产销平衡表
销地
产地
1，2……n
产量
1
a1
2
a2
┆
m
am
销量
b1，b2…bn
表7-2单位运价表
…
n
C11
C12
C1n
C21
C22
C2n
Cm1
Cm2
Cmn
为了制定使总运费最小的调运方案，我们可以建立数学模型。
如果我们设Xij表示由产地Ai供应给销地的运量，则运输问题的线性规划模型可分为三种情况：
（1）产销平衡，即在的情况下，求（总费用最少）。
满足约束条件：
1，2，…，n）（满足各销地的需要量）
1，2，…，m）（各产地的发出量等于各地产量）
Xij≥0（i=1，2，…，m；
j=1，2，…，n）（调出量不能为负数）
（2）产大于销，即在＞的情况下，求（总费用最少）。
1，2，…，n）
≤ai（i=1，2，…，m）
j=1，2，…，n）
（3）销大于产，即在＜的情况下，求（总费用最少）。
≤bj（j=1，2，…，n）
=a
升级会员 