线性规划模型实用版课件

线性规划模型（优选）线性规划模型线性规划问题的提出

解决有限资源的最佳分配问题。即如何对有限的资源作出最佳方式的调配和最有利的使用，以使最充分地发挥资源的效能去获取最佳的经济效益。线性规划（LinearProgramming,LP)

康托洛维奇

1939《生产组织与计划中的数学方法》

丹捷格（美）1947单纯形方法

第三章线性规划模型线性规划问题的提出线性规划（LP)问题包含下列要素变量决策要控制的因素目标决策目标（最优）的数学描述约束条件实现目标的一组限制条件求LP问题在约束条件下使目标最优的一组变量的取值解决环节确定问题、建立模型、问题求解、经济分析、敏感性分析第三章线性规划模型建立线性规划问题模型线性规划问题举例教材P40LP模型决策变量每周的生产批次G、T目标函数maxZ＝30×G+20×T（获利最大）约束条件1×G+2×T≤40（配料工序约束）(s.t.)2×G+1×T≤40（整流工序约束）1×G+1×T≤25（包装工序约束）G≥0;T≥0（生产批次的非负约束）第三章线性规划模型第三章线性规划模型建立线性规划问题模型总结模型构建的一般思路确定该LP问题的目标是什么？实现目标取决于什么因素和条件？确定哪几个因素为决策变量？目标如何用决策变量来加以描述？约束条件如何表达？决策变量本身是否有限制条件？第三章线性规划模型例31:请你构建以下问题的LP模型某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示用线性规划制订使总利润最大的生产计划。第三章线性规划模型建立的模型如下设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数Z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型maxZ=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.5x1+3.0x2+3.5x3+1.0x4≤5000x1,x2,x3,x4≥0第三章线性规划模型第三章线性规划模型项目A从第一年到第四年每年年初需要投资，并于次年末回收本利115％。原问题与对偶问题转换：将非标准形式转化为标准形式15X1A1.决策变量的变化X4=0X5=80X1+2X2=2第三章线性规划模型令Z’=Z,Z’为最大化问题。影子价格的作用决定企业的经营策略当KCD→KC’D时：最优值E→E1’；Xj≥0(e)可行域开放，目标函数无界杭甬高速公路在杭州入口处在24小时内通过的数量是不均匀的，因此，相应地，在入口处收费的人数安排也应按时段不同而有所差异。……(a)非凸集(b)非凸集(c)非凸集求解这个线性规划，可以得到最优解为x1=294.12x2=1500 x3=0x4=58.82 最大利润为 z=12737.06（元）请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。另外，变量是否需要取整也是需要考虑的问题。第三章线性规划模型总结线性规划问题的典型特征可用一些变量表示这类问题的待定方案，这些变量（决策变量）的一组值代表一个具体方案；存在一定的约束条件，这些约束条件都能用关于决策变量的线性不等式或等式来表示；有一个期望达到的目标，这个目标能以某种确定的数量指标刻划出来，而这种数量指标可表示为关于决策变量的线性函数，按所考虑的问题的不同，要求该函数值最大化或最小值。第三章线性规划模型线性规划问题的基本要求目标函数和约束条件必须是线性函数；线性表达相加性、比例性决策变量的连续分布；不限于整数，可以是小数，但不能四舍五入目标函数的单一性；多目标是要设法简化成单目标模型必须是确定型的；所有参数(a、b、c)都应是确定值决策变量的非负性第三章线性规划模型线性规划问题模型的一般形式目标函数约束条件第三章线性规划模型线性规划问题一般模型的简化形式目标函数maxZ=∑CjXj约束条件∑aijXj≥(=,≤)biXj≥0i=1,2,3,……,mj=1,2,3,……,n第三章线性规划模型j=1nXj

的单位贡献第i资源的约束量Xj

的技术性系数：表示第j种活动消耗资源i的数量线性规划问题的标准形式

目标函数为最大化；约束条件（非负条件除外）全为等式；约束条件右端项为大于等于零；

