线性规划进一步研究.ppt

《线性规划进一步研究.ppt》由会员分享，可在线阅读，更多相关《线性规划进一步研究.ppt（76页珍藏版）》请在三一办公上搜索。

1、第二章 线性规划进一步研究,第一节 对偶问题(Dual Problem),线性规划早期发展过程中的最为重要的理论成果之一就是线性规划的对偶问题及相关理论的提出。线性规划的对偶理论解释资源的影子价格、线性规划问题的灵敏度分析等的理论基础。,一、对偶问题的提出,例1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？,决策变量：x1、x2分别代表甲、乙两种产品的生产数量。即有数学模型（问题A）：问题A max z=50 x1+100 x2 x1+x2300 2x1+x2400 x2250

2、 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,从数学和经济的角度

3、分析，该问题的目标函数只能极小，即该问题的数 学模型为：问题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+a1n

4、xn 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即两线性规划问题互为对偶。事实上，任一线性规划问题都有一个固定的线性规划问题与之对偶，且二者互为对偶关系，线性规划的这种性质称为对称性。更进一步有，对于线性规划问题：m

5、ax 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无限制解：其

6、对偶问题为,max w=30y1+80 y2+50 y3 y1 y2+4 y3 2 3y1+5y2+2y3 8 3y1+4y24y3=4 y10，y2无限制，y30,一、单纯形法的矩阵描述设有线性规划问题max z=CXAXbX0加上松弛变量XS=（xn+1，xn+2，xn+m）T，将其化为标准形式得到max z=CX+0XSAX+I XS=bX0，XS0其中 I为mm阶单位阵。,第二节 对偶理论(Duality Theory),设A中存在一可行基B，相应的变量X分成基变量XB和非基变量XN，价格系数C也相应地分成CB和CN两部分，A阵也分成B、N两部分，即 A=（B，N），X=（XB，XN）

7、T，C=（CB，CN）这样因而有 BXB+NXN+I XS=b即 XB=B-1bB-1NXNB-1XS用非基变量XN表示目标函数有=CBXB+CNXN+0XS,将XB=B-1bB-1NXNB-1XS代入得 z=CB（B-1bB-1NXNB-1XS）+CNXN+0XS=CBB-1b+（CNCBB-1N）XNCBB-1XS令 XN=0，XS=0得到对应于基B的基可行解 X=（XB，XX，XS）T=（B-1b，0，0）T目标值为 z=CBB-1b相应的非基变量的检验数为 N=（CNCBB-1N，CBB-1）若将基变量一起考虑有=（0，CNCBB-1N，CBB-1）=（CCBB-1A，CBB-1）此外

8、，从上式中可推出计算某一具体变量xj的检验数计算公式，即 j=cjCBB-1pj,由最优性判别定理可知，当=（CCBB-1A，CBB-1）0时，X=（XB，XX，XS）T=（B-1b，0，0）T为线性规划的最优解；若存在j=cjCBB-1pj0，（jJ），有B-1pj0，则线性规划问题有无界解。,上述过程可用如下单纯形表描述。,定理2.1(弱对偶定理)设X(0)是原问题max z=CX，AXb，X0的可行解 Y(0)是其对偶问题min w=Yb，YAC，Y0的可行解则 CX（0）Y（0）b。原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值?,二、对偶问题基本定理,定理

9、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分别是原问题松弛变量向量和对偶问题剩

10、余变量向量。,例2.3 已知线性规划问题 max z=x1+2x2+3x3+4x4 x1+2x2+2x3+3x420 2x1+x2+3x3+2x420 x1、x2，x3，x40解：其对偶问题为 min w=20y1+20y2 y1+2y2 1（1）2y1+y2 2（2）2y1+3y2 3（3）3y1+2y2 4（4）y1、y20 2x3*+3x4*=20 3x3*+2x4*=20解得x3*=x4*=4。故原问题的最优解为 X*=（0，0，4，4）T,其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。,将y1*=6/5，y2*=1/5代入上述约束条件，

11、得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*0，y2*0，故原问题的两个约束条件应取等式，所以,定理2.5 原问题单纯形表的检验数行对应对偶问题的一个基本解。该定理的进一步解释有：若原问题最优解存在，则原问题最优单纯形表的检验数行中，松弛变量或剩余变量的检验数对应对偶问题的最优解。例2.4（原问题为极大化问题）对于原问题：max z=50 x1+100 x2x1+x23002x1+x2400 x2250 x1、x20其对偶问题为：min w=300y1+400y2+250y3y1+2y2 50y1+y2+y3 100 y1、y2、y3 0,表中x3、x

