西北大学-茹少锋管理运筹课后答案

.用图解法求解两个变量线性规划问题的最优解和最优值。u1/2u1/2.用图解法求解以下线性规划问题，并指出哪个问题有惟一解、无穷多最优解、无界解或无可行解minz=6%j+4x212X]+x2>1+4x2>3

x]9x2>0最优解：（1，53只\最优值:：36y34maxz-4X1+8x2

2x}+2x2<10—+与N8

x19x2NO

无可行解.某公司从中心制造地点向分别位于城区北、东、南、西方向的分配点运送材料。该公司有26辆卡车，用于从制造地点向分配点运送材料。其中有9辆，每辆能装5吨的大型卡车，12辆每辆能装2吨的中型卡车和5辆每辆能装1吨的小型卡车。北、东、南、西四个点分别需要材料14吨、10吨、20吨、8吨。每辆卡车向各分配点送材料一次的费用如表2-7所示。建立运送材料总费用最小的线性规划模型。表2-7车辆运送一次的费用北东南西大8063927511150605542小20153822解设大、中、小型车分别用，表示，贝川=1，2,3：东、南、西、北四个分点分别用•/表示，则）=1,2,3,4；向/方向发出的i型车数量为囹。minZ=80xn+63x12+92x13-f75x144-50x21+60x224-55x23+42x244-20x3j+15x^2+38与3+22X345xu+2x2j+x31>145x12+2x22+巧2-I。5/3+2%23+X33-205x14+2x24+/4N8X|J+X|2+X|j+X]4W9x2i+x22+x23+X24W12£1+必2+X33+X34W5x,7>0,z,j=l,2,3,4.某工厂生产A、B、C三种产品，现根据合同及生产状况制定5月份的生产计划。已知合同甲为：A产品1000件，每件价格为500元，违约金为100元/每件；合同乙：B产品500件，每件价格为400元，违约金为120元/每件；合同丙为：B产品600件，每件价格为420元，违约金为130元/每件；C产品600件，价格400元/每件，违约金为90元/每件。有关各产品生产过程所需工时以及原材料的情况如表2-8所示。试以利润为目标建立该工厂生产计划的线性规划模型。表2-8产品使用的原材料、加工工序、资源限制、成本产品A产品B产品C资源限制工时或原材料成本工序1212460015工序2311400010工序3232600010原料2432800040其他成本101010解设工厂5月份为完成合同甲生产马件A产品；为完成合同乙生产乙件B产品；为完成合同丙生产七件B产品，乙件C产品。maxZ=500x,-(1000-x,)+400x2-(500-x2)xl20+420x3-(600-x3)x130+400x4-(600-X4)x90-(2x15+3x10+2x10+3x20+4x40+10)/-(15+10+3xl0+20x2+3x40+10)x(x2+^)-(2x15+10+2x20+4x20+2x40+10)x4=290%]+295x2+325x3+260x4-2920002项+x2+x3+2x4<46003x(+x2+x3+2x4<40002X1+3x2+3x3+2x4<60003X1+2*2+与)+4*4<10000sf.，4X1+3(x2+.)+2X4<80000<Xj<1000,0<x2<500,0<x3<600,0<x4<600,5.某公司从事某种商品的经营，现欲制定本年度10至12月的进货及销售计戈h已知该种商品的初始库存量为2000件，公司仓库最多可存放10000件，公司拥有的经营资金80万元，据预测，10至12月的进货及销售价格如表2-9所示。若每个月仅在1号进货1次，且要求年底时商品存量达到3000件，在以上条件卜，建立该问题的线性规划模型，使公司获得最大利润？（注：不考虑库存费用）表2-9进货和销售价格月份1()1112进货价格/（元/件）909598销售价格/（元/件）100100115解七/=10,11,12,为每月购进的货物，= 口2为每月销售的货物。maxZ=100yI0+100yH+115yI2-90xl0-95xu—98xl290xI0+95%.+98阳2W80000资金限制2000+xI0<10000库容限制xn+2000+xio—yjoW10000库容限制x,j+Xu+2000+xio-yin-y..<10000库容限制Xo<2000+xI0stA销量限制y“4X”+2000+x10-X。销量限制yl24xl2+xu+2000+xl0-y10-yn销量限制f+x”+2000+-0-―-%-加=3000年底存量限制x,>0,i=10,ll,12y,>0,*=10,11,12.某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量单价如表2-10所示。表2-10饲料所含的营养成分及价格饲料蛋白质/g矿物质/g维生素/g价格/（元）1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8求这个问题的规划模型，使既满足动物生长的需要，又使费用最小的选用饲料的方案。解设各送这5钟饲料玉，％2,尤3,%4,X5kgominZ=0.2x)+0.7x2+0.4x3+0.3x4+0.8x.3xj+2x2+工3+6X4+18工5—700st.<x}+0.5x2+0.2x3+2x4+0.5x5>30st.<0.5x, +0.2x,+2x4+0.8xs>100I Z J n Jxj9i=1,2,3,4,5.某一企业家需要找人清理5间会议室、12张桌子和18个货架。今有两个临时工A和B可供该企业家雇佣。A一天可清理1间会议室、3张桌子与3个货架；而B一天可清理1间会议室、2张桌子与6个货架。A的工资每天25元，B每天22元。为了使成本最低,应雇佣A和B各多少天？（用线性规划图解法求解）解：设雇佣A和B分别为无丁天minZ=25x+22y

x+y>5st.<3x+2y>12st.<3x+6y>18为整数

由图知A点为最优解，联立方程：3x+2y=12x+y=5解得：x=2,丁=3,即：4加=25》+22^=25x2+22x3=116因此，雇佣A工人2天，B工人3天。8.某外贸公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。1月1II,公司拥有库存1000担杂粮，并有资金20000元。估计第一季度杂粮价格如表2-11所示。表2-11第一季度杂粮价格表进货价/元出货价/元1月2.853.102月3.053.253月2.902.95如果买进的杂粮当月到货，但需到下月才能卖出，且规定“货到付款公司希望本季度末库存为2000担，建立该问题的线性规划模型使上个月总的获利最大。解设一月份买入七担，卖出X担：：月份买入W担，卖出只担：三月份买入与担，卖出马担。

maxZ=3.1Ox；-2.85为+3.25x2-3.05x2+2.95x；-2.90x32.85芭<200001000—%)+%)W50003.05x2<20000-2.85%,+3.10x；st：1000—Xj+—%2+%2-50002.90x3<20000-2.85x)+3.10x；+3.25x；1000—%(+—x?+x2—七+.22000Xj>0,z=1,2,3;Xj>0,y=1,2,3.求下列线性规划问题的所有基解、基可行解、最优解maxz=3%+乙+3占｛网+工2+工3=2再+2x2+4x3=6

xpx2,x3>0

p;<自

解：由题意知：A=V2 4J=(P1.P2.P3)c=(3,1,3)B|=(P1.P2),IB||和，B|是基，石，W是基变量，项是非基变量，令x2覆=0,得玉=-2,x2=4即1X3>L(-2,4,0)T为基解，但不是基本可行解。⑵B⑵B2=(P1.P3),I卬和,4是基,斗，玉是基变量，%是非基变量。令004x2=0,得阳=2/3,七=3/4,即=为基解，同时为基本可行解,Zmax=(2/3)*3+0+4/3*3=6。(3)&="2/3),|当|邦，当是基，%,七是基变量，X是非基变量，令晨11仅、

x21X|=0,得“2=1,七=1,即=为基解，同时为基本可行解，Zmax=1+3=4。(~2\综上所述，基解为1综上所述，基解为1天J=,其中第二个和第三个%2为基本可行解,为最优解。2.%2为基本可行解,为最优解。2.分别用图解法和单纯形法求解下列线形规划问题,并指出单纯形法迭代的每一步相当于图形上哪一个顶点maxzX]=2x]maxzX]=2x]+3x2—%2-1st.-X]<2