maxZ=C1X1+C2X2+…+CnXns.t.a11X1+a12X2+…+a1nXn=b1a21X1+a22X2+…+a2nXn=b2……………am1X1+am2X2+…+amnXn=bmX1,X2,...,Xn≥0第三章线性规划模型将非标准形式转化为标准形式目标函数为最小化令Z’=Z,Z’为最大化问题。若约束条件是小于等于型在不等式左边加上一个新变量（松弛变量），不等式改为等式，目标函数中新变量系数为零。若约束条件是大于等于型在不等式左边减去一个新变量（剩余变量），不等式改为等式，目标函数中新变量系数为零。第三章线性规划模型为原始问题的对偶问题，最优值Y为影子价格不等式改为等式，目标函数中新变量系数为零。约束条件实现目标的一组限制条件配料配套问题（教材P44,实例3.(1/7,11/7)……………影子价格也是机会成本。maxZ=C1X1+C2X2+…+CnXn生产一件甲产品可获利2元，生产乙产品获利3元。得到X*1=4/7,X*2=5/7①Cj的变化影响到目标函数直线斜率K的变化。第三章线性规划模型第三章线性规划模型X2=85库存卖出买入月末库存线性规划问题举例教材P40若线性规划的可行域非空，则可行域必为凸集在不等式左边减去一个新变量（剩余变量），2(Y1+Y2+Y3)考虑到资金周转，应该是先卖出再买进，而且最好是月初卖出月底买进。将非标准形式转化为标准形式若约束方程右端项bi<0:在约束方程两端乘以（－1），不等号改变方向，然后再转化成等式。若决策变量Xk没有非负要求作两个新变量Xk’≥0,Xk”≥0,令Xk＝Xk’Xk”，在原有模型中用（Xk’－Xk”）代替所有的Xk，在非负约束中增加Xk’≥0和Xk”≥0。第三章线性规划模型第三章线性规划模型例32:将下列LP问题转化为标准形式x1,x3≥0,x2无符号限制minZ=2x1-3x2+x3s.t.x1-x2+2x3≤32x1+3x2-x3≥5x1+x2+x3=4第三章线性规划模型令Z’=Z，引进松弛变量x4≥0,和剩余变量x5≥0，令x2=x2'x2'‘其中x2'≥0，x2''≥0,得到以下等价的标准形式:MAXz’=-2x1+3x2'-3x2''-x3s.t.x1-x2'+x2''+2x3+x4=32x1+3x2'-3x2''-x3-x5=5x1+x2'-x2''+x3=4x1,x2',x2'',x3,x4,x5≥0第三章线性规划模型两个变量的线性规划问题的几何解释例33:z=0z=3z=6z=9z=12z=15.30123456-8-7-6-5-4-3-2-1654321x1x2目标函数等值线Z=X1+3X2可行域(4/3,14/3)Maxz=X1+3X2s.t.X1+X2≤6X1+2X2≤8X1,X2≥0线性规划的可行域及最优解的性质若线性规划的可行域非空，则可行域必为凸集若线性规划有最优解，则最优解至少在一个极点上第三章线性规划模型

(a)凸集(b)凸集 (c)凸集

(a)非凸集(b)非凸集(c)非凸集

第三章线性规划模型线性规划的可行域及最优解的可能结果可行域为封闭的有界区域唯一、多个最优解可行域为非封闭的无界区域唯一、多个最优解、目标函数无界，无最优解可行域为空集没有可行解，更无最优解

线性规划的可行域及最优解的可能结果图示：

(a)可行域封闭，唯一最优解(a)可行域封闭，多个最优解(d)可行域开放，多个最优解(e)可行域开放，目标函数无界

(f)

可行域为空集(c)可行域开放，唯一最优解第三章线性规划模型第三章线性规划模型线性规划的EXCEL求解例31:某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示用线性规划制订使总利润最大的生产计划。第三章线性规划模型线性规划问题的提出线性规划问题的建模典型特征和基本条件一般模型和标准模型线性规划的图解方法影子价格与敏感分析线性规划模型的应用第三章线性规划模型第三章线性规划模型

某厂生产甲、乙两种产品，消耗A、B两种原材料。生产一件甲产品可获利2元，生产乙产品获利3元。问在以下条件下如何安排生产？

