第二章 线性规划习题.doc

《第二章 线性规划习题.doc》由会员分享，可在线阅读，更多相关《第二章 线性规划习题.doc（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题2-1 判断下列说法是否正确：（1） 任何线性规划问题存在并具有惟一的对偶问题；P（2） 对偶问题的对偶问题一定是原问题；P（3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；O（4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；O（5） 若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；O（6） 应用对偶单纯形法计算时，若单纯形表中某一基变量xi0，说明在最优生产计划中第i种资源已经完全耗尽；若yi=0，说明在最优生产计划中的第i种资源一定

2、有剩余。O2-2将下述线性规划问题化成标准形式。解：(1)令，增加松弛变量，剩余变量，则该问题的标准形式如下所示： (2)令，增加松弛变量，则该问题的标准形式如下所示：2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。解：(1)图解法 最优点为B点，最优解为x1=1,x2=3/2，最优值为35/2。 单纯形表计算过程：j初始单纯形表（对应O点）zx1x2x3x4RHSz1-10-5000x30341099/3x40520188/5k第一次迭代（对应A点）zx1x2x3x4RHSz10-10216x30014/51-3/521/521

3、/5/14/5x11012/501/58/58/5/4/5l第二次迭代（对应B点，即最优解）zx1x2x3x4RHSz1005/1425/1435/2x25015/14-3/143/2x11010-1/72/71(2)图解法最优点为B点，最优解为x1=15/4,x2=3/4，最优值为33/4。 单纯形表计算过程：j初始单纯形表（对应O点）zx1x2x3x4RHSz1-2-1000x3035101515/3x4062012424/6k第一次迭代（对应A点）zx1x2x3x4RHSz10-1/301/38x30041-1/233/4x1211/301/644/1/3l第二次迭代（对应B点，即最优解

4、）zx1x2x3x4RHSz1001/127/2433/4x21011/4-1/83/4x1210-1/125/2415/42-4已知线性规划问题，写出其对偶问题：（1） (2)解：(1)原问题的对偶问题为：(2)原问题的对偶问题为：2-5运用对偶理论求解以下各问题：（1）已知线性规划问题：其最优解为（a）求k的值；（b）写出并求出其对偶问题的最优解。解：原问题的对偶问题为：设该对偶问题的三个人工变量为，由于原问题的最优解中的，则根据互补松弛性，所增加的人工变量，则：，。另外，原问题的最优值，也为对偶问题的最优值，即：。结合上述三式可得：（2）已知线性规划问题：其对偶问题的最优解为， 。试根据

5、对偶理论求出原问题的最优解。解：首先写出原问题的对偶问题如下：由于该对偶问题的最优解为，代入对偶问题的约束条件中可得，即对偶问题中的松弛变量。则根据互补松弛性可知，原问题中的决策变量必为0。将=0代入原问题中的约束条件，可得：。又因为均不为0，则同样根据互补松弛性可知，。则有：。求解该方程组可得：。（3）已知线性规划问题:试根据对偶问题性质证明上述线性规划问题目标函数值无界。解：首先写出原问题的对偶问题如下：由于该对偶问题中前两个约束条件所确定的可行域为空集，可知该对偶问题无解。则根据对偶性质可知，原问题无解可无界。另外，必为原问题的解之一，则可证原问题无界。2-6已知某求极大值线性规划问题用

6、单纯形法求解时的初始单纯形表及最终单纯形表如表2-44所示，求表中各括弧内未知数的值。表2-44 初始单纯形表及最终单纯形表zx1x2x3x4x5x6RHSz1-3-2-20000x40111100（b）x50(a)1201015x602(c)100120：zx1x2x3x4x5x6RHSz10（k）（g）05/4（j）95/4x4000（d）(l)-1/4-1/45/4x1310（e）03/4（i）25/4x2201（f）0（h）1/25/2解：由初始单纯形表中的基变量为可知，为最终单纯形表中所对应的消耗系数矩阵，即：则有：，可求得：。另外：，可求得。再由检验数计算公式可求得；而基变量的检验

7、数必为零，所以。即。2-7用对偶单纯形法求解下列线性规划问题。解：(1) 令z，=- z引进松弛变量x4，x50，标准化列出初始单纯形表z，x1x2x3x4x5RHSz，141218000x40-10-310-3x500-2-201-5-12/-2-18/-2选取x2进基。即选取a22=-2为主元，进行旋转运算，得到以下单纯形表。z，x1x2x3x4x5RHSz，140606-30x40-10-310-3x2-120110-1/25/2-4/-1-6/-3选取x4出基，a13=-3为主元进行旋转运算。z，x1x2x3x4x5RHSz，120026-36x3-181/301-1/301x2-12