x15x2>0存图解法知线性规划模型的可行域如阴影部分所示.存图解法知线性规划模型的可行域如阴影部分所示.CBXB2玉3x20毛0“4b令z=0，1，2 时，maxz逐渐增大，可行域是无界的，所以，此模型是无界解.（2）单纯形法：化为林群型为：maxz=2x]+3x2+Ox3+Ox4X,-x2+x3=1st.<X]+无4=2

xpx2,x3x4>0st.<-11A=V

01㊉-11010X410012a2300对应图中原点。以1㊉为轴心项，换基迭代，得CBY人82%3x20&0b2X11-11010X401©-111a05-20-2此时对应图中A点，坐标是（1,0）以1㊉为轴心项，换基迭代，得CBX人82%3x20X30“4b2X]100123x201-111a0035-7此时对应图中B点，坐标是（2,3）因为，b3=5>0,同时七对应的列小于等于0,则原模型有无界解。maxz=2芭+5x2%!<42x,<12St/3X]+2x2<18

xpx2>0解：（1）图解法:

可行域如上图阴影部分所示，令z=0,1,2……做等值线，得出在c点取最大值，c点坐标为（2,6）,maxz=34（2）单纯形法：化为标准型为:mest.A二C=(2,5,单名ixz= +5x2+0x3+0x4+0x5Xj+x3=42x2+x4=123X1+2x2+x5=18Xj>0,y=1,2……5‘10 10 0] (4'=0 2 0 1 0 12、3 2 0 01J=(P1,P2，P3，Pa，Ps)b=I8>0,0,0) WB=(Pi'P^'Ps)为可行基，Cb=(0,0,0)屯性表如下：CBxB2X5*20“30140X5b0X31㊉010040x402010120X53200118(T25000此时对应图中0点，坐标为（0,0）,以1㊉为轴心项，换基迭代，得2*5公0七0々0X5

2xx10100400201012002©-3016CT05-200-8此时对应图中A点，坐标为（4,0） 以2㊉为轴心项，换基迭代，得CBXb2xi5*20“30X40X5b2x\1010040X4003©1-16501-3/201/23a0011/20-2/5-23此时对应图中B点，坐标为（4,3） 以3㊉为轴心项，换基迭代，得CBXb2x\5X20巧0Z0X5b2Xj100-1/31/320£0011/3-1/325x20101/206a000-11/6-2/3-34由于°■庙=0,基<0,所以存在唯一解，也是最优解。此时对应图中C点，坐标为(2,6),maxz=2*2+5*6=34,(尤1'"2'"3'"4,"5)=(2,6,2,0,0)maxz=2工1+4x22x}+2x2<12Xi+2x?W8stJ 23x2<9xpx2>0解：（1）图解法:

可行域如图阴影部分，当Z=o,1,2……做等值线，已知z=2X|+4%与直线再+2%=8的斜率相同，当z与这条直线重合时，该模型取最大值，因此该模型有无穷多个解，无穷多个解是B,C两点线段中的点，maxz=16(2)单纯形法：化为标准型：maxz2-st.</A=C=(2单纯无=2x]+4x2+0x3+0x4+0x58+2x24-x3=12Cj+2x2+x4=93x2+x5=9>0J=l,2……52 2 1 0 0、12 0 100 3 0 0 1,,4,0,0,0)B=(P3，P4，P5)漾为：，128=(Pl,P2，P3，P4，P5) b=19Cb=(o,0,0)/CB%2xi4X20项0z0X5b0x32㊉2100120z1201080030019a24000此时对应图中点O,坐标为(0,0),以2㊉为轴心项，换基迭代，得

CBXb2王4X20“30X40X5b2不111/20060X401㊉-1/21020030019(T02-100-12此时对应图中点A,坐标为（6,0）以1㊉为轴心项，换基迭代，得CBXB2xi4X20*30*40X5b2Xj101-104401-1/21020002/3-313cr000-20-16此时对应图中点B,坐标为（4,2）由于又七为非基变量，且0'3=0,且此列存在正数，则此线性规划模型有无穷解。其中一个基本最优解为(尤1x(尤1x2X3x4%)'=(420,0,3)，maxz=2*4+4*2=16.用单纯形法求解卜列线性规划问题min/=Xj+2x2—x3I2X1+工2—X3-4x]一2x2+2x3<8%1+x2+ <5xpx2,x3,>0解：化为标准型:maxz=—X]-2x2+七+Ox4+Ox5+0x6

+x2—jc3+x4=4

x(-2x2+2x3+x5=8

%)4-x2+x6=5Xj>O,J=1,2......6

，2 1 -1100] (4、1 -2 2 0 1 0 8A1 1 0 0 0 1 .15,A=、 )b=、，令B=(〃4，〃5，〃6)B为可行基，Cb=单纯形表如下：C=(-1,-2,1,0,0,0)=(0,0,0)CBXb-2X2x30%0%50%6b0%21-110040X51-22㊉01080*6110015cr-21000以2㊉为轴心项，换基迭代，得CBXb-2X2金0%0天50天6b0%5/200]1/2081看1/2-1101/204041/2200-1/211cr-2/3-100-1/20-4°■桩=0, 基<0,存在唯一解，此时斗="2=0,*3=4。min40+2*0-4=4.用大M法求解下列线性规划问题max/=5X]+9+3x3

x,+4x2+2x3>10stxX]—2x2+x3<16〔xi,x2,xi>0解：化为标准型(加上人工变量a)：max/= 4-x24-3x3+0x4+0x5-MaX1+4%2+2xj—x4+a=10st.sx]-2x2+x3+x5=16Xj>0,y=1,2……5

