9512.net
甜梦文库
当前位置:首页 >> >>

运筹学模型

第四章

运筹学模型

本章教学重点是: 线性规划模型 目标规划模型 运输模型及其应用 图论模型 最小树问题 最短路问题 最大流问题与最小割 复习要求 1.进一步理解基本建模过程,掌握类比法、图示法以及问题分析、合理假设的内涵。 2.进一步理解数学模型的作用与特点。 本章复习重点是线性规划模型、运输问题模型和目标规划模型。具体说来,要求大家会 建立简单的线性规划模型,把实际问题转化为线性规划模型的方法要掌握,当然比较简单。 运输问题模型主要要求善于将非线性规划模型转化为运输规化模型, 这种转化后求解相当简 单。你至少把一个很实际的问题转化为用表格形式写出的模型,至于求解是另外一回事,一 般不要求。 目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模 型。这是主要的考虑方向。另外,关于图模型的问题涉及到最短路问题,具体说来用双标号 法来求解一个最短路模型。 这之前恐怕要善于将一个实际问题转化为图模型。 还有一个最小 数的问题,该如何把一个网络中的最小数找到。另外在个别场合可能会涉及一笔划问题。 1.营养配餐问题的数学模型为

min Z = C1 x1 + C 2 x + C n x n
a11 x1 + a12 x 2 + + a1n x n ≥ b1 , a 21 x1 + a 22 x 2 + + a 2 n x n ≥ b2 , st a x + a x + + a x ≥ b , m2 2 mn n m m1 1 x j ≥ 0( j = 1,2, , n)
或更简洁地表为

min Z =

∑C
j =1

n

j

xj

n ∑ aij x j ≥ bi j =1 s t x ≥ 0 (i = 1,2,, m) j j = 1,2,, n
其中的常数 C j 表示第 j 种食品的市场价格,a ij 表示第 j 种食品含第 i 种营养的数量,b i 表 示人或动物对第 i 种营养的最低需求量. 例 1 医院为病人配制营养餐,要求每餐中含有铁不低于 50 单位,蛋白质不低于 40 单位,钙不低于 42 单位.假设仅有两种食品 A 和 B 可供配餐,相关数据见下表.试问,如 何购买两种食品进行搭配,才能即使病人所需营养达到需求,又使总花费最低?

食品 营养含量 铁 蛋白质 钙 价格 A 10 5 6 4 B 5 8 5 3 (单位) (mg) (g) (mg) (元/kg)

解:设购买食品 A 和 B 依次为 x1 和 x2(kg) ,则有 营养最低要求满足: (铁含量) 10x1+5x2≥50 5x1+8x2≥40 (蛋白质含量) 6x1+5x2≥42 (钙含量) 总花费数记为 Z,则有数学模型

min Z = 4 x1 + 3x 2

10 x1 + 5 x2 ≥ 50, (3.1) 5 x + 8 x ≥ 40, (3.2) 1 2 s.t. 6 x1 + 5 x2 ≥ 42, (3.3) x1 , x2 ≥ 0
用图解法求解上述问题. 首先以 x1,x2 为坐标轴,建立平面直角坐标系(如图 3-10) ,由于 x1,x2 均非负,故只画出 了第一象限. 其次, 将其余约束条件几何化. (3.1) 条件 表示的是一个半平面, 先画出直线 10x1+5x2=50, 因为 10x1+5x2≥50,故直线(3.1)的上方区域即条件(3.1)所满足的 x1,x2 的取值范围;同 理将条件(3.2)(4.3)也几何化,并注意到几个条件要同时满足,便求得一个以顶点 A、 、 B、C、D 为顶点的右上方无界的五边形区域 x1 ABCD x2 .这个区域内的任一点(x1,x2)都是 x2 一个可行性配餐方案. x2

D C B A O ① ③ ② x1 O

D C B A x1

图 3—10

图 3—11

最后,为了求出最优解,将目标函数也进行几何化,有

x2 =

4 Z x1 + 3 3

(3.4)