甲乙总量设备台时原材料A原材料B140204

81612对偶问题的提出建立线性规划模型：目标函数：

MAXZ=2X1+3X2约束条件：

X1+2X2≤84X1+≤164X2≤12X1,X2≥0从另一角度考虑如果该厂决定不生产甲、乙两种产品，而将其资源出租或出售，这时工厂的决策者就要考虑给每种资源如何定价的问题。设用Y1,Y2,Y3分别表示出租单位设备台时的租金和出让原材料A、B的附加值。作如下比较，用一个单位设备台时和四个单位的原材料可以生产甲产品一件，获利2元，那么出租和出让的收益不应低于自己生产时的收益。因此有Y1+4Y2≥2;同样地乙产品也有2Y1+4Y3≥3第三章线性规划模型对偶问题的提出

全部出让或出租的总收入为W=8Y1+16Y2+12Y3从决策者来看，当然希望W值越大越好。但从接受者来讲，支付越少越好。为提高竞争力，因此工厂只能在满足≥所有产品的利润条件，使其总收入具有竞争力的，因此，W需要求解最小值。因此有线性规划模型目标函数minW=8Y1+16Y2+12Y3s.tY1+4Y2≥22Y1+4Y3≥3Y1,Y2,Y3≥0第三章线性规划模型线性规划模型目标函数MAXZ=2X1+3X2s.t.X1+2X2≤84X1≤164X2≤12X1,X2≥0第三章线性规划模型线性规划模型：目标函数：

MINW=8Y1+16Y2+12Y3s.t.Y1+4Y2≥22Y1+4Y3≥3Y1,Y2,Y3≥0

最优解：X1=4,X2=2,Z=14最优解：Y1=1.5,Y2=0.125,Y3=0,W=14原问题对偶问题0123456极小化问题bi（minW）在完全的市场条件下，随着资源的买进和卖出，影子价格随之变化，直到影子价格与市场价格第三章线性规划模型影子价格也是机会成本。实现目标取决于什么因素和条件？85X1≤20000+3.投资额应等于手中拥有的资金，不应有剩余。X1=120=yi*(i=1,2,…,m)若决策变量Xk没有非负要求X1=120；合理下料问题（例39)(a)非凸集(b)非凸集(c)非凸集X3+Y1=160日期12345如买进的商品当月到货，但需到下月才能卖出，且规定“货到付款”。Y1+4Y2≥2;25Y23.第三章线性规划模型目标决策目标（最优）的数学描述对偶问题与影子价格定义设以下线性规划问题 MAXZ=CTX s.t.AX≤b X≤0为原始问题，则称以下问题 MINW=bTY s.t.ATY≤C Y≥0为原始问题的对偶问题，最优值Y为影子价格第三章线性规划模型第三章线性规划模型对偶问题对偶问题第三章线性规划模型原问题与对偶问题转换：对偶问题与原始问题的关系第三章线性规划模型目标极大化问题Cj（maxZ）极小化问题bi（minW）目标变量nxj≥0——aTijyi≥cj约束nxj无约束——aTijyi=cjxj≤0——aTijyi≤cj约束maijxj≥bi——yi≤0变量maijxj=bi——yi无约束aijxj≤bi——yi≥0对偶问题的性质

对偶问题的对偶是原问题。若两个互为对偶问题之一有最优解，则另一个必有最优解，且目标函数值相等(Z*=W*)，最优解满足CX*=Y*b。若X*,Y*分别是原问题和对偶问题的可行解，则X*,Y*为最优解的充分必要条件是Y*XL=0和YSX*=0。第三章线性规划模型原问题标准型：MaxZ=CXAX+XL=bX,XL≥0对偶问题标准型：MinW=YbYA-YS=CY,YS≥0第三章线性规划模型对偶问题的性质（续）

原问题和对偶问题的互补松松弛关系第三章线性规划模型例3-4:根据对偶原理求解以下线性规划问题：作业运用对偶原理求以下原问题的最优解目标函数MINZ=2X1+3X2+X3s.t3X1X2+X3≥1X1+2X23X3≥2X1,X2,X3≥0