12、4、x5为松弛变量；原问题最优解为：X*=（500，250）T，z*=27500对偶问题的最优解为：Y*=（y1*，y2*，y3*）=（50，0，50），w*=27500,解 原问题最优单纯形表如表所示，对应的对偶问题最优解列于表中最后一行。,例2.5（原问题为极小化问题）对于原问题：min z=2x1+3x2x1+x2350 x1 1252x1+x2600 x1、x20其对偶问题为：max w=350y1+125y2+600y3y1+y2+2y3 2y1+y3 3y1、y20、y3 0,解 用以极小化为标准形式的单纯形法求得原问题最优单纯形表如下表所示，对应的对偶问题最优解列于表中最后一行。

13、,表中x3、x4为剩余变量，x5为松弛变量；原问题最优解为：X*=（250，100）T，Z*=800对偶问题的最优解为：Y*=（y1*，y2*，y3*）=（4，0，1），w*=800,从上述两个例子可以总结出：对偶问题的最优解对应原问题最优单纯形表中松弛变量检验数的相反数或剩余变量的检验数。,一、资源的影子价格(Shadow Price)如前所述，若X*为线性规划max z=CX，AXb，X0的最优解，则z*=CX*；若Y*为其对偶问题的最优解，则有w*=Y*b。根据对偶定理有 z*=w*即 z*=Y*b 因此 即 由此可以看出，对偶问题的最优解实际上是右端常数项的单位变化所引起的目标值的变化

14、；,第三节 对偶问题的经济意义,若原问题描述的是资源有限条件下最优生产决策问题，则其对偶问题的最优解yi*(i=1,，m)表示第i种资源在最优生产决策下的边际值，即若其他条件不变，增加单位第i种资源将会使目标函数值增加yi*。其经济意义是：yi*描述了第i种资源在具体生产中的一种估价，这种估价不同于该种资源的市场价格，而是该种资源在给定条件某生产的最优生产方案下的一种实际存在而又看不见的真实价值，因此称之为影子价格（shadow price）。,同一种资源在不同的生产条件或不同的范围可能有不同的影子价格；产品的市场价格变化，资源的影子价格也会发生变化；资源的数量结构不同，资源的影子价格也不同。

15、,资源的影子价格是针对具体生产或具体企业而言的,与资源的市场价格比较以决定是否安排生产或转让资源或提高产品的价格；革新可以提高资源的影子价格；可以指导管理部门对紧缺资源进行“择优分配”；帮助预测产品的价格。因此，产品的价格应在“成本”和影子价格之间；影子价格的高低可以作为同类企业经济效益的评估标准之一。,影子价格对于拥有资源的决策者有非常重要的作用,对于目标函数极小化约束条件为大等号的问题 min z=CX，AXb，X0，其右端常数项可理解为需要完成的任务。因此，该类线性规划一般为描述完成一定任务使耗费的资源最小的问题。此时，其对偶问题的最优解yi*(i=1,，m)表示第i种任务的边际成本，即