称为目标函数直线族,因为其中的 Z 作为参数出现.易见,随着 Z 的逐渐增大,目标函 数直线(3.4)向右上方平行移动.也就是说,随着目标函数直线的逐渐往右上方平移,Z 的值越来越大,反之,Z 的值越来越小(如图 3-11).又原问题是求函数 Z 的最小值,故应 令目标函数直线尽可能往左下方平移.但这种平移是有限制的,即点(x1,x2)必须在可行域 内.于是两者的结合便可确定本例的最优解. 通过上述斜率关系分析可知目标函数直线与直线(3.1)和直线(3.3)的交点(顶点 C) 相切,即直线(3.1)与直线(3.3)的交点即最优解点.于是问题就变成了求解方程组

10 x1 + 5 x 2 = 50, 6 x1 + 5 x 2 = 42.
易解得 x1=2,x2=6 为最优解,通常记作: x = = ( 2,6) 6 对应的目标函数值称为最优值,记作 Z*=26 2.运输问题模型 运输问题也是一种线性规划问题, 只是决策变量设置为双下标变量. 假如问题具有 m 个 产地和 n 个销地, 第 i 个产地用 Ai 表示,其产量为 ai(i=1,2,…,m),第 j 个销地用 Bj 表示,其 销量为 bj(j=1,2,…,n), 从 Ai 运往 Bj 的运价为 cij, 而 平衡运输问题的一般模型可以写成为


2

T

∑ ai =
i =1 n

m

∑b
j =1

n

j

表示产销平衡。那么产销

min Z = ∑∑ cij xij
i =1 j =1

m

n ∑ xij = a i j =1 m s t ∑ xij = b j i =1 i = 1,2, , m xij ≥ 0 j = 1,2, , n
例 2 某公司经营的一种产品拥有四个客户,由公司所辖三个工厂生产,每月产量分别 为 3000,5000,4000 件。该公司已承诺下月出售 4000 件给客户 1,出售 3000 件给客户 2 以及至少 1000 件给客户 3。客户 3 与客户 4 都想尽可能多购剩下的产品。已知各工厂运销 一件产品给客户 1、2、3、4 可得到的净利润是:工厂 1 为 65、63、62、64 元;工厂 2 为 68、67、65、62 元;工厂 3 为 63、60、59、60 元。问该公司应如何拟订运销方案,才能在 履行诺言的前提下获利最多? 上述问题是否可以转化为运输模型加以处理?若是, 请写出对应的表格形式的运输模型 (即产销平衡运价表) ,否则说明理由。 解:可以。产销平衡表如下:

表 4-1 产销平衡表 客户 工厂 1 2 3 虚 销量 1 65 68 63 -M 4000 2 63 67 60 -M 3000 3 62 65 59 -M 1000 3′ 62 65 59 0 4000 4 64 62 60 0 4000 产量 3000 5000 4000 4000

例 3 设有一批产品要从三个生产地 A1、A2 和 A3 运往四个销售地 B1、B2、B3 和 B4(生产地 和销售地以后简称为产地和销地) 。三个产地运往四个销地的运价,三个产地的产量和四个 销地的需求量如下表所示, 试策划一个运输方案, 使得在满足需求条件下, 总运输费用最少。 表 4-2 产销平衡运价表 单位:拾元/吨 销 地 运 价 B1 B2 B3 B4 产量 产 地 3 11 3 10 7 A1 1 9 2 8 4 A2 A3 7 4 10 5 9 20 销量 3 6 5 6 20 解:以 xij 表示从第 i 个产地运送到第 j 个销地的运量,则依供需关系有下列约束条件: 供给方面:

需求方面:

x11 + x12 + x13 + x14 = 7 x 21 + x 22 + x 23 + x 24 = 4 x31 + x32 + x33 + x34 = 9 x11 + x 21 + x31 = 3 x12 + x 22 + x32 = 6 x13 + x 23 + x33 = 5 x14 + x 24 + x34 = 6

非负性: xij≥0

(i = 1,2,3; j = 1,2,3,4)