8、-1/3101/3-1/23/2当前基既是原始可行基，又是对偶可行基，因而是最优基。最优解为x1=0，x2=3/2，x3=1，max z，=-36，即min z=36(2) 令z，=- z引进松弛变量x4，x50，标准化 列出初始单纯形表z，x1x2x3x4x5RHSz，1523000x40-3-1-210-4x50-6-3-501-10-2/-3-3/-5选取x3进基。即选取a23=-5为主元，进行旋转运算，得到以下单纯形表。z，x1x2x3x4x5RHSz，17/51/5003/5-6x40-3/51/501-2/50x3-36/53/510-1/52当前基既是原始可行基，又是对偶可行基，

9、因而是最优基。最优解为x1=0，x2=0，x3=2，max z，=-6，即min z=6 2-8已知2-45表为求解某线性规划问题的最终单纯形表，表中x4 , x5为松弛变量，问题的约束为形式。表2-45 最终单纯形表zx1x2x3x4x5RHSz104042X301/211/205/2X11-1/20-1/61/35/2（1）写出原线性规划问题；（2）写出原问题的对偶问题；（3）直接由原问题的最终单纯形表写出对偶问题的最优解。解：（1）由于x4 , x5为松弛变量，则从表2-45可知，。设原问题模型为： 则由初始单纯形表和最终单纯形表之间的关系可得：，则可得到，。，则可得，。另外，由最终单纯

10、形表中检验数的计算公式可知，则可得，。综上，原线性规划模型为：（2）该模型的对偶问题为：（3）由原问题的最终单纯形表可以得出，单纯形表中的检验数行是对偶问题决策变量的值。其中，对应对偶问题松弛变量的值，对应对偶问题决策变量的值。则对偶问题的最优解为：，。2-9已知线性规划问题：先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。（1）目标函数变为（2）约束右端项由变为;（3）增添一个新的约束条件。解：首先用单纯形法得到原问题的最优单纯形表。 zx1x2x3x4x5RHSz10312012x12111106x500311110且可得到，最终单纯形表中。（1）由于x2在最优单纯形

11、表中是非基变量，因此只影响它本身的检验数。计算：得到时问题的最优解不变。但由于由-1变为3，此时必然造成检验数的符号发生变化，相应的单纯形表如下：zx1x2x3x4x5RHSz10-112012x12111106x500311110以为主元，对该单纯形表进一步迭代可得：zx1x2x3x4x5RHSz1004/37/31/346/3x12102/32/3-1/38/3x23011/31/31/310/3此时最优解变为。目标函数值变为46/3。（2）当初始单纯形表中右端常数从(6,4)T变为(3,4)T时，即右端常数第一项减少3，则最终单纯形表中的右端常数项应为原最终单纯形表中的右端常数与B-1中

12、第一列与（-3）乘积之和，即：(6,10) T+(-3)*(1,1) T=(6-3,10-3)=(3,7) T。则可知，最优解变为，最优值变为27。（3）先将原问题最优解变量值代入，因有-6+0=-627，即该产品值得生产。（4）由原问题的最优单纯形表可知，该问题对偶问题的最优解为：，即劳动力的影子价格为0.2，材料的影子价格为0.6。而市场上材料的价格仅为0.4。由于影子价格市场价格，此时可以通过购买材料进行生产。设从市场上购买个单位的材料，则问题的最优单纯形表变为：zx1x2x3x4x5RHSz10201/53/527+x131-1/301/3-1/35-x34011-1/52/53+此时

13、当，即时，问题的最优解为。但当时，右端项第一行0，此时根据对偶单纯形法，需要x1出基，x5进基，可得x5的检验数为零，即材料的影子价格变为零。因此，应从市场上购买15个单位的材料。（5）暂停A产品的生产，相当于删除决策变量，对由剩余变量求解，可得问题的模型变为：可求得最优解为：，最优值。2-11已知运输问题的供求关系和单位运价表如表2-47所示，试用表上作业法求出问题的最优解。（1）表2-47（a）销地产地B1B2B3B4产量A1327650A2752360A3254525销量60402015解：采用Vogel法获得初始基本可行解。B1B2B3B4A13276501040A2752360252

14、015A32545252560402015计算该解下各非基变量的检验数，可得：B1B2B3B472A13276501040-1A2752360252015704A32545252560402015X22的检验数0，此时应将X22进基，更新解及非基变量的检验数可得：B1B2B3B468A132765035151A2752360252015664A32545252560402015可知，该解中非基变量检验数均为非负，为最优解。即A1往B1运35，往B2运15；A2往B2、B3、B4分别运25、20、15单位；A3往B1运25单位。最优值为：395。（2）表2-47（b）销地产地B1B2B3B4产量

15、A118141712100A2581315100A3177129150销量50706080解：由于总产量为350，而总销量为260，即产大于销的运输问题。因此，通过增加一个假想的销地B5，销量为90，运价均为0，使其变为产销平衡的运输问题。问题更新为：销地产地B1B2B3B4B5产量A11814171200100100A2581315A31771290150销量5070608090采用Vogel法获得初始基本可行解，并计算非基变量的检验数如下：B1B2B3B4B5-229A11814171201001090450A258131501005050513A317712901507008050706

