04-运输问题 运筹学 教学课件.pptVIP

平衡运输问题规划模型 产大于销运输问题规划模型 产小于销运输问题规划模型 运输问题求解方法 表上作业法 最佳调运方案 * 运输问题 有一企业欲将A1、A2、A3三地生产的某产品运往B1、B2、B3、B4四地销售，产地Ai的产品在销地Bj销售的单位利润为cij，三产地的产量分别是a1、a2、a3，四销地的销量分别是b1、b2、b3、b4，具体数据见下表。请设计最佳调运方案，使该企业利润最大。 3500 3000 2000 1500 销量 5000 8 4 3 9 A3 2500 6 7 2 8 A2 2500 7 6 5 10 A1 运量 B4 B3 B2 B1 销地 产地 单位 利润 问题规划模型 3500 3000 2000 1500 销量 5000 8 /x34 4 /x33 3 /x32 9 /x31 A3 2500 6 /x24 7 /x23 2 /x22 8 /x21 A2 2500 7 /x14 6 /x13 5 /x12 10 /x11 A1 运量 B4 B3 B2 B1 销地 产地 单位 利润 max z = 10x11+5x12+6x13+7x14 + 8x21+2x22+7x23+6x24 +9x31+3x32+4x33+8x34 s.t. x11+x12+x13+x14 = 2500， x21+x22+x23+x24 = 2500 ， x31+x32+x33+x34 = 5000 x11+x21+x31 = 1500， x12+x22+x32 = 2000， x13+x23+x33 = 3000， x14+x24+x34 = 3500， xij ≥ 0, i =1,2,3 j =1,2,3,4 一般运输问题 根据下面表格设计调运方案，使利润最大或成本最小。 bn … b2 b1 销量 am Cmn … Cm2 Cm1 Am … … … … … … a2 C2n … C22 C21 A2 a1 C1n … C12 C11 A1 产量 Bn … B2 B1 平衡运输问题 1、平衡运输问题：总产量=总销量 2、产大于销运输问题：总产量总销量 增加虚拟销地可以转化为平衡运输问题 3、产小于销运输问题：总产量总销量 增加虚拟产地可以转化为平衡运输问题 调运方案 bn … b2 b1 销量 am xmn … xm2 xm1 Am … … … … … … a2 x2n … x22 x21 A2 a1 x1n … x12 x11 A1 产量 Bn … B2 B1 xij是从产地Ai调运到销地Bj的调运量。 运输问题通用规划模型 使用规划求解软件求解运输问题 可解平衡和非平衡运输问题 运输问题表上作业法 特殊求解方法，非平衡运输问题必须转化为平衡运输问题才能求解 表上作业法与单纯形法相似，但适合手工计算，适合解决简单的运输问题。 表上作业法基本步骤： 确定初始方案 进行最优检验 调整、改进最优方案 列产销平衡表 A1调运1500到B1 A3调运3500到B4 A2调运2500到B3 A1调运500到B3 A1调运500到B2 A3调运1500到B2 初始调运计算结果 分解产地、销地位势