初中教育运输问题.pptx

第三章运输问题第三章运输问题教学大纲教学大纲一、基本要求：一、基本要求：一、基本要求：一、基本要求：1 1、掌握运输问题、掌握运输问题、掌握运输问题、掌握运输问题数学模型的基本特点数学模型的基本特点数学模型的基本特点数学模型的基本特点；2 2、熟练掌握、熟练掌握、熟练掌握、熟练掌握最小元素法最小元素法最小元素法最小元素法求初始可行解；求初始可行解；求初始可行解；求初始可行解；3 3、了解西北角法、了解西北角法、了解西北角法、了解西北角法、VogelVogel法；法；法；法；4 4、熟练掌握最优性检验方法中的一种：、熟练掌握最优性检验方法中的一种：、熟练掌握最优性检验方法中的一种：、熟练掌握最优性检验方法中的一种：闭回路法，位势法，闭回路法，位势法，闭回路法，位势法，闭回路法，位势法，初等变换法初等变换法初等变换法初等变换法；5 5、熟练掌握用、熟练掌握用、熟练掌握用、熟练掌握用闭回路法闭回路法闭回路法闭回路法调整方案；调整方案；调整方案；调整方案；6 6、掌握、掌握、掌握、掌握退化解、产销不平衡、断路退化解、产销不平衡、断路退化解、产销不平衡、断路退化解、产销不平衡、断路及最大化问题的处理思想。及最大化问题的处理思想。及最大化问题的处理思想。及最大化问题的处理思想。二、重点：表上作业法二、重点：表上作业法二、重点：表上作业法二、重点：表上作业法三、难点：表上作业法三、难点：表上作业法三、难点：表上作业法三、难点：表上作业法第一讲运输问题第一讲运输问题数学模型及其特点数学模型及其特点 例例例例3-13-1某建材公司下设三个水泥厂某建材公司下设三个水泥厂某建材公司下设三个水泥厂某建材公司下设三个水泥厂A A1 1、A A2 2、A A3 3，各厂每月产量各厂每月产量各厂每月产量各厂每月产量分别为分别为分别为分别为A A1 17 7千吨，千吨，千吨，千吨，A A2 24 4千吨，千吨，千吨，千吨，A A3 39 9千吨；现要将三千吨；现要将三千吨；现要将三千吨；现要将三个厂生产的水泥分别运往四个建筑工地个厂生产的水泥分别运往四个建筑工地个厂生产的水泥分别运往四个建筑工地个厂生产的水泥分别运往四个建筑工地B B1 1、B B2 2、B B3 3、B B4 4，各工各工各工各工地月需求量为地月需求量为地月需求量为地月需求量为B B1 13 3千吨，千吨，千吨，千吨，B B2 26 6千吨，千吨，千吨，千吨，B B3 35 5千吨，千吨，千吨，千吨，B B4 46 6千吨。已知各厂到各工地的单位运价如表，问应如何千吨。已知各厂到各工地的单位运价如表，问应如何千吨。已知各厂到各工地的单位运价如表，问应如何千吨。已知各厂到各工地的单位运价如表，问应如何调运才能在满足各工地需求条件下，使总运费最少？调运才能在满足各工地需求条件下，使总运费最少？调运才能在满足各工地需求条件下，使总运费最少？调运才能在满足各工地需求条件下，使总运费最少？销地销地销地销地产地产地产地产地B B1 1B B2 2B B3 3B B4 4A A1 13 311113 31010A A2 21 19 92 28 8A A3 37 74 410105 5运价表（单位：百元运价表（单位：百元运价表（单位：百元运价表（单位：百元/千吨）千吨）千吨）千吨）B B1 1 B B2 2B B3 3B B4 4产量产量产量产量A A1 13 311113 310107 7x x1111 x x1212 x x1313x x1414A A2 21 19 92 28 84 4x x2121 x x2222x x2323x x2424A A3 37 74 410105 59 9x x3131 x x3232x x3333x x3434销量销量销量销量3 36 65 56 62020设产地设产地设产地设产地A Ai i到销地到销地到销地到销地B Bj j的调运量为的调运量为的调运量为的调运量为x xij ij，运量平衡表为：，运量平衡表为：，运量平衡表为：，运量平衡表为：s.t.s.t.产量约束：产量约束：产量约束：产量约束：x x1111+x x1212+x x1313+x x1414=7=7(1)(1)x x2121+x x2222+x x2323+x x2424=4=4(2)(2)x x3131+x x3232+x x3333+x x3434=9=9(3)(3)销量约束：销量约束：销量约束：销量约束：x x1111+x x2121+x x3131=3=3(4)(4)x x1212+x x2222+x x3232=6=6(5)(5)x x1313+x x2323+x x3333=5=5(6)(6)x x1414+x x2424+x x3434=6=6(7)(7)非负约束：非负约束：非负约束：非负约束：x xij ij 0 0，i i=1,2,3,4=1,2,3,4，j j=1,2,3=1,2,3建立建立建立建立LPLP数学模型：数学模型：数学模型：数学模型：标函数标函数标函数标函数 MinZ=3MinZ=3x x1111+11+11x x1212+3+3x x1313+10+10 x x1414+x x2121+9+9x x2222+2+2x x2323+8+8x x2424+7+7x x3131+4+4x x3232+10+10 x x3333+5+5x x3434运输问题模型的特点运输问题模型的特点1 1 1 1、对于一个、对于一个、对于一个、对于一个m=3m=3，n=n=4 4的运输问题，共的运输问题，共的运输问题，共的运输问题，共有有有有mm n=n=1212个个个个变量变量变量变量，mm+n=7n=7个约束方程个约束方程个约束方程个约束方程；s.t.s.t.均由均由均由均由“”连接，且连接，且连接，且连接，且找不到单位矩阵。找不到单位矩阵。找不到单位矩阵。找不到单位矩阵。2 2、运输问题运输问题运输问题运输问题基变量共有基变量共有基变量共有基变量共有mm+n n-1-16 6个个个个基变量数应为基变量数应为基变量数应为基变量数应为mm+n n个，但，产销平衡，造成个，但，产销平衡，造成个，但，产销平衡，造成个，但，产销平衡，造成前前前前mm个供应地约束和后个供应地约束和后个供应地约束和后个供应地约束和后n n个需求地约束是线性相关的，即个需求地约束是线性相关的，即个需求地约束是线性相关的，即个需求地约束是线性相关的，即有一个约束方程可以用其余的约束方程表示。有一个约束方程可以用其余的约束方程表示。有一个约束方程可以用其余的约束方程表示。有一个约束方程可以用其余的约束方程表示。运输问题模型的特点运输问题模型的特点3 3 3 3、运输问题一定有最优解运输问题一定有最优解运输问题一定有最优解运输问题一定有最优解 一一一一方方方方面面面面，任任任任何何何何使使使使产产产产销销销销平平平平衡衡衡衡的的的的调调调调运运运运方方方方案案案案都都都都是是是是可可可可行行行行方方方方案案案案，这这这这样样样样的的的的方方方方案案案案一一一一定定定定能能能能找找找找到到到到，即即即即运运运运输输输输问问问问题题题题的的的的可可可可行行行行域域域域必必必必定定定定存存存存在；在；在；在；另一方面，由于另一方面，由于另一方面，由于另一方面，由于c c c cijijijij 0 0 0 0，则则则则ZZ0 0 0 0，而目标函数是极小而目标函数是极小而目标函数是极小而目标函数是极小化的，则化的，则化的，则化的，则Z Z有界。有界。有界。有界。4 4 4 4、运输问题代表了一大类问题，除调运以外，还有、运输问题代表了一大类问题，除调运以外，还有、运输问题代表了一大类问题，除调运以外，还有、运输问题代表了一大类问题，除调运以外，还有资源分配、材料配方、工作指派、投资分析、工作地资源分配、材料配方、工作指派、投资分析、工作地资源分配、材料配方、工作指派、投资分析、工作地资源分配、材料配方、工作指派、投资分析、工作地布置和农作物布局等，是布置和农作物布局等，是布置和农作物布局等，是布置和农作物布局等，是LPLPLPLP体系中形成最早，至今应体系中形成最早，至今应体系中形成最早，至今应体系中形成最早，至今应用最成功的分支。主要的求解方法是表上作业法（是用最成功的分支。主要的求解方法是表上作业法（是用最成功的分支。主要的求解方法是表上作业法（是用最成功的分支。主要的求解方法是表上作业法（是一种特殊的单纯形法）。一种特殊的单纯形法）。一种特殊的单纯形法）。一种特殊的单纯形法）。第二讲表上作业法第二讲表上作业法表上作业法表上作业法 表上作业法是一种特殊的单纯形法，其基本思路与表上作业法是一种特殊的单纯形法，其基本思路与表上作业法是一种特殊的单纯形法，其基本思路与表上作业法是一种特殊的单纯形法，其基本思路与其他数学规划一致，即其他数学规划一致，即其他数学规划一致，即其他数学规划一致，即第一步，给出初始方案（初始可行解）；第一步，给出初始方案（初始可行解）；第一步，给出初始方案（初始可行解）；第一步，给出初始方案（初始可行解）；第二步，对得到的方案进行最优性检验，若为最优第二步，对得到的方案进行最优性检验，若为最优第二步，对得到的方案进行最优性检验，若为最优第二步，对得到的方案进行最优性检验，若为最优则停止，否则转入下步；则停止，否则转入下步；则停止，否则转入下步；则停止，否则转入下步；第三步，调整方案，得出新的方案，其目标函数值第三步，调整方案，得出新的方案，其目标函数值第三步，调整方案，得出新的方案，其目标函数值第三步，调整方案，得出新的方案，其目标函数值应优于前一方案，然后回到第二步。应优于前一方案，然后回到第二步。应优于前一方案，然后回到第二步。应优于前一方案，然后回到第二步。一、初始方案的确定西北角法一、初始方案的确定西北角法 B B1 1 B B2 2B B3 3B B4 4产量产量产量产量A A1 13 311113 310107 7A A2 21 19 92 28 84 4A A3 37 74 410105 59 9销量销量销量销量3 36 65 56 62020中心思想：从运量平衡表的中心思想：从运量平衡表的中心思想：从运量平衡表的中心思想：从运量平衡表的“西北角西北角西北角西北角”（左上角）的变量开（左上角）的变量开（左上角）的变量开（左上角）的变量开始（从始（从始（从始（从x x1111开始），给予尽可能大的运量开始），给予尽可能大的运量开始），给予尽可能大的运量开始），给予尽可能大的运量。342236此时，此时，此时，此时，Z Z0 0=3=3 3+43+4 11+211+2 9+29+2 2+32+3 10+610+6 5=1355=135最小元素法最小元素法基本思路：就近调运，即在运费最低的路段开始，将尽可能基本思路：就近调运，即在运费最低的路段开始，将尽可能基本思路：就近调运，即在运费最低的路段开始，将尽可能基本思路：就近调运，即在运费最低的路段开始，将尽可能多的运量分配给运费最低的路段。多的运量分配给运费最低的路段。多的运量分配给运费最低的路段。多的运量分配给运费最低的路段。B B1 1 B B2 2B B3 3B B4 4产量产量产量产量A A1 13 311113 310107 7A A2 21 19 92 28 84 4A A3 37 74 410105 59 9销量销量销量销量3 36 65 56 62020314633此时，此时，此时，此时，Z Z=4=4 3+33+3 10+310+3 1+11+1 2+62+6 4+34+3 5=865=86沃格尔沃格尔Vogel近似法近似法 B B1 1 B B2 2B B3 3B B4 4产量产量产量产量行罚数行罚数行罚数行罚数A A1 13 311113 310107 7A A2 21 19 92 28 84 4A A3 37 74 410105 59 9销量销量销量销量3 36 65 56 62020基本思想：如果某行的罚数大，则不按该行最小单位运价安排基本思想：如果某行的罚数大，则不按该行最小单位运价安排基本思想：如果某行的罚数大，则不按该行最小单位运价安排基本思想：如果某行的罚数大，则不按该行最小单位运价安排运输，就会造成运费的较大损失，这种损失可能会大于不按全运输，就会造成运费的较大损失，这种损失可能会大于不按全运输，就会造成运费的较大损失，这种损失可能会大于不按全运输，就会造成运费的较大损失，这种损失可能会大于不按全局最小单位运价安排运输的损失。局最小单位运价安排运输的损失。局最小单位运价安排运输的损失。局最小单位运价安排运输的损失。011行罚数：一行中的：次小单位运价最小单位运价行罚数：一行中的：次小单位运价最小单位运价行罚数：一行中的：次小单位运价最小单位运价行罚数：一行中的：次小单位运价最小单位运价376151116312例：例：Vogel说明说明B B1 1 B B2 2B B3 3B B4 4A A1 19999999999994 45 5A A2 28 89 92 21 18 8A A3 37 74 410105 57 73 36 65 56 665罚数罚数罚数罚数95951 11 1二、方案的最优性检验闭回路法二、方案的最优性检验闭回路法闭回路闭回路闭回路闭回路从一个非基变量从一个非基变量从一个非基变量从一个非基变量（空格）（空格）（空格）（空格）出发，由水平或垂直直线组出发，由水平或垂直直线组出发，由水平或垂直直线组出发，由水平或垂直直线组成的一条封闭折线，该折线的其余顶点都为基变量成的一条封闭折线，该折线的其余顶点都为基变量成的一条封闭折线，该折线的其余顶点都为基变量成的一条封闭折线，该折线的其余顶点都为基变量（数学格）（数学格）（数学格）（数学格）。任一非基变量的闭回路是唯一的。任一非基变量的闭回路是唯一的。任一非基变量的闭回路是唯一的。任一非基变量的闭回路是唯一的。B B1 1 B B2 2B B3 3B B4 4产量产量产量产量A A1 13 311113 310107 74 43 3A A2 21 19 92 28 84 43 31 1A A3 37 74 410105 59 96 63 3销量销量销量销量3 36 65 56 620203 33 32 21 11 10 0空格（非基变量）的检验数空格（非基变量）的检验数空格（非基变量）的检验数空格（非基变量）的检验数 1111以空格（以空格（以空格（以空格（A A1 1，B B1 1）为例，为例，为例，为例，A A1 1至至至至B B1 1本来没有运量，现试作调整如下：本来没有运量，现试作调整如下：本来没有运量，现试作调整如下：本来没有运量，现试作调整如下：调整调整调整调整运费变化运费变化运费变化运费变化（A A1 1，B B1 1）处增加处增加处增加处增加1 1吨增加吨增加吨增加吨增加3 3元元元元（A A1 1，B B3 3）处减少处减少处减少处减少1 1吨减少吨减少吨减少吨减少3 3元元元元（A A2 2，B B3 3）处增加处增加处增加处增加1 1吨增加吨增加吨增加吨增加2 2元元元元（A A2 2，B B1 1）处减少处减少处减少处减少1 1吨减少吨减少吨减少吨减少1 1元元元元上述调整后，总运费上述调整后，总运费上述调整后，总运费上述调整后，总运费 11113 33 32 21 11 1，增加了，增加了，增加了，增加了1 1元元元元B B1 1 B B2 2B B3 3B B4 4产量产量产量产量A A1 13 311113 310107 74 43 3A A2 21 19 92 28 84 43 31 1A A3 37 74 410105 59 96 63 3销量销量销量销量3 36 65 56 620201 11 11 11 1B B1 1 B B2 2B B3 3B B4 4产量产量产量产量A A1 13 311113 310107 74 43 3A A2 21 19 92 28 84 43 31 1A A3 37 74 410105 59 96 63 3销量销量销量销量3 36 65 56 620201 12 21 11 110101212存在存在存在存在 24240 0，不是最优解。不是最优解。不是最优解。不是最优解。位势法（对偶变量法）位势法（对偶变量法）B B1 1 B B2 2B B3 3B B4 4A A1 13 311113 310107 74 43 3A A2 21 19 92 28 84 43 31 1A A3 37 74 410105 59 96 63 33 36 65 56 62020B B1 1B B2 2B B3 3B B4 4u ui i A A1 13 31010A A2 21 12 2A A3 34 45 5v vj j 1 1、c cij iju ui i+v vj j ，不妨令不妨令不妨令不妨令v v1 1任意数，一般如任意数，一般如任意数，一般如任意数，一般如0 0；0 01 11 12 28 8-3-37 71 12 21 1-1-1101012122 2、ij ij=c ci ij j-（u ui i+v vj j）初等变换法初等变换法第三步，作列初等变换：各列减去本列中未打（第三步，作列初等变换：各列减去本列中未打（第三步，作列初等变换：各列减去本列中未打（第三步，作列初等变换：各列减去本列中未打（）的数，使未）的数，使未）的数，使未）的数，使未打（打（打（打（）的数全为）的数全为）的数全为）的数全为0 0，这时（，这时（，这时（，这时（）内的数即为对应空格的检验数。）内的数即为对应空格的检验数。）内的数即为对应空格的检验数。）内的数即为对应空格的检验数。（1 1）（2 2）000000（1 1）00（-1-1）（1010）00（1212）00第一步，将非基格（空格）对应的运价打上（第一步，将非基格（空格）对应的运价打上（第一步，将非基格（空格）对应的运价打上（第一步，将非基格（空格）对应的运价打上（）；）；）；）；（3 3）（1111）31031011（9 9）22（8 8）（7 7）44（1010）55+1+1+5+5第二步，作行初等变换：第二步，作行初等变换：第二步，作行初等变换：第二步，作行初等变换：对同一列中有两个或两个以上未打（对同一列中有两个或两个以上未打（对同一列中有两个或两个以上未打（对同一列中有两个或两个以上未打（）的数的列，按行的顺序）的数的列，按行的顺序）的数的列，按行的顺序）的数的列，按行的顺序在同一行对各数加上一个数，使同列中未打（在同一行对各数加上一个数，使同列中未打（在同一行对各数加上一个数，使同列中未打（在同一行对各数加上一个数，使同列中未打（）数的值相等；）数的值相等；）数的值相等；）数的值相等；（3 3）（1111）31031022（1010）33（9 9）（1212）99（1515）1010第三讲表上作业法及讨论第三讲表上作业法及讨论三三、方方案案的的改改进进B B1 1 B B2 2B B3 3B B4 4产量产量产量产量A A1 13 311113 310107 74 43 3A A2 21 19 92 28 84 43 31 1A A3 37 74 410105 59 96 63 3销量销量销量销量3 36 65 56 620201 11 12 21 1101012121 1、按按按按 klkl=min=min ij ij ij ij00M0，其他条件不变。其他条件不变。其他条件不变。其他条件不变。例产地例产地例产地例产地A A1 1、A A2 2、A A3 3的产量分别为的产量分别为的产量分别为的产量分别为5050、5050、6060，销地，销地，销地，销地B B1 1、B B2 2、B B3 3、B B4 4的可能销量分别为的可能销量分别为的可能销量分别为的可能销量分别为4040、5555、6060、2020，单，单，单，单位产品运价如表，试求合理的调运方案。位产品运价如表，试求合理的调运方案。位产品运价如表，试求合理的调运方案。位产品运价如表，试求合理的调运方案。B B1 1B B2 2B B3 3B B4 4A A1 13 3不通不通4 45 5A A2 27 73 38 8不通不通A A3 32 23 3不通不通2 2B B1 1 B B2 2B B3 3B B4 4A A1 13 3MM4 45 55050A A2 27 73 38 8MM5050A A3 32 23 3MM2 260604040555560602020A A4 4*0 00 00 00 015151020405005050 0M-4M-42 25 55 5M-2M-2M-3M-31 11 1已是最优解，多重最优解已是最优解，多重最优解已是最优解，多重最优解已是最优解，多重最优解四、极大化问题四、极大化问题求解极大化问题时，对表上作业法作如下修正：求解极大化问题时，对表上作业法作如下修正：求解极大化问题时，对表上作业法作如下修正：求解极大化问题时，对表上作业法作如下修正：1 1、用最大元素法确定初始方案；、用最大元素法确定初始方案；、用最大元素法确定初始方案；、用最大元素法确定初始方案；2 2、当、当、当、当 ij ij00时，判定为最优解，时，判定为最优解，时，判定为最优解，时，判定为最优解，ij ij求法不变；求法不变；求法不变；求法不变；3 3、确定换入变量时，、确定换入变量时，、确定换入变量时，、确定换入变量时，maxmax ij ij|ij ij00=lklk，取取取取x xlklk为换为换为换为换入变量。换出变量的确定及运量调整不变。入变量。换出变量的确定及运量调整不变。入变量。换出变量的确定及运量调整不变。入变量。换出变量的确定及运量调整不变。例某农场的土地例某农场的土地例某农场的土地例某农场的土地10001000亩，按土质及水源条件不同分亩，按土质及水源条件不同分亩，按土质及水源条件不同分亩，按土质及水源条件不同分为三类：为三类：为三类：为三类：B B1 1、B B2 2、B B3 3，分别有分别有分别有分别有300300亩、亩、亩、亩、200200亩、亩、亩、亩、500500亩；亩；亩；亩；现有现有现有现有A A1 1、A A2 2、A A3 3三种作物种子，可供播种面积分别为三种作物种子，可供播种面积分别为三种作物种子，可供播种面积分别为三种作物种子，可供播种面积分别为100100亩、亩、亩、亩、500500亩、亩、亩、亩、400400亩。已知各种作物每亩收益如表亩。已知各种作物每亩收益如表亩。已知各种作物每亩收益如表亩。已知各种作物每亩收益如表（单位：元）（单位：元）（单位：元）（单位：元）,要求对作物进行合理布局要求对作物进行合理布局要求对作物进行合理布局要求对作物进行合理布局。B B1 1B B2 2B B3 3A A1 1700700500500480480A2A2850850700700600600A A3 3400400300300500500B B1 1 B B2 2B B3 3A A1 1700700500500480480100100A A2 2850850700700600600500500A A3 34004003003005005004004003003002002005005003002000100400小结小结经济问题经济问题经济问题经济问题最小元素法最小元素法最小元素法最小元素法西北角法西北角法西北角法西北角法VogelVogel法法法法位势法位势法位势法位势法闭回路法闭回路法闭回路法闭回路法初等变换法初等变换法初等变换法初等变换法改进方案改进方案改进方案改进方案闭回路法闭回路法闭回路法闭回路法新基可行解新基可行解新基可行解新基可行解产销平衡产销平衡产销平衡产销平衡Y YN N虚拟产虚拟产虚拟产虚拟产(销销销销)地地地地初始可行解初始可行解初始可行解初始可行解断路断路断路断路N NY Y断路运价断路运价断路运价断路运价MM判断最优判断最优判断最优判断最优N NY Y结论结论结论结论产产产产销销销销平平平平衡衡衡衡问问问问题题题题第五讲综合练习第五讲综合练习期中考试允许带计算器期中考试允许带计算器1 1、思考题：以下几种情况，最优解是否改变？、思考题：以下几种情况，最优解是否改变？、思考题：以下几种情况，最优解是否改变？、思考题：以下几种情况，最优解是否改变？1 1、所有运价都增加、所有运价都增加、所有运价都增加、所有运价都增加1 1；2 2、所有运价都乘以、所有运价都乘以、所有运价都乘以、所有运价都乘以2 2；3 3、某一行（或列）的所有运价都加、某一行（或列）的所有运价都加、某一行（或列）的所有运价都加、某一行（或列）的所有运价都加1 1；4 4、某一行（或列）的所有运价都乘以、某一行（或列）的所有运价都乘以、某一行（或列）的所有运价都乘以、某一行（或列）的所有运价都乘以2 2。B B1 1 B B2 2B B3 3B B4 4产量产量产量产量A A1 13 311113 310107 75 52 2A A2 21 19 92 28 84 43 31 1A A3 37 74 410105 59 96 63 3销量销量销量销量3 36 65 56 620200 02 22 21 112129 9不变不变不变不变不变不变不变不变不变不变不变不变可能改变可能改变可能改变可能改变答：答：答：答：2、综合题：、综合题：销地销地销地销地产地产地产地产地B B1 1B B2 2B B3 3B B4 4产量产量产量产量A A1 14 4不通不通不通不通4 411111818A A2 22 28 83 3不通不通不通不通1616A A3 38 85 511116 62020销量销量销量销量8 8141412121414已知某运输问题运价表如下，求最优调运方案：已知某运输问题运价表如下，求最优调运方案：已知某运输问题运价表如下，求最优调运方案：已知某运输问题运价表如下，求最优调运方案：B B1 1 B B2 2B B3 3B B4 4A A1 14 44 411111818A A2 22 28 83 31616A A3 38 85 511116 620208 8141412121414B B5 5*0 00 00 06 688414686解产销，设虚拟销地解产销，设虚拟销地解产销，设虚拟销地解产销，设虚拟销地B B5 5*；设大数设大数设大数设大数MM为不通道路的运价。为不通道路的运价。为不通道路的运价。为不通道路的运价。MMMM1 1M-10M-101 1M-10M-101 1101012125 5B B1 1 B B2 2B B3 3B B4 4A A1 14 44 411111818A A2 22 28 83 31616A A3 38 85 511116 620208 8141412121414B B5 5*0 00 00 06 688414686MMMM1 1调整方案：调整方案：调整方案：调整方案：8 8 8 8 12 12 12 12 14 14 14 14 6 6 6 6 0 0 0 0 B B1 1 B B2 2B B3 3B B4 4A A1 14 44 411111818A A2 22 28 83 31616A A3 38 85 511116 620208 8141412121414B B5 5*0 00 00 06 681261486MMMM1 1M-9M-9M-9M-91 19 911114 4已是最优解已是最优解已是最优解已是最优解01 1解一：解一：解一：解一：B B1 1 B B2 2B B3 3B B4 4A A1 14 44 411111818A A2 22 28 83 31616A A3 38 85 511116 620208 8141412121414B B5 5*0 00 00 06 681261486MMMM0 0M-10M-10M-9M-92 29 912125 5已是最优解已是最优解已是最优解已是最优解01 1解二：解二：解二：解二：3、应用举例、应用举例某企业与用户签订了设备交货合同，已知该企业各季度的生产某企业与用户签订了设备交货合同，已知该企业各季度的生产某企业与用户签订了设备交货合同，已知该企业各季度的生产某企业与用户签订了设备交货合同，已知该企业各季度的生产能力、每台设备的生产成本和每季度末的合同交货量如下表，若能力、每台设备的生产成本和每季度末的合同交货量如下表，若能力、每台设备的生产成本和每季度末的合同交货量如下表，若能力、每台设备的生产成本和每季度末的合同交货量如下表，若生产出的设备当季度不交货，每台设备每季度需支付保管维护费生产出的设备当季度不交货，每台设备每季度需支付保管维护费生产出的设备当季度不交货，每台设备每季度需支付保管维护费生产出的设备当季度不交货，每台设备每季度需支付保管维护费用用用用0.10.1万元，试问企业应如何安排生产计划，才能使总费用最小？万元，试问企业应如何安排生产计划，才能使总费用最小？万元，试问企业应如何安排生产计划，才能使总费用最小？万元，试问企业应如何安排生产计划，才能使总费用最小？季度季度季度季度生产能力生产能力生产能力生产能力交货量交货量交货量交货量生产成本生产成本生产成本生产成本/台台台台1 12525151512.012.02 23535202011.011.03 33030252511.511.54 42020202012.512.51 1 2 23 34 41 125252 235353 330304 4202015152020252520205*5*0 00 00 00 03030交货季交货季交货季交货季生生生生产产产产季季季季生生生生产产产产量量量量交货量交货量交货量交货量12.012.012.112.112.212.212.312.3MM11.011.011.111.111.211.2MMMM11.511.511.611.6MMMMMM12.512.54、应用举例、应用举例有三个产地有三个产地有三个产地有三个产地A A1 1、A A2 2、A A33生产同一种物品，使用者为生产同一种物品，使用者为生产同一种物品，使用者为生产同一种物品，使用者为B B1 1、B B2 2、B B33，各产地到各使用者的单位运价如下表。这三个使用者的需求量分，各产地到各使用者的单位运价如下表。这三个使用者的需求量分，各产地到各使用者的单位运价如下表。这三个使用者的需求量分，各产地到各使用者的单位运价如下表。这三个使用者的需求量分别为别为别为别为1010、4 4、6 6个单位。由于销售需要和客观条件的限制，产地个单位。由于销售需要和客观条件的限制，产地个单位。由于销售需要和客观条件的限制，产地个单位。由于销售需要和客观条件的限制，产地A A1 1至少要发出至少要发出至少要发出至少要发出6 6个单位的产品，它最多只能生产个单位的产品，它最多只能生产个单位的产品，它最多只能生产个单位的产品，它最多只能生产1111个单位的产品；个单位的产品；个单位的产品；个单位的产品；A A2 2必须发出必须发出必须发出必须发出7 7个单位的产品；个单位的产品；个单位的产品；个单位的产品；A A3 3至少要发出至少要发出至少要发出至少要发出4 4个单位的产品。试求最个单位的产品。试求最个单位的产品。试求最个单位的产品。试求最优运输方案。优运输方案。优运输方案。优运输方案。B B1 1B B2 2B B3 3A A1 12 24 43 3A A2 21 15 56 6A A3 33 32 24 4使用量使用量使用量使用量10104 46 6发货量发货量发货量发货量a a227 7a a3 3 4 4a a1 1 6 69977B B1 1 B B2 2B B3 3A A1 12 24 43 36 6A A2 21 15 56 67 7A A3 33 32 24 44 410104 46 6B B5 5*3 3A A1 1 2 4 32 4 3A A3 3 3 2 43 2 43 33 30 0MMMMMM0 0B B1 1 B B2 2B B3 3A A1 12 24 43 36 6A A2 21 15 56 67 7A A3 33 32 24 44 410104 46 6B B5 5*3 3A A1 1 2 4 32 4 3A A3 3 3 2 43 2 43 33 30 0MMMMMM0 074303303空白空白