总运费: min Z = 3 x11 + 11x12 + + 5 x34 将上述目标函数与约束条件合在一起便构成所谓具有三个产地和四个销地的产销平衡 运输问题的数学模型. 下面用表上作业法求解。 首先,用最小元素法确定初始方案。 表 4-3 单位:拾元/吨 销地 B1 B2 B3 B4 运价 产量 产地 A1 3 11 3 10 7 A2 1 9 2 8 4

A3 销量

7 3

4 6

10 5

5 6

9

如表 4-5 所示的运价中,由于 1 最小,于是决定由 A2 供应 B1,于是第一个基变量被确定 为 x21 .再看供求关系,B1 需要 3 吨,而 A2 产量为 4 吨,于是尽量满足需求,由 A2 供应 B13 吨.在 运价 1 的右下角写上③.由于 B1 的需求已满足,故 A1,A3 不必再向 B1 供应,于是在运价 3 与 7 右下角打×,表示变量 x11 与 x31 被确定为非基变量. 在剩下的 9 个运价中再找最小运价为 2,并按上述方法确定第二个基变量 x23=1,同时变 量 x22 与 x24 被确定为非基变量. 依此类推,便可确定 4 个基变量和 6 个非基变量如表 4-4 表4-4 销地 B1 B2 B3 B4 运价 产量 产地 A1 7 3× 11× 3○ 4 10 A2 4 1○ 3 9× 2○ 1 8× A3 9 7× 4○ 6 10× 5 3 6 5 6 销量 此时,只有两个变量 x14 和 x34 未被确定,但它们必须成为基变量.于是根据产销平衡关 系确定 10 下画③,5 下画③.终于得到初始基变量组及其取值为: x13=4, x14=3, x21=3, x23=1, x32=6, x34=3, 其余 xij=0 即为初始运输方案(表 4-8),其总运费也在表上计算为 Z(0)=3×4+10×3+1×3+2×1+4×6+5×3=86(拾元) 表4-5 销地 B1 B2 B3 B4 运价 产量 产地 A1 7 3× 11× 3○ 4 10○ 3 A2 4 1○ 3 9× 2○ 1 8× A3 9 7× 4○ 6 10× 5○ 3 3 6 5 6 销量 其次,方案的最优性检验——闭回路法 检验一个方案的最优性说到底是看此方案是否还有改进的余地.而方案是否有改进余 地,关键是看非基变量中是否有能转变为基变量(取值大于零)而使目标值进一步改善,若 有,则称这个变量为进基变量. 如 x11 增加 1, 按照产销平衡原则, x13 必须减值为 3, 否则与产量为 7 矛盾.而当 x13 减值为 3 时, x23 必须增值一个单位, 否则又与销量为 5 矛盾, 依此又知, x21 需减少一个单位.以上变化 导至总运费发生的变化值为 λ11=3-3+2-1=1>0 这就是说,令 x11 变为基变量,总运费将增加 1 个单位,故此举不合适。由此可知,λ11 具有检验 x11 进基是否能改善目标值的作用,称为非基变量 x11 的检验数.如果非基变量的检验数大于零, 则该变量进基不合适;若检验数等于零, 则该变量进基也无助于目标值的改进.由此可推出: 若所有非基变量的检验数均≥0, 则目前这个方案便没有改进的余地, 即已是最优方案.反之,