_p4 2-101](明V-2 1 0 1 °7b=V6JC=(5,1,3,0,0)CB5%X23演00天-Mab-Ma1㊉42-I011001-2101016a5+M1+4M3+2M-M00以2㊉为轴心项，换基迭代，得CBXB5%3七0%40V5-Mab5X\142-101100X50-6-11㊉1-16(70-19-750-5-M-10(M+5)以1㊉为轴心项，换基迭代，得CBX!i5a-iX23X30X40X5-Mab5x}1-210101600-6-111-16a011-20-5・M-10(M+8)由于第二列对应的检验数为11>0,并且所对应的列全小于0,则此线性规划模型的解是无界解。5.已知线性规划问题，用单纯形法计算时得到的中间某两步的计算表见表3-16所示,试将表中空白处的数字填上。表3-16单纯形迭代中的两步计算表Xb5*2以30x40%0%bX22310130083X5_4305_2310143

%1304_230120T「zj304_53005工20101541841_J04?804?4x3001__6_4154144150413Xj1002~~4\_\2411541444?4524115560104141411236.已知线性规划问题maxZ=CXXX+c2x2+c3x3"11"1+"12*2+"13“3+尤4~StJtl21-^j+a22X2+。23%3+%=b2x7.>0,j=l,-5用单纯形法求解，得到最优单纯形表如表如表3-17所示：表3-17最终单纯形表X"X]必£%4%b巧10112-12121210-122C厂Zj-3000-4⑴求011，"12,”13,”21，022,“23，0”外的值；⑵求。，。2，。3的值。解：由题意可知：初始的基变量是*4,%,将最终单纯形表的基变量通过迭代转换为％4,%,还原成最初单纯形表，如下：Xb为必%b9214108%5212015

C厂Zj92360C厂Zj9236001（9A-25从而得出： （2C=9-,3,6,0,0所以,"11=2 "12=1"13=47.某公司生产1、2两种产品，市场对1、2两种产品的需求量为：产品1在14月每月需求10000件，5-9月每月30000件，10-12月每月100000件，产品2在3-9月每月需求15000件，其它月每月50000件，该公司生产这两种产品的成本为：产品1在1-5月内生产每件5元，6-12月内生产每件4.5元；产品2在1-5月内生产每件8元，6-12月内生产每件7元。该公司每月生产这两种产品的能力总合不超过120000件。产品1容积每件0.2立方米,产品2每件0.4立方米，该公司仓库容量为15000立方米，占用公司仓库每月每立方米库容需1元；如该公司仓库不足时，可从外边租借，租用外面仓库每月每立方米库容需1.5元。试问在满足市场需求的情况下，该厂应如何安排生产，使总的费用最小？8.某炼油厂使用三种原料油甲、乙、丙混合加工成A、B、C三类不同的汽油产品，有关数据如下表3-18所示。另外，由于市场原因，A的产量不得低于产品总量的40%。问该厂应如何安排生产才能使其总利润最大？表3-18三种原料的信息产f\产规\品ABC原料成本（千元/吨）原料限量（吨）甲>60%>15%1.8002000乙1.3502500丙<20%<60%<50%0.9001200加工费（千元/吨）0.45003600.270售价（千元/吨）3.0602.5652.025

解：设为，勺，均分别为a产品中甲、乙、丙的成分；》4,“5,七分别为B产品中甲、乙、丙的成分；*7,七,与分别为c产品中甲、乙、丙的成分。由题意，有maxz=(3.060-0.450)*(xl+x2+x3)+(2.565-0.360)*(x4+x5+x6)+(2.025-0.270)*(x7+x8+x9)-1.800*(为+工4+、7)-1.350*(工2+/+玉)-0.900*(x3+x6+x9)用计算机求解为：9.线性规划的目标函数是求其值的极大化，在标准的单纯形法求解过程中得到如下表(其中是常数)表3-19求解中某一步的单纯形表gXb2%j528x30x40x50》6b0030205工2%_L2/0x4-2-118（1）在所有的空格上填上适当的数（可包含参数”「"2）（2）判断下面四种情况在什么时候成立，说明理由。1）此解为最优解，写出相应的基解和目标函数值；2）此解为最优解，且此线性规划有无穷多最优解；3）此规划有无界解；4）此解不是最优解，但可用单纯形法得到下一个基可行解。解：⑴CBXb2xj5与&巧0x40%04b0为6003000205x2乩10120"20x4-20-11118%26Hl0-205.-202（2）1）当2-5%<0即%>=时，此线性规划模型有唯一解，基解为（苍,工2，%3）丁=（0,”2，0）T最优值为5H2o22）2-5"1=0,即时，大于0,此线性规划模型有无穷多最优解。3）2-5〃i>0且"i<0,即"1<0时，此线性规划模型有无界解。24）2-5"i>0且"1>0且"2>0,即0<"i<5且"2>0时，此解不是最优解。10.表3-20是求某极大化线性规划问题计算得到的单纯形表。表中无人工变量，为、。2、即、d、G、。2为待定常数。试说明这些常数分别取何值时，以下结论成立。表3-20极大化线性规划问题计算得到的单纯形表XbX3%x5X6bX34a}10a20dX4-1-301-102%%-500-413

cicic20-3 0⑴表中解为惟一最优解;⑵表中解为最优解，但存在无穷多最优解;⑶该线性规划问题具有无界解；⑷表中解非最优，为对解改进，换入变量为X,换出变量为解：(1)当dK),q<o且c2<o,此线性规划模型有唯一解。(2)当dK),C1=O或c2=o,a><0,此线性规划模型有无穷个最优解。(3)当dK),c2>0且ai<0,此线性规划模型有无界解。d(4)当d>0,ci>0且色>12,表中解非最优，为对解改进，换入变量为百，换出变量为“6。第四节量为“6。第四节1.写出线性规划问题的对偶问题。maxz=10X]+3x2+5x3{2%j+5x24-x3<154x.+3.<7xxx>0maxz—5玉+6x2+3x3X]+2x2+2x3=5X]无约束，x2>0,x3<0(2)min(2)minco—5y\+3y2+8y3，一%+4丫3=52y,+5y2+7y3>6stx2y,-y2+3y3<3x无约束,丫2W0，HNOminz=ZZ*Fi=l7=1minz=3阳-2x2+4x3+2x5I3X1+5x2+匕-2x5N6x2+4x3+x5<82%j—3x2+7x3—x4+5x5=0

xpx2>0,x4<0解：⑴miiw=15)”+7y22yl+4y2>105y.>3St.S%+3为N5」”为.maxco-6yl+8y2+Oy33y,+2y3<35yl+%-3%<-2stJ4y2+7%=0-2^1+y2+5y3>2TOC\o"1-5"\h\zy}0,y2<0,乃无约束⑷m nma»y=/ajVj+>为〃,i=l J=1m ns【j,=1 j=lVj,均无约束f=1,2, m; j=1,2,n)2.判断F列说法是否正确，并说明理由。(1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解(2)如果线性规划的对偶问题无可行解，则其原问题也一定无可行解(3)在互为对偶问题的一对原问题与对偶问题中，不管原问题是求最大或最小，原问题可行解的目标函数值一定不超过其对偶问题的可行解的目标函数值(4)任何线性规划问题具有唯一的对偶问题解：(1)不正确。因为当原模型存在可行解且目标函数值无界时，其对偶模型无可行解。(2)不正确。因为对偶模型无可行解，其原模型可能存在可行解且目标函数值无界。(3)不正确。当原模型求最小值时，原模型的目标函数值可能超过对偶模型的目标函数值。(4)正确。对偶模型具有对称性。3.用计算机求解线性规划问题，说明每一种资源的影子价格。maxz=50X]+100x2X]+x2<3002x.+x,<400stJx2<250xx,x2>0解：计算机求解结果如卜图所示:LinearProgramingResults4.3SolutionX1X2RHSDualMaximize50.100.Constraint11.1.<=30050Constraint22.L<■400.0.Constraint301.<»250.50Solution-)50.250.$27,500.由图可知，原模型的最优解为(50,250),其对偶模型的最优解为(50,0,50),三个约束条件的影子价格分别为50,0,50。4.某企业生产甲、乙两种产品，其单位利润分别为2元和3元。每生产一件甲产品需劳动力3个，原材料2个单位。每生产一件乙产品需劳动力6个，原材料1个单位。企业现有劳动力24个，原材料10单位。试问：(1)该企业应如何安排生产才能获得最大利润？(2)若另一个企业想利用该企业的这两种资源(劳动力和原材料)，该企业最低应以多少价格转让？解：设该企业生产甲产品为个，乙产品々个，利润为z,建立模型为maxz=2阳+3x23X1+6x2<24st/2xt+x}<10xt,x2>0(1)化为标准型maxz=10Xj+3x2+0x3+0x42X1+5x2+x3=24st.4X]+3x3+x4=10

