第三章运输问题习题.doc

第三章 运输问题一、疑问：运输问题中，若出现退化情形，应该在什么地方补0？答：为了使产销平衡表上有(m + n - 1)个数字格，这时需要添加“0”，它的位置可以对应同时划去的那行或那列的任一空格处。（这时填数字格不构成闭回路）二、判断下列说法是否正确 ：(a) 运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列情况之一：有唯一最优解、有无穷多最优解、无界解和无可行解；(b) 在运输问题中，只要给出一组含（m + n 1）个非负的xij，且满足 ，就可以作为一个初始基可行解；(c) 表上作业法实质上就是求解运输问题的单纯形法；(d) 按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路；(e) 如果运输问题的单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化；(f) 如果运输问题的单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化；三、选择：1在产销平衡运输问题中，设产地为m个，销地为n个，那么解中非零变量的个数（ A ）。A不能大于(m+n-1)；B不能小于(m+n-1)；C等于(m+n-1)；D不确定。2在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题（ B ）。A无最优解；B有无穷多个最优解；C有唯一最优解；D出现退化解。四、判断表(a),(b),(c)中给出的调运方案能否作为作业法求解时的初始解，为什么？表 (a)销地产地B1B2B3B4B5B6产量A1A2A3A42010302010105052030507520销量204030105025表 (b)销地产地B1B2B3B4B5B6产量A1A2A3A4203010301030202530507520销量204030105025表(c)销地产地B1B2B3B4B5产量A1A2A3A45152018125202025304020销量2038172020解：(a) 可以作为初始方案。(b) 中非零元素小于9（产地+销地-1），不能作为初始方案。(c) 中存在以非零元素为顶点的闭回路，不能作为初始方案。五、已知某运输问题的产销平衡表，单位运价表及给出的一个调运方案分别见下表。判断所给出的调运方案是否为最优？如是，说明理由，如否，也说明理由。产销平衡表及某一调运方案 销地产地B1 B2B3B4B5B6产量A1A2A3A4525401020 2416105151150406031销量252520202071销地产地B1 B2B3B4B5B6A1A2A3A4233412 5 2324234 212342 5 412单位运价表解：题目中给出的调运方案有11个非零元素，不是基可行解，应先调整得到基可行解，然后求检验数，判别是否最优。六、已知某运输公司问题的产销平衡表与单位运价表如下所示销地产地A BCDE产量IIIIII1020301540 352015 4020 30 254030量25115603070 （a）求最优调拨方案；解：（a）最优调拨方案如下表：销地产地A BCDE产量IIIIII15103580 60 30 7050100150销量25115603070 （b）如产地III的产量变为130，又B地区需要的115单位必须满足，试重新确定最优调拨方案。(b)根据题设条件重新列出这个问题的产销平衡表与单位运价表销地产地A BCDE产量IIIIII（假想）10203001540 35 M2015 40 020 305504030 2505010013020销量25115603070 重新求出最优调拨方案如下表：销地产地A BCDE产量IIIIII（假想）255065 60 15 15 6555010013020销量25115603070七、表1和表2分别是一个具有无穷多最优解的运输问题的产销平衡表、单位运价表。表1给出了一个最优解，要求再找出两个不同的最优解。表1销地产地B1 B2B3B4产量A1A2A3A44214 244 7 51824612销量6 143530表2销地产地B1 B2B3B4A1A2A3A491081081097 131211 11 1414 13 12解：因（A4，B2）格检验数为0，从该空格寻找闭回路调整可以得到最优解，将两个不同最优解对应数字相加除以2，变得到第三个最优解。八、如表所示的问题中，若产地i有一个单位物资未运出，则将发生储存费用。假定1，2，3产地单位物资储存费用分别为5，4，3。又假定产地2的物资至少运出38个单位，产地3的物资至少运出27个单位，试求解此运输问题的最优解。销地产地A BC产量123 1 12 243253 20 40 30销量30202070 90解：增加假想销地D，销量为20，将产地分为1，2，2,3,3,其中2于3的物资必须全部运出，不准分给D，由此可以得到小表，再用表上作业最优方案。销地产地A BCD产量122/33/11122 244332553354M3M 202 383 27销量3020202090九、甲、乙、丙三各城市，每年分别需要煤炭320，250，350（万t），由A，B两个煤矿负责供应。已知煤矿煤产量A为400万t，B为450万t，从两煤矿至各城市煤炭运价如表323所示。由于需求大于产量，经协商平衡，甲城市必要时可少供030万t，乙城市需求量需全部满足，丙城市需求量不少于270万t。试求将甲、乙两煤矿全部分配出去，满足上述条件又使总运费为最低的调运方案。甲乙丙AB152118252216 十、某化学公司有甲，乙，丙，丁四个化工厂生产某种产品，产量分别为200，300，400，100（t），供应I,II,III,IV,V,VI六个地区的需要，需要量分别为200，150，400，100，150，150（t）。由于工艺，技术等条件的差别，各厂每kg的产品成本分别为1.2,1.4,1.1,1.5(元)，又由于行情的不同，各地区的销售价分别为每kg2.0,1.8,2.2,1.6,2.0(元)。已知从各厂运往各销售地区每kg产品价格如下表所示。销地产地I IIIIIIVVVI甲乙丙丁0.50.30.70.60.40.80.7 0.40.30.90.30.20.40.5 0.70.60.30.60.40.5 0.1 0.20.40.8如果第III个地区至少供应100t，第IV个地区的需要必须全部满足，试确定使该公司获利最大的产品调运方案。解：先列出这个问题的产销平衡表和单位运价表，再用表上作业法可以求得最优解：销地产地IIIIIIIIIIVVVI产量甲乙丙丁戊-0.3-0.3-0.20. 10-0.8-0.2-0.6-0.500.30.50.40. 10-0.30. 50.40.1M-0.6-0.3-0.4-0.1M-0.10. 4-0.10. 40-0.7-0.4-0.50. 30200300400100150销量200150300100100150150销地产地I IIIIIIIIIVVVI产量甲乙丙丁戊2005010030001000100150 1500200300400100150销量200150300100100150150十一、某糖厂每月最多生产糖270吨，先运至A1,A2,A3三个仓库，然后再分别供应B1,B2,B3,B4,B5五个地区需要。已知各仓库容量分别为50,100,150（吨），各地区的需要量分别为25,105,60,30,70（吨）。已知从糖厂经由各仓库然后供应各地区的运费和储存费如表所示。B1B2B3B4B5A11015202040A22040153030A33035405525解：仓库容量300吨，各地区需要量总计290