若至少有一个非基变量的检验数<0, 则目前的方案便非最优方案.这就是运输问题的方案最 优性检验原理. 值得注意的是,在求非基变量 x11 的检验数时,恰好是在不存在闭回路的基变量组内引进 一个非基变量后所形成的唯一闭回路中进行的相应运算:以进基变量为第一个顶点,按逆时针 (或顺时针)将闭回路的奇数顶点运价赋以“+”号,偶数顶点运价赋以“-”号所形成的代数和便 是该变量的检验数.按此法则,可求得所有非基变量的检验数如下: λ11=3-3+2-1>0, λ12=11-10+5-4>0 λ22=9-2+3-10+5-4>0,λ24=8-10+3-2=-1<0 λ31=7-5+10-3+2-1>0, λ33=10-5+10-3>0 由于λ14<0,故初始方案非最优方案. 然后,用闭回路法调整方案 由λ24<0,故令 x24 进基,按产销平衡原则在相应的闭回路上进行调整.注意到基变量总数 量 m+n-1 个,则应令原基变量组成员之一出基(取值为 0).易见,令 x24=min{该闭回路上偶数顶 点运量}={1,3}=1,便知新基变量 x24 取值为 1,被保留下来的基变量为 x13=4+1=5,x14=3-1=2,x21=3,x32=6,x34=3, 其余为非基变量,其中 x23=1-1=0 为新增非基变量. 重新画一张表 4-9,标上新基变量及其取值,便得新运输方案表,总运费为 z=3×5+10× 2+1×3+8×1+4×6+5×3=85(拾元). 那么这个方案是否最优方案?返回 2)步再检验即可. 表4-6 销地 B1 B2 B3 B4 产量 产地 A1 7 3 11 3○ 10○ 5 2 A2 4 1○ 9 2× 8○ 3 1 A3 9 7 4○ 10 5○ 6 3 3 6 5 6 销量 现求新方案中非基变量的检验数: λ12=11-10+5-4>0, λ11=3-10+8-1=0, λ22=9-8+5-4>0, λ31=7-1+8-5>0, λ23=2-8+10-3>0, 33=10-5+10-3>0, 可见所有λij≥0,故表 4-9 所给方案已是最优方案, 用运销图画在下面:
5

B3 A2
2

3 1

B1 A3 B4

6 3

B2 B4

A1 B4

图 4-1 3.目标规划模型 例 4 某工厂生产两种产品 A、B 分两班生产,每周生产总时间为 80 小时,两种产品的 预测销售量、生产率和赢利如下表 产品 A B 预测售量(万件/周) 7 4.5 生产率(件/小时) 1000 1000 单位利润(元/件) 0.15 0.3

制定一合理的生产方案,要求依次满足下列目标: (1)充分利用现有能力,避免设备闲置; (2)周加班时间限制在 10 小时以内; (3)两种产品周生产品量应满足预测销售,满足程度的权重之比等于它们单位利润之 比; (4)尽量减少加班时间. 解: (1)建立模型 设:①每班上班时间为 8 小时,在上班时间内只能生产一种产品; ②周末加班时间内生产哪种产品不限; ③生产 A 产品用 x 班,生产 B 产品用 y 班,周加班时生产 A 产品用 x1 小时,生产 B 产 品用 y1 小时.则有

x + y = 10 8 y + y ≤ 45 1 8 x + x1 ≤ 70 8 y + y1 8 x + x1 9 : 14 = 2 : 1 x1 + y1 ≤ 10 x, y, x , y ≥ 0 且为整数 1 1
(2)求解 现在求满足(1)中第 2,3 个方程可看出: x ≤ 8 , y ≥ 5 ; 将(1)中的第 1 个方程代入第 4 个方程得: 128 y = 720 + 9 x1 7 y1 现在就是在满足 y ≤ 5 , x1 + y1 ≤ 10 条件下,使上式两端的取值尽量接近.显然

y = 5 , x1 = 0 , y1 = 10
因此 x = 5 制定方案为, 生产 A, 两种产品所占总时间各一半, B 周加班 10 小时全用于生产产品 B. 4.最短路问题的数学模型 许多实际问题都归结为最短路问题,例如两地间的管道铺设,线路安装,道路修筑, 运路选取等等;再如工厂布局,设备更新等问题也可转化为最短路问题。 最短路问题一般描述如下:在一个图(或者说网络)中,给定一个始点 vs 和一个终点 vt,求 vs 到 vt 的一条路,使路长最短(即路的各边权数之和最小) 。 这里介绍求最短路的常用算法: 狄克斯屈(E.D.Dijkstra)双标号法 该法是狄克斯屈在 1959 年提出的,适用于所有权数均为非负(即一切 wij ≥ 0 , wij 表示 顶点 vi 与 vj 的边的权数)的网络,能够求出网络的任一点 vs 到其它各点的最短路,为目前 求这类网络最短路的最好算法。 该法在施行中,对每一个点 vj 都要赋予一个标号,并分为固定标号 P(vj)和临时标号 T(vj)两种,其含义如下:

