最全运筹学习题及答案

第1页共64页运筹学习题答案第一章（39页）11用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）MAX12ZX51050X2142X，01（2）MINZ151X2331X2，01X（3）MAXZ221X211X2052，01X（4）MAXZ1X201X233，01X2解（1）（图略）有唯一可行解，MAXZ14（2）（图略）有唯一可行解，MINZ9/4（3）（图略）无界解（4）（图略）无可行解12将下列线性规划问题变换成标准型，并列出初始单纯形表。第2页共64页（1）MINZ34251X234X422X23431412322X234X，0，无约束1（2）MAXKZSP1NMKIKIZAX1,IKN0I1NK1,MIKX（1）解设Z,0Z4X565X6标准型MAX342500MMZ12356789X10ST4221X235X6103147232221X235X689X,023567891初始单纯形表JC3425500MMBCXB1X23X56X78X910XIM10X24121100012071411311100014第3页共64页M9X22312201102/3Z4M36M4M423M3M553M0M002解加入人工变量，得1X23NXMAXS1/MMMKP1NIMKIK12NSTI1,2,3,N1MIIKX0,0,I1,2,3NK1,2,MIKIM是任意正整数初始单纯形表JCMMM1KAP12K1MKAP1NK2NKAPMNKAPBCXB1X2NX112X1X1NX2NNXIM1110011000M2X10100000MN1001000111SNM000KAMP12K1MKAMPNK2NKAMPMNKAP13在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。（1）MAXZ23471X234X234826731X34X,022MAXZ52361X34X第4页共64页23471X234X22301X34（1）解系数矩阵A是267令A，1P234与线形无关，以（，）为基，为基变量。1P21X2有23841X23X42367令非基变量，03X4解得1；212基解（1，2，0，0为可行解XT81Z同理，以（，）为基，基解（45/13，0，14/13，0是非可行解；1P32XT以（，）为基，基解（34/5，0，0，7/5是可行解，117/5；43T3Z以（，）为基，基解（0，45/16，7/16，0是可行解，163/16；2344以（，）为基，基解（0，68/29，0，7/29是非可行解；P45XT以（，）为基，基解（0，0，68/31，45/31是非可行解；36最大值为117/5；最优解（34/5，0，0，7/5。Z3T（2）解系数矩阵A是134第5页共64页令A，1P234，线性无关，以（，）为基，有1P227341X23X4232令，0得3X41/3，11/312基解（1/3，11/3，0，0为非可行解；XT同理，以（，）为基，基解（2/5，0，11/5，0是可行解43/5；1P32XT2Z以（，）为基，基解（1/3，0，0，11/6是非可行解；43以（，）为基，基解（0，2，1，0是可行解，1；234T4Z以（，）为基，基解（0，0，1，1是3；4P6X6最大值为43/5；最优解为（2/5，0，11/5，0。2Z2T14分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。（1）MAXZ21X2351562241X2，0（2）MAXZ251X241X21232181X2，0第6页共64页解（图略）（1）MAXZ33/4最优解是15/4,3/4单纯形法标准型是MAXZ2001X234XST35151X2362244,01X23单纯形表计算JC2100BCBXB1X23X4I03X1535105042462014Z0210003X30411/23/421411/301/612Z801/301/312X3/4011/41/82115/4101/125/24Z33/4001/127/24解为（15/4，3/4，0，0TMAXZ33/4迭代第一步表示原点；第二步代表C点（4，0，3，0；T第三步代表B点（15/4，3/4，0，0。T（2）解（图略）MAXZ34此时坐标点为（2，6）单纯形法，标准型是MAXZ250001X234X5第7页共64页ST41X3212432181X25,024表略最优解X（2，6，2，0，0TMAXZ34迭代第一步得（0，0，4，12，18表示原点，迭代第二步得1XT（0，6，4，0，6，第三步迭代得到最优解的点。2T15以14题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。解目标函数MAXZ1CX21当0时2C（/）Z/其中，K/X1C21X2C1C23/5，3ABKBCKK时，1C，2同号。当0时，目标函数在C点有最大值2C当0时，目标函数在原点最大值。BCKKAB时，1C，2同号。当0，目标函数在B点有最大值；2C当0，目标函数在原点最大值。ABKK0时，1C，2同号。当0时，目标函数在A点有最大值2C当0时，目标函数在原点最大值。第8页共64页K0时，1C，2异号。当0，0时，目标函数在A点有最大值；2C当0，10时，目标函数在C点最大值。KABK时，C，2同号当0时，目标函数在AB线断上任一点有最大值2C当0，目标函数在原点最大值。KBCK时，1C，2同号。当0时，目标函数在BC线断上任一点有最大值2C当0时，目标函数在原点最大值。K0时，1C0当0时，目标函数在A点有最大值2当0，目标函数在OC线断上任一点有最大值C（2）当0时，MAXZ1C2X0时，目标函数在C点有最大值1C0时，目标函数在OA线断上任一点有最大值1C0时，在可行域任何一点取最大值。16分别用单纯形法中的大M法和两阶段法求解下列线性问题，并指出属于哪类解。（1）MAXZ2351X2315X2325241，0X（2）MINZ231X23第9页共64页4281X23326，01X23（3）MAXZ1015121X23X5391X23561515X251X3，0（4）MAXZ221X2361X232220X3，01解（1）解法一大M法化为标准型MAXZ235M0M1X234X56ST7425101X35X6,0M是任意大整数。4单纯形表JC235M0MBCXB1X23X45X6IM4X71111007第10页共64页M6X102510115Z17M3M234M2M50M0M4207/21/211/21/24/721X515/21/201/21/2Z2M1007/2M805M6005M115M132X4/7011/72/71/71/72145/7106/75/71/71/7Z102/70050/7M16/71/7M1/7最优解是X（45/7，4/7，0，0，0T目标函数最优值MAXZ102/7有唯一最优解。解法二第一阶段数学模型为MINW4X6ST71X234X251056,，,01X34X（单纯形表略）最优解X（45/7，4/7，0，0，0T目标函数最优值MINW0第二阶段单纯形表为JC2350BCBXB1X23X5I32X4/7011/71/72145/7106/71/7第11页共64页Z102/70050/71/7最优解是X（45/7，4/7，0，0，0TMAXZ102/7（2）解法一大M法Z有MAXMIN（）MINZZZ化成标准形MAX2300MM1X234X567XST42412346326X57X,，,，01246（单纯性表计算略）线性规划最优解X（4/5，9/5，0，0，0，0T目标函数最优值MINZ7非基变量的检验数0，所以有无穷多最优解。3X3两阶段法第一阶段最优解X（4/5，9/5，0，0，0，0是基本可行解,MINW0T第二阶段最优解（4/5，9/5，0，0，0，0MINZ7非基变量的检验数0，所以有无穷多最优解。3X3（3）解大M法加入人工变量，化成标准型MAXZ101512000M1X23X45X67XST5395615151X23X52567,，,，01X345X单纯形表计算略第12页共64页当所有非基变量为负数，人工变量05，所以原问题无可行解。7X两阶段法（略）（4）解法一大M法单纯形法，（表略）非基变量的检验数大于零，此线性规划问题有无界4X解。两阶段法略17求下述线性规划问题目标函数Z的上界和下界；MAXZ1CX21AB22X其中，13C246C182B2014B13A，125A2A解求Z的上界MAXZ361X2ST21224141X2，0加入松弛变量，化成标准型，用单纯形法解的，最优解X（0，7/2，5，0T目标函数上界为Z21存在非基变量检验数等于零，所以有无穷多最优解。求Z的下界线性规划模型MAXZ41X2ST35846101X2，0第13页共64页加入松弛变量，化成标准型，解得最优解为X（0，8/5，0，1/5T目标函数下界是Z32/518表16是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，D，为待定常数，试说明这些常数分别取何值时，以1A231C2下结论成立。（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为，换出变量为。1X6X基B123X4X5X6XD3X41A102A02413011036X350041JJCZ1C2C0030解（1）有唯一最优解时，D0，0，01C2（2）存在无穷多最优解时，D0，0，0或D0，0，0C1C2（3）有无界解时，D0，0，0且1C21A（4）此时，有D0，0并且，3/D/43319某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下班次时间所需人数16点到10点60210点到14点70314点到18点60418点到22点50522点到2点2062点到6点30设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。第14页共64页解设（K1，2，3，4，5，6）为个司机和乘务人员第K班次开始上班。KXKX建立模型MINZ1X234X56ST606701X260350X420530X6,012345110某糖果公司厂用原料A、B、C加工成三种不同牌号的糖果甲乙丙，已知各种糖果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如表所示原料甲乙丙原料成本（元/千克）每月限制用量（千克）A601522000B152500C20605011200加工费050403售价34285225问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大建立数学模型。解解设，是甲糖果中的A，B，C成分，是乙糖果的1X234X56A，B，C成分，是丙糖果的A，B，C成分。789X线性规划模型MAXZ0914190450951450057X04580959X1X2345X6ST0406060X第15页共64页02020801X23X08501501504560606040XX0770580590X20001482500259X120036,7,8,9X01X245111某厂生产三种产品I、III。每种产品经过AB两道加工程序，该厂有两种设备能完成A工序，他们以,表示；有三种设备完成B工序，分1A2别为，；产品I可以在AB任何一种设备上加工，产品可以在任何1B23规格的A设备上加工，但完成B工序时，只能在设备上加工；产品III只能1B在，上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大2化。产品设备IIIIII设备有效台时满负荷时的设备费用1A510600030027912100003211B68400025024117000783374000200原料费02503505单价12520028解产品1，设,完成A工序的产品，件；B工序时，,，完121X21B23第16页共64页成B工序的，件，产品，设,完成A工序的产品，件；B3X45126X7工序时，1完成B的产品为8X件；产品111，完成A工序的9件，2完成B工序的9X件；12345X7X86建立数学模型MAXZ12502520357X28059X5101X261300/6000797129321/10000688250/40004116X2349783/70007200/40005XST510600016797X129100002688400034119X70007400051X234X5786,7X,8,901X23456最优解为X（1200，230，0，859，571，0，500，500，324T最优值1147试题1（2005年华南理工大学）设某种动物每天至少需要700克蛋白质、30克矿物质、100毫克维生素。现有5种饲料可供选择，每种饲料每公斤营养成分的含量及单价如下表所示试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模型。第17页共64页表11饲料蛋白质（克）矿物质（克）维生素（毫克）价格（元/公斤）1310502220510731020204462203518050808解题分析这是一道较简单的数学规划模型问题，根据题意写出约束即可。解题过程12345MIN07008ZXXX3451213456751,0STXX第二章（67页）21用改进单纯形法求解以下线性规划问题。（1）MAXZ6231X23232X3441，0X23（2）MINZ21X2331X4362231X,02解（1）先化成标准型MAXZ623001X234X5ST222第18页共64页441X35,024X令（，）（,0,00B4P510BX4X5T0BC,（，0N123240N123XT6,2,3，,0NC10B0B非基变量的检验数0NB100NC6,2,30因为的检验数等于6，是最大值，所以，为换入变量，1X1X；0B2410P2由规则得1为换出变量。4X，,（,，6,01B4P52011BXX5T1BC,（，1N4231N4230，2，3，,1C1051B非基变量的检验数（3，1，3）N因为的检验数为1，是正的最大数。所以为换入变量；2X2X10B2P5由规则得6所以是换出变量。5X第19页共64页，,（,，6,22B1P2102BX1X2T2BC,，,（，2N4532N4530，0，3，,2C122B6非基变量的检验数（2，2，9）2N非基变量的检验数均为负数，愿问题已达最优解。最优解X46即X（4,6,0T目标函数最优值MAXZ12（2）解MINZ20MM01X234X56ST33124436X35X23126,0X345X6M是任意大的正数。（非基变量检验数计算省略）原问题最优解是X（06，12，0）目标函数最优值Z12/522已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将空白处数字填上。JC354000BCBXB1X23X45X652X8/32/3101/3000514/34/3052/310第20页共64页06X20/35/3042/301JCZ1/3045/3002X15/418/4110/4136/415/414/411X2/4112/4115/41JCZ解JC354000BCBXB1X23X45X652X8/30514/306X20/3JCZ52X80/4101015/414350/410016/4131X44/411002/41JCZ00045/4123写出下列线性规划问题的对偶问题。（1）MINZ2241X23第21页共64页23521X233734651X2,03（1）解对偶问题是MAXW2351Y23ST23213342Y576413,0Y22MAXZ2341X34X35123467358XX12999201234,00无约束XX解对偶问题MINW58204Y1Y3ST612179421Y33933594Y413第22页共64页无约束，0；4Y01Y3（3）MINZ1MNIJICXI1,M1NIJIXAJ1,N1MIJJB0IJX解对偶问题MAXW1MIAY1NJMBSTIYMJIJCI,J无约束I1,2,MJ1,2,N4MAXZ1NJCX,I1,1NIJIAB1M,I1NIJIX1,2,0,当J1，J1NJX无约束，当J,解MINW1MJIIBYSTJ1,2,31MIJAYJC1N第23页共64页J1N1,2,N1MIJAYJC0I1,2I1IY无约束，I1,M2M24判断下列说法是否正确，并说明为什么1如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。（2）如线性规划的对偶问题无可行解，则原问题也一定无可行解。（3）如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划问题一定有有限最优解。1错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在；（2）错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解；（3）错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能有无界解；25设线性规划问题1是MAX1ZNJCX，I1，2，M1NIJIAB0,2,JXN（）是其对偶问题的最优解。1,MY又设线性规划问题2是MAX21NJZCX，I1，2，M1NIJIABIK0,2,JXN其中是给定的常数，求证IKMAX2Z1ZMIKY第24页共64页解证明把原问题用矩阵表示MAXCX1ZSTAXBX0B（,12MT设可行解为,对偶问题的最优解（，）已知。11YY2MMAXCX2ZSTAXBKX0K（,1K2MT设可行解为，对偶问题最优解是,对偶问题是，2YMINWYBKSTYACY0因为2是最优解，所以2Y（BK）（BK）1X是目标函数的可行解，A2XBK；2YAX2（BK）2ZBYK1Y原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。26已知线性规划问题MAXZ123CXCX12A213A40X5112B0,5JX用单纯形法求解，得到最终单纯形表如表所示，要求（1）求，的值；1A2132A231B2（2）求的值；,C第25页共64页BXB1X2X3X4X5X3X3/21011/21/2221/21012JJCZ30004解（1）初始单纯形表的增广矩阵是C123120AB最终单纯形表的增广矩阵为20512C是作初等变换得来的，将2C作初等变换，使得2C的第四列和第五列的矩阵成为的单位矩阵。有9/2；1；4；5/2；1；2；1A1213A212A239；5B由检验计算得3；01C23C27已知线性规划问题MAXZ2561X234XST2834222121XX0，J1,4J对偶变量，其对偶问题的最优解是4，试应用对偶问题1Y21Y2的性质，求原问题的最优解。解对偶问题是第26页共64页MINW8121Y2ST22221Y5261Y2，0互补松弛性可知，如，是原问题和对偶问题的可行解，那么，XY0和YSX0，当且仅当，是最优解。设X,Y是原问题和对偶问题的可行解，（，4Y，）SY356有YSX0且X0S0，原问题约束条件取等号，4；45X63X4最优解X（0，0，4，4T目标函数最优值为44。28试用对偶单纯形法求解下列线性规划问题。（1）MINZ1X224771X,022MINZ3241X234X245012343722XX第27页共64页5210151X234X,0解（1）取WZ，标准形式MAXW001X234XST2412377X4，0123X单纯形法求解（略）最优解X（21/13，10/13，0，0T目标函数最优值为31/13。（2）令WZ，转化为标准形式MAXW3240001X234X567XST2450123453722XX65261512347，0XX567X单纯形法略原问题最优解X（3，0，0，0，6，7，0T目标函数最优值为9。29现有线性规划问题MAXZ55131X23320123第28页共64页12410901X23，0先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化（1）约束条件1的右端常数20变为30（2）约束条件2的右端常数90变为70（3）目标函数中的系数变为83X（4）的系数向量变为1X12（5）增加一个约束条件235501X3（6）将约束条件2变为105101002X解把原问题化成标准型的MAXZ5513001X23X45XST32012351241090XX，012345单纯形法解得最优解X（0，20，0，0，10T目标函数最优值为100。非基变量的检验数等于0，原线性问题有无穷多最优解。1X（1）约束条件的右端常数变为30有1BB因此单纯形法解得最优解X（0，0，9，3，0T目标函数最优值为117。第29页共64页（2）约束条件右端常数变为702有1BB因此单纯形法解得，最优解X（0，5，5，0，0T目标函数最优值为90。（3）的系数变成8，是非基变量，检验数小于0，所以最优解不变。3X3X（4）的系数向量变为105是非基变量，检验数等于5，所以最优解不变。1X（5）解加入约束条件3用对偶单纯形表计算得X（0，25/2，5/2，0，15，0T目标函数最优值为95。（6）改变约束条件，没有变化，345,P线性规划问题的最优解不变。210已知某工厂计划生产I,II,III三种产品，各产品在ABC设备上加工，数据如下表，设备代号IIIIII每月设备有效台时A8210300B1058400C21310420单位产品利润/千元3229（1）如何充分发挥设备能力，使生产盈利最大（2）如果为了增加产量，可借用其他工厂的设备B，每月可借用60台时，租金为18万元，问借用是否合算（3）若另有两种新产品IV,V，其中IV为10台时，单位产品利润21千元；新产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利187千元。如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否划算（4）对产品工艺重新进行设计，改进结构，改进后生产每件产品I，需要设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润45千元，问这对原计划有何影响解第30页共64页（1）设产品三种产品的产量分别为，建立数学模型1X23MAXZ32291X23XST82103001231058400X21310420123,0X3把上述问题化为标准型，用单纯形法解得最优解X（338/15，116/5，22/3，0，0，0T目标函数最优值为2029/15。（2）设备B的影子价格为4/15千元/台时，借用设备的租金为03千元每台时。所以，借用B设备不合算。（3）设备,V生产的产量为，系数向量分别为V7X8712,50TP84检验数006，所以生产不合算，7V37/300，生产V合算。8单纯形法计算得最优解X（107/4，31/2，0，0，0，0，55/4T目标函数最优值为10957/80。（4）改进后,检验数253/300，大于零。1所以，改进技术可以带来更好的效益。211分析下列参数规划中当T变化时最优解的变化情况。第31页共64页（1）MAX36T22T55TT0TZ1X23XST24301X233246044201X2，03（2）MAX72T12T10TT0TZ1X23XST201X232230，01X3（3）MAX20T25TZ1X2ST102T1X25T2102TX，012（4）MAX211218150T59TZ1X23X4ST636330T1X2346312678TX93691352T1X234，0X解第32页共64页（1）化成标准形式MAX36T22T55T000T0TZ1X23X456XST24301X23432460544201X26，,034X56令T0，用单纯形表计算，JC36T22T55T000BCXB1X23X45X6I22T2X1001/410051/4055T32303/20101/2046006X2020021120Z1350T1350T400T12T20T增大，T大于1，首先出现，大于0，所以当0T1时有最优解。45X（0，100，230，0，0，20T目标函数最优值为1350（T1）（0T1）。T1是第一临界点。T大于1时，是换出变量。6XT大于1，最优解是X（0，0，0，430，460，420T目标函数最优值为MAX0，（T大于1）TZ（2）化成标准型，然后令T0，单纯形法解得T开始增大时，当T大于8/3时，首先出现4大于0，所以0T8/3，得最优解。第33页共64页目标函数最优值MAX220，（0T8/3）TZ所以，T8/3为第一临界点。当8/35，首先大于0，8/35时，是换入变量，为换出变量，单纯性法计算，1X2X当T继续增大，所有检验数都非正，所以当T5，最优解X（15，0，0，5T目标函数最优值为10530T，T03化成标准型，令T0,用单纯形法计算得当T开始增大，T大于5时，首先出现小于0，当0T5，最优解为2BX（102T，0，102T，5T，0T目标函数最优值为6T30，（0T5）。所以T5是第一临界点。当T大于5时，是换出变量，是换入变量。用对偶单纯形法计算，4X5X当T大于5时，最优解为X（102T，15T，0，0，T5T目标函数最优值为355T。（4）解先化为标准型，令T0，用单纯形法计算，得当T开始增大，当T大于6时，首先出现小于0，当0T6，有最优解2BX（0，0，0，10T/3，0，183T，455TT目标函数最优值为1505T（0T6）。当T大于6时，首先出现小于0，是换出变量，是换入变量，使用2BX2X单纯形法计算得T继续增大，当T大于11时，首先小于零，是换出变量，3B7为换入变量，对偶单纯形法迭代得3X第34页共64页无限制当T59，有最优解X（0，T/32，T/811/8，59/4T/4，0，0，0T目标函数最优值为5T/2345/2，（11T59）。试题1（2006年西北工业大学）已知线性规划12MAX3ZX124,0STX（1）用单纯形法求解该线性规划问题的最优解和最优值；（2）写出线性规划的对偶问题；（3）求解对偶问题的最优解和最优值。解题分析本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。解题过程183205TX，有无穷多解。MAXZ对偶问题为123IN4WYY123,0STYY12WZ2（2005年东南大学）写出如下线性规划问题的对偶问题123MAXX1230,STXX并利用弱对偶性说明的最大值不大于1。Z解题过程原问题的对偶问题为123MINWY第35页共64页12313210,YSTY由于（0，1，0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的任一可行解都有XCXYB而，所以的最大值不大于1。201YBZ第三章（86页）31判断表中给出的调运方案能否作为用表上作业法求解时的最初解为什么表31销地产地1234产量1015152151025355销量5151510表32销地产地12345产量1150250400220030050032505030049021030058020100销量24041055033070解表31中，有5个数字格，作为初始解，应该有MN13416个数字格，所以表31的调运方案不能作为用表上作业法求解时的初始解。表32中，有10个数字格，而作为初始解，应该有MN19个数字格，所以表32的调运方案不能作为表上作业法的初始解。32第36页共64页表33和表34中分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔法直接给出近似最优解。表33销地产地123产量15181222411433674销量91011表34销地产地12345产量11023159252520152430315514715204201513M830销量2020301025解（1）在表33中分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。得到销地产地123行差额151842241133673列差额136从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，上表中，第三列是最大差额列，此列中最小元素为1，由此可以确定产地2的产品应先供应给销售地3，得到下表销地产地123产量1122143114销量91011同时将运价表第三列数字划去，得第37页共64页销地产地12产量15112224143364销量910对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列，重复上面的步骤，直到求出初始解，最终结果是销地产地123产量121223111434104销量91011（2）34分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素。（方法同33相同）最终得出原问题的初始解销地产地12345产量12522030320430销量202030102533用表上作业法求给出运输问题的最优解（M是任意大正数）（1）销地产地甲乙丙丁产量137645224322343853销量3322解（1）计算出各行和各列的次最小运费和最小运费的差额，填入该表的1最右列和最下列。第38页共64页从行差额或者列差额中找出最大的，选择它所在的行或者列中的2最小元素，丙列中的最小元素为3，由此可以确定产地2的产品应先供应丙的需要，而产地2的产量等于丙地的销量，故在（2，丙）处填入0，同时将运价表中的丙列和第二行的数字划去，得到销地产地甲乙丙丁产量137452234353销量332对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，3填入该标的最右列和最下行，重复步骤，直到求出初始解为止。得到下表12销地产地甲乙丙丁产量132522023033销量3322使用位势法进行检验上表中，数字格处填入单位运价并增加一行一列，在列中填入1（I1，2，3），在行中填入（J1，2，3，4），先令IUV（I，JB，BIUJVC为基，下同）来确定IU和I，得到下表销地产地甲乙丙丁IU134023223431IV3254由IJC（IUV）（I，J为非基，下同）计算所有空格的检验数，并2在每个格的右上角填入单位运价，得到下表销地产地甲乙丙丁IU第39页共64页130756140022144302023403082501IV3254由上表可以看出，所有的非基变量检验数0，此问题达到最优解。又因为0，此问题有无穷多最优解。34总运费MINZ3333232432（2）销地产地甲乙丙丁产量110671242161059935410104销量5246解（2）计算出各行和各列的次最小运费和最小运费的差额，填入该1表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的2最小元素，甲列是最大差额列，甲列的最小元素是5，所以产地3的产品先供应甲的需求，同时将运价表中产地3所在行的数字划去。对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，3填入该标的最右列和最下行，重复步骤，直到求出初始解为止。得到下表12销地产地甲乙丙丁产量112142369344销量5246使用位势法进行检验上表中，数字格处填入单位运价，并增加一行一列，在列中填入1（I1，2，3），在行中填入（J1，2，3，4），先令0，由IUJV1UIV（I，JB，B为基，下同）来确定I和IVC第40页共64页由IJC（IUV）（I，JN）计算所有空格的检验数，并在每个格的2右上角填入单位运价，得到下表销地产地甲乙丙丁IU1100671210216810650902350431081045IV106711由上表可以看出，所有的非基变量检验数0，此问题达到最优解。此问题有唯一最优解。总运费MINZ118（3）销地产地甲乙丙丁戊产量11020591052210830663120710424863759销量44624解（3）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为2。这样就达到了产销平衡。用伏格尔法求初始解计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列1和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元2素，产地1所在的行是最大差额行，最小元素0，说以一产地的产品应该优先供应己的需要，同时划掉己列的数字。对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，3填入该标的最右列和最下行，重复步骤，直到求出初始解为止。得到下表12销地产地甲乙丙丁戊己产量1325242632244329第41页共64页销量446242使用位势法进行检验上表中，数字格处填入单位运价，并增加一行一列，在列中填入1（I1，2，3，4），在行中填入（J1，2，3，4，5，6），先令0，由IUJV1UIV（I，JB，B为基，下同）来确定IU和IVC由IJ（IUV）（I，JN）计算所有空格的检验数，并在每个格的2右上角填入单位运价。由上表可以看出，所有的非基变量检验数0，此问题达到最优解。又因为0，此问题有无穷多最优解。14总运费MINZ90（4）销地产地甲乙丙丁戊产量11018291322100213M211416120306113M1404911231819805242836303460销量1001201006080解（4）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为40。这样就达到了产销平衡。用伏格尔法求初始解计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列1和最下行。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元2素，同时划掉所在列或行的元素。对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，3填入该标的最右列和最下行，重复步骤，直到求出初始解为止。12并用位势法进行检验销地产地甲乙丙丁戊己IU1101822981302260120第42页共64页2133MM1621014116001203006011030MM602210494110237181019801755242280363305346012IV101621131612由上表可以看出，所有的非基变量检验数0，此问题达到最优解。又因为0，此问题有无穷多最优解。31总运费MINZ552034已知运输问题的产销平衡表、单位运价表及最优调运方案如下表所示表1销地产地B23B4产量1A5101520101525355销量5151510表2销地产地1B2B3B4B1A1012011212792032141618（1）2A到B的单位运价在什么范围变化时，上述最优方案不变2C（2）到4的单位运价变为何值时，有无穷多最优方案。除表1中方案外，至少写出其他两个。解1在对应表的数字格处（未知）填入单位运价，并增加一行，在列12C第43页共64页中填入（I1，2，3），在行中填入（J1，2，3，4），先令0，由IUJV1UIV（I，JB）来确定IU和IC由IJ（IV）（I，JN）计算所有空格的检验数，并在每个格的2右上角填入单位运价（未知）。2C最优调运方案不变，则所有非基变量的检验数都是非负。所以302C1001002C2401802C解得3102单位运价在此区间变化时，最优调运方案不变。（2）在对应表的数字格处（未知）填入单位运价，并增加一行，在12C列中填入（I1，2，3），在行中填入（J1，2，3，4），先令0，由IUIUJV1IV（I，JB）来确定IU和IC由IJC（IV）（I，JN）计算所有空格的检验数，并在每个格的2右上角填入单位运价（未知）。2有无穷多最优方案，则至少有一个非基变量的检验数为0取170，所以单价变为17时，该问题有无穷多最优调运方案。24C另外的两种调运方案1销地产地1B23B4产量1A15015第44页共64页2A0151025355销量51515102销地产地1B23B4产量1A1515200151025355销量515151035某百货公司去外地采购ABCD四种规格的服装，数量分别为A,1500套；B，2000套；C，3000套；D，3500套；有三个城市可以供应上述服装，分别为I，2500套，II，2500套；III，5000套。已知下表，求预期盈利最大的采购方案。ABCDI10567II8276III9348解因为利润表中的最大利润是10，所以令M10，用M减去利润表上的数字，此问题变成一个运输问题，见下表销地产地ABCD产量I05432500II28342500III17625000销量1500200030003500使用伏格尔法计算初始解计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列1和最下行。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元2素，同时划掉所在列或行的元素。对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，3填入该标的最右列和最下行，重复步骤，直到求出初始解为止。12第45页共64页销地产地ABCD产量I15005005002500II25002500III150035005000销量1500200030003500使用位势法检验数字格处填入单位运价，并增加一行一列，在列中填入（I1，2，3），1IU在行中填入（J1，2，3，4），先令0，由IUV（I，JB，）来确定JV1UCIU和I由IJC（IUV）（I，JN）计算所有空格的检验数，并在每个格的2右上角填入单位运价。如果没有得到最优解，用逼回路法进行改进。盈利最大方案销地产地ABCDIUI05040320II238430441III10716121IV0541此时，总运费为28000元最大盈利为72000元。36甲乙丙三个城市每年需要煤炭分别为320万吨、250万吨、350万吨，由A、B两处煤矿供应。煤炭供应量分别为A,400万吨；B,450万吨；运价如下表，由于需大于供应，经研究平衡决定，甲城市供应量可以减少030万吨，乙城市需要完全供应，丙城市供应不少于270万吨。试求将供应量分配完又使总运费最低的调运方案。甲乙丙第46页共64页A151822B212516解此问题的供应量小于需求量，假设供应地C，产量为70万吨。用伏格尔法求解得销地产地甲甲乙丙丙供应A150250400B1403027010450C7070需求2903025027080使用位势法检验数字格处填入单位运价，并增加一行一列，在列中填入（I1，2，3），1IU在行中填入（J1，2，3，4），先令0，由IUV（I，JB，）来确定JV1UCIU和I由IJC（IUV）（I，JN）计算所有空格的检验数，并在每个格的2右上角填入单位运价。如果没有得到最优解，用闭回路法进行改进。最优解时，最小运费是14650万元。37某造船厂根据合同要从当年起连续三年末各提供三条规格型号相同的大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下表，年度正常生产时间内可完成的客货轮数加班生产时间内可完成的客货轮数正常生产时的每艘成本/万元123500242600313550已知加班生产时，每艘客货轮的成本比正常生产高出70万元，又知道造出来的可货轮如当年不交货，每艘积压一年造成积压损失40万元，在签合同时，该厂已经存储了2艘客货轮，而该厂希望在第三年木完成合同后还能存储一艘备用，问该厂如何安排每年的生产量，能够在满足上述要求的情况下，总的生产费用加积压损失最少解第47页共64页设，是三年的需求订货，是三年的正常生产能力；1A231B23，是三年的加班能力，S是事先积压产生的供货能力。第三年的需求1B23量是4艘。此问题产销不平衡，增加设想销地，运价0，销量74A使用伏格尔法求初始解并用位势法检验此问题有无穷多最优解，总运费MINZ4730万元销地产地1A23A4供应量1B50054000602600060B060355010620060S40460需求量50054056060试题2001年上海大学某产品由产地AI发往销地BJ的每吨运费如下表元/吨B1B2B3供应量（吨）A1504060150A2453065200A3201050250需求量150220180为满足各销地需求，应如何确定运输方案使总费用最小（1）建立此运输问题的数学模型。（2）将此问题化为产销平衡的运输问题，并求出一个初始基本可行解。解（1）设某产品为从AI发往销地BJ的吨数，则此运输问题的数学模型为IJX第48页共64页3,21,0180250150265324560450MAX323321212133213213321321132JIXXXXXXTSXXXZIJ（2）增加一个虚拟销地B4，其需求量为50吨，各产地到虚拟销地B4的每吨运费分别为0，则可将此问题化为如下产销平衡的运输问题元/吨B1B2B3B4供应量24530650200A32010500250需求最小元素法可得到如下的一个初始基本可行解元/吨B1B2B3B4供应量A110050150A212080200A330220250需求四章（98页）41若用以下表达式作为目标规划的目标函数，试述其逻辑是否正确（1）MAX1D（2）MAXZ（3）MINZ1（4）M