x,,x2,x3,x4>0st.(2 5A=I4 3 V,C=(10,3,0,0),b=(2410%最初或纯形表x 251024x 210010a 2300经过换基迭代后，形成最优单纯形表Xb 2X\3X20X30X4bx 012/9-1/32x 10-1/91/34a 00-4/9-1/3由最优单纯形表可知，最优解为（4,2,0,0）,即应生产4个甲产品，2个乙产品，获利最大。（2）由（1）中最优单纯形表知对偶模型最优解为（4/9,1/3）,因此，最低转让价应为24*4/9+10*1/3=14（元）。5.已知线性规划问题minz=8x1+6x2+3x3+6x4—X]—2^2—X4——33/+x2+x3+x4>6st.<x}+x4>2

+.22

>0,j=l,2,3,4（1）写出该问题的对偶问题（2）已知原问题的最优解为：X*=（112 。根据对偶理论，直接求出对偶问题的最优解。解：（1）对偶模型为maxco=-3y\+6y2+2y3+2y4yi+乃+%v82y1+y2<6st，y2+y3+y4<3% 46<0,y2,y3,y4>0(2)根据对偶模型的互补松弛性理论，可知原模型的松弛变量*5=0,*6=0,尤7=0,4=-1。设对偶模型最优解为y",由互补松弛性可知，y'x-o,所以y；=o。又设对偶模型剩余变量为％,治，%，然，且均为正数，互补性有Xx*=o,于是得％="=为=%=o,此时对偶模型的约束条件为-M+%+乂=8_2y*+y；=6«y；+y；+y；=3・♦*,_y+%+%=6y；=0解之得％=2,^2=10>、3=-2, >4=0,6.对线性规划问题maxz=X]+2x2+x3Xj+x2—x3<2x]-x2+x3=\st.<2xl+x2+x3>2xx>0,x2«0,均无约束(1)写出其对偶问题；(2)利用对偶问题性质证明原问题目标函数值z«U解：(1)对偶模型为minco=2y\+yi+2%%+为+2月21%一为+y342st.<一%+%+%=17i2。,力无约束，X4。(2)取对偶模型的可行解(0,1,0),求得对偶模型的目标函数值为1,根据弱对偶性中原模型可行解H标函数值不可能超过对偶模型可行解H标函数值,可证得原模型H标函数值z«l。7.给出线性规划问题maxz=x]+x2{—X]+%2+X3K2-2X]+AT2一工341x[>0,x2>0,x3>0利用对偶问题性质证明上述问题目标函数值无界。min=2yI+y2解：对偶模型为:一力解：对偶模型为:一力-2y2N1月+为21,-20、M，为2°由图解法可知该线型规划模型无可行解，对于原模型可取匹=与=》3=1,说明原模型有可行解，根据弱对偶性可知原模型目标函数无界。8.用对偶单纯形方法求解下列线性规划问题minz=4xminz=4x)+12x2+18x3f%1+3x3>3(1)st.<2x2+2x3>5Xj,x2,x3>0minz=5X[+2x2+4x33x1+x2+2x3>4(2)stJ6x)+3x2+5x3>10x[9x29x3>0解：(1)化为标准中maxz'=T为一12占-18x3+0x4+0x5{-Xj— +z=—3—2x?—2xj+/=-5再,X2,工3,工4，工5N。‘-1 -1 1 0)A=、-2 -2 1 1J,c=H,-12,-18,0,0),b=(-3到用时偶取纯形法斛初始取纯形会为Xb-4xi -12“2 -18x3 0x4 0天 b*-1 0 -3 10-3工20 »2e -2 0 1 -5(7-4 -12 -18 0 0山(R,・12,・18,0,0)40可知B为正则基；以一2④为轴心项，换基迭代得Xb -4X\ -12X2 -18*3 014Ox5

-1 010-3X4-30 110-1/25/2x2b-4 0-60-6以-3㊉为轴心项，换基迭代得Xb-4X\ -12“2-18x30X40X5bX31/3 0-1/3-1/301X2-1/3 11/31/3-1/23/2(y-2 0-2-2-6由于所有检验数bNO,得到最优解为(0,3/2,Do(2)化为标准型maxz'=-5x,-2x2-4x3+0x44-0x5{-3%|一£-2x3+x4=—4—6X]-3x2-5x3+x5="10

xpx2,x3,x4,x5>0A=-3-1-21°〕A=-3-1-21°〕-3-5I1J,c=(-5,-2,-4,0,0),b，4-1-5xi-2X2-4x3 0X4 Ox5 b-3®-1-2 10-4-6-3-5 0 1 -10-5-2-4 0 0-6初始单纯形表为以-3©为轴心项，换基迭代得簿-5』-2X2-4X30X40X5bX]11/32/3-1/304/3/0-le-1-21-2a0-1/3-2/3-5/30以-产为轴心项，换基迭代得Xb-5xi-2X2公0X40X5bX]101/3-11/32/3x20112-12a00-1/3-1-1/3由于所有检验数bNO,得到最优解为（2/3,2,0）«9.对卜列线性规划问题minz=60Xj+40x2+80x3

3%j+2x2+x3>24X[+々+3a：3>42x}+2x2+2x3>3x1?x2,x3>0（1）写出对偶问题;（2）用对偶单纯形法求解原问题；（3）用单纯形法求解其对偶问题；（4）比较（2）与（3）中每一步计算得到的结果解：（1）对偶模型

maxco=2y\+4y2+3y3StJ3y1+4为+2y3-602»+为+2%«40y+3%+2%$8°StJ3，乃，为之0（2）原模型化为标准模型得maxz'=-60Xj-40x2-8OX3+。+0%+。/一3X1—JV?一工3十元4=-2

-4%|一X2-313+元5=—4—2工］—2%—2,Xy+4=—3

xi>0,i=1,234,5,6对偶单纯形法得到的初始单纯形表Xb-60xi-40x2-80七0/40天50X6bX4-3㊉-1-1100-2x5-4-1-3010-44-2-2-2001-3(T以-3-60®为轴心项,-40 -80换基迭代得000x〃-60xi-40x2-80x30X40x50X6b的12/31/3-1/3002/3x505/3-5/3-4/3®10-4/3X60-2/3-4/3-2/301-5/3(y00-60-2000以-4/3®为轴心项，换基迭代得0兀Xb-60xi-40x2-80*3 0x40兀X]11/43/40-1/4010-5/45/41-3/401工60-3/2@-1/30-1/21-1a0-25-350-150以-3/2日为轴心项,换基迭代得Xb-60匹-40x2-80七0匕0X5016b104/93/4-1/12-1/125/6*40055/361-3/4-5/611/6X2012/901/3-2/32/3CT00-260/90-20/325全部的检验数b20,得到最优解为(5/6,2/3,0)。(3)对偶模型化为标准型得max69-2yi+4y2+3y3+0y4+0_y5+0y63丫1+4%+2乂+%=605卜2»+为+2h+为=4°'凶+3为+2必+儿=80J,>0,j=1,2,3,4,5,6初始单纯形表为yB294y23y30)J40%0%b以304310060%21201040)’613200180CT243000

%2yl4y23%0%0%0%b%14/3e2/31/30020%0-5/32/3-2/3100丸05/34/3-1/30060(704/35/3-2/300以4/3®为轴心项,换基迭代得力2yl4y23y30%0”b当3/411/21/40015%5/403/2㊉-1/41025以-5/401/2-3/40035(7-4/301-100以3/2®为轴心项，换基迭代得yB2yl4y23y3 0y4o%b力1/310 1/3-1/3020/3%5/601 -1/62/3050/3九-5/300 -2/3-1/3085/3(T-13/600 -5/6-2/30山全部检验数bW0,得最优解为(0,20/3,50/3).（4）比较第五届1.某公司制造甲、乙两种产品，甲、乙两种产品的产量每天分别为30个和120个。公司希望了解是否通过改变这两种产品的数量而提高公司的利润，制造每个产品所需的加工工时和各个车间的加工能力如表5-10所示。表5-10产品的相关数据车间产品甲产品乙车间能力(每天加工寸数)12030020354032244041.21300利润/每个产品(元)500400假设每天甲、乙产品的生产产量分别为：西,外，则线性规划模型为maxz=500项+400x22项<3003x2<5402X]+2x2<4401.2X1+1.5x2<300X],x2>0使用QM软件求解并回答下面问题。(1)最优解是什么，最大利润是多少？(2)哪个车间的加工工时已用完？那个车间的加工工时还没用完？其松弛变量即没用完的加工工时各为多少？(3)四个车间的加工工时的对偶价格各为多少？请对此对偶的含义予以说明。(4)如果请你在这四个车间中选择一个车间进行加班生产，你会选择哪一个？为什么？(5)目标函数中a的系数在什么范围内变化时，最优解不变。(6)目标函数中期的系数从400提高到490时，最优解变了没有，为什么？(7)请解释右端常数项各值的上限和下限。(8)车间1的加工工时数从300增加到400时，总利润能增加多少，这时最优解变化了没有？(9)车间3的加工工时数从440增加到480时，能否求得总利润增加的数量？为什么？解：(1)将原模型变换成标准形

vA取BC-maxz=500^+4OO.r2+(2X] =3003x2+x4=540st.<2x]+2x2+x5=4401.2%1+1.5x2+x6=30(xi>0,i=1,2,3,4,5,6，2 0 1 0 0 0] (300、0 3 0 1 0 0 540= b=2 2 0 0 1 01 440J.2 1.5 0 0 0 1) (300,=(P3PaPsP6)为可行基,则GCPB-'A=C,得到最初单纯形表为：%+0x4+0x5+0x6C=(5004000000)=(0000),CBB-'b=0,B-'A=A,CBXB500xt400x20X30x4%°》6b0七2®010003000匕0301005400*522001044001.21.50001300c厂-Zj5004000000500X|100.50001500%4030100540002®-10101400乙01.5-0.6001120c厂0400-250000500苞100.50001500%001.51-1.50330400x201-0.500.5070

04000.150-0.7511500-500-2000最优解为:阳=150,x2=70最大利润：maxZ=500a+400x2=500x150+400x70=10300(2)由最终单纯形表知：W=9=0,x4=330,x6=15(因此，一车间和三车间的加工工时已用完，二车间和四车间没有用完，分别剩余330和15个加工工时。(3)由最终单纯形表知：第一车间的影子价格为(50),即50,第二车间的影子价格为(200),即200。这表示在一定范围内，第一车间每增加一个设备台时，目标函数增加50；第二车间00.5000、001.51-1.5001-0.500.50、000.150-0.75b4000)<0每增加一个设备台时，H标函数增加200。4000)<0(4)选择第三车间，因为第三车间的影子价格高，每增加一工时带来的利润大。(5)由最优单纯形表知：C=(5004000000),CB=(500+204000),’100.50 0 0)001.5 1-1.5001-0.50 0.5 0B'A=、000.150-0.751；O范的系数为基变量系数，因此，设：G的波动为丸，令。=500+丸，要使优解不变，贝IJ：C-CbB~'A<0t即:(500+24000000)-(500+20解得：2<—100, c\=500+,,ci—(6)设的波动为4，令。2=40叶丸，若使最优解不变，则：C-CbB-'A<Qy即:(500400+20000(500400+20000)-(5000400+20)(100.500001.51-1.501-0.500.5<000.150-0.750、00<0解得：一400W；lV100,V2<-100.-.0<c2<500o(7)常数项波动变化，当4变化时，只要则8仍是最优基。令E=300+4,贝ij：'0.5000、’300+2、1.51-1.50540-0.500.50440B-1b>0,HP：、0.150-0.75b、300；>0解得：一100WXW140,；b,=300+4,二200444440同理：分别令b2=30°+4,b?=300+4，b4=300+24;解得：h2e[210,+od),300<b3<460,b4e[285,+oo)(8)400在常数项变化范围<200,440)之间,因此，总利润变化量:50x(400-300)=5000；最优解变化为：(9)不能，因为常数项变化超出其变化范围(300,460)02.已知线性规划问题：maxz=匹+2x2—2^1+x]42—工I+2x?<7stJXj<3xpx2>0的最终单纯形表如表5-11所示。表5-11最优单纯形表CbXb2x20x30x40x5b2%010%%51X|1000130X3001-%.%3c—zJ"J000-1-2(1)写出其对偶模型；(2)求出对偶模型的最优解；(3)写出最优基6及其逆矩阵5」；(4)若右端项变为"=(2，12,2)丁，最优基是否变化？求出变化后的最优解及其最优值。解：(1)其对偶模型为:

mins=2乃+7乃+力-2^1-y2+y3>1st.'y+2y2>2)1，力，>320(2)原模型最优解为：(3,5,3,0,0)',设对偶模型最优解为Y*Xs=0,知X*=0；设对偶模型的剩余变量为打，打，由YsX=0知：3打+5匕=0,由于剩余变量均为非负，故L=o,痣=0,此时对偶模型的约束条件为:YI=0Y2=lY3=2(3)最优基为-2匕-石+匕*=1Y*+2Y*=2K,YI=0Y2=lY3=2(3)最优基为-2匕-石+匕*=1Y*+2Y*=2K,=0B=（P2,P],舄）=2、0-2-11•・•解得对偶模型的最优解为:1]0,即：8°,1/20-1/2K=0丫2*=2Y；=11/2'13/2,(4)常数项波动变化，当U变化时，只要8一620,则B仍是最优基。令3=2+4,b2=7+22(b3=3+23|ji|j：5-'b>0解得：\g[-b+oo}2,[-343}21[l,+oo)当常数项b'=(2，12,2)在其变化范围中变化，故最优基不变；最优解为(2,6,0,2,0)二最优值为14。.给出了下列线形规划：maxz=6x]+2x2+12x35

f4%j+£+3x3<24

stJ2xl+6x2+3x3<30

