第二章线性规划

《第二章线性规划》由会员分享，可在线阅读，更多相关《第二章线性规划（7页珍藏版）》请在装配图网上搜索。

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

2、2将下述线性规划问题化成标准形式。(1) max z = 一3x + 4x 一 2x + 5x1234 x 一 x + 2 x 一 x = 一21234x + x 一 x + 2 x 0, x4无约束st.(2)min z = 2x - 2x + 3x123厂一 x + x + x = 4123st.一 2x + x x 6123x 0, x无约束1232-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。(1)max z = 10 x + 5 x(2)max z = 2 x + x3x + 4x 91 2st. 5x + 2x 012

3、2 1 23x + 5x 151 2st. 6x + 2x 0122-4已知线性规划问题，写出其对偶问题：max z = 10x + 24x + 20x + 20x + 25x12345x + x + 2 x + 3 x + 5 x 1912345s.t.Q 2x + 4x + 3x + 2x + x 0 (j = 123,4,5)j(2) min z = 8x + 6x + 3x + 6x12343 x + x + x + x 61234s.t.sx + x 234x + x 213x 0 (j = 1,2,3,4) j2-5 运用对偶理论求解以下各问题：(1)已知线性规划问题：min z

4、二 2 x 一 x + 2 x123x + x + x 4123s.t. 一 x + x 一 kx 6123x 0, x无约束123其最优解为x1 5, x2 0, x3 1(a) 求k的值；(b) 写出并求出其对偶问题的最优解。2)已知线性规划问题：max z x + 2 x + 3x + 4 x1234x + 2x + 2x + 3x 20 1234s.t.Q 2x + x + 3x + 2x 01234其对偶问题的最优解为，1.2 y 0.212 试根据对偶理论求出原问题的最优解。( 3)已知线性规划问题:max z x + x12一 x + x + x 2123st. 一 x + x

5、一 x 0123试根据对偶问题性质证明上述线性规划问题目标函数值无界。2-7 用对偶单纯形法求解下列线性规划问题。Gmin z = 4 x +12 x12x + 3 x 313st. 523x , x , x 0123+18x (2)min z = 5x + 2x + 3x31233x + x + 2x 4123st. 10123x , x , x 01232-6 已知某求极大值线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形 表如表 2-44 所示，求表中各括弧内未知数的值。表 2-44 初始单纯形表及最终单纯形表z Xx2x?x4x5x6RHSz1-3-2-20000x4011110

6、0(b)x50(a)1201015x602(c)100120z Xx2x?x4x5x6RHSz10(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-8已知2-45表为求解某线性规划问题的最终单纯形表，表中x4 , x5为松弛变量, 问题的约束为W形式。表 2-45 最终单纯形表zx1x2x3x4x5RHSz104042X301/211/205/2X11-1/20-1/61/35/2（1）写出原线性规划问题；（2）写出原问题的对偶问题；（3）直接由原问题的最终单纯形表写出对偶问题的最优解2-

7、9已知线性规划问题:max z = 2 x - x + x123x + x + x 6123st. - x + 2x 0123 先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。（1）目标函数变为max z = 2 x + 3x + x123（2）约束右端项由4变为4 ;l4丿l4丿（3）增添一个新的约束条件xi + x3 2。2-10 某厂生产 A，B，C 三种产品，其所需劳动力、材料等有关数据见表 2-46。要 求：（1）确定最大的产品生产计划；（2）产品A的利润在什么范围内变动时，上述 最优计划不变；（3）如果设计一种新产品D,单件劳动力消耗为8单位，材料消耗 为 2

8、单位，每件可获利 3元，问该种产品是否值得生产？（4）如果劳动力数量不增， 材料不足时可从市场购买，每单位 0.4 元。问该厂要不要购进原材料扩大生产，以 购多少为宜。（5）由于某种原因该厂决定暂停A产品的生产，试重新确定该厂的最 优生产计划。表 2-46 产品单位利润及资源消耗 消耗定额产品、资源ABC可用量（单位）劳动力63545材料34530产品利润（元/件）3142-11 已知运输问题的供求关系和单位运价表如表2-47 所示，试用表上作业法求出问 题的最优解。1)表 2-47(a)销地产地B1B2B3B4产量Ai327650A2752360A3254525销量604020152）表 2