P(vj)——从始点 vs 到 vj 的最短路长; T(vj)——从始点 vs 到 vj 的最短路长上界。 一个点 vj 的标号只能是上述两种标号之一。若为 T 标号,则需视情况修改,而一旦成 为 P 标号,就固定不变了。 开始先给始点 vs 标上 P 标号 0,然后检查点 vs,对其一切关联边(vs, vj)的终点 vj,给 出 vj 的 T 标号 wij;再在网络的已有 T 标号中选取最小者,把它改为 P 标号。以后每次都检 查刚得到 P 标号那点,按一定规则修改其一切关联边终点的 T 标号,再在网络的所有 T 标 号中选取最小者并把它改为 P 标号。这样,每次都把一个 T 标号点改为 P 标号点,因为网 络中总共有 n 个结点,故最多只需 n-1 次就能把终点 vt 改为 P 标号。这意味着已求得了 vs 到 vt 的最短路。 狄克斯屈标号法的计算步骤如下: 1° 令 S={vs} 为 固 定 标 号 点 集 , S = V \ {v s } 为 临 时 标 号 点 集 , 再 令

P (vi ) = 0 vt ∈ S
2°检查点 vi,对其一切关联边(vi, vj)的终点 v j ∈ S ,计算并令

min{T (v j ), P(vi ) + wij } T (v j )
3°从一切 v j ∈ S 中选取并令

min{T (v j )} = T (v r ) T (v r )
。再令 选取相应的弧(vi, vr)

S ∪ {v r } S , S \ {v r } S
4°若 S = , 则停止,P (v j ) 即 vs 到 vj 的最短路长, 特别 P (vt ) 即 vs 到 vt 的最短路长, 而已选出的弧即给出 vs 到各点的最短路;否则令 v r vi ,返 2°。 注意: 注意:若只要求 vs 到某一点 vt 的最短路,而没要求 vs 到其他各点的最短路,则上述步 骤 4°可改为 4°若 r=t 则结束, P ( v r ) 即为所求最短路长;否则令 v r v i ,返 2°.

例 5 设有七个单位要求煤气公司为其铺设煤气管道,经施工单位测量,七个单位间可 通管道的路线长度如表 4-7 所示.其中单位 A 距煤气公司供应网最近, 1.5km.现拟铺设地 为 下管道,并经 A 与供应网连通,铺设费用为 25 元/m,试协助施工单位进行施工路线设计, 使得费用最少,求出最小费用值.
表 4-7 单位:km

j 距 离 I A B 0 3 3 0 4 3 7 2 — 4 — — — — A B C D E F G

C 4 3 0 — 5 7 — D 7 2 — 0 2 — 6 E — 4 5 2 0 1 4 F — — 7 — 1 0 2 G — — — 6 4 2 0 (其中的“-”表示其间无直达路线.) 解:先建立问题的图论模型.以七个单位为研究对象,其间有直达路线则连一条边,在 相应的边旁标以相应的路长,便构成一个网络赋权图模型如图 4—2.可见其中充满了圈,于 是从中寻求树(顶点数相同)便成为关键.

图 4—2

图 4—3

先看 A、B、C、D 四个顶点形成的图 4-3(a). 该图总边长为 19。 在保证通气条件下,这个路线的费用最贵.因为如果按照图 4—3(b)的树形图铺设,保 证通气条件下, 总费用仅为 14 (km) 的费用.而按树形图 4—3 (C) 铺设, 则费用只有 8 (km) 的费用.换句话讲,在相同顶点情形下,构成的树的总权数大小也有区别。因此自然提出了 最小赋权树,简称最小树的概念:在具有相同顶点的树中,总赋权数最小的树称为最小树. 在本例,我们要寻求的就是上述图模型中的最小树. 最小树的求法有两种,一种称为“避圈法” ,一种是“破圈法” ,两法各具优缺点,但 它们具有共同的特征——去掉图中的圈并且每次都是去掉圈中边权较大的边。 这里仅介绍破 圈法,就本例说明如下:

