《运筹学(远程)cai课件》由会员分享，可在线阅读，更多相关《运筹学(远程)cai课件（47页珍藏版）》请在金锄头文库上搜索。
1、3. 1 运输问题模型与性质 运输模型 例、某公司从两个产地A1、A2将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各 产地运往个销地每件物品的运费如下表所示，问 ：应如何调运可使总运输费用最小？3、运 输 问 题（3.1） 1解： 产销平衡问题： 总产量 = 总销量设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表 ：Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200x21 + x22+ x23 = 300x11 + x21 = 150x12 + x22 = 150x13 +
2、 x23 = 200xij 0 ( i = 1、2；j = 1、2、3）3、运 输 问 题（3.1） 2 系数矩阵 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 特点： 1、共有m+n行，分别表示产地和销地；mn列分别表示各变量 ； 2、每列只有两个 1，其余为 0，分别表示只有一个产地和一个 销地被使用；3、运 输 问 题（3.1） 3 设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输 量问题的模型：m nMin f = cij xiji=1 j=in s.t. xij = si i = 1,2,m j=
3、1 m xij = dj j = 1,2,ni=1xij 0 (i = 1,2,m ; j = 1,2,n) 一般运输模型：产销平衡A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地；si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资为从产地Ai运往销地Bj的单位运价。3、运 输 问 题（3.1续） 43、运 输 问 题（3.1续） 变化：1）有时目标函数求最大，如求利润最大或 营业额最大等；2）当某些运输线路上的能力有限制时，模 型中可直接加入（等式或不等式）约束；3）产销不平衡时，可加入虚设的产地（产 大于销时）或销地（销大于产时
4、）。53、运 输 问 题（3.1续） 求解思路 是基本可行解 最优否 结束否 换基 运输问题基变量的特点* 运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1。* 运输问题的 m + n -1 个变量构成基变量的充分必要条件是 不含闭回路。要弄清下列概念 ：闭回路、闭回路的顶点。63. 2 运输问题的表上作业法 本章重点 1、初始基本可行解的确定： （1）西北角法：从西北角（左上角）格开始，在格内的右下 角标上允许取得的最大数。然后按行（列）标下一格的数。 若某行（列）的产量（销量）已满足，则把该行（列）的其 他格划去。如此进行下去，直至得到一个基本可行解。 （2）最小元素
5、法：从运价最小的格开始，在格内的右下角标 上允许取得的最大数。然后按运价从小到大顺序填数。若某 行（列）的产量（销量）已满足，则把该行（列）的其他格 划去。如此进行下去，直至得到一个基本可行解。 注：应用西北角法和最小元素法，每次填完数，都只划去一行 或一列，只有最后一个元例外（同时划去一行和一列）。当 填上一个数后行、列同时饱和时，也应任意划去一行（列） 在保留的列（行）任意没被划去的格内标一个0。3、运 输 问 题（3.2） 7*3、运 输 问 题（3.2） 8*3、运 输 问 题（3.2） 92、最优性检验：因为求最小，当所有检验数均大于等于0时为最优解 （1）位势法求检验数： 位势：设
6、对应基变量 xij 的 m + n - 1 个 ij ，存在 ui , vj 满足 ui + vj = cij ，i = 1, , m ; j = 1, , n . 称这 些 ui , vj 为该基本可行解对应的位势。由于有 m + n 个变量（ ui , vj ），m + n - 1 个 方程（基变量个数），故有一个自由变量，位势不 唯一。 利用位势求检验数：ij = cij - ui - vj i = 1, , m ; j = 1, , n3、运 输 问 题（3.2） 10 前例，位势法求检验数：step 1 从任意基变量对应的 cij 开始，任取 ui 或 vj ，然后利用公 式 cij
7、 = ui + vj 依次找出 m + n 个 ui , vj ；从 c14 = 10 开始 step 2 计算非基变量的检验数 ij = cij - ui - vj ；填入圆圈内3、运 输 问 题（3.2） 113、主元变换： （1）选负检验数中最小者 rk，那么 xrk 为主元，作 为进基变量；（上页图中 x24 ） （2）以为 xrk 起点找一条闭回路，除 xrk 外其余顶点 必须为基变量格；（上页图中 蓝色回路） （3）为闭回路的每一个顶点标号， xrk 为 1，沿一个 方向依次给各顶点标号； （4）求=minxijxij对应闭回路上的偶数标号格= xpq那么确定xpq为出基变量，为调
8、整量； （5）对闭回路的各奇标号顶点 xij + ，对各偶标号顶 点 xij - ，特别 xpq - = 0，变为非基变量；3、运 输 问 题（3.2） 重复2、3步，直到所有检验数均非负，得到最优解。 12主元变换： 由前面得到 = 1，于是3、运 输 问 题（3.2） ij 0，得到最优解 x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3, 其余 xij = 0 ;最优费用：f* = 3*5+10*2+1*3+8*1+4*6+5*3 = 85 *习题：p 123 习题3 3-1, 3-2133. 3 产销不平衡的运输问题 1、产量大于
9、销量 例、某公司从两个产地A1、A2将物品 运往三个销地B1、B2、B3，各产地的产量、各销地的销量 和各产地运往个销地每件物品的运费如下表所示，问：应 如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为03、运 输 问 题（3.3） 142、销量大于产量例、某公司从两个产地A1、A2将物品运往三个销地B1、B2、 B3，各产地的产量、各销地的销量和各产地运往个销地每件 物品的运费如下表所示，问：应如何调运可使总运输费用最 小？解：增加一个虚设的产地运输费用为03、运 输 问 题（3.3） 15 下面给出一些例题，可作为建模的练习：例、石家庄北方研究院有一、二、三，三个区。每年分别需
10、 要用煤3000、1000、2000吨，由河北临城、山西盂县两处 煤矿负责供应，价格、质量相同。供应能力分别为1500、 4000吨，运价如下表。由于需大于供，经院研究决定一区 供应量可减少0-200吨，二区必须满足需求量，三区供应 量不少于1700吨，试求总费用为最低的调运方案。3、运 输 问 题（例题）16解： 根据题意，作出产销平衡与运价表：取 M 代表一个很大的正数，其作用是强迫相应 的 x31、 x33、 x34取值为0。 3、运 输 问 题（例题）17例、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表。试求总费用为最低的化肥调拨方案。3、
11、运 输 问 题（例题）18解： 根据题意，作出产销平衡与运价表：最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要求的差允许按需要安排，因此把相应的 虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适 当取的数据，根据产销平衡要求确定 D的产量为 50。3、运 输 问 题（例题）19例、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方
12、案。3、运 输 问 题（例题）20解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那末应满足： 交货：x11 = 10 生产：x11 + x12 + x13 + x14 25x12 + x22 = 15 x22 + x23 + x24 35x13 + x23 + x33 = 25 x33 + x34 30x14 + x24 + x34 + x44 = 20 x44 10把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维 护等费用看作运费。可构造下列产销平衡问题：目标函数：Min f = 10.8
13、x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 3、运 输 问 题（例题）21例、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的 生产能力、合同销量和单台电脑绣花机平均生产费用见下表已知上年末库存103台绣花机，如果当月生产出来的机器当月 不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机 器每月的平均仓储费、维护费为0.2万元。在7-8月份销售淡季，全 厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加 班生产
14、机器每台增加成本1万元。问应如何安排1-6月份的生产，可 使总的生产费用（包括运输、仓储、维护）最少？3、运 输 问 题（例题）22解： 这个生产存储问题可化为运输问题来做。考虑： 各月生产与交货分别视为产地和销地1）1-6月份合计生产能力（包括上年末储存量 ）为743台，销量为707台。设一假想销地销量为36 ；2）上年末库存103台，只有仓储费和运输费，把 它列为的0行；3）6月份的需求除70台销量外，还要80台库存， 其需求应为70+80=150台；4）1-6表示1-6月份正常生产情况， 1-6表示1 -6月份加班生产情况。续下页 产销平衡与运价表：3、运 输 问 题（例题）23*习题：p 124 习题3 3-3，3-43、运 输 问 题（例题）返回目录244. 1 动态规划概念与模型 多阶段