x,,x2,x3>0的最优单纯形表如表5-12所示。表5/2最优单纯形表4 Xb6%,2x212x3Os,Os2b12 %A3131_LJ080 S2—250-116cj-zj-10一20-40(1)求出最优基不变的外的变化范围；(2)求出最优解不变的。3的变化范围；(3)在原线性规划的约束条件上，增加下面的约束条件：西+232+2与412其最优解是否变化，如变化，求出最优解。8―尸0]解：⑴设b2的变化为b2+" M,只要MbNO,则b仍为最优基2>-6,即：b2+2>24,即外在[24,+8)上变化是最优基不变。(2)设的变化为C3+2,要是最优基不变，则C-C88TA40,即：/ 、/ /4/31/311/30(6212+200)-(12+20) 0 []=(-10-42/3-2-2/30-4-2/30)<02>-6.•・。3+226即当在[6,+00)上变化时，最优解不变(3)其最优解变化为(006612°)，.有一标准型的线性规划问题：maxz=CX

[AX=bs.t<[X>0其最优单纯形表如表5/3所示：表5-13最优单纯形表cbXbCjXjc}x2C3X3C4X4hCl匹10-13-11%必012-11200-3-3-1z=8其中：乙,七是对用于初始单位矩阵的松弛变量。试求:(1)利用最优单纯形表求弓，,2，。3，。4，。5。

△b=△b=（2）假定用〃+龙功代替〃，其中-1,-CO<2<+CO,要使现行最优基B保持不变，见的变化范围？当'时，求最优解。（3）求约束影响价格。解：（1）从最优单纯形表中得出:-1由于“4,“5是松弛变量所以。4,均为0。根据%―8"知:(C,,C2,C3,C4,C5)-(C,,C2)一123(C,,C2,C3,C4,C5)-(C,,C2)一123-1-1=(0,0,-3,-3,-1)得出：。，。2，。3，。4，。5分别为2,3,1,0,0。（2）要使最优基不变，则4，3=B'b>0,即I-1-1>0得出:2。当2,在区间内，最优基不变,最优解为:33(x1,x2,x3,x4,x5)T=(-,-,0,0,0)T（3）根据影子价格与松弛变量之间的关系知：必=（3）根据影子价格与松弛变量之间的关系知：必=3>2=1.有最大问题的最优单纯形表如下，其中*4，与为松弛变量。苞与%4 %0-11311-10—100-30一3-1表5・14最优单纯形表x3汇］⑴写出该问题的最优解。⑵当为何值时，其对偶问题无解？并说明理由。解：（1）由以上的最优单纯表得出最优解为：（玉/2，七,34，/）T=（4,0,2,0,0）1（2）若原模型有可行解但目标函数值无界，则对偶模型无解。设C=（q,C2，C3，C4，C5）,因为C4，为松弛变量，所以均为。。

-1-1b=c-GBM=(J,c2,c3,o,0)-(c3*c-1-1解得：ci=0, 。2=4C3=l设。3=。3+A。3,当C-CrB'Awo时，最优基不变，即C-C*'^=(0,-4,1+八。3,<0 -1 1 3 1]0.0).(1+Ac3,0)V -1 0 T °J<0 解得:心"不即当-七443时，最优基不变。此时0*2=。2—GfB12=4(C3+.3,0)V-U=.3+^C3当0'2K)且-仁八。3/3时，原模型有无界解，即八。3=3时，对偶模型无可行解。6.考虑下列线性规划：maxz--5x|+5x2+13巧{—X]+勺+3巧—2012xj+4工2+10x3«90xz>0,/=1,2,3最优单纯形表如表5・15所示：表5/5最优单纯形表Xb再%b一113102()%160-2-4110%00-2一50100(1)写出此线性规划的最优解、最优基8和它的逆(2)求此线性规划的对偶问题的最优解；(3)试求。2在什么范围内，此线性规划的最优解不变；(4)若优=20变为45,最优解及最优值是什么？解：(1)由最优单纯形表知：最优解为&|,%2，%3，34，%5)1=(0,20,0,0,10)T(2)因为对偶模型的最优解是原模型松弛变量检验数值的相反数，所以，对偶模型的最优解为：y=5, %=0。(3)设。2=。2+/1,C2是基变量对应的系数，要使原模型的最优解不变，则C.CbB'A^即—W4W0 —Wc?«5解得：3，所以3 2 ,c?在此范围内变化时，此线性规划模型最优解不变。<1 0]（20+/1]（4）设仇=仇+丸，当夕620时最优基不变，即I"4 1八90 J>0>解得:5 45-20<2<- 0<6.<— , ,2即'2。若4=20变为45,最优基发生变化，将45代入伍，重新用单纯形表解得最优解为（0,0,9）T,最优值为117。97.分析线性规划问题中。变化时最优解变化情况：maxz®)=(3+26储+(5-0}x2 ®>0)st.<Xj<42x2<123Xj+2x2<18xnx2>0解：化为标准型：maxz(6)=(3+26)x]+(5-^)x2+0x3+0x4+0x5 >0)jq+X3=42x2+x4=12Stio-r4人2十人s—10XjNO,j=1,2,...,5IX 1 八 八、 、1 U 1 U UA=0 2 0 1 0 b=? 7 0 0 14121R /n<nnn单纯形表如下：CB（3+2。）X(5-(9)x20*30X40X5b0x31㊉010040%02010120X53200118a3+2。5-0000

以1㊉为轴心项，换基迭代得:CBXb(3+2。)演(5-。)Z0X30X40X5b3+2。%1010040%0201012002㊉-3016CT05-0-3-2000一12-8。当。>5时，b<0,此线性规划模型有唯一解，最优解为(占,%2，七,z4，匕)1=(4,0,0,12,6)T 。当。=5时，%=0且对应的列存在正数，有无穷个解。当。<5时，ct2>0,以2㊉为轴心项，进一步换基迭代，得:CBXb（3+2。）X]（5-e）%0X30X40X5b3+2。不1010040%0031-165-0X201-3/201/23a00211. u220--+-e22—27—50由于。<5,则b<0,此线性规划模型有唯一解，最优解为：(^1,x2,x3,x4,x5)T=(4,3,0,6,0)T8.现有线性规划问题maxz=-5X1+5x2+13x3{-X|+X1+3Xj42012X]+4x2+10x3<90

