第二章 线性规划进一步研究

1、第一节第一节 对偶问题对偶问题 (dual problem)线性规划早期发展过程中的最为重要的理线性规划早期发展过程中的最为重要的理论成果之一就是线性规划的对偶问题及相论成果之一就是线性规划的对偶问题及相关理论的提出。线性规划的对偶理论解释关理论的提出。线性规划的对偶理论解释资源的影子价格、线性规划问题的灵敏度资源的影子价格、线性规划问题的灵敏度分析等的理论基础。分析等的理论基础。一、对偶问题的提出 例1 （生产计划问题）某企业利用（生产计划问题）某企业利用a、b、c三种资源，三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、

2、单位产品利润等数据如下表，问如何安排生产计的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？划使企业利润最大？ 产产 品品资资 源源甲甲乙乙资源限制资源限制abc120111300kg400kg250kg单位产品利润单位产品利润(元元/件件)50100 决策变量决策变量：x1、x2分别代表甲、乙两种产品的生分别代表甲、乙两种产品的生产数量。产数量。即有数学模型（问题即有数学模型（问题a）：）：问题问题a max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20称之为上述问题的数学模型。称之为上述问题的数学模型。 同样是上述问

3、题，提问同样是上述问题，提问：企业不安排生产，而转让三：企业不安排生产，而转让三种资源，应如何给三种资源定价？种资源，应如何给三种资源定价？ 决策变量决策变量：y1、y2、y3分别代表分别代表a、b、c三种资源的价三种资源的价格（最低转让净收入）。格（最低转让净收入）。 约束条件约束条件1：生产一件产品甲所耗资源数量转让所得净收入生产一件产品甲所耗资源数量转让所得净收入不能低于一不能低于一 件产品甲所获利润，即：件产品甲所获利润，即： 1y1+ 2y2 50 约束条件约束条件2：生产一件产品乙所耗资源数量转让所得净收入：生产一件产品乙所耗资源数量转让所得净收入不能低于一不能低于一 件产品乙所获

4、利润，即：件产品乙所获利润，即： 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的的对偶问题对偶问题，

5、问题，问题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+

6、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 即两线性规划问题互为对偶。即两线性规划问题互为对偶。 事实上，任一线性规划问题都有一个固定的线性事实上，任一线性规划问题都有一个固定的线性规划问题与之对偶，

7、且二者互为对偶关系，线性规划问题与之对偶，且二者互为对偶关系，线性规划的这种性质称为规划的这种性质称为对称性对称性。 更进一步有，对于线性规划问题：更进一步有，对于线性规划问题：max z=cx；ax = b，x0 其对偶问题为：其对偶问题为：min w=yb；yac，y无限制无限制 根据以上分析，线性规划原问题与对偶问题的数量根据以上分析，线性规划原问题与对偶问题的数量关系可用下表描述。关系可用下表描述。原问题原问题（或对偶问题或对偶问题）对偶问题对偶问题（或原问题或原问题）目标函数目标函数max zmin w目标函数目标函数变量变量n个个00无约束无约束n个个=约束条件约束条件约束条件约束

8、条件m个个=m个个00无约束无约束变量变量约束条件右端常数项约束条件右端常数项目标函数变量系数目标函数变量系数目标函数变量系数目标函数变量系数约束条件右端常数项约束条件右端常数项 例例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 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题 m

9、in 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一、单纯形法的矩阵描述一、单纯形法的矩阵描述设有线性规划问题设有线性规划问题max z=cxaxbx0加上松弛变量加上松弛变量xs=（xn+1，xn+2，xn+m）t，将其，将其化为标准形式得到化为标准形式得到max z=cx+

10、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）t，c=（cb，cn） 这样这样 因而有因而有 bxb+nxn + i xs = b 即即 xb = b-1bb-1nxnb-1xs 用非基变量用非基变量xn表示目标函数有表示目标函数有