第三章线性规划模型第三章线性规划模型对偶问题解的经济解释－－影子价格根据对偶问题的性质有Z*=W*=∑biyi*两边对bi求偏导数得到

∂Z*=yi*(i=1,2,…,m)∂bi即yi*表示每增加一个单位bi后Z*的增量第三章线性规划模型mi=1对偶问题解的经济解释－－影子价格

bi在原问题中是约束条件的右端项，表明了第i种资源的可用量。因此，对偶解的经济含义就是资源的单位改变引起目标函数值的增加量。定量表达了在最优生产方案下对单位第i种资源的一种估价，这种估价不是该种资源的市场价格，而是在最优生产方案下的一种虚拟价格，故称其为影子价格（shadowprice)。第三章线性规划模型影子价格的作用决定企业的经营策略影子价格真实地反映了资源在经济结构中最优决策下对总收益的影响和贡献大小。影子价格越高，表明该种资源的贡献越大。影子价格为正数（非零），该资源约束的松弛变量取值为零（没有松弛变量），因此表明了该资源在最优决策下已充分利用耗尽，并成为进一步增加总收益的紧缺资源。影子价格越高，表明该种资源越紧缺。影子价格为零，表明该资源在最优决策下尚有剩余。第三章线性规划模型影子价格的作用决定企业的经营策略影子价格也是机会成本。当第i种资源的市场价格低于影子价格时，企业应适量购进这种资源，组织和增加生产；相反，当市场价格高于影子价格时，可以卖出资源而不安排生产或提高产品的价格。在完全的市场条件下，随着资源的买进和卖出，影子价格随之变化，直到影子价格与市场价格保持同等水平。第三章线性规划模型若线性规划有最优解，则最优解至少在一个极点上决策变量每周的生产批次G、T4米长的钢材，可有若干种下料方式把它截取成我们所需要的轴，如可以截取2根2.例3-4:根据对偶原理求解以下线性规划问题：am1X1+am2X2+…+amnXn=bm两边对bi求偏导数得到MAXZ=1.第三章线性规划模型变量的取值存货限制Y1≤1000;Y2≤1000Y1+X1;Y3≤1000Y1+X1Y2+X2(a)非凸集(b)非凸集(c)非凸集得到X*1=4/7,X*2=5/76(X1+X2+X3+X4+X5)+0.s.线性规划问题模型的一般形式影子价格的作用决定企业的经营策略多目标是要设法简化成单目标01影子价格的作用决定企业的经营策略从资源最优利用的角度，提出企业挖潜改革，扬长避短的方向。剩余资源也是进一步发展生产的潜在优势。指导管理部门对紧缺资源进行择优分配。资源影子价格的高低作为同类企业经济效益的评价指标之一。帮助预测产品的价格。买方要购入卖方的产品作为资源投入生产，要求其价格必须小于该产品作为自己最优生产的影子价格，卖方要求出售其产品的价格必须大于自己的生产成本，因此，产品的价格应在双方的成本和影子价格之间。

第三章线性规划模型第三章线性规划模型例35:生产计划问题（例31）影子价格最优解x1=294.12x2=1500 x3=0x4=58.82Z=12737.06敏感性分析

分析参数（A，b，C）的改变对最优值的影响，推算出模型的最优解对原有模型系数变化的敏感范围（最优解能够允许其系数变化的范围）。目标函数的变化所需资源的变化资源消耗的变化决策变量的变化第三章线性规划模型敏感性分析－－目标函数的变化第三章线性规划模型①

Cj的变化影响到目标函数直线斜率K的变化。要保持E点仍为最优解，K必须介于直线AB

和直线CD的斜率之间，即KCD

<

K<

KABK<

KCDE→

CK>KABE→

B

K=KCDE→

ECK=KABE→EBX1X2BE①DC③②OKABAKCDK敏感性分析－－约束方程系数aij变化第三章线性规划模型X1X2BEDCOKC’DAKCDKABaij的变化，使直线AB与CD的斜率发生变化。当KCD→KC’D

时：最优值

E→E1’；