xi,x2,xi>0先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化?(1)第一个约束条件的右端常数由常数20变为30：(2)第二个约束条件的右端常数由常数90变为70：(3)目标函数中巧的系数由13变为8；H(4)项的系数列向量由(“J变为(5人⑸增加一个约束条件2xi+3々+5巧(50；(6)将原来第二个约束条件改变为10xi+5x2+10x3<100解：单纯形法求得最优单纯形表为Xb-5xi5X213X30Z0x5b 由x2-11310表用得，20最优解X5160-2-4110 为(0,b,00-2-5020,0),B=f1(Pi,Ps),B-'=I-4 1J(1)设4波动为4,0hB-,a='1 0、<~4b(20+4)190J，20+4)=JOfJ20,得-20<A<2.25,即W22.5时最优解不变。所以当A从20变为30时，最优解已经改变为(0,0,9).q0](20 ](20 、(2)设打波动为4,由限4=(-4 1八90+aJ=(10+4八0,得4N10,即4280时最优解不变。所以当打从90变为70时，最优解已经改变为(0,5,5),(3)由8=(%,Ps)知为非基变量系数，其变化幅度a<%=2时，最优解不变。所以当G从13变为8时，2=8-13=-5<2,最优解不变。尸1(4)当玉系数列向量由(12J变为时，最优单纯形表为Xb-5X1 5X2 1313Ox4 Ox5

x20131020 由表可知，x510-2-4110 最优解5-50-2-50仍为(0,20,0).(5)增加约束条件2玉+3々+5七450后，模型变为maxz--5x)+5x2+13x3—Xj+/+3x3W2012x}+4x2+10x3<90

stx '2%j4-3x2+5x3<50xpx2,x3>0最优单纯形表为Xb-5x\5X213*30X40X50^6b-5/4013/40-1/45/2x527/200-5/4127/640/3x233/1210-5/403/425/2CT-5/200-7/20-23/6由表得最优解为(0,25/2,5/2).(6)条件改变后模型变为maxz——+5x2+13x3{一再+工2+3x3V20IO%)+5x24-10x3<100X1，X2,X3>0最优单纯形表为麓-5xi5x213*30X40X5bz-1131020x?150-5-5000 0 -2 -5 0 以： 优解为(0,0,0).9.求最大化线性规划的模型的最初始单纯形表及最优单纯形表如表5-16及5-17所示。(1)填写最优表5-17中空白处的数字。(2)写出原线性规划问题。(3)写出其对偶线性规划模型及其最优值。(4)当〃变为〃+，**其中"=0一1°)、问2在什么范围内变化，原最优基不变？(5)目标函数必的系数。2从-1变为-2,原最优基是否会改变？求出。2=-2时最优值。表5-16最初单纯形表3Xb2x}-13卜30x40%0几b0x4311100瓦0%142010%0%11-1001打%2/1000表5-17最优单纯形表cBXb2%]-1X2以30x40x50》6b0x4-1-2152X]121210-1_12125aJ解：(1)填入数字后，单纯形表为CBXk2x)一支250x40*50%b0x40011-1-2152X]101/20121210-101-3/20_12125%00-3/20-3/2-1/2(2)原线性规划模型为maxz=2X1-％+x33xj+x2+x3<50%1- 4~K5st.<Xj+x2—x3<15Xj20,1=1,2,3,4(2)其对偶模型为maxco=50yl+5y2+15y33%+为+%22,%一%+为2-1st.<凹+2丁2-月21y,>0,/=1,2,3对偶模型的最优解为最优单纯形表的检验数相反数，即(0,3/2,1/2).(4)要使最优基不变，q—1-2、’15+4、'2几-5 、01/21/210-A15/2-A/2则BT@+劝*尸e-1/21/2,A,=//2-5/2)>0解得544415。(5)々为基变量，从一1变为一2后，%=。2_仆B"P2=2W0,原最优基不变。c2=-2时最优值为10。10.A投资公司为很多公司和个人管理资金，公司的投资策略应该符合客户的需求，有一位新客户委任A投资公司对120万元进行两方面投资，股票和货币市场，每单位股票市场投资资金是50元，年资金收益率为10%；每单位货币巾场投资资金是100元，年资金收益率4%。客户希望在满足年投资收入至少是6万元的前提下，尽量降低风险。通过A投资公司风险测量系统可以知道，投资在股票市场的单位数量风险指数是8,投资在货币市场的单位货币数量风险指数是3。A投资公司的客户要求在货币市场上的投资至少是30万元。(1)试建立风险指数最低的投资方案模型，并用单纯形法求解这个问题；(2)最优值是衡量投资风险程度的尺度，增加每年收入的要求会对投资组合的风险尺度产生什么影响？(3)求多的影响范围：(4)如果对每年收入的要求从6万元增加到6.5万元，那么最优解和最优值会如何变化？(5)如果对股票基金的风险评定从8增加到9,那么最优解和最优值如何变化？解：(1)设股票市场投资玉单位，货币市场投资超单位，建立的模型为minz=8%+3x2SOx.+lOO^<1200000

5X1+4x2>60000S1 100x2>300000xt,x2>0单纯刑法求得的最优单纯形表为蜀8xi3X20*30X40x5bx5001.666716.6671700,000X]10-0.0133-0.33304,000x2010.01670.1667010,000a00-0.0567-2.16670最优解为(4000,10000),最优值为62000。(2)在一定的范围内增加每年年收入的要求风险尺度不变，超出一定的范围后，风险尺度将变高。(3)由B"bNO可知在4800044W102000时，最优基不变，在此范围内变动无影响。(4)当年收入由60000变为65000时,最优解变为(5666,9166),最优值变为72833。(5)股票风险评定有8变为9时，最优解不变，仍为(4000,10000),最优值变为66000.1.某公司在三个地方有三个分厂，生产同一种产品，其产量分别为300箱、400箱、500箱。需要供应四个地方的销售，这四个地方的产品需求分别为400箱、250箱、350箱、200箱。三个分厂到四个销地的单位运价如下表7-35所示：表7-35单位运价表

甲乙丙T1分厂211723252分厂101530193分厂23212022(1)应如何安排运输方案，使得总运费最小？(2)如果2分厂的产量从400箱提高到了600箱，那么应如何安排运输方案，使得总运费最小？(3)如果销地甲的需求从400箱提高到550箱，那么该如何安排运输方案，使得总运费最小？解：(1)这个问题是产销平衡运输问题。由伏格尔法得初始调运方案为：销地产地甲乙丙J产量/箱1分厂250503002分厂40004003分厂350150500销量/箱4002503502001200由位势法判别：建立方程组[w+Uj=Cij(%为基变量对应运价)-Vj=0解得：V2=-6,v3=-3.5=16,U2=17,u3=23,iu=25山非基变量Xij检验数Oij=Vj+Uj-Cij,得出Ojj<0,该方案即为最优。即：应安排1分厂给乙供货250箱，给丁供货50箱，2分厂给甲供货400箱，3分厂给丙供货350箱，给丁供货150箱，此时总运费最少。(2)这个问题是产大于销的运输问题。为了求得产销平衡，在产销平衡表中增加一个虚拟的销地戊，其销量为200箱。则产销平衡表和单位运价表如下：销地产地甲乙丙丁戊产量/箱1分厂2117232503002分厂1015301906003分厂232120220500

销量/箱4002503502002001400由伏格尔法得•初始调运方案为：销地 甲产地乙丙丁戊产量/箱1分厂25050(-50：(+50)300④2分厂40020006003分厂③②500300(+50)200(-50)销量/箱4002503502002001400由位势法判另।Vi+iij=GjYVj=0由非基变量Xij检验数©ij=Vi+Uj-Cij,得出。心)，.•.该方案即为最优。即：应安排1分厂给乙供货250箱，2分厂给甲供货400箱，给丁供货200箱，3分厂给丙供货350箱，此时总运费最少。(3)这个问题是销大于产的运输问题。为了求得产销平衡，在产销平衡及中增加一个虚拟的产地4分厂，其产量为150箱。则产销平衡表和单位运价表如下：销地产地1分厂甲乙丙T产量/箱211723253002分厂101530194003分厂232120225004分厂0000150

销量/箱5502503502001350由伏格尔法得初始调运方案为:销地产地甲乙丙T产量/箱1分厂502503002分厂4004003分厂100(-100)200(+100)200500②(3)4分厂①④150(+100)150(-100)销量/箱5502503502001350由位势法判别:建立方程组「Vi+Uj=CijIVj=O山非基变量Xij检验数5j=Vi+UrCij,得出。41>0，•••该方案不是最优方案。故调整方案，由闭合回路法得出新的调运方案：销地产地甲乙丙T产量/箱1分厂502503002分厂4004003分厂300(+50)200(-50)5004分厂100②50(-50)①(+50)150销量/箱5502503502001350由位势法判别:建立方程组“Vi+Uj=CijYVj=0由非基变量X/故调整方案，日销地产地佥验数Oij=Vi+Uj・Cij,得出。44>0，，该方案不是最优方案。1闭合回路法得出新的调运方案：甲乙丙T产量/箱1分厂502503002分厂4004003分厂350150500

4分厂10050150销量/箱5502501350由位势法判别：建立方程组“Vi+Uj=CijYVj=0由非基变量Xij检验数5j=Vi+Uj-Cij,得出。以0,.,.该方案即为最优。即：应安排1分厂给甲供货50箱，给乙供货250箱，2分厂给甲供货400箱，3分厂给丙供货350箱，给丁供货150箱，此时总运费最少。.用表上作业法求下表7-36所列运输问题表7-36各个运输点之间的运量与收量三B,B,B,B」瓦里A,87149a234629X561062收量5537解：这个问题是产销平衡运输问题。由伏格尔法得初始调运方案为：发点收点Bib2b3b4发量/件A\369Az5(-2)②—3(+2)—.③19A,①④2(+2)2(-2)收量/件553720由位势法判别：建立方程组"vj+Uj=Cij（Cij为基变量对应运费）"Vj=0由非基变量Xij检验数Ojj=Vi+Uj-Cij,得出61=0,其余检验数均小于0o,该方案是最优方案，且不是唯一最优的，该问题存在另一最优解。故进行方案调整，调整后得另一最优解为：发点收点B（b2B3b4发量/件A\369

A23519A322收量/件553720即要想使运费最少，应作如下安排：B)―、A[(5)>Bi-»A](3)、A3(2),Bj—*A](3),B4~»A\(6)、A](1)或者，B(->A2(3)、A3(2),B2TA2(5),B3TAi(3),B4TAi(6)、A2(1).某种产品今后四周的需求量分别是300、700、900、600件，必须得到满足。已知每件产品的成本在起初两周是10元，以后两周是15元。工厂每周能生产这种产品700件，且在第二、三周能加班生产，加班后，每周可增产200件，但成本每件增加5元。产品如不能在本周交货，则每件每周存储费为3元，问如何安排生产时总费用最少。（要求建立运输问题模型但不求解）解：设“4为第i周运往第j周的产品数量，1=1,2,3,4户1,2,34再"6'分别表示第2、3周加班生产运往第j周的产品数量minZ=10阳1+13xj2+16肛j+19x\4+10422+13工23+16攵4+15町3+18x34+15x44+15叼2+1如3+2出4+15163+1^x64卬=300xl2+x22+x52=700再3+工23+工33+工53+工63=90°再4+X24+工34+工54+X64=60°X”+/2+工13+X\4-700x22+x23-16x24<700X33+0—700^44<700x52+x53+x54<200%+%<200/NO/=l,2,3,4,5,6,j=5,6,7,8.求解下列模型+8X31+2x22+TxH+xl2+x}3=100々1+X22+X23=50工31++8X31+2x22+TxH+xl2+x}3=100々1+X22+X23=50工31+》32+》33=60X4I+x42+X43=4033+5*41+542+2^43xH+x21+x3I+x4J=85

X|2+x22+x32+x42=90

X|3+X23+X33+X43=75

X">0,i=1,2,3,4;；=1,2,3

解：设Ai为第i(i=l,2,3,4)行，Bj为第j(j=l,2,3)歹ij,则由一知得该线性规划模型的约束条件和系数表为：BjAjA]Bib2b3LAi324100A?24550A、82160A455240EBj859075250由伏格尔法得初始表为:BjAiBiB2b3LAiA,35(-25)②65(+25)③100A?5050a325(-25)_⑤60④35(+25)A4①(+25)―®40(-25)40ZB)859075250由位势法判别：建立方程组「Vi+Uj=Cij(Cij为系数)1Vi=0Ai非基变量Xjj检验数5j=Vi+Uj-Gj,得出%>0，；•该可行解不是最优解。故调整方案，由闭合回路法得出新的解：B,ABib2b3£AiA]1090100A?5050A、253560

