资源描述
运筹学习题答案第一章（39页）1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）max 5+1050+14，0（2）min z=+1.5+33+2，0（3）max z=2+2-1-0.5+2，0（4）max z=+-03-3，0解：（1）（图略）有唯一可行解，max z=14（2）（图略）有唯一可行解，min z=9/4（3）（图略）无界解（4）（图略）无可行解1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。（1）min z=-3+4-2+54-+2-=-2+3-14-2+3-+22，0，无约束（2）max 0 (i=1n; k=1,m)（1）解：设z=-,=-, ,0标准型：Max =3-4+2-5(-)+0+0-M-Ms. t . -4+-2+-+=2+3-+=14-2+3-+2-2-+=2,0 初始单纯形表:3-42-5500-M-Mb-M2-41-21-100012014113-11100014-M2-23-12-20-1102/3-4M3-6M4M-42-3M3M-55-3M0-M00(2)解：加入人工变量，得：Max s=(1/)-M-M-.-Ms.t. (i=1,2,3,n)0, 0, (i=1,2,3n; k=1,2.,m)M是任意正整数初始单纯形表：-M-M-Mb-M110011000-M10100000-M1001000111-snM0001.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。（1）max z=2+3+4+7 2+3-4=8 -2+6-7=-3,0(2)max z=5-2+3-6+2+3+4=72+2=30（1）解：系数矩阵A是：令A=(，)与线形无关，以（，）为基，为基变量。有 2+3=8+4 -2=-3-6+7令非基变量，=0解得：=1；=2基解=（1，2，0，0为可行解=8同理，以（，）为基，基解=（45/13，0，-14/13，0是非可行解；以（，）为基，基解=（34/5，0，0，7/5是可行解，=117/5；以（，）为基，基解=（0，45/16，7/16，0是可行解，=163/16；以（，）为基，基解=（0，68/29，0，-7/29是非可行解；以（，）为基，基解=（0，0，-68/31，-45/31是非可行解；最大值为=117/5；最优解=（34/5，0，0，7/5。（2）解：系数矩阵A是：令A=(，)，线性无关，以（，）为基，有：+2=7-3-42+=3-2令 ，=0得=-1/3，=11/3 基解=（-1/3，11/3，0，0为非可行解；同理，以（，）为基，基解=（2/5，0，11/5，0是可行解=43/5；以（，）为基，基解=（-1/3，0，0，11/6是非可行解；以（，）为基，基解=（0，2，1，0是可行解，=-1；以（，）为基，基解=（0，0，1，1是=-3；最大值为=43/5；最优解为=（2/5，0，11/5，0。1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。（1）max z=2+ 3+515 6+224，0（2）max z=2+542123+218，0解：（图略）（1）max z=33/4 最优解是(15/4,3/4)单纯形法：标准型是max z=2+0+0s.t. 3+5+=15 6+2+=24 ,0单纯形表计算：2100b0153510502462014-z0210003041-1/23/42411/301/612-z-801/30-1/313/4011/4-1/8215/410-1/125/24-z-33/400-1/12-7/24解为：（15/4，3/4，0，0 Max z=33/4迭代第一步表示原点；第二步代表C点（4，0，3，0；第三步代表B点（15/4，3/4，0，0 。（2）解：（图略） Max z=34 此时坐标点为（2，6）单纯形法，标准型是：Max z=2+5+0+0+0s.t. +=4 2+=12 3+2+=18,0(表略)最优解 X=（2，6，2，0，0 Max z=34迭代第一步得=（0，0，4，12，18表示原点，迭代第二步得=（0，6，4，0，6，第三步迭代得到最优解的点。1.5以1.4题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。解：目标函数：max z=+(1)当0时 =-（/）+z/ 其中，k=-/=-3/5，=-3l k 时， ，同号。当0时，目标函数在C点有最大值当0时，目标函数在原点最大值。l k时，同号。当0， 目标函数在B点有最大值；当0，目标函数在原点最大值。l k 0时， 同号。当0时，目标函数在A点有最大值当0时，目标函数在原点最大值。l k 0时， ，异号。当0， 0时，目标函数在A点有最大值；当0， 0时，目标函数在C点最大值。l k= 时， 同号当0时，目标函数在AB线断上任一点有最大值当0，目标函数在原点最大值。l k= 时， 同号。当0时，目标函数在BC线断上任一点有最大值当0时，目标函数在原点最大值。l k=0时，=0当0时，目标函数在A点有最大值当0，目标函数在OC线断上任一点有最大值（2）当=0时，max z= l 0时，目标函数在C点有最大值l 0时，目标函数在OA线断上任一点有最大值l =0时，在可行域任何一点取最大值。1.6分别用单纯形法中的大M法和两阶段法求解下列线性问题，并指出属于哪类解。（1）max z=2+3-5+152-5+24，0（2）min z=2+3+4+283+26，0（3）max z=10+15+125+3+9-5+6+15152+5，0（4）max z=2-+2+6-2+22-0，0解：（1）解法一：大M法化为标准型：Max z=2+3-5-M+0-Ms.t. +=7 2-5+-+=10,0 M是任意大整数。单纯形表：23-5-M0-Mb-M71111007-M102-510-115-z17M3M+23-4M2M-50-M0-M207/21/211/2-1/24/7251-5/21/20-1/21/2-z2M-100(7/2)M+80.5M-600.5M+1-1.5M-134/7011/72/71/7-1/7245/7106/75/7-1/71/7-z-102/700-50/7-M-16/7-1/7-M+1/7最优解是： X=（45/7，4/7，0，0，0 目标函数最优值 max z=102/7有唯一最优解。解法二：第一阶段数学模型为 min w= + S.t. + + =72 -5 + - + =10,，,0（单纯形表略）最优解X=（45/7，4/7，0，0，0 目标函数最优值 min w=0第二阶段单纯形表为：23-50b34/7011/71/7245/7106/7-1/7-z-102/700-50/7-1/7最优解是X=（45/7，4/7，0，0，0 Max z=102/7（2）解法一：大M法=-z 有max =-min （-）=-min z化成标准形：Max =-2-3-+0+0-M-MS.T. +4+2-+=4 3+2-+=6 ,，,，0（单纯性表计算略）线性规划最优解X=（4/5，9/5，0，0，0 ，0 目标函数最优值 min z=7非基变量的检验数=0，所以有无穷多最优解。两阶段法：第一阶段最优解X=（4/5，9/5，0，0，0，0 是基本可行解,min w=0第二阶段最优解（4/5，9/5，0，0，0，0 min z=7非基变量的检验数=0，所以有无穷多最优解。（3）解：大M法加入人工变量，化成标准型：Max z=10 +15 +12 +0 +0 +0 -M s.t. 5 +3 + + =9 -5 +6 +15 + =15 2 + + - + =5 ,，,，0单纯形表计算略当所有非基变量为负数，人工变量=0.5，所以原问题无可行解。两阶段法（略）（4）解法一：大M法单纯形法，（表略）非基变量的检验数大于零，此线性规划问题有无界解。两阶段法略1.7求下述线性规划问题目标函数z的上界和下界；Max z=+其中：，解：l 求Z的上界Max z=3+6s.t. -+212 2+414，0加入松弛变量，化成标准型，用单纯形法解的，最优解X=（0，7/2，5，0 目标函数上界为z=21存在非基变量检验数等于零，所以有无穷多最优解。l 求z的下界线性规划模型：Max Z= +4s.t. 3+58 4+610 ，0加入松弛变量，化成标准型，解得：最优解为X=（0，8/5，0，1/5 目标函数下界是z=32/51.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，d，为待定常数，试说明这些常数分别取何值时，以下结论成立。（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为，换出变量为。基b d4100 2-1-301-10 3-500-4100-30解：（1）有唯一最优解时，d0，0，0（2）存在无穷多最优解时，d0，0，=0或d0，=0，0.（3）有无界解时，d0，0，0且（4）此时，有d0，0并且，3/d/41.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下：班次时间所需人数16点到10点60210点到14点70314点到18点60418点到22点50522点到2点2062点到6点30设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。解 ：设（k=1，2，3，4，5，6）为个司机和乘务人员第k班次开始上班。建立模型：Min z=+s.t. +60 +70 +60 +50 +20 +30, 01.10某糖果公司厂用原料A、B、C加工成三种不同牌号的糖果甲乙丙，已知各种糖果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如表所示：原料甲乙丙原料成本（元/千克）每月限制用量（千克）A60%15%22000B1.52500C20%60%50%11200加工费0.50.40.3售价3.42.852.25问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模型。解:解：设，是甲糖果中的A，B，C成分，是乙糖果的A，B，C成分，是丙糖果的A，B，C成分。线性规划模型：Max z=0.9+1.4+1.9+0.45+0.95+1.45-0.05+0.45+0.95s.t. -0.4+0.6+0.60 -0.2-0.2+0.80 -0.85+0.15+0.150 -0.6-0.6+0.40 -0.7-0.5+0.50 +2000 +2500 +1200, 01.11某厂生产三种产品I、III。每种产品经过AB两道加工程序，该厂有两种设备能完成A工序，他们以,表示；有三种设备完成B工序，分别为，；产品I可以在AB任何一种设备上加工，产品可以在任何规格的A设备上加工，但完成B工序时，只能在设备上加工；产品III只能在，上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化。设备产品设备有效台时满负荷时的设备费用IIIIII5106000300791210000321684000250411700078374000200原料费0.250.350.5单价1.252.002.8解：产品1，设,完成A工序的产品，件；B工序时，,，完成B工序的，件，产品，设,完成A工序的产品，件；B工序时，完成B的产品为件；产品111，完成A工序的件，完成B工序的件；+ = + + + = 建立数学模型：Max z=(1.25-0.25)*( + )+(2-0.35)*( + )+(2.8-0.5) -(5 +10 )300/6000-(7 +9 +12 )321/10000-(6 +8 )250/4000-(4 +11 )783/7000-7 *200/4000s.t 5 +10 60007 +9 +12 100006 +8 40004 +11 70007 4000+ = + + + = , 0最优解为X=（1200，230，0，859，571，0，500，500，324 最优值1147.试题：1. （2005年华南理工大学）设某种动物每天至少需要700克蛋白质、30克矿物质、100毫克维生素。现有5种饲料可供选择，每种饲料每公斤营养成分的含量及单价如下表所示：试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模型。表 11饲料蛋白质（克）矿物质（克）维生素（毫克）价格（元/公斤）1310.50.2220.510.7310.20.20.446220.35180.50.80.8解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可。解题过程：第二章（67页）2.1用改进单纯形法求解以下线性规划问题。（1）Max z=6-2+32-+32+44，0（2）min z=2+3+=34+36+23,0解：（1）先化成标准型：Max z=6-2+3+0+0s.t. 2-+2+=2 +4+=4 , 0令=（，）= =（,=(0,0)=(,)= , =（，=(6,-2,3)，=,=非基变量的检验数=-=(6,-2,3)因为的检验数等于6，是最大值，所以，为换入变量，=；=由规则得：=1为换出变量。=(，)=,=（,，=(6,0).=(,), =（，=(0，-2，3)，=,=非基变量的检验数 =（-3，1，-3）因为的检验数为1，是正的最大数。所以为换入变量；=由规则得：=6所以是换出变量。=(，)=,=（,，=(6,-2).=(,，), =（，=(0，0，3)，=,=非基变量的检验数 =（-2，-2，-9）非基变量的检验数均为负数，愿问题已达最优解。最优解X= 即：X=（4,6,0目标函数最优值 max z=12 （2） 解 ：Min z=2+0+M+M+0S.T. 3+=34+3-+=6+2+=3, 0M是任意大的正数。（非基变量检验数计算省略）原问题最优解是X=（0.6，1.2，0）目标函数最优值： z=12/52.2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将空白处数字填上。354000b58/32/3101/300014/3-4/305-2/310020/35/304-2/301-1/304-5/300.15/418/41-10/41-6/415/414/41-2/41-12/4115/41-解：354000b58/3014/3020/3-.580/4101015/41450/41001-6/41344/41100-2/41-000-45/412.3写出下列线性规划问题的对偶问题。（1）min z= 2 +2 +4 2 +3 +5 23 + +7 3+4 +6 5 , 0（1）解：对偶问题是：Max w=2-3-5s.t. 2-3-2 3-42 5-7-64,0(2)max z= +2+3 +4 -+-3=56+7+3-5812-9-9+920,0; 0;无约束解：对偶问题：Min w=5+8+20S.t. -+6+121 +7-92 -+3-93 -3-5+9=4无约束，0；0（3）min z= i=1,m j=1,n0解：对偶问题: max w=+s.t. + , 无约束 i=1,2,.m; j=1,2,.n(4)Max z=, i=1,., , i=0,当j=1，.，无约束，当j=解：Min w=s.t. j=1,2,3 j=+1, +2,.n0 i=1,2. 无约束， i=+1, +2.m2.4判断下列说法是否正确，并说明为什么.(1)如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。（2）如线性规划的对偶问题无可行解，则原问题也一定无可行解。（3）如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划问题一定有有限最优解。(1)错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在；（2）错误，对偶问题没有可行解，原问题可能有可行解也可能有无界解；（3）错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能有无界解；2.5设线性规划问题1是：Max = ，i=1，2，m（）是其对偶问题的最优解。又设线性规划问题2是Max + ，i=1，2，m其中是给定的常数，求证： +解：证明：把原问题用矩阵表示：Max =CXs.t. AXb X0b=（,.设 可行解为,对偶问题的最优解=（， ）已知。Max =CXs.t. AXb+k X0k=（,.设可行解为，对偶问题最优解是,对偶问题是，Min w=Y(b+k)S.t. YA C Y 0因为是最优解，所以（b+k）（b+k）是目标函数的可行解，Ab+k ；A（b+k）b+Yk原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。2.6已知线性规划问题 Max z=用单纯形法求解，得到最终单纯形表如表所示，要求：（1） 求，的值；（2） 求的值；3/21011/2-1/221/210-12-3000-4解：（1）初始单纯形表的增广矩阵是：=最终单纯形表的增广矩阵为=是作初等变换得来的，将作初等变换，使得的第四列和第五列的矩阵成为的单位矩阵。有：=9/2； =1； =4； =5/2； =1； =2；=9； =5由检验计算得：=-3； =02.7已知线性规划问题Max z=2+5+6 s.t. 2+82+2+2120，j=1,4对偶变量，其对偶问题的最优解是=4，试应用对偶问题的性质，求原问题的最优解。解：对偶问题是：Min w=8+12 s.t. 2+22 21 +5 +26 ，0互补松弛性可知，如，是原问题和对偶问题的可行解，那么，=0和=0，当且仅当，是最优解。设 X,Y是原问题和对偶问题的可行解，=（，）有：Y=0; 且 X=0=0，原问题约束条件取等号，=4；=4最优解X=（0，0，4，4 目标函数最优值为44。2.8试用对偶单纯形法求解下列线性规划问题。（1）min z=+ 2+4 +77 ,0(2) min z=3+2+42+4+5+ 03- +7-2 25+2+10 15 , , 0解：（1）取w=-z，标准形式：Max w=-+0+0s.t. -2-+=-4-7+=-7 ，0单纯形法求解（略）：最优解：X=（21/13，10/13，0，0 目标函数最优值为31/13。（2）令：w=-z，转化为标准形式：Max w=-3-2-4+0+0+0s.t.-2-4-5-+=0-3+-7+2+=-2-5-2-6+=-15，0单纯形法略原问题最优解：X=（3，0，0，0，6，7，0 目标函数最优值为9。2.9现有线性规划问题max z=- 5+5+13- +3 2012 +4+10 90 ， 0先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？（1） 约束条件1的右端常数20变为30（2） 约束条件2的右端常数90变为70（3） 目标函数中的系数变为8（4） 的系数向量变为（5） 增加一个约束条件2+3+550（6） 将约束条件2变为10+5+10100解： 把原问题化成标准型的：Max z=-5 +5 +13 +0 +0 s.t- + +3 + =2012 +4 +10 + =90，0单纯形法解得：最优解：X=（0，20，0，0，10 目标函数最优值为100。非基变量的检验数等于0，原线性问题有无穷多最优解。（1）约束条件的右端常数变为30有 因此 单纯形法解得：最优解：X=（0，0，9，3，0 目标函数最优值为117。（2）约束条件右端常数变为70 有 因此 单纯形法解得，最优解：X=（0，5，5，0，0 目标函数最优值为90。（3）的系数变成8，是非基变量，检验数小于0，所以最优解不变。（4）的系数向量变为是非基变量，检验数等于-5，所以最优解不变。（5）解：加入约束条件用对偶单纯形表计算得：X=（0，25/2，5/2，0，15，0 目标函数最优值为95。（6）改变约束条件，没有变化，线性规划问题的最优解不变。2.10已知某工厂计划生产I,II,III三种产品，各产品在ABC设备上加工，数据如下表，设备代号IIIIII每月设备有效台时A8210300B1058400C21310420单位产品利润/千元322.9（1）如何充分发挥设备能力，使生产盈利最大？（2）如果为了增加产量，可借用其他工厂的设备B，每月可借用60台时，租金为1.8万元，问借用是否合算？（3）若另有两种新产品IV,V，其中IV为10台时，单位产品利润2.1千元；新产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利1.87千元。如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否划算？（4）对产品工艺重新进行设计，改进结构，改进后生产每件产品I，需要设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润4.5千元，问这对原计划有何影响？解：（1）设：产品三种产品的产量分别为，建立数学模型：Max z=3+2+2.9s.t. 8+2+1030010+5+84002+13+10420,0把上述问题化为标准型，用单纯形法解得：最优解：X=（338/15，116/5，22/3，0，0，0 目标函数最优值为2029/15。（2）设备B的影子价格为4/15千元/台时，借用设备的租金为0.3千元每台时。所以，借用B设备不合算。（3）设备,V生产的产量为，系数向量分别为：检验数=-0.06，所以生产不合算，=37/300，生产V合算。单纯形法计算得：最优解：X=（107/4，31/2，0，0，0，0，55/4 目标函数最优值为10957/80。（4）改进后,检验数=253/300，大于零。所以，改进技术可以带来更好的效益。2.11分析下列参数规划中当t变化时最优解的变化情况。（1）Max =(3-6t) +(2-2t) +(5-5t) (t0)s.t. +2+ 4303+2 460+4 420，0（2）Max =(7+2t)+(12+t) +(10-t) (t0)s.t. + 202+2+ 30，0（3）Max =2+ (0 t 25)s.t. 10+2t + 25-t 10+2t，0（4）Max =21+12+18+15 (0 t 59)s.t. 6+3+6+3 30+t6-3+12+6 78-t9+3-6+9 135-2t，0解：（1）化成标准形式：Max =(3-6t) +(2-2t) +(5-5t) +0+0+0 (t0)s.t. +2+=4303+2+=460+4+=420，, 0令t=0，用单纯形表计算，3-6t2-2t5-5t000B2-2t100-1/4100.5-1/40-5-5t2303/20101/20460020200-21120-z1350t-1350t-400t-12t-20t增大，t大于1，首先出现，大于0，所以当0t1时有最优解。X=（0，100，230，0，0，20 目标函数最优值为1350（t-1） （0t1）。t=1是第一临界点。t大于1时，是换出变量。t大于1，最优解是：X=（0，0， 0，430，460，420目标函数最优值为Max =0， （t大于1）（2）化成标准型，然后令t=0，单纯形法解得：t开始增大时，当t大于8/3时，首先出现大于0，所以0t8/3，得最优解。目标函数最优值Max =220，（0t8/3）所以，t=8/3为第一临界点。当8/3t5，首先大于0，8/3t5的时候，最优解为：X=（0，15，0，5 目标函数最优值为180+15t ，（8/35时，是换入变量，为换出变量，单纯性法计算，当t继续增大，所有检验数都非正，所以当t5，最优解：X=（15，0，0，5目标函数最优值为105+30t， t0(3)化成标准型，令t=0,用单纯形法计算得：当t开始增大，t大于5时，首先出现小于0，当0t5，最优解为：X=（10+2t，0，10+2t，5-t，0 目标函数最优值为6t+30 ，（0t5）。所以t=5是第一临界点。当t大于5时，是换出变量，是换入变量。用对偶单纯形法计算，当t大于5时，最优解为：X=（10+2t，15+t，0，0，t-5 目标函数最优值为35+5t。（4）解：先化为标准型，令t=0，用单纯形法计算，得：当t开始增大，当t大于6时，首先出现小于0，当0t6，有最优解：X=（0，0，0，10+t/3，0，18-3t，45-5t 目标函数最优值为150+5t （0t6）。当t大于6时，首先出现小于0，是换出变量，是换入变量，使用单纯形法计算得：t继续增大，当t大于11时，首先小于零，是换出变量，为换入变量，对偶单纯形法迭代得：当 t59，有最优解：X=（0，t/3-2，t/8-11/8，59/4-t/4，0，0，0 目标函数最优值为5t/2+345/2 ，（11t59）。试题：1. （2006年西北工业大学）已知线性规划：（1） 用单纯形法求解该线性规划问题的最优解和最优值；（2） 写出线性规划的对偶问题；（3） 求解对偶问题的最优解和最优值。解题分析：本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。解题过程：，有无穷多解。对偶问题为： 2. （2005年东南大学）写出如下线性规划问题的对偶问题：无限制并利用弱对偶性说明的最大值不大于1。解题过程：原问题的对偶问题为：由于（0，1，0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的任一可行解都有 而，所以的最大值不大于1。第三章（86页）3.1判断表中给出的调运方案能否作为用表上作业法求解时的最初解？为什么？表31销地产地1234产量1015152151025355销量5151510表32销地产地12345产量1150250400220030050032505030049021030058020100销量24041055033070解：表31中，有5个数字格，作为初始解，应该有m+n-1=3+4-1=6个数字格，所以表3-1的调运方案不能作为用表上作业法求解时的初始解。表3-2中，有10个数字格，而作为初始解，应该有m+n-1=9个数字格，所以表3-2的调运方案不能作为表上作业法的初始解。3.2表3-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔法直接给出近似最优解。表3-3 销地产地123产量15181222411433674销量91011表3-4 销地产地12345产量11023159252520152430315514715204201513M830销量2020301025解：（1）在表3-3中分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。得到： 销地 产地123行差额151842241133673列差额136从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，上表中，第三列是最大差额列，此列中最小元素为1，由此可以确定产地2的产品应先供应给销售地3，得到下表： 销地 产地123产量1111221434销量91011同时将运价表第三列数字划去，得 销地 产地12产量15112224143364销量910对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列，重复上面的步骤，直到求出初始解，最终结果是： 销地 产地123产量121012231114344销量91011（2）3-4分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素。（方法同3-3相同）最终得出原问题的初始解： 销地产地12345产量12522030320430销量20203010253.3用表上作业法求给出运输问题的最优解（M是任意大正数）（1）销地产地甲乙丙丁产量137645224322343853销量3322解：（1）计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。 从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，丙列中的最小元素为3，由此可以确定产地2的产品应先供应丙的需要，而产地2的产量等于丙地的销量，故在（2，丙）处填入0，同时将运价表中的丙列和第二行的数字划去，得到：销地产地甲乙丙丁产量137452234353销量332对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤，直到求出初始解为止。得到下表：销地产地甲乙丙丁产量132522023033销量3322使用位势法进行检验：上表中，数字格处填入单位运价并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令+=（i，jB，B为基，下同）来确定和，得到下表：销地产地甲乙丙丁1340232-234313254由=-（+）（i，j为非基，下同）计算所有空格的检验数，并在每个格的右上角填入单位运价，得到下表销地产地甲乙丙丁13075614002 21443020-234030825013254由上表可以看出，所有的非基变量检验数0，此问题达到最优解。又因为=0，此问题有无穷多最优解。总运费min z=3*3+3*3+2*3+2*4=32（2）销地产地甲乙丙丁产量110671242161059935410104销量5246解：（2）计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。 从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，甲列是最大差额列，甲列的最小元素是5，所以产地3的产品先供应甲的需求，同时将运价表中产地3所在行的数字划去。 对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤，直到求出初始解为止。得到下表：销地产地甲乙丙丁产量112142369344销量5246使用位势法进行检验：上表中，数字格处填入单位运价，并增加一行一列，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB，B为基，下同）来确定和.由=-（+）（i，jN）计算所有空格的检验数，并在每个格的右上角填入单位运价，得到下表销地产地甲乙丙丁11006712102 1681065090-235043108104-5106711由上表可以看出，所有的非基变量检验数0，此问题达到最优解。此问题有唯一最优解。总运费min z=118（3） 销地产地甲乙丙丁戊产量11020591052210830663120710424863759销量44624解：（3）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为2。这样就达到了产销平衡。用伏格尔法求初始解：计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，产地1所在的行是最大差额行，最小元素0，说以一产地的产品应该优先供应己的需要，同时划掉己列的数字。 对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤，直到求出初始解为止。得到下表： 销地产地甲乙丙丁戊己产量1325242632244329销量446242使用位势法进行检验：上表中，数字格处填入单位运价，并增加一行一列，在列中填入（i=1，2，3，4），在行中填入（j=1，2，3，4，5，6），先令=0，由 +=（i，jB，B为基，下同）来确定和.由=-（+）（i，jN）计算所有空格的检验数，并在每个格的右上角填入单位运价。由上表可以看出，所有的非基变量检验数0，此问题达到最优解。又因为=0，此问题有无穷多最优解。总运费min z=90（4） 销地产地甲乙丙丁戊产量1 1018291322100213M211416120306113M1404911231819805242836303460销量1001201006080解：（4）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售地己，令单位运价为0。销量为40。这样就达到了产销平衡。用伏格尔法求初始解：计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下行。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，同时划掉所在列或行的元素。 对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤，直到求出初始解为止。并用位势法进行检验： 销地产地甲乙丙丁戊己1 1018229813022601202133MM-1621014116001203006011030MM-6022-104941102371810198017-552422803633053460121016211316-12由上表可以看出，所有的非基变量检验数0，此问题达到最优解。又因为=0，此问题有无穷多最优解。总运费min z=55203.4已知运输问题的产销平衡表、单位运价表及最优调运方案如下表所示表1 销地产地产量51015010152555销量5151510表2 销地产地10120111279202141618（1）到的单位运价在什么范围变化时，上述最优方案不变？（2）到的单位运价变为何值时，有无穷多最优方案。除表1中方案外，至少写出其他两个。解：(1)在对应表的数字格处（未知）填入单位运价，并增加一行，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB）来确定和.由=-（+）（i，jN）计算所有空格的检验数，并在每个格的右上角填入单位运价（未知）。最优调运方案不变，则所有非基变量的检验数都是非负。所以：-30+10010-024-018-0解得:310单位运价在此区间变化时，最优调运方案不变。（2）在对应表的数字格处（未知）填入单位运价，并增加一行，在列中填入（i=1，2，3），在行中填入（j=1，2，3，4），先令=0，由 +=（i，jB）来确定和.由=-（+）（i，jN）计算所有空格的
展开阅读全文