11、 = cbxb+cnxn+0xsbnbnsssxx(a,i)= (b,n,i) x= bx+nx +ixxxbsbnsnxz =cx+0x =(c ,c )+0xx 将将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）

12、 若将基变量一起考虑有若将基变量一起考虑有 =（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，则线性规划问题有无界解。，则线性规划问题有无界解。ccbcn0bcbxbxbxnxsc

13、bxbib-1nb-1b-1b z0cncbb-1n-cbb-1-cbb-1b上述过程可用如下单纯形表描述。上述过程可用如下单纯形表描述。定理定理2.1(2.1(弱对偶定理弱对偶定理) ) 设设x(0)是原问题是原问题max z=cx，axb，x0的可行解的可行解 y(0)是其对偶问题是其对偶问题min w=yb，yac，y0的可行解的可行解则则 cx（0）y（0）b。 原问题任一可行解对应的目标函数值不大于其对偶问题原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值的任一可行解对应目标函数值?二、对偶问题基本定理二、对偶问题基本定理定理定理2.2(2.2(最优性定理最

14、优性定理) ) 设设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(2.3(对偶定理对偶定理) ) 若原问题若原问题max z=cx，axb，x0有最优解，有最优解，则其对偶问题则其对偶问题min w=yb，yac，y0 一定有最优解，一定有最优解，且二者的目标函数值相等。且二者的目标函数值相等。定理定理2.4(2.4(互补松弛定理互补松弛定理) ) 原问题原问题max z=cx

15、，axb，x0及其及其对偶问题对偶问题min w=yb，yac，y0 的可行解的可行解x（0）、y（0）是最优解是最优解的充要条件是的充要条件是 y（0）xs = 0 ； ysx（0）= 0 其中，其中，xs、ys分别是原问题松弛变量向量和对偶问题剩余变量向量。分别是原问题松弛变量向量和对偶问题剩余变量向量。 例例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

16、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代入上述约束代入上述约束条件，得（条件，得（1）、（）、（2）为严格不等）为严格不等式；由互补松弛定理可以推得式；由互补松弛定理

17、可以推得x1*=0，x2*=0。又因。又因y1*0，y2*0，故原问题的两个约束条件应取等式，故原问题的两个约束条件应取等式，所以所以定理定理2.52.5 原问题单纯形表的检验数行对应对偶问题的原问题单纯形表的检验数行对应对偶问题的一个基本解。一个基本解。 该定理的进一步解释有：若原问题最优解存在，则原该定理的进一步解释有：若原问题最优解存在，则原问题最优单纯形表的检验数行中，松弛变量或剩余变问题最优单纯形表的检验数行中，松弛变量或剩余变量的检验数对应对偶问题的最优解。量的检验数对应对偶问题的最优解。 例例2.4 （原问题为极大化问题）（原问题为极大化问题） 对于原问题：对于原问题： max

18、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、x4、x5为松弛变量；为松弛变量； 原问题最优解为：原问题最优解为：x*=（500，250）t， z*=27500 对偶问题的最优解为对偶问题的最优解为：y*=（y1*，y2*，y3*）=（50，0，50），）， w*=27500cj50100000b cbxb x1 x2x3x4x5 50 x11010-1500 0 x400-21150

19、 100 x2010-01250 z0050050-27500对偶问题最优对偶问题最优解解 y1*y2*y3* 解解 原问题最优单纯形表如表所示，对应的对偶问原问题最优单纯形表如表所示，对应的对偶问题最优解列于表中最后一行。题最优解列于表中最后一行。 例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 解解 用以极小化为标准形式的单纯形法求得原问题最优单用以极小化为标准形式

20、的单纯形法求得原问题最优单纯形表如下表所示，对应的对偶问题最优解列于表中最后纯形表如下表所示，对应的对偶问题最优解列于表中最后一行。一行。表中表中x3、x4为剩余变量，为剩余变量，x5为松弛变量；为松弛变量；原问题最优解为：原问题最优解为：x*=（250，100）t， z*=800对偶问题的最优解为：对偶问题的最优解为：y*=（y1*，y2*，y3*）=（4，0，1），）， w*=800cj23000mmb cbxb x1 x2x3x4x5x6x73x201-20-1201002x110101-102500x400111-1-1125 -z00401-4+mm-800对偶问题最对偶问题最优解优