A44040ZBj859075250由位势法判别:建立方程组「Vi+Uj=Gj(eg为系数)IV)=0由非基变量Xij检验数Oij=Vj+Uj-Cij,得出5jVO,・••该可行解即为最优解。即：Xn=10,x)2=90,X|3=0X21=50,X22=0，X23=0X31=0,X32=25,X33=35X4i=0, X42=0, X43=405.某公司有A|，A2,A3三个分厂已分别制造生产了同一产品35oo件，2500件，5000件。在公司生产前已有B|,B2,B3,B4四个客户分别订货1500件，2000件，3000件,3500件。客户B1,B?在了解到公司完成订货任务后，产品有1000件剩余，因此都想增加订货购买剩余的1000件产品。公司卖给客户的产品利润（元/件）见下表7-37,公司如何安排供应才能使总利润最大。表7-37公司从不同的客户处所获的单件产品利润利润（7地B.B2B,B4A、10567A?8276A39348B,B；B28；B3B4产量Ai-10-10-5-5-6-73500AI-8-8-2-2-7-62500A、-9-9-3-3-4-85000

M0M0MM1000销量150010002000100030003500解得820006.某电站设备制造厂根据合同要从当年起连续三年末各提供三种规格型号相同的大型电站设备。已知该厂这三年内生产大型电站设备的能力及每套电站设备成本如下表7-38所表7-38生产大型电站设备的能力及每套电站设备成本年度正常生产时间内可完成的电站设备数加班生产时间内可完成的电站设备数正常生产时每套成本/万元123500242600313550已知加班生产时，每套电站设备成本比正常生产时高出70万元，制造出来的电站设备如当年不交货，每套每积压一年造成积压损失为40万元。在签订合同时，该厂已积压了两套未交货的电站设备，而该厂希望在第三年末完成合同后还能存储一套备用。问该厂应如何安排每年电站设备的生产量，使在满足上述各项要求的情况下，总的生产费用为最少？解：B,4产量A5005405802A；57061065034M6006404A；M6707102&MM5501A：MM6203s40801202销量3341.安排4个人去做4项不同的工作。每个人完成各项工作所耗用的时间如下表表8-5每个人完成各项工作所耗用的时间ABCD甲20192028乙18242720

丙26161518丁17202419(1)应指派哪个工人去完成哪些项工作，可使总消耗时间最少？(2)如果将上述表中的数据看成创造效益的数据，那么应如何指派，可使总效益最大？(3)如果在上表中再增加一个人戊，他完成A、B、C,D工作的时间分别是16、17、20、21,这时应指派哪些人去完成哪项工作，使总时间耗用最少？(4)如果在上表中再增加一个工作E,4人完成该工作的时间分别是17、20、15、16,这时应如何指派哪些人去干哪项工作，使总时间耗用最少？‘-20-19—18-24‘-20-19—18-24-26-16(2)将矩阵中各项变为负数，即C=「17-20换,尸980〕(86行变换、9307列变换、9001011X077405,17I—20-28、-27-20-15-18—24，用匈牙利算法，先进行行变80、(868◎]07试指派、9007118©711805,7105.解：⑴行变换、’201918242616J*20'1019、06922028、27