16、08090X14的检验数=0,k+10=0,10-k=0,24-k=0,18-k=0。取前述不等式解的交集，可得k的取值范围为：3=k=10。2-14某糖厂每月最多生产糖270 t，先运至A1A2A3三个仓库，然后再分别供应五个地区的需要。已知各仓库的容量分别为50,100,150（t），各地区的需要量分别为25,105,60,30,70（t）。已知从糖厂经各仓库然后供应各地区的运费和存储费如表2-50所示。表2-50运费及存储费 B1 B2 B3 B4 B5 A11015 202040 A12040153030 A13035405525试确定一个使总费用最低的调运方案。（暂时不用考虑本题，待

17、和出题老师核实后再公布该题答案）2-15一艘货轮分前、中、后三个舱位，它们的容积与最大允许的载重量如表2-51和2-52所示，现有三种货物待运，已知有关数据列于表2-27（b）2-51 容积及最大允许的载重量项目前舱中舱后舱最大允许载重量（t）200030001500容积（m3）4000540015002-52 待运货物单件体积、重量及运价商品数量（件）每件体积（m3/件）每件重量（t/件）运价（元/件）A6001081000B100056700C80075600又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过

18、15%,前后舱之间不超过10%。问该货轮应装载A、B、C各多少件运费收入才最大？试建立这个问题的线性规划模型。解：设决策变量（）表示由前、中、后舱装载货物、的数量，则模型为：s.t. ，（船舱载重量约束）， ，（船舱体积约束），（货物数量约束），（载重量比例约束）2-16一贸易公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。1月1日，公司拥有库存1000担杂粮，并有资金20000元。估计第一季度杂粮价格如表2-53所示。如买进的杂粮当月到货，但需到下月才能卖出，且规定“货到付款”。公司希望本季末库存为2000担。问：应采取什么样的买进与卖出的策略使3个月总的获利最大？（列出问题的

19、线性规划模型，不求解）表2-53 各月份的进货单价及出货单价月份进货价/（元/担）出货价/（元/担）12.853.1023.053.2532.902.95解：设决策变量（）表示1、2、3月买进、卖出的杂粮担数，则模型如下：s.t. ，（仓库容量约束），（季末库存约束），（资金约束），（“下月卖出”约束）2-17某农户年初承保了40亩土地，并备有生产专用资金25 000元。该户劳动力情况为：春夏季4 000工时，秋冬季3 500工时。若有闲余工时则将为别的农户帮工，其收入为：春夏季5元/ 工时，秋冬季4元/ 工时。该户承包的地块只是以种植大豆、玉米、小麦，为此已备齐各种生产资料，因此不必动用现金

20、。另外，该农户还饲养奶牛和鸡。每头奶牛每年需投资4 000元，每只鸡需投资30元。每头奶牛需用地1.5亩种植饲草，并占用劳动力：春夏季50工时、秋冬季100工时，每年净收入4 000元。每只鸡占用劳动力：春夏季0.3工时、秋冬季0.6工时，每年净收入100元。该农户现有鸡舍最多能容纳300只鸡，牛棚最多能容纳8头奶牛。三种农作物一年需要的劳动力及收入情况见表2-54。问该农户应如何拟定经营方案才能使当年净收入最大？试建立该问题的数学模型。表2-54 三种农作物需要的劳动力及收入情况种类需用工时（工时/ 亩）春夏季需工时秋冬季需工时净收入/（元/ 亩）大豆2050500玉米3575800小麦10

21、40400解：设决策变量表示饲养牛、鸡的头数()，决策变量为种植大豆、玉米和小麦的亩数()，则模型如下：s.t. （土地面积约束）（资金约束），（鸡舍、牛棚约束），（劳动力约束）2-18对某厂I，II，III三种产品下一年各季度的合同预订数如表2-55所示。表2-55 三种产品下一年各季度的合同预订数产品季度1234I1 5001 0002 0001 200II1 5001 5001 2001 500III1 0002 0001 5002 500该三种产品1季度初无库存，要求在4季度末各库存150件。已知该厂每季度生产工时为15 000 h，生产I，II，III产品每件分别需时2、4、3 h。因更换工艺装备，产品I在2季度无法生产。规定当产品不能按期交货时，产品I、II每件每迟交一个季度赔偿20元，产品III赔偿10元；又生产出的产品不在本季度交货的，每件每季度的库存费用为5元。问该厂应如何安排生产，使总的赔偿加库存费用为最小（要求建立数学模型，不需求解）。解：设Xij为第j季度生产的产品i的数量，sij为第j季度末需库存的产品i的数量，Fij为第j季度末交货的产品i的数量，Rij为第j季度对产品i的预订数，则有