CHAPTER 1 LP(1).ppt

第一讲 线性规划(Linear Programming,LP),概 述,线性规划问题的提出最早是1939年由前苏联数学家康托洛维奇在研究铁路运输的组织问题、工业生产的管理问题时提出来的。1947年，美国学者丹西格（G.B.Dantzig）提出了线性规划问题的单纯形方法。线性规划理论最为成熟、应用最为广泛,第一节 线性规划问题及其数学模型,一、问题提出例1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？,决策变量：x1、x2分别代表甲、乙两种产品的生产数量。目标函数：max z=50 x1+100 x2约束条件：x1+x2300 2x1+x2400 x2250即有：max z=50 x1+100 x2 x1+x2300 2x1+x2400 x2250 x1、x20称之为上述问题的数学模型。,例2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小.,决策变量：x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。则目标函数：min z=1000 x1+800 x2约束条件：第一段河流（工厂1工厂2之间）：(2x1)/500 0.2%第二段河流：0.8(2x1)+(1.4x2)/7000.2%此外有：x12；x21.4化简有：min z=1000 x1+800 x2 x1 1 0.8x1+x2 1.6 x1 2 x21.4 x1、x20称之为上述问题的数学模型。,从上述两个例子，我们可以总结出线性规划的数学模型的一般形式。max(min)z=c1x1+c2x2+cnxn 目标函数 a11x1+a12x2+a1nxn=(,)b1 a21x1+a22x2+a2nxn=(,)b2 约束条件 am1x1+am2x2+amnxn=(,)bm x1，x2，xn0模型特点：目标函数(Objective function)与约束条件(Constraint)均为线性的；目标函数实现极大化或极小化。,第二节 线性规划图解法(Graphical Solution),一、基本概念可行解(Feasible Solution)任一满足约束条件的一组决策变量的数值；可行域(Feasible Region)所有可行解组成的集合，也称为可行解集；目标函数等值线(Objective function line)为于同一直线上的点，具有相同的目标函数值；二、图解法步骤(Procedure)（1）画出线性规划问题的可行域；（2）画出两条目标函数等值线；（3）平行移动目标函数等值线，使目标函数在可行域范围内达到最优。,三、图解法举例,例1 max Z=50 x1+100 x2 x1+x2300 2x1+x2400 x2250 x1、x20,该问题有唯一最优解x1=50；x2=250,例2 max Z=50 x1+50 x2 x1+x2300 2x1+x2400 x2250 x1、x20,B点和C点所代表的坐标同时为最优解，即该问题有无穷多最优解,max Z=50 x1+100 x2,例3 max z=x1+x2 x1x2 1 x1+2x20 x1、x20 问题有无界解(unbounded)例4 min z=x1+x2 x1x2 1 x1+2x20 x1、x20 有唯一最优解,例4 max z=x1+x2 x1+2x21 x1+x22 x1、x20 问题无可行解(no feasible solution),直 观 结 论,可行域可以是个凸多边形，可能无界，也可能为空；若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到；若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解；若可行域非空有界，则一定有最优解。,四、线性规划问题的标准形式(Standard form),规定如下形式的线性规划数学模型为LP标准形式。max z=c1x1+c2x2+cnxn 目标函数 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 约束条件 am1x1+am2x2+amnxn=bm x1，x2，xn0特点：Zmax；约束条件为等号；变量非负；右端常数项大等于零。问题：n m why？,上述标准形式的线性规划模型还可写成如下一些形式:,(1)(2),(3),(5),(4),五、化非标准形为标准形,（1）若min f=cX此时可令：z=f，则max z=min f=cX，这样处理所得最优解不变；举例：min z=x1x2 2x1+x22 x1+x21 x1、x20 max f=x1+x2,(2)约束条件为“”时，aijxjbi aijxj+xn+i=bi xn+i 松弛变量(slack variable)；(3)约束条件为“”时，aijxj bi aijxj xn+i=bi xn+i 过剩变量(surplus variable)；这样处理所得最优解不变；max z=x1+10 x2 x1+2x2100 x1、x20,max z=x1+10 x2 x1+2x2+x3=100 x1、x20,（4）若xk为无限制，则令xk=xk1xk2，其中xk1、xk20（5）若bi 0举例:化下列线性规划为标准形 max z=2x1+2x24x3 x1+3x23x3 30 x1+2x24x380 x1、x20，x3无限制,max z=2x1+2x24x3+4x3”x1+3x23x3+3x3”x4=30 x1+2x24x3+4x3”+x5=80 x1、x2、x3、x3”、x4、x5 0,第三节 线性规划的计算机求解(Computer Solution for LP),一、用计算机求解下列线性规划问题max z=50 x1+100 x2 x1+x2=300 2x1+x2=400 x2=250 x1、x20,二、派公司生产计划问题的LP模型与计算机求解 派公司计划生产高中价位的高尔夫袋。生产过程为：1.切割并印染原材料；2.缝合；3.成型；4.检查和包装。各过程单位用时、总用时及产品单位利润如下表：如何生产使公司利润最大？,解：很显然，若设x1、x2分别代表标准袋和高档袋的生产数量,则问题的数学模型为：max z=10 x1+9x2 7/10 x1+x2=630 1/2 x1+5/6 x2=600 x1+2/3 x2=708 1/10 x1+1/4 x2=135 x1、x20,三、M&D公司问题问题描述:M&D公司生产两种产品A和B，根据现有库存水平和下个月的购买潜力分析，M&D管理层确定A和B的总产量至少达到350加仑。此外公司的一个主要客户订购了125加仑的产品A，该产量必须满足。产品A和产品B的制造时间分别是2小时/加仑和1小时/加仑，下个月的总工作时间是600小时。公司的目标是在满足客户要求的前提下，尽量降低成本。每加仑A的制造成本是2美元，每加仑B的制造成本是3美元。,很显然，若设x1、x2分别代产品A和产品B的生产数量,则问题的数学模型为：min z=2x1+3x2 x1=125 x1+x2=350 2x1+x2=600 x1、x20,第四节 对偶问题(Dual Problem),线性规划早期发展过程中的最为重要的理论成果之一就是线性规划的对偶问题及相关理论的提出。线性规划的对偶理论解释资源的影子价格、线性规划问题的敏度分析等的理论基础。,一、对偶问题的提出,例1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？,决策变量：x1、x2分别代表甲、乙两种产品的生产数量。即有数学模型（问题A）：问题A max z=50 x1+100 x2 x1+x2300 2x1+x2400 x2250 x1、x20称之为上述问题的数学模型。同样是上述问题，提问：企业不安排生产，而转让三种资源，应如何给三种资源定价？,决策变量：y1、y2、y3分别代表A、B、C三种资源的价格（最低转让净收入）。约束条件1：生产一件产品甲所耗资源数量转让所得净收入不能低于一 件产品甲所获利润，即：1y1+2y2 50约束条件2：生产一件产品乙所耗资源数量转让所得净收入不能低于一 件产品乙所获利润，即：1y1+1y2+1y3 100目标函数为：w=300y1+400y2+250y3即有 w=300y1+400y2+250y3 y1+2y2 50 y1+y2+y3 100 y1、y2、y3 0,从数学和经济的角度分析，该问题的目标函数只能极小，即该问题的数 学模型为：问题B min w=300y1+400y2+250y3 y1+2y2 50 y1+y2+y3 100 y1、y2、y3 0称问题B为问题A的对偶问题，问题A为原问题。问题A max z=50 x1+100 x2 x1+x2300 2x1+x2400 x2250 x1、x20,定义2.1 设有线性规划问题 max z=CX AXb X0其对偶问题定义为 min w=Yb YAC Y0且前者称为原问题，后者称为对偶问题。,二、对偶问题的定义,具体的数量对应关系为,原问题 max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1，x2，xn0对偶问题 min w=b1y1+b2y2+bmym a11y1+a21y2+am1ym c1 a12y1+a22y2+am2ym c2 a1ny1+a2ny2+amnym cn y1，y2，ym0,根据对偶问题的定义不难推出，对于线性规划问题：min w=Yb；YAC；Y0其对偶问题为：max z=CX；AXb；X0即两线性规划问题互为对偶。事实上，任一线性规划问题都有一个固定的线性规划问题与之对偶，且二者互为对偶关系，线性规划的这种性质称为对称性。更进一步有，对于线性规划问题：max z=CX；AX=b，X0其对偶问题为：min w=Yb；YAC，Y无限制,根据以上分析，线性规划原问题与对偶问题的数量关系可用下表描述。,例2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x24x3 x1+3x2+3x3 30 4x1+2x2+4x380 x1、x2，x30,解：其对偶问题为min w=30y1+80y2 y1+4y2 23y1+2y2 23y1+4y2 4 y1、y20,例2.2 写出下列线性规划问题的对偶问题 min z=2x1+8x24x3 x1+3x23x3 30 x1+5x2+4x3=80 4x1+2x24x350 x10、x20，x3无限制解：其对偶问题为,max w=30y1+80 y2+50 y3 y1 y2+4 y3 2 3y1+5y2+2y3 8 3y1+4y24y3=4 y10，y2无限制，y30,定理2.1(弱对偶定理)设X(0)是原问题max z=CX，AXb，X0的可行解 Y(0)是其对偶问题min w=Yb，YAC，Y0的可行解则 CX（0）Y（0）b。原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值?,三、对偶问题基本定理,定理2.2(最优性定理)设X(0)是原问题max z=CX，AXb，X0的可行解，Y（0）是其对偶问题min w=Yb，YAC，Y0的可行,若 CX（0）=Y（0）b，则 X（0）、Y（0）分别是它们的最优解。定理2.3(对偶定理)若原问题max z=CX，AXb，X0有最优解，则其对偶问题min w=Yb，YAC，Y0 一定有最优解，且二者的目标函数值相等。定理2.4(互补松弛定理)原问题max z=CX，AXb，X0及其对偶问题min w=Yb，YAC，Y0 的可行解X（0）、Y（0）是最优解的充要条件是 Y（0）XS=0；YSX（0）=0 其中，XS、YS分别是原问题松弛变量向量和对偶问题剩余变量向量。,（一）资源的影子价格(Shadow Price)如前所述，若X*为线性规划max z=CX，AXb，X0的最优解，则z*=CX*；若Y*为其对偶问题的最优解，则有w*=Y*b。根据对偶定理有 z*=w*即 z*=Y*b 因此 即 由此可以看出，对偶问题的最优解实际上是右端常数项的单位变化所引起的目标值的变化；,四、对偶问题的经济意义,若原问题描述的是资源有限条件下最优生产决策问题，则其对偶问题的最优解yi*(i=1,，m)表示第i种资源在最优生产决策下的边际值，即若其他条件不变，增加单位第i种资源将会使目标函数值增加yi*。其经济意义是：yi*描述了第i种资源在具体生产中的一种估价，这种估价不同于该种资源的市场价格，而是该种资源在给定条件某生产的最优生产方案下的一种实际存在而又看不见的真实价值，因此称之为影子价格（shadow price）。,同一种资源在不同的生产条件或不同的范围可能有不同的影子价格；产品的市场价格变化，资源的影子价格也会发生变化；资源的数量结构不同，资源的影子价格也不同。,资源的影子价格是针对具体生产或具体企业而言的,与资源的市场价格比较以决定是否安排生产或转让资源或提高产品的价格；革新可以提高资源的影子价格；可以指导管理部门对紧缺资源进行“择优分配”；帮助预测产品的价格。因此，产品的价格应在“成本”和影子价格之间；影子价格的高低可以作为同类企业经济效益的评估标准之一。,影子价格对于拥有资源的决策者有非常重要的作用,对于目标函数极小化约束条件为大等号的问题 min z=CX，AXb，X0，其右端常数项可理解为需要完成的任务。因此，该类线性规划一般为描述完成一定任务使耗费的资源最小的问题。此时，其对偶问题的最优解yi*(i=1,，m)表示第i种任务的边际成本，即单位任务的增加引起的资源耗费的增加量。,（二）任务的边际成本(Marginal Cost),M&D公司生产两种产品A和B，根据现有库存水平和下个月的购买潜力分析，M&D管理层确定A和B的总产量至少达到350加仑。此外公司的一个主要客户订购了125加仑的产品A，该产量必须满足。产品A和产品B的制造时间分别是2小时/加仑和1小时/加仑，下个月的总工作时间是600小时。公司的目标是在满足客户要求的前提下，尽量降低成本。每加仑A的制造成本是2美元，每加仑B的制造成本是3美元。问题的线性规划模型为 min z=2x1+3x2 x1=125 x1+x2=350 2x1+x2=600 x1、x20,无论对偶问题的最优解表示的是资源的影子价格还是任务的边际成本，只要为正，则表示右端常数项增加目标函数值增加，为负则表示右端常数项增加目标函数值减少。而对于极大化的问题，目标函数值增加表明目标函数得到改善，对于极小化的问题，目标函数减少表明目标函数得到改善。为了二者的统一，定义如下对偶价格。,（三）对偶价格(Dual Price),定义2.2 线性规划问题某约束条件的右端常数项的单位增加量所引起的目标函数的改善量称为该右端常数项的对偶价格。因此，若对偶价格为正，则增加右端常数项，目标函数值得到改善；若对偶价格为负，则增加右端常数项，目标函数值将会“恶化”。,（三）对偶价格(Dual Price),第五节、灵敏度分析(Sensitivity Analysis),灵敏度分析就是分析aij、bi、cj等因素中的一个或几个的变化给生产决策带来的影响。灵敏度分析的内容是：aij、bi、cj中一个或几个发生某一具体变化时，线性规划问题的最优决策相应会发生什么样的变化；aij、bi、cj在什么范围内变化，线性规划问题的最优解或最优基不变；灵敏度分析一般是在已得到线性规划问题最优基的基础上进行的。,例（生产计划问题）某工厂在计划期内用资源A、B、C安排生产甲、乙两种产品，有关数据如下：,max z=5x1+4x2 x1+3x2=90 2x1+x2=80 x1+x2=45 x1、x2，x30,若x1、x2分别表示工厂生产甲、乙产品的数量，则使工厂获得最大利润的生产计划数学模型为：,该问题的计算机求解结果如下目标函数最优值为：215变量 最优解 检验数x1 35 0 x2 10 0约束 松弛/剩余变量 对偶价格1 25 02 0 13 0 3目标函数系数范围（最优解不变）变量 下限 当前值 上限x1 4 5 8x2 2.5 4 5右端常数项范围（对偶价格不变）约束 下限 当前值 上限1 65 90 无上限2 67.5 80 903 40 45 50,max z=5x1+4x2 x1+3x2=902x1+x2=80 x1+x2=45 x1、x2，x30,（一）、派公司的灵敏度分析 1、原问题计算机求解 派公司计划生产高中价位的高尔夫袋。生产过程为：1.切割并印染原材料；2.缝合；3.成型；4.检查和包装。各过程单位用时、总用时及产品单位利润如下表：如何生产使公司利润最大？,灵敏度分析与解答举例,解：很显然，若设S、D分别代表标准袋和高档袋的生产数量,则问题的数学模型为：max z=10S+9D 7/10 S+D=630 1/2 S+5/6 D=600 S+2/3 D=708 1/10 S+1/4 D=135 S、D0,2.对派公司问题的修改增加小型袋现管理层希望生产一种小巧的、击球者可以自己背着的高尔夫袋。设计部门计算后得出小型袋在各过程中所耗时间为：切割印染0.8h、缝合1h、成型1h、检验包装0.25h。单位利润：12.85美元/个；设L为小型袋的个数，则新的模型为：,max z=10S+9D+12.85L 7/10 S+D+0.8L=630 1/2 S+5/6 D+L=600 S+2/3 D+L=708 1/10 S+1/4 D+0.25L=135 S、D、L0,3.对派公司问题的修改增加约束条件现管理层无法接受高档袋为零的事实。于是就增加约束条件，即高档袋至少是标准袋的30%，于是有新的模型为：,max z=10S+9D+12.85L 7/10 S+D+0.8L=0 S、D、L0,灵敏度分析与解答举例,二、牧草农场问题极小化问题（P69）计算机求解与解释（科学管理的实际应用P77）三、电子通讯公司问题等式约束（P73），自己看,第六节 线性规划的应用(Applications of LP),线性规划是管理决策制定的最成功的数量方法之一。它广泛应用于化工、航空、钢铁、石油和其他工业。它研究的问题是多种多样的生产计划、媒体选择、金融计划、资金预算、运输、工厂选择、生产组合、人员调配等等。,例 红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？,一、人力资源分配问题,解：设x1为星期一开始上班的人数，x2为星期二开始上班的人数，x7星期日开始上班的人数。我们就可得到如下的数学模型：min x1+x2+x3+x4+x5+x6+x7x3+x4+x5+x6+x728x4+x5+x6+x7+x115x5+x6+x7+x1+x224x6+x7+x1+x2+x325x7+x1+x2+x3+x419x1+x2+x3+x4+x531x2+x3+x4+x5+x628x1、x2、x3、x4、x5、x6、x70该问题的最优解为：x1=8，x2=0，x3=12，x4=0，x5=11，x6=5，x7=0；目标函数的最小值为36。,例 某房地产开发公司正在建造一个湖边小区，公司准备投入3万元进行广告媒体宣传，希望能够吸引周围的中高收入家庭前来购房。目前有5种媒体可供选择，相关信息如表所示。,对于这次活动，公司有下列要求：至少进行10次电视广告；至少有5万名潜在顾客被告知；电视广告投入不超过18000元。如何进行媒体组合，才能使广告质量最高？,二、媒体选择,解 问题中媒体组合实际上就是要决定每种媒体的使用次数。设x1、x2、x3、x4、x5分别表示表中日间电视、夜间电视、日报、周末新闻杂志、电台广播五种媒体的使用次数。该问题的线性规划模型为 max z=65x1+90 x2+40 x3+60 x4+20 x5 1500 x1+3000 x2+400 x3+1000 x4+100 x5 300001000 x1+2000 x2+1500 x3+2500 x4+300 x5 50000 x1+x2 10 1500 x1+3000 x2 18000 x1 15 x2 10 x3 25 x4 4 x5 30 x1，x2，x3，x4，x50,这是一个有5个变量，9个约束条件的线性规划模型，求解结果如下：,目标函数最优值为：2370变量 最优解 检验数x1 10 0 x2 0 65x3 25 0 x4 2 0 x5 30 0约束 松弛/剩余变量 对偶价格1 0 0.062 11500 03 0 254 3000 05 5 06 10 07 0 168 2 09 0 14,包括：资本预算、资产分配、财政计划等（一）投资组合问题：从多种投资选择中选择具体的投资：股票和债券、基金、保险等；目标：预期收益极大化、风险最小化约束：投资类型、国家法律、公司政策、风险或效益限制等,三、财政应用,案例 Welte公司拥有100000美元，财务专家确定了如下5个投资机会，并预计了它们的年收益：1.在石油或钢铁行业投资不能超过50000每元；2.对政府债券的投资至少相当于对钢铁行业投资的25%；3.对太平洋石油的投资不能多于整个石油行业投资的60%求预期收益最大的投资方案。,设：Atl=大西洋石油投资；Pac=太平洋石油投资；Mid=中西部钢铁投资；Hub=Huber钢铁投资；Gov=政府债券投资则问题的数学模型为：Max z=0.073Atl+0.103Pac+0.064Mid+0.075Hub+0.045Gov Atl+Pac+Mid+Hub+Gov=100000 总投资 Atl+Pac 50000 石油投资限制 Mid+Hub 50000 钢铁投资限制-0.25Mid 0.25Hub+Gov 0 政府债券比例-0.6Atl+0.4Pac 0 太平洋石油限制 Atl,Pac,Mid,Hub,Gov 0,(二)、金融计划案例 某公司现有68名员工申请提前退休。公司必须在此后的8年内对这些员工分期支付一定数量的现金，如下表所示。,为了完成这项现金支付任务，公司的财务人员必须现在就为此制定一个投资计划。投资计划有政府债券投资和银行储蓄两种方式组成。,注意:三种政府债券的票面价值均为1000元，债券到期时按票面价值进行支付，利率的计算也以票面的价值为基准。银行储蓄年利率为4%。如何安排投资计划，使公司以最小的投资额完成对退休员工的现金支付任务？,政府债券投资有三种债券类型可供选择，如下表所示。,解：1确定决策变量设F为完成投资计划所需要的总资金额。x1、x2、x3分别表示债券1、2、3的购买量；yi(i=1,，8)表示第 i年初银行储蓄的投资额。2确定约束条件这类问题的一个典型特征就是每年现金支付的一般表达式为：年初可用资金额 当年用于债券和储蓄的资金额=当年现金支付于是有 F 1.15x1 1x2 1.35x3 y1=430（第1年）,对于第二年，用于三种债券投资的第一年利息加上第一年储蓄利息为年初可用资金，第二年用于储蓄的资金为y2，因此有 0.08875x1+0.055x2+0.1175x3+1.04y1 y2=210（第2年）同理对于其它年份有0.08875x1+0.055x2+0.1175x3+1.04y2 y3=222（第3年）0.08875x1+0.055x2+0.1175x3+1.04y3 y4=231（第4年）0.08875x1+0.055x2+0.1175x3+1.04y4 y5=240（第5年）1.08875x1+0.055x2+0.1175x3+1.04y5 y6=195（第6年）1.055x2+0.1175x3+1.04y6 y7=225（第7年）1.1175x3+1.04y7 y8=255（第8年）因此事实上，y8的值应为0，若大于0，那么对应的投资计划必定不是最优的。,3.确定目标函数目标就是使满足要求的投资额最小，即Minz=F综合有如下数学模型 Minz=FF 1.15x1 1x2 1.35x3 y1=430 0.08875x1+0.055x2+0.1175x3+1.04y1 y2=2100.08875x1+0.055x2+0.1175x3+1.04y2 y3=2220.08875x1+0.055x2+0.1175x3+1.04y3 y4=2310.08875x1+0.055x2+0.1175x3+1.04y4 y5=2401.08875x1+0.055x2+0.1175x3+1.04y5 y6=195 1.055x2+0.1175x3+1.04y6 y7=225 1.1175x3+1.04y7 y8=255 x1，x2，x30，yi0，i=1，8,该线性规划模型的求解结果为目标函数最优值为：1728.794变量 最优解 检验数F 1728.794 0 x1 144.988 0 x2 187.856 0 x3 228.188 0y1 636.148 0y2 501.606 0y3 349.682 0y4 182.681 0y5 0 0.064y6 0 0.0126y7 0 0.0213y8 0 0.671,即得到最佳投资计划如下表所示:,约束 松弛/剩余变量 对偶价格1 0 1.0002 0 0.9623 0 0.9254 0 0.8895 0 0.8556 0 0.7607 0 0.7198 0 0.671结果分析：前4年的储蓄额均大于0，可见从第6年起债券的利息和债券到期收入才能够完全满足当前现金支付需要。每一个约束条件的对偶价格均为负值，说明减少任何一年的现金支付都将有利于公司总投资额的降低。对偶价格的逐年降低也说明了，在前面年份减少现金支付将对总投资额的减少更为有效。从而暗示了公司可以适当减少前面年份的现金支付量，而在后面年份进行补足。,(一)制造或购买决策案例P98 某公司有，两种产品，预计两种产品的市场需求量分别为3000件和2000件。两种产品均由a、b、c三个部件组成，各部件生产消耗工时和自制/外购成本如下表所示。,四、生产管理应用,由于生产能力有限，公司只有200个正常制造工时和50个加班工时可用于这两种产品的生产。每个加班工时需额外支付9元。如何安排部件自制和外购的数量，从而使总成本（包括生产成本、外购成本和加工费用）最低？,解：1确定决策变量 设xa、xb1、xb2、xc1、xc2分别表示a部件、用于产品的b部件、用于产品的b部件、用于产品的c部件、用于产品 的c部件的自制量。相应地，设ya、yb1、yb2、yc1、yc2分别为各部件的外购量。设y0为加班工时数。2确定约束条件a部件的需求量约束 xa+ya=5000用于产品的b部件的需求量约束 xb1+yb1=3000用于产品的b部件的需求量约束 xb2+yb2=2000用于产品的c部件的需求量约束 xc1+yc1=3000用于产品的c部件的需求量约束 xc2+yc2=2000最大加班工时数约束 y050最大生产能力约束 xa+3xb1+2.5xb2+xc1+1.5xc2 20060+60 y0,3确定目标函数目标是使总成本最小，即Min z=0.5xa+0.6ya+3.75xb1+4yb1+3.3xb2+3.9yb2+0.6xc1+0.65yc1+0.75 xc2+0.78yc2+9y0因此，该问题的数学模型为Min z=0.5xa+0.6ya+3.75xb1+4yb1+3.3xb2+3.9yb2+0.6xc1+0.65yc1+0.75 xc2+0.78yc2+9y0 xa+ya=5000 xb1+yb1=3000 xb2+yb2=2000 xc1+yc1=3000 xc2+yc2=2000 y050 xa+3xb1+2.5xb2+xc1+1.5xc2 60 y012000 xa、xb1、xb2、xc1、xc2、yb1、yb2、yc1、yc2、y00,该线性规划模型的求解结果为目标函数最优值为：1728.794变量 最优解 检验数xa 5000 0.000ya 0 0.017xb1 667 0.000ybl 2333 0.000 xb2 2000 0.000yb2 0 0.392 xc1 0 0.033yc1 3000 0.000 xc2 0 0.095yc2 2000 0.000y0 0 4.000,约束 松弛/剩余变量 对偶价格1 0 0.5832 0 4.0003 0 3.5084 0 0.6505 0 0.7806 50 0.0007 0 0.083,目标函数系数范围变量 下限 当前值 上限xa 无下限 0.500 0.517ya 0.583 0.600 无上限xb1 3.700 3.750 3.850ybl 3.900 4.000 4.050 xb2 无下限 3.300 3.692yb2 3.508 3.900 无上限xc1 0.567 0.600 无上限yc1 无下限 0.650 0.683xc2 0.655 0.750 无上限yc2 无下限 0.780 0.875y0 5.000 9.000 无上限,右端常数项范围约束 下限 当前值 上限1 0.000 5000 70002 666.667 3000 无上限3 0.000 2000 28004 0.000 3000 无上限5 0.000 2000 无上限6 0.000 50 无上限7 10000.000 12000 19000,(二)生产计划问题生产计划问题是线性规划应用最为广泛的领域之一;问题描述:一定时期内，经理必须决定生产水平，使公司能够满足生产需求，在受到产品生产量、劳动力水平以及存储空间上所有限制的同时，还要使生产成本最小。线性规划解决该类问题的优点：可重复利用已建立好的线性规划模型指定不同时期的生产计划。,案例P100,Bollinger 电子公司接到未来三个月的两种产品的定单：生产部门分析，生产费用有以下方面：（1）生产成本；（2）库存储成本；（3）改变生产力水平所需费用。有关数据如下表,现要求制定一个未来3个月的生产计划，使总成本最小。,决策变量（能描述问题）：x1i=第i月生产322A的数量；i=1，2，3(四、五、六月)x2i=第i月生产802B的数量；i=1，2，3 s1i=第i月末322A的存储量；i=1，2，3 s2i=第i月末802B的存储量；i=1，2，3 Ii=第i月生产量增加量；i=1，2，3 Di=第i月生产量下降量；i=1，2，3 目标函数 min z=20 x11+20 x12+20 x13+10 x21+10 x22+10 x23+0.3s11+0.3s12+0.3s13+0.15s21+0.15s22+0.15s23+0.5I1+0.5I2+0.5I3+0.2D1+0.2D2+0.2D3,约束条件（1）需求约束 上月期末库存+本月生产量 本月期末库存=本月需求量第一个月：设期初库存为：322A：500；802B：200；这样有：500+x11-s11=1000 x11-s11=500 200+x21-s21=1000 x11-s11=800 第二个月 s11+x12 s12=3000 s21+x22 s22=500第三个月 s12+x13 s13=5000 s22+x23 s23=3000（2）期末库存量约束 s13 400;s23 200,(3)机器生产能力约束 0.1x11+0.08x21 400 第一个月 0.1x12+0.08x22 500 第二个月 0.1x13+0.08x23 600 第三个月(4)劳动力能力约束 0.05x11+0.07x21 300 第一个月 0.05x12+0.07x22 300 第二个月 0.05x13+0.07x23 300 第三个月(5)库存能力约束 2s11+3s21 10000 第一个月 2s12+3s22 10000 第二个月 2s13+3s23 10000 第三个月,(6)生产量变化约束 本月产量-上月产量=本月产量变化量四月份 x11+x21 2500=I1 D1 x11+x21 I1+D1=2500 五月份 x12+x22(x11+x21)=I2 D2 x12+x22(x11+x21)I2+D2=0 六月份 x13+x23(x12+x22)=I3 D3 x13+x23(x12+x22)I3+D3=0注意：这里的 Ii 和Di 均为非负变量，而且至少有一个为零。计算机求解结果：,（三）劳动力分配问题问题描述：一个企业有多个生产部门，一定时期各生产部门劳动力数量一定，但劳动力可以在各部门之间转移或再分配最佳的分配方案。案例P105（麦科米克公司劳动时间分配问题）,设P1,P2分别为产品1、2的产量，则问题的数学模型为：max z=10P1+9P2 0.65P1+0.95P26500 0.45P1+0.85P26000 1.00P1+0.70P27000 0.15P1+0.30P21400 P1、P20计算机求解结果目标函数最优值为：73589.744变量 最优解 检验数P1 5743.59 0P2 1794.87 0约束 松弛/剩余变量 对偶价格1 1061.583 02 1889.744 03 0 8.462 4 0 10.256,问题：若部门之间可利用时间可以调配，是否可以增加总利润？假设各部门之间交叉培训能力和可转移时间信息如下,引入新的决策变量：tij=从i部门转移到j部门的劳动时间 bi=分配给第i部门的劳动时间,这样，问题的约束条件如下：（1）生产能力约束 0.65P1+0.95P2 b10 0.45P1+0.85P2 b20 1.00P1+0.70P2 b30 0.15P1+0.30P2 b30（2）劳动时间平衡约束 分配到本部门的劳动时间=总可用时间+转入时间转出时间因此：b1=6500+t41-t12-t13 b2=6000+t12+t42-t23-t24 b3=7000+t13+t23-t34 b4=1400+t24+t34-t41-t42（3）最大转移时间约束 t12+t13 400 t34 100 t23+t24 800 t41+t42 200,b1-t41+t12+t13=6500b2-t12-t42+t23+t24=6000 b3-t13-t23+t34=7000 b4-t24-t34+t41+t42=1400,问题描述：当混合两种以上资源生产一种以上产品时，管理者必须决定每种资源的购买量以在成本最低的情况下满足产品的需要。应用领域：石油化工、食品行业等；案例P108（大绳石油公司混合问题）,六、混合问题,决策变量：,目标函数：Max Z=1（X1R+X2R+X3R）+1.08（X1P+X2P+X3P）-0.5（X1R+X1P）-0.6（X2R+X2P）-0.84（X3R+X3P）=0.5X1R+0.4X2R+0.16X3R+0.58X1P+0.48X2P+0.24X3P,约束条件：（1）供应量约束 X1R+X1P 5000 X2R+X2P10000 X3R+X3P10000（2）比例约束 X1R/（X1R+X2R+X3R）0.3 即 0.7X1R-0.3X2R-0.3X3R 0同理有-0.4X1R+0.6X2R-0.4X3R 0-0.2X1R-0.2X2R+0.8X3R 0 0.75X1P-0.25X2