图 4-4

用破圈法求最小树时, 先从图中任取一圈, 去掉该圈的一条最大边; 然后重复这个步骤, 直到无圈为止。使用破圈法求解本例的过程如图 4-4 所示.最优方案为

3 2 2 1 2 A → B → D → E F → → G
3

C
最小树长为 13(km) 。再通过 A 与供应网联接,总长度为 14.5km,因此总费用为 25×14.5×103=36.25(万元)



更多相关文章:
数学建模 运筹学模型(一).doc
数学建模 运筹学模型(一) - 运筹学模型(一) 本章重点: 线性规划基础模型、
运筹学经典模型_图文.ppt
运筹学经典模型 - 一、运输问题 返回导航 运输问题(Transportatio
第七讲 运筹学建模_图文.ppt
第七讲 运筹学建模 - 第七讲 运筹学模型 ?7.1 线性规划模型 ?(运输问题
运筹学模型案例.pdf
运筹学模型案例 - 运用运筹学模型解决施工实际问题 黄旭艳 苏州建设交通高等职业
运筹学模型.doc
运筹学模型 - 第5章 运筹学模型 5.2 图论模型 图论是运筹学的一个重要分支
数学建模 运筹学模型(一)汇总.doc
数学建模 运筹学模型(一)汇总 - 运筹学模型(一) 本章重点: 线性规划基础模
运筹学 图与网络模型.ppt
运筹学 图与网络模型 - 第7章 图与网络模型 §1 §2 §3 §4 §5 图
运筹学模型及其应用.txt
第1章绪论 运筹学模型及其应用第1章绪论 运筹学主要研究经济活动、军事活动以及工
运筹学模型与软件实践_图文.ppt
运筹学模型与软件实践 - 运筹学模型与软件实践 Models and Softw
运筹学建模简介及应用_图文.ppt
运筹学建模简介及应用 - 运筹学建模 1.线性规划 2.对偶规划和影子价格 3.运输问题 4.整数规划 5.动态规划 运筹学简介 ? 1.引言: 运筹学(Operations Researc....
运筹学存货模型_图文.ppt
运筹学存货模型 - 第七章 存储模型 ---Inventory Models 第
运筹学模型-线性规划2010_图文.ppt
运筹学模型-线性规划2010 - 例1某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品
运筹学讲义_图文.ppt
运筹学讲义 - 运筹学讲义,黄丽娟运筹学视频讲义,黄丽娟运筹学讲义,黄丽娟考研运筹学讲义,考试点运筹学讲义,黄丽娟运筹学pdf,运筹学软件lingo,运筹学结课报告,运筹...
2-1运筹学数学模型_图文.ppt
2-1运筹学数学模型 - 第二章 线性规划 ? 运筹学中应用最广泛的方法之一 ? 运筹学的最基本的方法之一,网络规划,整数 规划,目标规划和多目标规划都是以线性...
运筹学》考试及参考答案_图文.doc
运筹学》考试及参考答案 - 《运筹学》考试试卷及参考答案 一、填空题 1.运筹学的主要研究对象是各种有组织系统的管理问题,经营活动。 2.运筹学的核心主要是...
运筹学PPT完整版_图文.ppt
运筹学PPT完整版 - 经济管理学核心课程 运筹学 ( Operations R
运筹学 ( 第2次 ).doc
运筹学 ( 第2次 ) - 第 2 次作业 一、单项选择题(本大题共 40 分,共 20 小题,每小题 2 分) 1. 运筹学要求模型的变量、参数与方程式( )、可以控制...
1. 运筹学概论_图文.ppt
1. 运筹学概论 - 运筹学 (Operations Research) 运决筹
运筹学模型在运输问题中的应用.doc
学年第二学期专业班级: 12 普本信计 学号: 1201110054 运筹学 运筹学模型在运输问题中的应用 月 24 日至 2015 年 05 月 30 日共 1 周 姓名: 孟浩 课程...
运筹学经典模型_图文.ppt
运筹学经典模型 - 一、运输问题 返回导航 运输问题(Transportatio

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图