第二章线性规划-习题

057234219532..5432154321jxxxxxxxxxxxts习题2-1判断下列说法是否正确：（1）任何线性规划问题存在并具有惟一的对偶问题；（2）对偶问题的对偶问题一定是原问题；（3）根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；（4）若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；（5）若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；（6）应用对偶单纯形法计算时，若单纯形表中某一基变量xi0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解。（7）若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；（8）已知yi为线性规划的对偶问题的最优解，若yi0，说明在最优生产计划中第i种资源已经完全耗尽；若yi=0，说明在最优生产计划中的第i种资源一定有剩余。2-2将下述线性规划问题化成标准形式。无约束43214321432143214321,0,,232142224.5243max)1(xxxxxxxxxxxxxxxxstxxxxz无约束321321321321,0,0624.322min2xxxxxxxxxstxxxz2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。0,825943.510max121212121xxxxxxstxxz0,24261553.2max221212121xxxxxxstxxz2-4已知线性规划问题，写出其对偶问题：（1）543212520202410maxxxxxxz)5,4,3,2,1(j0226332..31434321421jxxxxxxxxxxxxts无约束321321321,0,064..xxxkxxxxxxts(2)2-5运用对偶理论求解以下各问题：（1）已知线性规划问题：其最优解为（a）求k的值；（b）写出并求出其对偶问题的最优解。（2）已知线性规划问题：其对偶问题的最优解为，。试根据对偶理论求出原问题的最优解。（3）已知线性规划问题:0,,12.max32132132121xxxxxxxxxstxxz试根据对偶问题性质证明上述线性规划问题目标函数值无界。43216368minxxxxz)4,3,2,1(j32122minxxxz1,0,5321xxx4321432maxxxxxz0,,,2023220322..432143214321xxxxxxxxxxxxts2.11y2.02y2-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/22-7用对偶单纯形法求解下列线性规划问题。0,,52233.18124min13213231321xxxxxxxstxxxz0,,10536423.325min2321321321321xxxxxxxxxstxxxz2-8已知2-45表为求解某线性规划问题的最终单纯形表，表中x4,x5为松弛变量，问题的约束为≤形式。表2-45最终单纯形表zx1x2x3x4x5RHSz104042X301/211/205/2X11-1/20-1/61/35/2（1）写出原线性规划问题；（2）写出原问题的对偶问题；（3）直接由原问题的最终单纯形表写出对偶问题的最优解。2-9已知线性规划问题:0,,426.2max32121321321xxxxxxxxstxxxz先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。（1）目标函数变为32132maxxxxz（2）约束右端项由46变为43;（3）增添一个新的约束条件231xx。2-10某厂生产A，B，C三种产品，其所需劳动力、材料等有关数据见表2-46。要求：（1）确定最大的产品生产计划；（2）产品A的利润在什么范围内变动时，上述最优计划不变；（3）如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？（4）如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜。（5）由于某种原因该厂决定暂停A产品的生产，试重新确定该厂的最优生产计划。表2-46产品单位利润及资源消耗消耗定额产品资源ABC可用量（单位）劳动力材料6353454530产品利润（元/件）3142-11已知运输问题的供求关系和单位运价表如表2-47所示，试用表上作业法求出问题的最优解。（1）表2-47（a）销地产地B1B2B3B4产量A1327650A2752360A3254525销量60402015（2）表2-47（b）销地产地B1B2B3B4产量A118141712100A2581315100A3177129150销量507060802-121，2，3三个城市每年需分别供应电力320,250,和350单位，由Ⅰ，II两个电站提供，它们的最大可供电量分别为400个单位和450个单位，单位费用如表2-23所示。由于需要量大于可供量，决定城市1的供应量可减少0~30单位，城市2的供应量不变，城市3的供应量不能少于270单位，试求总费用最低的分配方案（将可供电量用完）。表2-48供应电力单位费用表城市电站123I151822II2125162-13已知某运输问题的运输表及给出的一个最优调运方案分别见表2-49，试确定表2-49中k的取值范围。表2-49运输表及最优调运方案12341101201115510212k9202501015321416185551515102-14某糖厂每月最多生产糖270t，先运至A1A2A3三个仓库，然后再分别供应五个地区的需要。已知各仓库的容量分别为50,100,150（t），各地区的需要量分别为25,105,60,30,70（t）。已知从糖厂经各仓库然后供应各地区的运费和存储费如表2-50所示。表2-50运费及存储费B1B2B3B4B5A11015202040A12040153030A13035405525试确定一个使总费用最低的调运方案。2-15一艘货轮分前、中、后三个舱位，它们的容积与最大允许的载重量如表2-51和2-52所示，现有三种货物待运，已知有关数据列于表2-27（b）2-51容积及最大允许的载重量项目前舱中舱后舱最大允许载重量（t）200030001500容积（m3）4000540015002-52待运货物单件体积、重量及运价商品数量（件）每件体积（m3/件）每件重量（t/件）运价（元/件）A6001081000B100056700C80075600又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过15%,前后舱之间不超过10%。问该货轮应装载A、B、C各多少件运费收入才最大？试建立这个问题的线性规划模型。2-16一贸易公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。1月1日，公司拥有库存1000担杂粮，并有资金20000元。估计第一季度杂粮价格如表2-53所示。如买进的杂粮当月到货，但需到下月才能卖出，且规定“货到付款”。公司希望本季末库存为2000担。问：应采取什么样的买进与卖出的策略使3个月总的获利最大？（列出问题的线性规划模型，不求解）表2-53各月份的进货单价及出货单价月份进货价/（元/担）出货价/（元/担）12.853.1023.053.2532.902.952-17某农户年初承保了40亩土地，并备有生产专用资金25000元。该户劳动力情况为：春夏季4000工时，秋冬季3500工时。若有闲余工时则将为别的农户帮工，其收入为：春夏季5元/工时，秋冬季4元/工时。该户承包的地块只是以种植大豆、玉米、小麦，为此已备齐各种生产资料，因此不必动用现金。另外，该农户还饲养奶牛和鸡。每头奶牛每年需投资4000元，每只鸡需投资30元。每头奶牛需用地1.5亩种植饲草，并占用劳动力：春夏季50工时、秋冬季100工时，每年净收入4000元。每只鸡占用劳动力：春夏季0.3工时、秋冬季0、6工时，每年净收入100元。该农户现有鸡舍最多能容纳300只鸡，牛棚最多能容纳8头奶牛。三种农作物一年需要的劳动力及收入情况见表2-54。问该农户应如何拟定经营方案才能使当年净收入最大？试建立该问题的数学模型。表2-54三种农作物需要的劳动力及收入情况种类需用工时（工时/亩）春夏季需工时/亩秋冬季需工时/亩净收入/（元/亩）大豆2050500玉米3575800小麦10404002-18对某厂I，II，III三种产品下一年各季度的合同预订数如表2-55所示。表2-55三种产品下一年各季度的合同预订数产品季度1234I1500100020001200II1500150012001500III1000200015002500该三种产品1季度初无库存，要求在4季度末各库存150件。已知该厂每季度生产工时为15000h，生产I，II，III产品每件分别需时2、4、3h。因更换工艺装备，产品I在2季度无法生产。规定当产品不能按期交货时，产品I、II每件每迟交一个季度赔偿20元，产品III赔偿10元；又生产出的产品不在本季度交货的，每件每季度的库存费用为5元。问该厂应如何安排生产，使总的赔偿加库存费用为最小（要求建立数学模型，不需求解）。