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