KAB→KA’B时：最优值

E→E2’；

同时变化时：最优值

E→E3’E1’KA’BE3’E2’1、最优解的极点不变，但坐标变化，Z值变。2、最优解的极点变化？C’A’敏感性分析－－约束方程常数项bi变化第三章线性规划模型X1X2BEDCOAD’A’C’B’E3’bi

的变化直接导致截距的变化，

E有可能变成E1’，E2’，E3’。最优解的极点变化？

bi

的变化与影子价格的关系？E2’E1’第三章线性规划模型敏感性分析－－增加一个新产品(教材P56)

GT总量影子价格V配料124002蒸馏2240102包装1125102获利302050代价0202040新产品V投产带来的收益值10对偶问题与原始问题的关系第三章线性规划模型目标极大化问题Cj（maxZ）极小化问题bi（minW）目标变量nxj≥0——aTijyi≥cj约束nxj无约束——aTijyi=cjxj≤0——aTijyi≤cj约束maijxj≥bi——yi≤0变量maijxj=bi——yi无约束aijxj≤bi——yi≥0作业1:对偶问题求解运用对偶原理求以下原问题的最优解目标函数MINZ=2X1+3X2+X3s.t3X1X2+X3≥1X1+2X23X3≥2X1,X2,X3≥0写出对偶问题目标函数MAXW=Y1+2Y2s.t:3Y1+Y2≤2Y1+2Y2≤3Y13Y2≤1Y1,Y2≥0

(0,3/2)01

-11Y1Y2(2/3,0)3Y1+Y2=1Y1-3Y2=1-Y1+2Y2=3-1(1/7,11/7)Y1+2Y2=23/7求解对偶问题最优解Y*1=1/7,Y*2=11/7,Y*3=0,Y*4=0,Y*5=39/7根据互补松弛定理得到X*3=0,X*4=0,X*5=0因此有3X1X2=1X1+2X2=2得到X*1=4/7,X*2=5/7原问题的解为X*1=4/7,X*2=5/7,X*3=0Z*=W*=23/7第三章线性规划模型线性规划问题的提出线性规划问题的建模典型特征和基本条件一般模型和标准模型线性规划的图解方法影子价格与敏感分析线性规划模型的应用第三章线性规划模型线性规划模型的应用生产计划问题（教材P42,实例3.1,例36,7)项目投资问题（教材P43,实例3.2,例38)配料配套问题（教材P44,实例3.3,思考题)合理下料问题（例39)人力资源问题（例310）运输调运问题（线性规划问题扩展）任务指派问题（线性规划问题扩展）

第三章线性规划模型例36:生产计划问题

某车间在每个生产期5天所需要的每种刀具的统计资料如下

