《第二章 线性规划进一步研究》由会员分享，可在线阅读，更多相关《第二章 线性规划进一步研究（76页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章 线性规划进一步研究线性规划进一步研究第一节第一节 对偶问题对偶问题 (DualProblem)线性规划早期发展过程中的最为重要的理线性规划早期发展过程中的最为重要的理论成果之一就是线性规划的对偶问题及相论成果之一就是线性规划的对偶问题及相关理论的提出。线性规划的对偶理论解释关理论的提出。线性规划的对偶理论解释资源的影子价格、线性规划问题的灵敏度资源的影子价格、线性规划问题的灵敏度分析等的理论基础。分析等的理论基础。一、对偶问题的提出例1（生生产产计计划划问问题题）某某企企业业利利用用A、B、C三三种种资资源源，在在计计划划期期内内生生产产甲甲、乙乙两两种种产产品品，已已知知生生产
2、产单单位位产产品品资资源源的的消消耗耗、单单位位产产品品利利润润等等数数据据如如下下表表，问问如如何何安安排排生生产产计计划使企业利润最大？划使企业利润最大？产产品品资资源源甲甲乙乙资源限制资源限制ABC120111300kg400kg250kg单位产品利润单位产品利润(元元/件件)50100决决策策变变量量：x1、x2分分别别代代表表甲甲、乙乙两两种种产产品品的的生生产数量。产数量。即有数学模型（问题即有数学模型（问题A）：）：问题问题Amaxz=50x1+100x2x1+x23002x1+x2400x2250x1、x20称之为上述问题的数学模型。称之为上述问题的数学模型。同同样样是是上上述
3、述问问题题，提提问问：企企业业不不安安排排生生产产，而而转转让让三三种资源，应如何给三种资源定价？种资源，应如何给三种资源定价？决决策策变变量量：y1、y2、y3分分别别代代表表A、B、C三三种种资资源源的的价价格（最低转让净收入）。格（最低转让净收入）。约束条件约束条件1：生产一件产品甲所耗资源数量转让所得净收入生产一件产品甲所耗资源数量转让所得净收入不能低于一不能低于一件产品甲所获利润，即：件产品甲所获利润，即：1y1+2y250约束条件约束条件2：生产一件产品乙所耗资源数量转让所得净收入：生产一件产品乙所耗资源数量转让所得净收入不能低于一不能低于一件产品乙所获利润，即：件产品乙所获利润，
4、即：1y1+1y2+1y3100目标函数为目标函数为：w=300y1+400y2+250y3即有即有w=300y1+400y2+250y3y1+2y250y1+y2+y3100y1、y2、y30从从数学数学和和经济经济的角度分析，该问题的目标函数只能极小，的角度分析，该问题的目标函数只能极小，即该问题的数即该问题的数学模型为：学模型为：问题问题Bminw=300y1+400y2+250y3y1+2y250y1+y2+y3100y1、y2、y30称问题称问题B为问题为问题A的的对偶问题对偶问题，问题，问题A为为原问题原问题。问题问题Amaxz=50x1+100x2x1+x23002x1+x240
5、0x2250x1、x20定义定义2.1设有线性规划问题设有线性规划问题maxz=CXAXbX0其对偶问题定义为其对偶问题定义为minw=YbYACY0且前者称为且前者称为原问题原问题，后者称为，后者称为对偶问题对偶问题。二、对偶问题的定义二、对偶问题的定义具体的数量对应关系为具体的数量对应关系为原问题原问题maxz=c1x1+c2x2+cnxna11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0对偶问题对偶问题minw=b1y1+b2y2+bmyma11y1+a21y2+am1ymc1a12y1+a22y2+am2
6、ymc2a1ny1+a2ny2+amnymcny1，y2，ym0根根据据对对偶偶问问题题的的定定义义不不难难推推出出，对对于于线线性性规规划划问问题：题：minw=Yb；YAC；Y0其对偶问题为：其对偶问题为：maxz=CX；AXb；X0即两线性规划问题互为对偶。即两线性规划问题互为对偶。事事实实上上，任任一一线线性性规规划划问问题题都都有有一一个个固固定定的的线线性性规规划划问问题题与与之之对对偶偶，且且二二者者互互为为对对偶偶关关系系，线线性性规划的这种性质称为规划的这种性质称为对称性对称性。更进一步有，对于线性规划问题：更进一步有，对于线性规划问题：maxz=CX；AX=b，X0其对偶问
7、题为：其对偶问题为：minw=Yb；YAC，Y无限制无限制根据以上分析，线性规划原问题与对偶问题的数量根据以上分析，线性规划原问题与对偶问题的数量关系可用下表描述。关系可用下表描述。原问题原问题（或对偶问题或对偶问题）对偶问题对偶问题（或原问题或原问题）目标函数目标函数maxzminw目标函数目标函数变量变量n个个00无约束无约束n个个=约束条件约束条件约束条件约束条件m个个=m个个00无约束无约束变量变量约束条件右端常数项约束条件右端常数项目标函数变量系数目标函数变量系数目标函数变量系数目标函数变量系数约束条件右端常数项约束条件右端常数项例例2.1写出下列线性规划问题的对偶问题写出下列线性规
8、划问题的对偶问题maxz=2x1+2x24x3 x1+3x2+3x3304x1+2x2+4x380x1、x2，x30解：其对偶问题为解：其对偶问题为minw=30y1+80y2y1+4y223y1+2y223y1+4y24y1、y20例例2.2写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题minz=2x1+8x24x3x1+3x23x330x1+5x2+4x3=804x1+2x24x350x10、x20，x3无限制无限制解：其对偶问题为解：其对偶问题为maxw=30y1+80y2+50y3y1y2+4y323y1+5y2+2y383y1+4y24y3=4y10，y2无限制，无限制
9、，y30一、单纯形法的矩阵描述一、单纯形法的矩阵描述设有线性规划问题设有线性规划问题maxz=CXAXbX0加上松弛变量加上松弛变量XS=（xn+1，xn+2，xn+m）T，将其将其化为标准形式得到化为标准形式得到maxz=CX+0XSAX+IXS=bX0，XS0其中其中I为为mm阶单位阵。阶单位阵。第二节第二节对偶理论对偶理论(DualityTheory)设设A中存在一可行基中存在一可行基B，相应的变量相应的变量X分成基变量分成基变量XB和非基变量和非基变量XN，价格系数价格系数C也相应地分成也相应地分成CB和和CN两部分，两部分，A阵也分成阵也分成B、N两部两部分，即分，即A=（B，N），
10、），X=（XB，XN）T，C=（CB，CN）这样这样因而有因而有BXB+NXN+IXS=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，C
11、BB-1）若将基变量一起考虑有若将基变量一起考虑有=（0，CNCBB-1N，CBB-1）=（CCBB-1A，CBB-1）此外，从上式中可推出计算某一具体变量此外，从上式中可推出计算某一具体变量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，则线性规划问题有无界解。则线性规划问题有无界解。CCBCN0bCBXBXBXNXSCBXBI
12、B-1NB-1B-1bz0CNCBB-1N-CBB-1-CBB-1b上述过程可用如下单纯形表描述。上述过程可用如下单纯形表描述。定理定理2.1(2.1(弱对偶定理弱对偶定理) )设设X(0)是原问题是原问题maxz=CX，AXb，X0的可行解的可行解Y(0)是其对偶问题是其对偶问题minw=Yb，YAC，Y0的可行解的可行解则则CX（0）Y（0）b。原问题任一可行解对应的目标函数值不大于其对偶问题原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值的任一可行解对应目标函数值?二、对偶问题基本定理二、对偶问题基本定理定理定理2.2(2.2(最优性定理最优性定理) )设设X(
13、0)是原问题是原问题maxz=CX，AXb，X0的可行解，的可行解，Y（0）是其对偶问题是其对偶问题minw=Yb，YAC，Y0的可行的可行,若若CX（0）=Y（0）b，则则X（0）、Y（0）分别是它们的最优解。分别是它们的最优解。定理定理2.3(2.3(对偶定理对偶定理) )若原问题若原问题maxz=CX，AXb，X0有最优解，有最优解，则其对偶问题则其对偶问题minw=Yb，YAC，Y0一定有最优解，一定有最优解，且二者的目标函数值相等。且二者的目标函数值相等。定理定理2.4(2.4(互补松弛定理互补松弛定理) )原问题原问题maxz=CX，AXb，X0及其及其对偶问题对偶问题minw=Y
14、b，YAC，Y0的可行解的可行解X（0）、Y（0）是最优解是最优解的充要条件是的充要条件是Y（0）XS=0；YSX（0）=0其中，其中，XS、YS分别是原问题松弛变量向量和对偶问题剩余变量向量。分别是原问题松弛变量向量和对偶问题剩余变量向量。例例2.3已知线性规划问题已知线性规划问题maxz=x1+2x2+3x3+4x4x1+2x2+2x3+3x4202x1+x2+3x3+2x420x1、x2，x3，x40解：解：其对偶问题为其对偶问题为minw=20y1+20y2y1+2y21（1）2y1+y22（2）2y1+3y23（3）3y1+2y24（4）y1、y202x3*+3x4*=203x3*+
15、2x4*=20解得解得x3*=x4*=4。故原问题的最优解故原问题的最优解为为X*=（0，0，4，4）T其对偶问题的最优解为其对偶问题的最优解为y1*=6/5，y2*=1/5。试试用互补松弛定理求该线用互补松弛定理求该线性规划问题的最优解。性规划问题的最优解。将将y1*=6/5，y2*=1/5代入上述约束代入上述约束条件，得（条件，得（1）、（）、（2）为严格不等）为严格不等式；由互补松弛定理可以推得式；由互补松弛定理可以推得x1*=0，x2*=0。又因又因y1*0，y2*0，故原问题的两个约束条件应取等故原问题的两个约束条件应取等式，所以式，所以定理定理2.52.5原问题单纯形表的检验数行对
16、应对偶问题的原问题单纯形表的检验数行对应对偶问题的一个基本解。一个基本解。该定理的进一步解释有：若原问题最优解存在，则原该定理的进一步解释有：若原问题最优解存在，则原问题最优单纯形表的检验数行中，松弛变量或剩余变问题最优单纯形表的检验数行中，松弛变量或剩余变量的检验数对应对偶问题的最优解。量的检验数对应对偶问题的最优解。例例2.4（原问题为极大化问题）（原问题为极大化问题）对于原问题：对于原问题：maxz=50x1+100x2x1+x23002x1+x2400x2250x1、x20其对偶问题为：其对偶问题为：minw=300y1+400y2+250y3y1+2y250y1+y2+y3100y1
17、、y2、y30表中表中x3、x4、x5为松弛变量；为松弛变量；原问题最优解为：原问题最优解为：X*=（500，250）T，z*=27500对偶问题的最优解为对偶问题的最优解为：Y*=（y1*，y2*，y3*）=（50，0，50），），w*=27500Cj50100000bCBXBx1x2x3x4x550x11010-15000x400-21150100x2010-01250z0050050-27500对偶问题最优对偶问题最优解解y1*y2*y3*解解原问题最优单纯形表如表所示，对应的对偶问题原问题最优单纯形表如表所示，对应的对偶问题最优解列于表中最后一行。最优解列于表中最后一行。例2.5 （原
18、问题为极小化问题）对于原问题：minz=2x1+3x2x1+x2350x11252x1+x2600x1、x20其对偶问题为：maxw=350y1+125y2+600y3y1+y2+2y32y1+y33y1、y20、y30解解 用以极小化为标准形式的单纯形法求得原问题最优单纯用以极小化为标准形式的单纯形法求得原问题最优单纯形表如下表所示，对应的对偶问题最优解列于表中最后一行。形表如下表所示，对应的对偶问题最优解列于表中最后一行。表中表中x3、x4为剩余变量，为剩余变量，x5为松弛变量；为松弛变量；原问题最优解为：原问题最优解为：X*=（250，100）T，Z*=800对偶问题的最优解为：对偶问题
19、的最优解为：Y*=（y1*，y2*，y3*）=（4，0，1），），w*=800Cj23000MMbCBXBx1x2x3x4x5x6x73X201-20-1201002X110101-102500X400111-1-1125-z00401-4+MM-800对偶问题最对偶问题最优解优解y1*y2*-y3*y1*+my2*+m从上述两个例子可以总结出：对偶问题的最从上述两个例子可以总结出：对偶问题的最优解对应原问题最优单纯形表中松弛变量检优解对应原问题最优单纯形表中松弛变量检验数的相反数或剩余变量的检验数。验数的相反数或剩余变量的检验数。一、资源的影子价格一、资源的影子价格(Shadow Price
20、)(Shadow Price)如前所述，若如前所述，若X*为线性规划为线性规划maxz=CX，AXb，X0的最优解，的最优解，则则z*=CX*；若；若Y*为其对偶问题的最优解，为其对偶问题的最优解，则则有有w*=Y*b。根据对偶定理有根据对偶定理有z*=w*即即z*=Y*b因此因此即即由此可以看出，对偶问题的最优解实际上是右端常数由此可以看出，对偶问题的最优解实际上是右端常数项的单位变化所引起的目标值的变化；项的单位变化所引起的目标值的变化；第三节第三节 对偶问题的经济意义对偶问题的经济意义若原问题描述的是资源有限条件下最优生产决策问题，若原问题描述的是资源有限条件下最优生产决策问题，则其对偶
21、问题的最优解则其对偶问题的最优解yi*(i=1,，m)表示表示第第i种资源种资源在最优生产决策下的边际值，即若其他条件不变，增在最优生产决策下的边际值，即若其他条件不变，增加单位加单位第第i种资源将会使目标函数值增加种资源将会使目标函数值增加yi*。其经济意义其经济意义是：是：yi*描述了描述了第第i种资源在具体生产中的一种资源在具体生产中的一种估价，这种估价不同于该种资源的市场价格，而是种估价，这种估价不同于该种资源的市场价格，而是该种资源在给定条件某生产的最优生产方案下的一种该种资源在给定条件某生产的最优生产方案下的一种实际存在而又看不见的真实价值，因此称之为实际存在而又看不见的真实价值，
22、因此称之为影子价影子价格格（shadowprice）。1)同一种资源在不同的生产条件或不同的范同一种资源在不同的生产条件或不同的范围可能有不同的影子价格；围可能有不同的影子价格；2)产品的市场价格变化，资源的影子价格也产品的市场价格变化，资源的影子价格也会发生变化；会发生变化；3)资源的数量结构不同，资源的影子价格也资源的数量结构不同，资源的影子价格也不同。不同。资源的影子价格是针对具体生产或具体企业而言的资源的影子价格是针对具体生产或具体企业而言的1)与资源的市场价格比较以决定是否安排生产或转让资与资源的市场价格比较以决定是否安排生产或转让资源或提高产品的价格；源或提高产品的价格；2)革新可
23、以提高资源的影子价格；革新可以提高资源的影子价格；3)可以指导管理部门对紧缺资源进行可以指导管理部门对紧缺资源进行“择优分配择优分配”；4)帮助预测产品的价格。因此，产品的价格应在帮助预测产品的价格。因此，产品的价格应在“成本成本”和影子价格之间；和影子价格之间；5)影子价格的高低可以作为同类企业经济效益的评估标影子价格的高低可以作为同类企业经济效益的评估标准之一。准之一。影子价格对于拥有资源的决策者有非常重要的作用影子价格对于拥有资源的决策者有非常重要的作用对于目标函数极小化约束条件为大等号的问题对于目标函数极小化约束条件为大等号的问题minz=CX，AXb，X0，其右端常数项可理解为其右端
24、常数项可理解为需要完成的任务。因此，该类线性规划一般为描述需要完成的任务。因此，该类线性规划一般为描述完成一定任务使耗费的资源最小的问题。此时，其完成一定任务使耗费的资源最小的问题。此时，其对偶问题的最优对偶问题的最优解解yi*(i=1,，m)表示第表示第i种任务的种任务的边际成本边际成本，即单位任务的增加引起的资源耗费的增，即单位任务的增加引起的资源耗费的增加量。加量。二、任务的边际成本二、任务的边际成本 (MarginalCost)M&D公司生产两种产品公司生产两种产品A和和B，根据现有库存水平和下根据现有库存水平和下个月的购买潜力分析，个月的购买潜力分析，M&D管理层确定管理层确定A和和
25、B的总产量的总产量至少达到至少达到350加仑。此外公司的一个主要客户订购了加仑。此外公司的一个主要客户订购了125加仑的产品加仑的产品A，该产量必须满足。产品该产量必须满足。产品A和产品和产品B的制造的制造时间分别是时间分别是2小时小时/加仑和加仑和1小时小时/加仑，下个月的总工作加仑，下个月的总工作时间是时间是600小时。公司的目标是在满足客户要求的前提小时。公司的目标是在满足客户要求的前提下，尽量降低成本。每加仑下，尽量降低成本。每加仑A的制造成本是的制造成本是2美元，每加美元，每加仑仑B的制造成本是的制造成本是3美元。美元。问题的线性规划模型为问题的线性规划模型为minz=2x1+3x2
26、x1=125x1+x2=3502x1+x2=600x1、x20无无论论对对偶偶问问题题的的最最优优解解表表示示的的是是资资源源的的影影子子价价格格还还是是任任务务的的边边际际成成本本，只只要要为为正正，则则表表示示右右端端常常数数项项增增加加目目标标函函数数值值增增加加，为为负负则则表表示示右右端端常常数数项项增增加加目目标标函函数数值值减减少少。而对于极大化的问题，目标函数值增加表明目标函数得而对于极大化的问题，目标函数值增加表明目标函数得到改善，对于极小化的问题，目标函数减少表明目标函到改善，对于极小化的问题，目标函数减少表明目标函数得到改善。为了二者的统一，定义如下对偶价格。数得到改善。
27、为了二者的统一，定义如下对偶价格。三、对偶价格三、对偶价格(DualPrice)定义定义2.2线性规划问题某约束条件的右端常数项的单位线性规划问题某约束条件的右端常数项的单位增加量所引起的目标函数的改善量称为该右端常数项的增加量所引起的目标函数的改善量称为该右端常数项的对偶价格对偶价格。因此，若对偶价格为正，则增加右端常数项，目标函数因此，若对偶价格为正，则增加右端常数项，目标函数值得到改善；若对偶价格为负，则增加右端常数项，目值得到改善；若对偶价格为负，则增加右端常数项，目标函数值将会标函数值将会“恶化恶化”。三、对偶价格三、对偶价格(DualPrice)根据该定义，对于极大化的问题，对偶价
28、格就等于其对偶问题的根据该定义，对于极大化的问题，对偶价格就等于其对偶问题的最优解；对于极小化问题，对偶价格就等于其对偶问题最优解的最优解；对于极小化问题，对偶价格就等于其对偶问题最优解的相反数。相反数。例如本节例例如本节例2.4的极大化问题三个约束条件的对偶价格分别为的极大化问题三个约束条件的对偶价格分别为50，0和和50；本节例本节例2.6的极小化问题两个约束条件的对偶价格分别为的极小化问题两个约束条件的对偶价格分别为360和和800；下面在举一个含有等号约束的例子。；下面在举一个含有等号约束的例子。例例2.7求下列线性规划问题各约束条件的对偶价格求下列线性规划问题各约束条件的对偶价格mi
29、nz=2x1+3x2+4x3x1+x2+x31202x1+x2+x360x1+2x2+x3=80x1、x2，x30用大用大M法（极小化为标准形式）求解得问题的最优单纯形表如表法（极小化为标准形式）求解得问题的最优单纯形表如表26。故对偶问题的最优解为故对偶问题的最优解为y1*=0，y2*=1/3，y3*=4/3。由于是极小化问由于是极小化问题，所以三个约束条件的对偶价格为对偶问题最优解的相反数，即题，所以三个约束条件的对偶价格为对偶问题最优解的相反数，即分别为分别为0、1/3和和4/3。即第二个约束条件的右端常数项增加。即第二个约束条件的右端常数项增加1个个单位，则目标函数值单位，则目标函数值
30、“恶化恶化”1/3个单位，减少个单位，减少一一个单位，则目标函个单位，则目标函数值数值“改善改善”1/3个单位。对于第一和第三个约束条件可作同样的分个单位。对于第一和第三个约束条件可作同样的分析。析。Cj23400MMbCBXBx1x2x3x4x5x6x70x2001/311/3-1/3-1/3220/32x1101/30-2/32/3-1/340/33x4011/301/3-1/32/3100/3-z007/301/31/3+M4/3+M-380/3对偶问题最对偶问题最优解优解y1*y2*y3*+M第六节第六节线性规划的应用线性规划的应用(ApplicationsofLP)线性规划是管理决策
31、制定的最成功的数量方线性规划是管理决策制定的最成功的数量方法之一。法之一。它广泛应用于化工、航空、钢铁、石油和其它广泛应用于化工、航空、钢铁、石油和其他工业。他工业。它研究的问题是多种多样的它研究的问题是多种多样的生产计划、生产计划、媒体选择、金融计划、资金预算、运输、工媒体选择、金融计划、资金预算、运输、工厂选择、生产组合、人员调配等等。厂选择、生产组合、人员调配等等。例例红旗商场是个中型的红旗商场是个中型的百货商场，它对售货人员的百货商场，它对售货人员的需求经过统计分析如表所示。需求经过统计分析如表所示。为了保证售货人员充分休息，为了保证售货人员充分休息，售货人员每周工作五天，休售货人员每
32、周工作五天，休息两天，并要求休息的两天息两天，并要求休息的两天是连续的，问应该如何安排是连续的，问应该如何安排售货人员的作息，既满足了售货人员的作息，既满足了工作需要又使配备的售货人工作需要又使配备的售货人员的人数最少？员的人数最少？时间时间所需售货员所需售货员星期日星期日星期一星期一星期二星期二星期三星期三星期四星期四星期五星期五星期六星期六28人人15人人24人人25人人19人人31人人28人人一、人力资源分配问题人力资源分配问题解：解：设设x1为星期一开始上班的人数为星期一开始上班的人数，x2为星期二开为星期二开始上班的人数，始上班的人数，x7星期日开始上班的人数。星期日开始上班的人数。
33、我们就可得到如下的数学模型：我们就可得到如下的数学模型：minx1+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。媒体媒体被告知的潜在被告知的潜在顾客数（人顾客数（人/次）次）广告费用广告费用（
34、元（元/次）次）媒体最高使媒体最高使用次数（次）用次数（次）每次宣传每次宣传的质量的质量日间电视日间电视夜间电视夜间电视日报日报周末新闻杂志周末新闻杂志电台广播电台广播10002000150025003001500300040010001001510254306590406020例例 某房地产开发公司正在建造一个湖边小区，公司准某房地产开发公司正在建造一个湖边小区，公司准备投入备投入3万元进行广告媒体宣传，希望能够吸引周围的中万元进行广告媒体宣传，希望能够吸引周围的中高收入家庭前来购房。目前有高收入家庭前来购房。目前有5种媒体可供选择，相关信种媒体可供选择，相关信息如表所示。息如表所示。对于这
35、次活动，公司有下列要求：至少进行对于这次活动，公司有下列要求：至少进行10次电视广次电视广告；至少有告；至少有5万名潜在顾客被告知；电视广告投入不超过万名潜在顾客被告知；电视广告投入不超过18000元。如何进行媒体组合，才能使广告质量最高？元。如何进行媒体组合，才能使广告质量最高？二、媒体选择二、媒体选择解解问题中媒体组合实际上就是要决定每种媒体的使用次数问题中媒体组合实际上就是要决定每种媒体的使用次数。设设x1、x2、x3、x4、x5分别表示表中日间电视、夜间电视、分别表示表中日间电视、夜间电视、日报、周末新闻杂志、电台广播五种媒体的使用次数。日报、周末新闻杂志、电台广播五种媒体的使用次数。
36、该问题的线性规划模型为该问题的线性规划模型为maxz=65x1+90x2+40x3+60x4+20x51500x1+3000x2+400x3+1000x4+100x5300001000x1+2000x2+1500x3+2500x4+300x550000x1+x2101500x1+3000x218000x115x210x325x44x530x1，x2，x3，x4，x50这是一个有这是一个有5个变量，个变量，9个约束条件的线性规个约束条件的线性规划模型，求解结果如下：划模型，求解结果如下：媒体媒体最佳播放次数（次）最佳播放次数（次）广告费用（元）广告费用（元）日间电视日间电视1015000日报日报
37、2510000周末新闻杂志周末新闻杂志22000电台广播电台广播303000被被告告知知的的顾顾客客数数=61500人人产产品品宣宣传传质质量量=2370目标函数最优值为：目标函数最优值为：2370变变量量最最优优解解检检验数验数x1100x2065x3250x420x5300约束约束松弛松弛/剩余变量剩余变量对偶价格对偶价格100.0621150003025430000550610070168209014包括：资本预算、资产分配、财政计划等包括：资本预算、资产分配、财政计划等（一）投资组合（一）投资组合问题：问题：从多种投资选择中选择具体的投资：股票和从多种投资选择中选择具体的投资：股票和债
38、券、基金、保险等；债券、基金、保险等；目标目标：预期收益极大化、风险最小化：预期收益极大化、风险最小化约束约束：投资类型、国家法律、公司政策、风险或效：投资类型、国家法律、公司政策、风险或效益限制等益限制等三、财政应用三、财政应用案例案例Welte公司拥有公司拥有100000美元，财务专家确定了如美元，财务专家确定了如下下5个投资机会，并预计了它们的年收益：个投资机会，并预计了它们的年收益：1.在石油或钢铁行业投资不能超过在石油或钢铁行业投资不能超过50000每元；每元；2.对政府债券的投资至少相当于对钢铁行业投资的对政府债券的投资至少相当于对钢铁行业投资的25%；3.对太平洋石油的投资不能多
39、于整个石油行业投资的对太平洋石油的投资不能多于整个石油行业投资的60%求预期收益最大的投资方案。求预期收益最大的投资方案。投资投资预期收益率（预期收益率（%）大西洋石油大西洋石油太平洋石油太平洋石油中西部钢铁中西部钢铁Huber钢铁钢铁政府债券政府债券7.310.36.47.54.5设：设：Atl=大西洋石油投资大西洋石油投资；Pac=太平洋石油投资太平洋石油投资；Mid=中西部钢铁投资中西部钢铁投资；Hub=Huber钢铁投资钢铁投资；Gov=政府债券投资政府债券投资则问题的数学模型为：则问题的数学模型为：Maxz=0.073Atl+0.103Pac+0.064Mid+0.075Hub+0.
40、045GovAtl+Pac+Mid+Hub+Gov=100000总投资总投资Atl+Pac50000石油投资限制石油投资限制Mid+Hub50000钢铁投资限制钢铁投资限制-0.25Mid0.25Hub+Gov0政府债券比例政府债券比例-0.6Atl+0.4Pac0太平洋石油限制太平洋石油限制Atl,Pac,Mid,Hub,Gov0(二二)、金融计划、金融计划案例案例某公司现有某公司现有68名员工申请提前退休。公司必须名员工申请提前退休。公司必须在此后的在此后的8年内对这些员工分期支付一定数量的现金，年内对这些员工分期支付一定数量的现金，如下表所示。如下表所示。为了完成这项现金支付任务，公司的
41、财务人员必须现在为了完成这项现金支付任务，公司的财务人员必须现在就为此制定一个投资计划。投资计划有政府债券投资和就为此制定一个投资计划。投资计划有政府债券投资和银行储蓄两种方式组成。银行储蓄两种方式组成。年份（年）年份（年）12345678合计合计现现金金支支付付(千千元元)430 210 222 231 240 195 225 255 2008注意注意:三种政府债券的票面价值均为三种政府债券的票面价值均为1000元，债券到元，债券到期时按票面价值进行支付，利率的计算也以票面的价值期时按票面价值进行支付，利率的计算也以票面的价值为基准。银行储蓄年利率为为基准。银行储蓄年利率为4%。如何安排投资
42、计划，使。如何安排投资计划，使公司以最小的投资额完成对退休员工的现金支付任务？公司以最小的投资额完成对退休员工的现金支付任务？政府债券投资有三种债券类型可供选择，如下表所示。政府债券投资有三种债券类型可供选择，如下表所示。债券债券价格（元）价格（元）利率（利率（%）到期年限到期年限111508.8755210005.50063135011.7507解：解：1确定决策变量确定决策变量设设F为完成投资计划所需要的总资金额。为完成投资计划所需要的总资金额。x1、x2、x3分别分别表示债券表示债券1、2、3的购买的购买量；量；yi(i=1,，8)表示表示第第i年初银行储蓄的投资额。年初银行储蓄的投资额
43、。2确定约束条件确定约束条件这类问题的一个典型特征就是每年现金支付的一般表这类问题的一个典型特征就是每年现金支付的一般表达式为：达式为：年初可用资金额年初可用资金额当年用于债券和储蓄的资金额当年用于债券和储蓄的资金额=当年现金支付当年现金支付于是有于是有F1.15x11x21.35x3y1=430（第第1年）年）对于第二年，用于三种债券投资的第一年利息加上第对于第二年，用于三种债券投资的第一年利息加上第一年储蓄利息为年初可用资金，第二年用于储蓄的资一年储蓄利息为年初可用资金，第二年用于储蓄的资金为金为y2，因此有因此有0.08875x1+0.055x2+0.1175x3+1.04y1y2=21
44、0（第第2年）年）同理对于其它年份有同理对于其它年份有0.08875x1+0.055x2+0.1175x3+1.04y2y3=222（第第3年）年）0.08875x1+0.055x2+0.1175x3+1.04y3y4=231（第第4年）年）0.08875x1+0.055x2+0.1175x3+1.04y4y5=240（第第5年）年）1.08875x1+0.055x2+0.1175x3+1.04y5y6=195（第第6年）年）1.055x2+0.1175x3+1.04y6y7=225（第第7年）年）1.1175x3+1.04y7y8=255（第第8年年）因此事实上因此事实上，y8的值应为的值应
45、为0，若大于，若大于0，那么对应的投，那么对应的投资计划必定不是最优的。资计划必定不是最优的。3.确定目标函数确定目标函数目标就是使满足要求的投资额最小，目标就是使满足要求的投资额最小，即即Minz=F综合有如下数学模型综合有如下数学模型Minz=FF1.15x11x21.35x3y1=4300.08875x1+0.055x2+0.1175x3+1.04y1y2=2100.08875x1+0.055x2+0.1175x3+1.04y2y3=2220.08875x1+0.055x2+0.1175x3+1.04y3y4=2310.08875x1+0.055x2+0.1175x3+1.04y4y5=
46、2401.08875x1+0.055x2+0.1175x3+1.04y5y6=1951.055x2+0.1175x3+1.04y6y7=2251.1175x3+1.04y7y8=255x1，x2，x30，yi0，i=1，8该线性规划模型的求解结果为该线性规划模型的求解结果为目标函数最优值为：目标函数最优值为：1728.794变量变量最优解最优解检验数检验数F1728.7940x1144.9880x2187.8560x3228.1880y1636.1480y2501.6060y3349.6820y4182.6810y500.064y600.0126y700.0213y800.671即得到最佳投资
47、计划如下表所示即得到最佳投资计划如下表所示: : 债债券券购买量购买量投资额投资额(千元千元)年份年份储蓄额储蓄额(千元千元)1144.9881.150144.988=166.7361636.1482187.8561.000187.856=187.8562501.6063228.1881.350228.188=308.0543349.682总投资额总投资额F=1728794元元4182.681580 约束 松弛/剩余变量 对偶价格101.000200.962300.925400.889500.855600.760700.719800.671结果分析：结果分析：前前4年的储蓄额均大于年的储蓄额均
48、大于0，可见从第，可见从第6年起债券的利息年起债券的利息和债券到期收入才能够完全满足当前现金支付需要。和债券到期收入才能够完全满足当前现金支付需要。每一个约束条件的对偶价格均为负值，说明减少任每一个约束条件的对偶价格均为负值，说明减少任何一年的现金支付都将有利于公司总投资额的降低。何一年的现金支付都将有利于公司总投资额的降低。对偶价格的逐年降低也说明了，在前面年份减少现对偶价格的逐年降低也说明了，在前面年份减少现金支付将对总投资额的减少更为有效。从而暗示了金支付将对总投资额的减少更为有效。从而暗示了公司可以适当减少前面年份的现金支付量，而在后公司可以适当减少前面年份的现金支付量，而在后面年份进
49、行补足。面年份进行补足。(一一)制造或购买决策制造或购买决策案例案例某公司有某公司有，两种产品，预计两种产品两种产品，预计两种产品的市场需求量分别为的市场需求量分别为3000件和件和2000件。两种产品件。两种产品均均由由a、b、c三个部件组成，各部件生产消耗工时和三个部件组成，各部件生产消耗工时和自制自制/外购成本如下表所示。外购成本如下表所示。部件部件单位部件制造工单位部件制造工时（分钟）时（分钟）自制成本自制成本（元（元/分钟）分钟）购买成本购买成本（元（元/小时）小时）A1.00.500.60B产品产品3.03.754.00产品产品2.53.303.90C产品产品1.00.600.65
50、产品产品1.50.750.78四、生产管理应用四、生产管理应用部件部件单位部件制造工单位部件制造工时（分钟）时（分钟）自制成本自制成本（元（元/分钟）分钟）购买成本购买成本（元（元/小时）小时）A1.00.500.60B产品产品3.03.754.00产品产品2.53.303.90C产品产品1.00.600.65产品产品1.50.750.78由于生产能力有限，公司只有由于生产能力有限，公司只有200个正常制造工时和个正常制造工时和50个加班工时可用于这两种产品的生产。每个加班工时需个加班工时可用于这两种产品的生产。每个加班工时需额外支付额外支付9元。如何安排部件自制和外购的数量，从而使元。如何安
51、排部件自制和外购的数量，从而使总成本（包括生产成本、外购成本和加工费用）最低？总成本（包括生产成本、外购成本和加工费用）最低？解：解：1确定决策变量确定决策变量设设xa、xb1、xb2、xc1、xc2分分别表示别表示a部件、用于产品部件、用于产品的的b部件、用于产品部件、用于产品的的b部件、部件、用于产品用于产品的的c部件、用于产品部件、用于产品的的c部件的自制量。相部件的自制量。相应地，设应地，设ya、yb1、yb2、yc1、yc2分别为各部件的外购量。分别为各部件的外购量。设设y0为加班工时数。为加班工时数。2确定约束条件确定约束条件a部件的需求量约束部件的需求量约束xa+ya=5000用
52、于产品用于产品的的b部件的需求量约束部件的需求量约束xb1+yb1=3000用于产品用于产品的的b部件的需求量约束部件的需求量约束xb2+yb2=2000用于产品用于产品的的c部件的需求量约束部件的需求量约束xc1+yc1=3000用于产品用于产品的的c部件的需求量约束部件的需求量约束xc2+yc2=2000最大加班工时数约束最大加班工时数约束y050最大生产能力约束最大生产能力约束xa+3xb1+2.5xb2+xc1+1.5xc220060+60y03确定目标函数确定目标函数目标是使总成本最小，即目标是使总成本最小，即Minz=0.5xa+0.6ya+3.75xb1+4yb1+3.3xb2+
53、3.9yb2+0.6xc1+0.65yc1+0.75xc2+0.78yc2+9y0因此，该问题的数学模型为因此，该问题的数学模型为Minz=0.5xa+0.6ya+3.75xb1+4yb1+3.3xb2+3.9yb2+0.6xc1+0.65yc1+0.75xc2+0.78yc2+9y0xa+ya=5000xb1+yb1=3000xb2+yb2=2000xc1+yc1=3000xc2+yc2=2000y050xa+3xb1+2.5xb2+xc1+1.5xc260y012000xa、xb1、xb2、xc1、xc2、yb1、yb2、yc1、yc2、y00该线性规划模型的求解结果为该线性规划模型的求解
54、结果为目标函数最优值为：目标函数最优值为：1728.794变变量量最最优优解解检检验验数数xa50000.000ya00.017xb16670.000ybl23330.000xb220000.000yb200.392xc100.033yc130000.000xc200.095yc220000.000y004.000约束约束松弛松弛/剩余变量剩余变量对偶价格对偶价格100.583204.000303.508400.650500.7806500.000700.083部件部件自制量（件）自制量（件）购买量（件）购买量（件）a50000b产品产品6672333产品产品20000c产品产品03000产品
55、产品02000总成本总成本=24，443.33元元目标函数系数范围目标函数系数范围变变量量下下限限当当前前值值上限上限xa无下限无下限0.5000.517ya0.5830.600无上限无上限xb13.7003.7503.850ybl3.9004.0004.050xb2无无下下限限3.3003.692yb23.5083.900无上限无上限xc10.5670.600无上限无上限yc1无下限无下限0.6500.683xc20.6550.750无上限无上限yc2无下限无下限0.7800.875y05.0009.000无上限无上限右端常数项范围右端常数项范围约约束束下下限限当当前前值值上限上限10.00
56、0500070002666.6673000无上限无上限30.0002000280040.0003000无上限无上限50.0002000无上限无上限60.00050无上限无上限710000.0001200019000(二二)生产计划问题生产计划问题生产计划问题是线性规划应用最为广泛的领域之一生产计划问题是线性规划应用最为广泛的领域之一;问题描述问题描述:一定时期内，经理必须决定生产水平，一定时期内，经理必须决定生产水平，使公司能够满足生产需求，在受到产品生产量、劳使公司能够满足生产需求，在受到产品生产量、劳动力水平以及存储空间上所有限制的同时，还要使动力水平以及存储空间上所有限制的同时，还要使生
57、产成本最小。生产成本最小。线性规划解决该类问题的线性规划解决该类问题的优点优点：可重复利用已建立：可重复利用已建立好的线性规划模型指定不同时期的生产计划好的线性规划模型指定不同时期的生产计划。案例案例Bollinger电子公司接到未来三个月的两种产品的定单：电子公司接到未来三个月的两种产品的定单：生产部门分析，生产费用有以下方面：生产部门分析，生产费用有以下方面：（1）生产成本；）生产成本；（2）库存储成本；（）库存储成本；（3）改变生产力水平所需费用。）改变生产力水平所需费用。有关数据如下有关数据如下表表组件组件需求需求生产成本生产成本(美元美元/件件)存储成本存储成本(美元美元/件件月）月
58、）改变生产力改变生产力费用费用(美元美元/件件)四月四月五月五月六月六月322A802B1000100030005005000300020100.30.15增加：增加：0.5减少：减少：0.2现现要求制定一个未来要求制定一个未来3个月的生产计划，使总成本最小。个月的生产计划，使总成本最小。Bollinger公司生产力、劳动力能力和库存能力公司生产力、劳动力能力和库存能力月份月份生产能力生产能力(h)劳动力能力劳动力能力(h)库存能力库存能力（面积）（面积）四月四月五月五月六月六月400500600300300300100001000010000单位组件对生产机器、劳动力和存储的要求单位组件对生
59、产机器、劳动力和存储的要求组件组件机器机器(h/单位单位)劳动力劳动力(h/单位单位)库存库存(面积面积/单位单位)322A802B0.100.080.050.0723决策变量（能描述问题）决策变量（能描述问题）：x1i=第第i月生产月生产322A的数量的数量；i=1，2，3(四、五、六月四、五、六月)x2i=第第i月生产月生产802B的数量；的数量；i=1，2，3s1i=第第i月末月末322A的存储量；的存储量；i=1，2，3s2i=第第i月末月末802B的存储量；的存储量；i=1，2，3Ii=第第i月月生产量增加量；生产量增加量；i=1，2，3Di=第第i月生产量下降量；月生产量下降量；i
60、=1，2，3目标函数目标函数minz=20x11+20x12+20x13+10x21+10x22+10x23+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=1000x11-s11=500200+x21-s21=1000x11-s1
61、1=800第二个月第二个月s11+x12s12=3000s21+x22s22=500第三个月第三个月s12+x13s13=5000s22+x23s23=3000（2）期末库存量约束期末库存量约束s13400;s23200(3)机器生产能力约束机器生产能力约束0.1x11+0.08x21400第一个月第一个月0.1x12+0.08x22500第二个月第二个月0.1x13+0.08x23600第三个月第三个月(4)劳动力能力约束劳动力能力约束0.05x11+0.07x21300第一个月第一个月0.05x12+0.07x22300第二个月第二个月0.05x13+0.07x23300第三个月第三个月(
62、5)库存能力约束库存能力约束2s11+3s2110000第一个月第一个月2s12+3s2210000第二个月第二个月2s13+3s2310000第三个月第三个月(6)生产量变化约束生产量变化约束本月产量本月产量-上月产量上月产量=本月产量变化量本月产量变化量四月份四月份x11+x212500=I1D1x11+x21I1+D1=2500五月份五月份x12+x22(x11+x21)=I2D2x12+x22(x11+x21)I2+D2=0六月份六月份x13+x23(x12+x22)=I3D3x13+x23(x12+x22)I3+D3=0注意：注意：这里的这里的Ii和和Di均为非负变量，而且至少有一个
63、为零。均为非负变量，而且至少有一个为零。计算机求解结果：计算机求解结果：（三）劳动力分配问题三）劳动力分配问题问题描述：一个企业有多个生产部门，一定时期各生问题描述：一个企业有多个生产部门，一定时期各生产部门劳动力数量一定，但劳动力可以在各部门之间产部门劳动力数量一定，但劳动力可以在各部门之间转移或再分配转移或再分配最佳的分配方案。最佳的分配方案。案例案例（麦科米克公司劳动时间分配问题）麦科米克公司劳动时间分配问题）麦科米克公司单位产品劳动小时数和总体有效生产时间麦科米克公司单位产品劳动小时数和总体有效生产时间部门部门单位劳动时间单位劳动时间总总可用时间可用时间产品产品1产品产品212340.
64、650.451.000.150.950.850.700.306500600070001400单位利润单位利润109设设P1,P2分别为产品分别为产品1、2的产量，则问题的数学模型为：的产量，则问题的数学模型为：maxz=10P1+9P20.65P1+0.95P265000.45P1+0.85P260001.00P1+0.70P270000.15P1+0.30P21400P1、P20计算机求解结果计算机求解结果目标函数最优值为：目标函数最优值为：73589.744变变量量最最优优解解检检验验数数P15743.590P21794.870约束约束松弛松弛/剩余变量剩余变量对偶价格对偶价格11061.
65、583021889.7440308.4624010.256问题问题：若部门之间可利用时间可以调配，是否可以增：若部门之间可利用时间可以调配，是否可以增加总利润？加总利润？假设各部门之间交叉培训能力和可转移时间信息如下假设各部门之间交叉培训能力和可转移时间信息如下原原部门部门交叉培训后允许转移到的部门交叉培训后允许转移到的部门最大可转移最大可转移时间时间12341234yesYesyesYesYesYesYes400800100200引入新的决策变量：引入新的决策变量：tij=从从i部门转移到部门转移到j部门的劳动时间部门的劳动时间bi=分配给第分配给第i部门的劳动时间部门的劳动时间这样，问题的
66、约束条件如下：这样，问题的约束条件如下：（1）生产能力约束）生产能力约束0.65P1+0.95P2b100.45P1+0.85P2b201.00P1+0.70P2b300.15P1+0.30P2b30（2）劳动时间平衡约束劳动时间平衡约束分配到本部门的劳动时间分配到本部门的劳动时间=总可用时间总可用时间+转入时间转入时间转出时间转出时间因此：因此：b1=6500+t41-t12-t13b2=6000+t12+t42-t23-t24b3=7000+t13+t23-t34b4=1400+t24+t34-t41-t42（3）最大转移时间约束最大转移时间约束t12+t13400t34100t23+t2
67、4800t41+t42200b1-t41+t12+t13=6500b2-t12-t42+t23+t24=6000b3-t13-t23+t34=7000b4-t24-t34+t41+t42=1400问题描述问题描述：当混合两种以上资源生产一种以上产品时，：当混合两种以上资源生产一种以上产品时，管理者必须决定每种资源的购买量以在成本最低的情管理者必须决定每种资源的购买量以在成本最低的情况下满足产品的需要。况下满足产品的需要。应用领域：石油化工、食品行业等；应用领域：石油化工、食品行业等；案例案例（大绳石油公司混合问题）大绳石油公司混合问题）大绳石油公司混合问题的成本和供给大绳石油公司混合问题的成本
68、和供给石油成分石油成分成本成本(美元美元/加仑加仑)最大供应量最大供应量(加仑加仑)1230.500.600.8450001000010000五、混合问题五、混合问题决策变量：决策变量：最终产品最终产品一般规格汽油一般规格汽油特殊规格汽油特殊规格汽油原材料原材料成分成分1成分成分2成分成分3X1RX2RX3RX1PX2PX3P目标函数目标函数：MaxZ=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大绳石油
69、公司混合问题的具体产品要求大绳石油公司混合问题的具体产品要求产品产品规格规格价格价格一般规格汽油一般规格汽油高级规格汽油高级规格汽油成分成分130%,成分成分240%,成分成分320%成分成分125%,成分成分240%,成分成分330%1.001.08约束条件约束条件：（1）供应量约束）供应量约束X1R+X1P5000X2R+X2P10000X3R+X3P10000（2）比例约束比例约束X1R/（X1R+X2R+X3R）0.3即即0.7X1R-0.3X2R-0.3X3R0同理有同理有-0.4X1R+0.6X2R-0.4X3R0-0.2X1R-0.2X2R+0.8X3R00.75X1P-0.25
70、X2P-0.25X3P0-0.4X1P+0.6X2P-0.4X3P0-0.3X1P-0.3X2P+0.7X3P0(3)产量约束产量约束X1R+X2R+X3R10000早期由美国航空公司在是否决定折价出售和出售多早期由美国航空公司在是否决定折价出售和出售多少飞机座位时开发的；通过制定出售折扣座位和原少飞机座位时开发的；通过制定出售折扣座位和原价座位的最优决策，航空公司可以在增加平均乘客价座位的最优决策，航空公司可以在增加平均乘客数的同时使混合出售两种座位的所得收益最大化。数的同时使混合出售两种座位的所得收益最大化。收益管理用于其他产业只是最近的事：定价策略、收益管理用于其他产业只是最近的事：定价策略、超额预定策略、短期供应决策、长期资产管理等。超额预定策略、短期供应决策、长期资产管理等。六、收益管理六、收益管理线性规划应用小结线性规划应用小结线性规划有着广泛的应用；线性规划有着广泛的应用；线性规划的应用非常灵活；线性规划的应用非常灵活；所讲案例只是真实情况的缩微；所讲案例只是真实情况的缩微；第二章第二章 结束结束