21、解 y1*y2*-y3* y1*+m y2*+m 从上述两个例子可以总结出：对偶问题的最从上述两个例子可以总结出：对偶问题的最优解对应原问题最优单纯形表中松弛变量检优解对应原问题最优单纯形表中松弛变量检验数的相反数或剩余变量的检验数。验数的相反数或剩余变量的检验数。一、资源的影子价格一、资源的影子价格(shadow price)(shadow price) 如前所述，若如前所述，若x*为线性规划为线性规划max z=cx，axb，x0的最优解，的最优解，则则z*=cx*；若；若y*为其对偶问题的最优解，为其对偶问题的最优解，则则有有w*=y*b。根据对偶定理有。根据对偶定理有 z*=w* 即即

22、 z*=y*b 因此因此 即即 由此可以看出，对偶问题的最优解实际上是右端常数由此可以看出，对偶问题的最优解实际上是右端常数项的单位变化所引起的目标值的变化；项的单位变化所引起的目标值的变化；/*z* *b b = = y y/ *iiyzbi=1,.,m第三节第三节 对偶问题的经济意义对偶问题的经济意义 若原问题描述的是资源有限条件下最优生产决策问题，若原问题描述的是资源有限条件下最优生产决策问题，则其对偶问题的最优解则其对偶问题的最优解yi*(i=1,，m)表示第表示第i种资源在种资源在最优生产决策下的边际值，即若其他条件不变，增加最优生产决策下的边际值，即若其他条件不变，增加单位第单位第

23、i种资源将会使目标函数值增加种资源将会使目标函数值增加yi*。 其经济意义其经济意义是：是：yi*描述了第描述了第i种资源在具体生产中的一种资源在具体生产中的一种估价，这种估价不同于该种资源的市场价格，而是种估价，这种估价不同于该种资源的市场价格，而是该种资源在给定条件某生产的最优生产方案下的一种该种资源在给定条件某生产的最优生产方案下的一种实际存在而又看不见的真实价值，因此称之为实际存在而又看不见的真实价值，因此称之为影子价影子价格格（shadow price）。1) 同一种资源在不同的生产条件或不同的范同一种资源在不同的生产条件或不同的范围可能有不同的影子价格；围可能有不同的影子价格；2)

24、 产品的市场价格变化，资源的影子价格也产品的市场价格变化，资源的影子价格也会发生变化；会发生变化；3) 资源的数量结构不同，资源的影子价格也资源的数量结构不同，资源的影子价格也不同。不同。资源的影子价格是针对具体生产或具体企业而言的资源的影子价格是针对具体生产或具体企业而言的1)与资源的市场价格比较以决定是否安排生产或转让资与资源的市场价格比较以决定是否安排生产或转让资源或提高产品的价格；源或提高产品的价格；2)革新可以提高资源的影子价格；革新可以提高资源的影子价格；3)可以指导管理部门对紧缺资源进行可以指导管理部门对紧缺资源进行“择优分配择优分配”；4)帮助预测产品的价格。因此，产品的价格应

25、在帮助预测产品的价格。因此，产品的价格应在“成本成本”和影子价格之间；和影子价格之间；5)影子价格的高低可以作为同类企业经济效益的评估标影子价格的高低可以作为同类企业经济效益的评估标准之一。准之一。影子价格对于拥有资源的决策者有非常重要的作用影子价格对于拥有资源的决策者有非常重要的作用 对于目标函数极小化约束条件为大等号的问题对于目标函数极小化约束条件为大等号的问题 min z=cx，axb，x0，其右端常数项可理解为，其右端常数项可理解为需要完成的任务。因此，该类线性规划一般为描述需要完成的任务。因此，该类线性规划一般为描述完成一定任务使耗费的资源最小的问题。此时，其完成一定任务使耗费的资源

26、最小的问题。此时，其对偶问题的最优对偶问题的最优解解yi*(i=1,，m)表示第表示第i种任务的种任务的边际成本边际成本，即单位任务的增加引起的资源耗费的增，即单位任务的增加引起的资源耗费的增加量。加量。二、任务的边际成本二、任务的边际成本 (marginal cost) m&d公司生产两种产品公司生产两种产品a和和b，根据现有库存水平和下，根据现有库存水平和下个月的购买潜力分析，个月的购买潜力分析，m&d管理层确定管理层确定a和和b的总产量的总产量至少达到至少达到350加仑。此外公司的一个主要客户订购了加仑。此外公司的一个主要客户订购了125加仑的产品加仑的产品a，该产量必须

27、满足。产品，该产量必须满足。产品a和产品和产品b的制造的制造时间分别是时间分别是2小时小时/加仑和加仑和1小时小时/加仑，下个月的总工作加仑，下个月的总工作时间是时间是600小时。公司的目标是在满足客户要求的前提小时。公司的目标是在满足客户要求的前提下，尽量降低成本。每加仑下，尽量降低成本。每加仑a的制造成本是的制造成本是2美元，每加美元，每加仑仑b的制造成本是的制造成本是3美元。美元。问题的线性规划模型为问题的线性规划模型为 min z=2x1+3x2 x1 = 125 x1 + x2 = 350 2x1+ x2 =600 x1、x20 无论对偶问题的最优解表示的是资源的影子价格还是任无论对

28、偶问题的最优解表示的是资源的影子价格还是任务的边际成本，只要为务的边际成本，只要为正正，则表示右端常数项增加目标，则表示右端常数项增加目标函数值函数值增加增加，为，为负负则表示右端常数项增加目标函数值则表示右端常数项增加目标函数值减减少少。 而对于极大化的问题，目标函数值增加表明目标函数得而对于极大化的问题，目标函数值增加表明目标函数得到改善，对于极小化的问题，目标函数减少表明目标函到改善，对于极小化的问题，目标函数减少表明目标函数得到改善。为了二者的统一，定义如下对偶价格。数得到改善。为了二者的统一，定义如下对偶价格。三、对偶价格三、对偶价格(dual price) 定义定义2.2 线性规划

29、问题某约束条件的右端常数项的单位线性规划问题某约束条件的右端常数项的单位增加量所引起的目标函数的改善量称为该右端常数项的增加量所引起的目标函数的改善量称为该右端常数项的对偶价格对偶价格。 因此，若对偶价格为正，则增加右端常数项，目标函数因此，若对偶价格为正，则增加右端常数项，目标函数值得到改善；若对偶价格为负，则增加右端常数项，目值得到改善；若对偶价格为负，则增加右端常数项，目标函数值将会标函数值将会“恶化恶化”。三、对偶价格三、对偶价格(dual price) 根据该定义，对于极大化的问题，对偶价格就等于其对偶问题的根据该定义，对于极大化的问题，对偶价格就等于其对偶问题的最优解；对于极小化问

30、题，对偶价格就等于其对偶问题最优解的最优解；对于极小化问题，对偶价格就等于其对偶问题最优解的相反数。相反数。 例如本节例例如本节例2.4的极大化问题三个约束条件的对偶价格分别为的极大化问题三个约束条件的对偶价格分别为50，0和和50； 本节例本节例2.6的极小化问题两个约束条件的对偶价格分别为的极小化问题两个约束条件的对偶价格分别为360和和800；下面在举一个含有等号约束的例子。；下面在举一个含有等号约束的例子。 例例2.7 求下列线性规划问题各约束条件的对偶价格求下列线性规划问题各约束条件的对偶价格 min z=2x1+3x2+4x3 x1 + x2 + x3 120 2x1 + x2 +

31、 x3 60 x1 +2x2 + x3 =80 x1、x2，x30 用大用大m法（极小化为标准形式）求解得问题的最优单纯形表如表法（极小化为标准形式）求解得问题的最优单纯形表如表26。故对偶问题的最优解为故对偶问题的最优解为y1*=0，y2*=1/3，y3*=4/3。由于是极小化问。由于是极小化问题，所以三个约束条件的对偶价格为对偶问题最优解的相反数，即题，所以三个约束条件的对偶价格为对偶问题最优解的相反数，即分别为分别为0、1/3和和4/3。即第二个约束条件的右端常数项增加。即第二个约束条件的右端常数项增加1个个单位，则目标函数值单位，则目标函数值“恶化恶化”1/3个单位，减少个单位，减少一

32、一个单位，则目标函个单位，则目标函数值数值“改善改善”1/3个单位。对于第一和第三个约束条件可作同样的分个单位。对于第一和第三个约束条件可作同样的分析。析。cj23400mmb cbxb x1 x2x3x4x5x6x70 x2001/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 第六节第六节 线性规划的应用线性规划的应用(applications of lp) 线性规划是管理决策制定的最成功的数量方

33、线性规划是管理决策制定的最成功的数量方法之一。法之一。 它广泛应用于化工、航空、钢铁、石油和其它广泛应用于化工、航空、钢铁、石油和其他工业。他工业。 它研究的问题是多种多样的它研究的问题是多种多样的生产计划、生产计划、媒体选择、金融计划、资金预算、运输、工媒体选择、金融计划、资金预算、运输、工厂选择、生产组合、人员调配等等。厂选择、生产组合、人员调配等等。 例例 红旗商场是个中型的红旗商场是个中型的百货商场，它对售货人员百货商场，它对售货人员的需求经过统计分析如表的需求经过统计分析如表所示。为了保证售货人员所示。为了保证售货人员充分休息，售货人员每周充分休息，售货人员每周工作五天，休息两天，并

34、工作五天，休息两天，并要求休息的两天是连续的，要求休息的两天是连续的，问应该如何安排售货人员问应该如何安排售货人员的作息，既满足了工作需的作息，既满足了工作需要又使配备的售货人员的要又使配备的售货人员的人数最少？人数最少？时间时间所需售货员所需售货员星期日星期日星期一星期一星期二星期二星期三星期三星期四星期四星期五星期五星期六星期六28人人15人人24人人25人人19人人31人人28人人一、人力资源分配问题人力资源分配问题 解：解：设设x1为星期一开始上班的人数为星期一开始上班的人数，x2为星期二开为星期二开始上班的人数，始上班的人数，x7星期日开始上班的人数。星期日开始上班的人数。我们就可得

35、到如下的数学模型：我们就可得到如下的数学模型： 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。媒体媒体被告知的潜在被告知的潜在顾客数（人顾客数（人/次）次）广告费用广告费用（元

36、（元/次）次）媒体最高使媒体最高使用次数（次）用次数（次）每次宣传每次宣传的质量的质量日间电视日间电视夜间电视夜间电视日报日报周末新闻杂志周末新闻杂志电台广播电台广播10002000150025003001500300040010001001510254306590406020例例 某房地产开发公司正在建造一个湖边小区，公司准某房地产开发公司正在建造一个湖边小区，公司准备投入备投入3万元进行广告媒体宣传，希望能够吸引周围的中万元进行广告媒体宣传，希望能够吸引周围的中高收入家庭前来购房。目前有高收入家庭前来购房。目前有5种媒体可供选择，相关信种媒体可供选择，相关信息如表所示。息如表所示。对于这次

37、活动，公司有下列要求：至少进行对于这次活动，公司有下列要求：至少进行10次电视广次电视广告；至少有告；至少有5万名潜在顾客被告知；电视广告投入不超过万名潜在顾客被告知；电视广告投入不超过18000元。如何进行媒体组合，才能使广告质量最高？元。如何进行媒体组合，才能使广告质量最高？二、媒体选择二、媒体选择 解解 问题中媒体组合实际上就是要决定每种媒体的使用次数问题中媒体组合实际上就是要决定每种媒体的使用次数。设设x1、x2、x3、x4、x5分别表示表中日间电视、夜间电视、分别表示表中日间电视、夜间电视、日报、周末新闻杂志、电台广播五种媒体的使用次数。日报、周末新闻杂志、电台广播五种媒体的使用次数

38、。 该问题的线性规划模型为该问题的线性规划模型为 max z = 65x1 + 90 x2 + 40 x3 +60 x4 + 20 x5 1500 x1 + 3000 x2 + 400 x3 + 1000 x4 + 100 x5 30000 1000 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个约束条件的线性规个约束条件的线性规划模型，求解结果如

39、下：划模型，求解结果如下：媒体媒体最佳播放次数（次）最佳播放次数（次）广告费用（元）广告费用（元）日间电视日间电视1015000日报日报2510000周末新闻杂志周末新闻杂志22000电台广播电台广播303000被告知的顾客数被告知的顾客数= 61500 人人 产品宣传质量产品宣传质量= 2370目标函数最优值为：目标函数最优值为：2370变量变量 最优解最优解 检验数检验数 x1 10 0 x2 0 65 x3 25 0 x4 2 0 x5 30 0约束约束 松弛松弛/剩余变量剩余变量 对偶价格对偶价格 1 0 0.06 2 11500 0 3 0 25 4 3000 0 5 5 0 6 1

40、0 0 7 0 16 8 2 0 9 0 14 包括：资本预算、资产分配、财政计划等包括：资本预算、资产分配、财政计划等（一）投资组合（一）投资组合 问题：问题：从多种投资选择中选择具体的投资：股票和从多种投资选择中选择具体的投资：股票和债券、基金、保险等；债券、基金、保险等； 目标目标：预期收益极大化、风险最小化：预期收益极大化、风险最小化 约束约束：投资类型、国家法律、公司政策、风险或效：投资类型、国家法律、公司政策、风险或效益限制等益限制等三、财政应用三、财政应用案例案例 welte公司拥有公司拥有100000美元，财务专家确定了如美元，财务专家确定了如下下5个投资机会，并预计了它们的年

41、收益：个投资机会，并预计了它们的年收益：1. 在石油或钢铁行业投资不能超过在石油或钢铁行业投资不能超过50000每元；每元；2. 对政府债券的投资至少相当于对钢铁行业投资的对政府债券的投资至少相当于对钢铁行业投资的25%；3. 对太平洋石油的投资不能多于整个石油行业投资的对太平洋石油的投资不能多于整个石油行业投资的60%求预期收益最大的投资方案。求预期收益最大的投资方案。投资投资预期收益率（预期收益率（%）大西洋石油大西洋石油太平洋石油太平洋石油中西部钢铁中西部钢铁huber钢铁钢铁政府债券政府债券7.310.36.47.54.5设：设：atl=大西洋石油投资大西洋石油投资；pac=太平洋石油

42、投资太平洋石油投资； 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 太平洋石

43、油限制太平洋石油限制 atl , pac , mid , hub , gov 0(二二)、金融计划、金融计划 案例案例 某公司现有某公司现有68名员工申请提前退休。公司必须名员工申请提前退休。公司必须在此后的在此后的8年内对这些员工分期支付一定数量的现金，年内对这些员工分期支付一定数量的现金，如下表所示。如下表所示。为了完成这项现金支付任务，公司的财务人员必须现在为了完成这项现金支付任务，公司的财务人员必须现在就为此制定一个投资计划。投资计划有政府债券投资和就为此制定一个投资计划。投资计划有政府债券投资和银行储蓄两种方式组成。银行储蓄两种方式组成。年份（年）年份（年）12345678合计合计现

44、金支付现金支付(千元千元)430 210 222 231 240 195 225 255 2008注意注意: 三种政府债券的票面价值均为三种政府债券的票面价值均为1000元，债券到期元，债券到期时按票面价值进行支付，利率的计算也以票面的价值为时按票面价值进行支付，利率的计算也以票面的价值为基准。银行储蓄年利率为基准。银行储蓄年利率为4%。如何安排投资计划，使公。如何安排投资计划，使公司以最小的投资额完成对退休员工的现金支付任务？司以最小的投资额完成对退休员工的现金支付任务？政府债券投资有三种债券类型可供选择，如下表所示。政府债券投资有三种债券类型可供选择，如下表所示。债券债券价格（元）价格（元

45、）利率（利率（%）到期年限到期年限111508.8755210005.50063135011.7507解：解：1确定决策变量确定决策变量 设设f为完成投资计划所需要的总资金额。为完成投资计划所需要的总资金额。x1、x2、x3分别分别表示债券表示债券1、2、3的购买的购买量；量；yi ( i =1,，8)表示第表示第 i年年初银行储蓄的投资额。初银行储蓄的投资额。2确定约束条件确定约束条件 这类问题的一个典型特征就是每年现金支付的一般表这类问题的一个典型特征就是每年现金支付的一般表达式为：达式为：年初可用资金额年初可用资金额 当年用于债券和储蓄的资金额当年用于债券和储蓄的资金额 = 当年现金支付

46、当年现金支付于是有于是有 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.0

47、55x2 +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.确

48、定目标函数确定目标函数目标就是使满足要求的投资额最小，目标就是使满足要求的投资额最小，即即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.0

49、55x2 +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 0 y1 636.148 0 y2 501.606 0 y3 349.682 0 y4 182.681 0 y5 0 0.06

50、4 y6 0 0.0126 y7 0 0.0213 y8 0 0.671即得到最佳投资计划如下表所示即得到最佳投资计划如下表所示: : 债债券券购买量购买量投资额投资额(千元千元)年份年份储蓄额储蓄额(千元千元)1144.9881.150144.988=166.7361636.1482187.8561.000187.856=187.8562501.6063228.1881.350228.188=308.0543349.682总投资额总投资额 f = 1728794 元元4182.681 580 约束 松弛/剩余变量 对偶价格 1 0 1.000 2 0 0.962 3 0 0.925 4 0

51、0.889 5 0 0.855 6 0 0.760 7 0 0.719 8 0 0.671结果分析：结果分析： 前前4年的储蓄额均大于年的储蓄额均大于0，可见从第，可见从第6年起债券的利息年起债券的利息和债券到期收入才能够完全满足当前现金支付需要。和债券到期收入才能够完全满足当前现金支付需要。 每一个约束条件的对偶价格均为负值，说明减少任每一个约束条件的对偶价格均为负值，说明减少任何一年的现金支付都将有利于公司总投资额的降低。何一年的现金支付都将有利于公司总投资额的降低。 对偶价格的逐年降低也说明了，在前面年份减少现对偶价格的逐年降低也说明了，在前面年份减少现金支付将对总投资额的减少更为有效。

52、从而暗示了金支付将对总投资额的减少更为有效。从而暗示了公司可以适当减少前面年份的现金支付量，而在后公司可以适当减少前面年份的现金支付量，而在后面年份进行补足。面年份进行补足。 (一一) 制造或购买决策制造或购买决策 案例案例 某公司有某公司有， 两种产品，预计两种产品的两种产品，预计两种产品的市场需求量分别为市场需求量分别为3000件和件和2000件。两种产品均件。两种产品均由由a、b、c三个部件组成，各部件生产消耗工时和三个部件组成，各部件生产消耗工时和自制自制/外购成本如下表所示。外购成本如下表所示。部件部件单位部件制造工单位部件制造工时（分钟）时（分钟）自制成本自制成本（元（元/分钟）分

53、钟）购买成本购买成本（元（元/小时）小时）a1.00.500.60b产品产品3.03.754.00产品产品2.53.303.90c产品产品1.00.600.65产品产品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个加

54、班工时可用于这两种产品的生产。每个加班工时需个加班工时可用于这两种产品的生产。每个加班工时需额外支付额外支付9元。如何安排部件自制和外购的数量，从而元。如何安排部件自制和外购的数量，从而使总成本（包括生产成本、外购成本和加工费用）最低？使总成本（包括生产成本、外购成本和加工费用）最低？解：解：1确定决策变量确定决策变量 设设xa、xb1、xb2、xc1、xc2分别表分别表示示a部件、用于产品部件、用于产品的的b部件、用于产品部件、用于产品的的b部件、用部件、用于产品于产品的的c部件、用于产品部件、用于产品 的的c部件的自制量。相应部件的自制量。相应地，设地，设ya、yb1、yb2、yc1、yc

55、2分别为各部件的外购量。分别为各部件的外购量。设设y0为加班工时数。为加班工时数。 2确定约束条件确定约束条件 a部件的需求量约束部件的需求量约束 xa + ya =5000 用于产品用于产品的的b部件的需求量约束部件的需求量约束 xb1 + yb1 =3000 用于产品用于产品的的b部件的需求量约束部件的需求量约束 xb2 + yb2 =2000 用于产品用于产品的的c部件的需求量约束部件的需求量约束 xc1 + yc1 =3000 用于产品用于产品的的c部件的需求量约束部件的需求量约束 xc2 + yc2 =2000 最大加班工时数约束最大加班工时数约束 y050 最大生产能力约束最大生产

56、能力约束 xa +3xb1 + 2.5xb2 + xc1 + 1.5xc2 20060 +60 y03确定目标函数确定目标函数目标是使总成本最小，即目标是使总成本最小，即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.

57、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.000 ya 0 0.017 xb1 667 0.000 ybl 2333 0.

58、000 xb2 2000 0.000 yb2 0 0.392 xc1 0 0.033 yc1 3000 0.000 xc2 0 0.095 yc2 2000 0.000 y0 0 4.000约束约束 松弛松弛/剩余变量剩余变量 对偶价格对偶价格 1 0 0.583 2 0 4.000 3 0 3.508 4 0 0.650 5 0 0.780 6 50 0.000 7 0 0.083部件部件自制量（件）自制量（件）购买量（件）购买量（件）a50000b产品产品6672333产品产品20000c产品产品03000产品产品02000总成本总成本 = 24，443. 33元元目标函数系数范围目标函数

59、系数范围变量变量 下限下限 当前值当前值 上限上限 xa 无下限无下限 0.500 0.517 ya 0.583 0.600 无上限无上限 xb1 3.700 3.750 3.850 ybl 3.900 4.000 4.050 xb2 无下限无下限 3.300 3.692 yb2 3.508 3.900 无上限无上限 xc1 0.567 0.600 无上限无上限 yc1 无下限无下限 0.650 0.683 xc2 0.655 0.750 无上限无上限 yc2 无下限无下限 0.780 0.875 y0 5.000 9.000 无上限无上限右端常数项范围右端常数项范围约束约束 下限下限 当前值

60、当前值 上限上限 1 0.000 5000 7000 2 666.667 3000 无上限无上限 3 0.000 2000 2800 4 0.000 3000 无上限无上限 5 0.000 2000 无上限无上限 6 0.000 50 无上限无上限 7 10000.000 12000 19000(二二) 生产计划问题生产计划问题 生产计划问题是线性规划应用最为广泛的领域之一生产计划问题是线性规划应用最为广泛的领域之一; 问题描述问题描述: 一定时期内，经理必须决定生产水平，一定时期内，经理必须决定生产水平，使公司能够满足生产需求，在受到产品生产量、劳使公司能够满足生产需求，在受到产品生产量、劳动力水平以及存储