每一把刀具成本为0.6元，用过的刀具送到机修车间研磨，每把需花费0.2元。刀具用过后送去磨(只一次），两天后可以磨好送回，供当天（第三天）使用。第五天后应全部换新，每期开始时没有任何刀具，问这个车间需要多少刀具才能应付需要，而成本又最低？试建立线性规划模型。第三章线性规划模型日期12345刀具数12085160145300确定变量问题是要确定每期需要新刀具的总数，它等价于要确定每天所需的新刀具，同时考虑到送去研磨的刀具第三天可使用，为此，设决策变量Xi(i=1,2,3,4,5)为第i天使用的新刀具；Yj(j=1,2,3)为第j天送去研磨的刀具数。确定目标函数（新刀具成本＋研磨成本）为最小，即minZ＝0.6(X1+X2+X3+X4+X5)+0.2(Y1+Y2+Y3)第三章线性规划模型确定约束条件由于研磨的刀具第三天才能使用，因此，X1=120；X2=85第三天开始，每天使用新的和研磨送回的刀具X3+Y1=160,X4+Y2=145,X5+Y3=300在头三天送去研磨的刀具应满足Y1≤120,Y2≤85+(120Y1);Y3≤160+(120Y1)+(85Y2)每天使用的新刀具和送研磨的刀具数为非负整数X1,X2,X3,X4,X5,Y1,Y2,Y3≥0,且均为整数第三章线性规划模型完整的模型为minZ＝0.6(X1+X2+X3+X4+X5)+0.2(Y1+Y2+Y3)s.t.X1=120X2=85X3+Y1=160X4+Y2=145X5+Y3=300Y1≤120Y2≤85+(120Y1)Y3≤160+(120Y1)+(85Y2)X1,X2,X3,X4,X5,Y1,Y2,Y3≥0,且均为整数第三章线性规划模型求解结果

X1=120X2=85X3=160X4=0X5=80Y1=0Y2=145Y3=220第三章线性规划模型例37营销策略一贸易公司专门经营某商品的批发业务，公司有库容5000单位的仓库，某年一月一日，公司有库存1000单位，并有资金20000元，估计第一季度该商品的价格如下表所示。如买进的商品当月到货，但需到下月才能卖出，且规定“货到付款”。公司希望本季末库存为2000单位，问应采取什么样的买卖策略可使3个月总的获利最大？一月二月三月进货价（元）2.853.052.90出货价（元）3.103.252.95第三章线性规划模型例37营销策略考虑到资金周转，应该是先卖出再买进，而且最好是月初卖出月底买进。决策变量每月买进Xi(i=1,2,3),每月卖出Yi(i=1,2,3)。分析库存情况库存卖出买入月末库存一月1000Y1X11000Y1+X1二月1000Y1+X1Y2X21000Y1+X1Y2+X2三月1000Y1+X1Y2+X2Y3X31000Y1+X1Y2+X2Y3+X3存货限制Y1≤1000;Y2≤1000Y1+X1;Y3≤1000Y1+X1Y2+X2库容限制1000Y1+X1≤5000；1000Y1+X1Y2+X2≤50001000Y1+X1Y2+X2Y3+X3＝2000第三章线性规划模型例37营销策略分析资金流动情况月初资金卖出买入一月200003.10Y12.85X1二月20000+3.10Y12.85X13.25Y23.05X2三月20000+3.10Y12.85X1+3.25Y23.05X22.95Y32.90X3资金限制2.85X1≤20000+3.10Y13.05X2≤20000+3.10Y12.85X1+3.25Y22.90X3≤20000+3.10Y12.85X1+3.25Y23.05X2+2.95Y3目标函数MAXZ=3.10Y1+3.25Y2+2.95Y32.85X13.05X22.90X3第三章线性规划模型例38连续投资问题某部门在五年内考虑给下列项目投资项目A从第一年到第四年每年年初需要投资，并于次年末回收本利115％。项目B从第三年初需投资，到第五年末能回收本利125％，但规定最大投资额不超过4万元。项目C第二年初需要投资，到第五年末能回收本利140％，但规定最大投资额不超过3万元。项目D五年内每年初可购买公债于当年末归还并加利息6％。该部门现有资金10万元，问应如何确定给这些项目每年的投资额，使到第五年末拥有的资金的本利总额为最大。第三章线性规划模型第三章线性规划模型确定变量以XiA,XiB,XiC,XiD(i=1,2,3,4,5)分别表示第i年年初给项目A,B,C,D的投资额。具体列于下表第1年第2年第3年第4年第5年ABCDX1AX1DX2AX2CX2DX3AX3BX3DX4AX4DX5D确定约束条件投资额应等于手中拥有的资金，不应有剩余。第一年X1A+X1D=100000第二年年初资金仅为D项目第一年的本息。X2A+X2C+X2D=X1D(1+6%)第三年年初资金为A第一次回收本利＋D第二次本息X3A+X3B+X3D=X1A(1+15%)+X2D(1+6%)第四年X4A+X4D=X2A(1+15%)+X3D(1+6%)第五年X5D=X3A(1+15%)+X4D(1+6%)B、C投资额限制X3B≤40000;X2C≤30000确定目标函数第五年末资金最大MAXZ=1.15X4A+1.40X2C+1.25X3B+1.06X5D

第三章线性规划模型完整的模型为MAXZ=1.15X4A+1.40X2C+1.25X3B+1.06X5Ds.t.X1A+X1D=1000001.06X1D+X2A+X2C+X2D=01.15X