9、-47（b）销地产地B1B2B3B4产量A118141712100A2581315100A3177129150销量507060802-12 1, 2, 3三个城市每年需分别供应电力320,250，和350单位，由I, II两个电站 提供，它们的最大可供电量分别为400个单位和 450个单位，单位费用如表2-23所 示。由于需要量大于可供量,决定城市 1 的供应量可减少030单位,城市 2的供应 量不变,城市 3 的供应量不能少于270 单位,试求总费用最低的分配方案（将可供 电量用完）。表 2-48 供应电力单位费用表城市123电站I151822II2125162-13 已知某运输问题的运输表

10、及给出的一个最优调运方案分别见表2-49,试确定表表 2-49 运输表及最优调运方案2-49中k的取值范围。152552-14某糖厂每月最多生产糖270 t,先运至AA2A3三个仓库，然后再分别供应 五个地区的需要。已知各仓库的容量分别为50,100,150 （t）,各地区的需要量分别为 25,105,60,30,70 （t）。已知从糖厂经各仓库然后供应各地区的运费和存储费如表2-50 所示。表 2-50 运费及存储费BBB3B5A11015202040A12040153030A3035405525试确定一个使总费用最低的调运方案。2-15 一艘货轮分前、中、后三个舱位，它们的容积与最大允许的

11、载重量如表2-51和2-52所示，现有三种货物待运，已知有关数据列于表2-27 （b）2-51 容积及最大允许的载重量项目前舱中舱后舱最大允许载重量（t）200030001500容积（m3）4000540015002-52待运货物单件体积、重量及运价商品数量（件）每件体积（m3/ 件）每件重量（t/ 件）运价（元/件）A6001081000B100056700C80075600又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的 比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过15%,前后 舱之间不超过10%。问该货轮应装载A、B、C各多少件运费收入才最大？试建

12、立这 个问题的线性规划模型。2-16一贸易公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。 1月 1 日，公司拥有库存1000担杂粮，并有资金20000元。估计第一季度杂粮价格如表 2-53 所示。如买进的杂粮当月到货，但需到下月才能卖出，且规定“货到付款”。公司希望 本季末库存为2000担。问：应采取什么样的买进与卖出的策略使3个月总的获利最 大？（列出问题的线性规划模型，不求解）表 2-53 各月份的进货单价及出货单价月份进货价/（元/担）出货价/（元/担）12.853.1023.053.2532.902.952- 1 7某农户年初承保了40亩土地，并备有生产专用资金25 0

13、00元。该户劳动力情 况为：春夏季4 000工时，秋冬季3 500工时。若有闲余工时则将为别的农户帮工 其收入为：春夏季5元/ 工时，秋冬季4元/ 工时。该户承包的地块只是以种植大豆、 玉米、小麦，为此已备齐各种生产资料，因此不必动用现金。另外，该农户还饲养 奶牛和鸡。每头奶牛每年需投资4 000 元，每只鸡需投资30 元。每头奶牛需用地1.5 亩种植饲草，并占用劳动力：春夏季50工时、秋冬季100工时，每年净收入4 000 元。每只鸡占用劳动力：春夏季 0.3 工时、秋冬季 0、6 工时，每年净收入 100 元。 该农户现有鸡舍最多能容纳300只鸡，牛棚最多能容纳8 头奶牛。三种农作物一年

14、需要的劳动力及收入情况见表 2-54。问该农户应如何拟定经营方案才能使当年净收 入最大？试建立该问题的数学模型。表 2-54 三种农作物需要的劳动力及收入情况种类-需用工时（工时/亩）春夏季需工时/亩秋冬季需工时/亩净收入/ （元/亩）大豆2050500玉米3575800小麦10404002-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 元。问该厂应如何安排生产，使总的赔偿加库存费用为最小 （要求建立数学模型，不需求解）。