16、单位任务的增加引起的资源耗费的增加量。,二、任务的边际成本(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,无论对偶问

17、题的最优解表示的是资源的影子价格还是任务的边际成本，只要为正，则表示右端常数项增加目标函数值增加，为负则表示右端常数项增加目标函数值减少。而对于极大化的问题，目标函数值增加表明目标函数得到改善，对于极小化的问题，目标函数减少表明目标函数得到改善。为了二者的统一，定义如下对偶价格。,三、对偶价格(Dual Price),定义2.2 线性规划问题某约束条件的右端常数项的单位增加量所引起的目标函数的改善量称为该右端常数项的对偶价格。因此，若对偶价格为正，则增加右端常数项，目标函数值得到改善；若对偶价格为负，则增加右端常数项，目标函数值将会“恶化”。,三、对偶价格(Dual Price),根据该定义，

18、对于极大化的问题，对偶价格就等于其对偶问题的最优解；对于极小化问题，对偶价格就等于其对偶问题最优解的相反数。例如本节例2.4的极大化问题三个约束条件的对偶价格分别为50，0和50；本节例2.6的极小化问题两个约束条件的对偶价格分别为360和800；下面在举一个含有等号约束的例子。例2.7 求下列线性规划问题各约束条件的对偶价格 min z=2x1+3x2+4x3 x1+x2+x3 120 2x1+x2+x3 60 x1+2x2+x3=80 x1、x2，x30,用大M法（极小化为标准形式）求解得问题的最优单纯形表如表26。,故对偶问题的最优解为y1*=0，y2*=1/3，y3*=4/3。由于是极

19、小化问题，所以三个约束条件的对偶价格为对偶问题最优解的相反数，即分别为0、1/3和4/3。即第二个约束条件的右端常数项增加1个单位，则目标函数值“恶化”1/3个单位，减少一个单位，则目标函数值“改善”1/3个单位。对于第一和第三个约束条件可作同样的分析。,第六节 线性规划的应用(Applications of LP),线性规划是管理决策制定的最成功的数量方法之一。它广泛应用于化工、航空、钢铁、石油和其他工业。它研究的问题是多种多样的生产计划、媒体选择、金融计划、资金预算、运输、工厂选择、生产组合、人员调配等等。,例 红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售

20、货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？,一、人力资源分配问题,解：设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、x

21、70该问题的最优解为：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分别表示表中日间电视、夜间电视、日报、周末新闻杂志、电台广播五种

22、媒体的使用次数。该问题的线性规划模型为 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

23、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.对太平洋石油

24、的投资不能多于整个石油行业投资的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,Go

25、v 0,(二)、金融计划案例 某公司现有68名员工申请提前退休。公司必须在此后的8年内对这些员工分期支付一定数量的现金，如下表所示。,为了完成这项现金支付任务，公司的财务人员必须现在就为此制定一个投资计划。投资计划有政府债券投资和银行储蓄两种方式组成。,注意:三种政府债券的票面价值均为1000元，债券到期时按票面价值进行支付，利率的计算也以票面的价值为基准。银行储蓄年利率为4%。如何安排投资计划，使公司以最小的投资额完成对退休员工的现金支付任务？,政府债券投资有三种债券类型可供选择，如下表所示。,解：1确定决策变量设F为完成投资计划所需要的总资金额。x1、x2、x3分别表示债券1、2、3的购买

26、量；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.

27、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.

28、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变量 最优解

29、检验数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年起债券的利息和债券到期收入才能够完全满足当前现金支付需要。

30、每一个约束条件的对偶价格均为负值，说明减少任何一年的现金支付都将有利于公司总投资额的降低。对偶价格的逐年降低也说明了，在前面年份减少现金支付将对总投资额的减少更为有效。从而暗示了公司可以适当减少前面年份的现金支付量，而在后面年份进行补足。,(一)制造或购买决策案例 某公司有，两种产品，预计两种产品的市场需求量分别为3000件和2000件。两种产品均由a、b、c三个部件组成，各部件生产消耗工时和自制/外购成本如下表所示。,四、生产管理应用,由于生产能力有限，公司只有200个正常制造工时和50个加班工时可用于这两种产品的生产。每个加班工时需额外支付9元。如何安排部件自制和外购的数量，从而使总成本（

31、包括生产成本、外购成本和加工费用）最低？,解：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最大生产能力约束

32、 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

33、+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

34、.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 700

35、02 666.667 3000 无上限3 0.000 2000 28004 0.000 3000 无上限5 0.000 2000 无上限6 0.000 50 无上限7 10000.000 12000 19000,(二)生产计划问题生产计划问题是线性规划应用最为广泛的领域之一;问题描述:一定时期内，经理必须决定生产水平，使公司能够满足生产需求，在受到产品生产量、劳动力水平以及存储空间上所有限制的同时，还要使生产成本最小。线性规划解决该类问题的优点：可重复利用已建立好的线性规划模型指定不同时期的生产计划。,案例,Bollinger 电子公司接到未来三个月的两种产品的定单：生产部门分析，生产费用有以

36、下方面：（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.

37、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)机

38、器生产能力约束 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+D

39、1=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 均为非负变量，而且至少有一个为零。计算机求解结果：,（三）劳动力分配问题问题描述：一个企业有多个生产部门，一定时期各生产部门劳动力数量一定，但劳动力可以在各部门之间转移或再分配最佳的分配方案。案例（麦科米克公司劳动时间分配问题）,设P1,P2分别为产品1、2的产量，则问题的数学模型为：max z=10P1+9P2 0.65P1+0.95P26500 0.

40、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.6

41、5P1+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-t1

42、3-t23+t34=7000 b4-t24-t34+t41+t42=1400,问题描述：当混合两种以上资源生产一种以上产品时，管理者必须决定每种资源的购买量以在成本最低的情况下满足产品的需要。应用领域：石油化工、食品行业等；案例（大绳石油公司混合问题）,五、混合问题,决策变量：,目标函数：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

43、+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.25X2P-0.25X3P 0-0.4X1P+0.6X2P-0.4X3P 0-0.3X1P-0.3X2P+0.7X3P 0(3)产量约束 X1R+X2R+X3R 10000,早期由美国航空公司在是否决定折价出售和出售多少飞机座位时开发的；通过制定出售折扣座位和原价座位的最优决策，航空公司可以在增加平均乘客数的同时使混合出售两种座位的所得收益最大化。收益管理用于其他产业只是最近的事：定价策略、超额预定策略、短期供应决策、长期资产管理等。,六、收益管理,线性规划应用小结,线性规划有着广泛的应用；线性规划的应用非常灵活；所讲案例只是真实情况的缩微；,第二章 结束,