运筹学模型Word文件下载.docx
《运筹学模型Word文件下载.docx》由会员分享，可在线阅读，更多相关《运筹学模型Word文件下载.docx（17页珍藏版）》请在冰点文库上搜索。
105
58
65
（mg）
（g）
价格
43
（元/kg）
解：
设购买食品A和B依次为x1和x2（kg），则有
营养最低要求满足：
10x1+5x2≥50（铁含量）
5x1+8x2≥40（蛋白质含量）
6x1+5x2≥42（钙含量）
总花费数记为Z，则有数学模型
s.t.
用图解法求解上述问题．
首先以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为顶点的右上方无界的五边形区域
ABCD
.这个区域内的任一点（x1,x2）都是一个可行性配餐方案．
图3—10图3—11
最后，为了求出最优解，将目标函数也进行几何化，有
称为目标函数直线族，因为其中的Z作为参数出现.易见，随着Z的逐渐增大，目标函数直线（3.4）向右上方平行移动．也就是说，随着目标函数直线的逐渐往右上方平移，Z的值越来越大，反之，Z的值越来越小（如图3-11）.又原问题是求函数Z的最小值，故应令目标函数直线尽可能往左下方平移．但这种平移是有限制的，即点（x1,x2）必须在可行域内.于是两者的结合便可确定本例的最优解.
通过上述斜率关系分析可知目标函数直线与直线（3.1）和直线（3.3）的交点（顶点C）相切，即直线（3.1）与直线（3.3）的交点即最优解点.于是问题就变成了求解方程组
易解得x1=2,x2=6为最优解，通常记作：
对应的目标函数值称为最优值，记作Z*=26
2．运输问题模型
运输问题也是一种线性规划问题，只是决策变量设置为双下标变量.假如问题具有m个产地和n个销地,第i个产地用Ai表示,其产量为ai（i=1,2,…，m），第j个销地用Bj表示,其销量为bj（j=1,2,…,n）,从Ai运往Bj的运价为cij,而
表示产销平衡。
那么产销平衡运输问题的一般模型可以写成为
例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
4
产量
65
63
62
64
3000
68
67
5000
60
59
4000
虚
-M
销量
1000
例3设有一批产品要从三个生产地A1、A2和A3运往四个销售地B1、B2、B3和B4（生产地和销售地以后简称为产地和销地）。
三个产地运往四个销地的运价，三个产地的产量和四个销地的需求量如下表所示，试策划一个运输方案，使得在满足需求条件下，总运输费用最少。
表4-2产销平衡运价表单位：
拾元/吨
销地
运价
产地
B1B2B3B4
A1
A2
A3
311310
1928
74105
7
9
3656
20
20
以xij表示从第i个产地运送到第j个销地的运量,则依供需关系有下列约束条件:
供给方面:
需求方面:
非负性:
xij≥0
总运费:
将上述目标函数与约束条件合在一起便构成所谓具有三个产地和四个销地的产销平衡运输问题的数学模型.
下面用表上作业法求解。
首先，用最小元素法确定初始方案。
表4－3单位:
销地
运价
产地
B1B2B3B4
如表4－5所示的运价中,由于1最小,于是决定由A2供应B1，于是第一个基变量被确定为
.再看供求关系,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
3×
11×
3
10
9×
2
8×
7×
4
10×
5
此时，只有两个变量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（拾元）
表４－5
B1B2B3B4
8×
其次，方案的最优性检验——闭回路法
检验一个方案的最优性说到底是看此方案是否还有改进的余地.而方案是否有改进余地，关键是看非基变量中是否有能转变为基变量（取值大于零）而使目标值进一步改善，若有，则称这个变量为进基变量.如
x11增加1,按照产销平衡原则,x13必须减值为3,否则与产量为7矛盾.而当x13减值为3时,x23必须增值一个单位,否则又与销量为5矛盾,依此又知,x21需减少一个单位.以上变化导至总运费发生的变化值为
λ11=3－３+2－１=1＞0
这就是说,令x11变为基变量,总运费将增加1个单位,故此举不合适。
由此可知,λ11具有检验x11进基是否能改善目标值的作用,称为非基变量x11的检验数.如果非基变量的检验数大于零,则该变量进基不合适;
若检验数等于零,则该变量进基也无助于目标值的改进.由此可推出:
若所有非基变量的检验数均≥0,则目前这个方案便没有改进的余地,即已是最优方案.反之,若至少有一个非基变量的检验数＜0,则目前的方案便非最优方案.这就是运输问题的方案最优性检验原理.
值得注意的是,在求非基变量x11的检验数时,恰好是在不存在闭回路的基变量组内引进一个非基变量后所形成的唯一闭回路中进行的相应运算:
以进基变量为第一个顶点,按逆时针（或顺时针）将闭回路的奇数顶点运价赋以“+”号,偶数顶点运价赋以“－”号所形成的代数和便是该变量的检验数.按此法则,可求得所有非基变量的检验数如下:
λ11=3－３+2－1＞0, λ12=11－10+5－4＞0
λ22=9－2+3－10+5－４＞0,λ24=８－10+３－２＝－１＜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×
3=85（拾元）.
那么这个方案是否最优方案?
返回2）步再检验即可.
表４－6
3113
92×
8
74
105
现求新方案中非基变量的检验数:
λ11=3－10+8－1=0, λ12=11－10+5－4＞0,
λ22=9－8+5－４＞0,λ31=7－1+8－5＞0,
33=10－5+10－3＞0,λ23=2－8+10－3＞0,
可见所有λij≥0,故表4－9所给方案已是最优方案,用运销图画在下面:
A1A2A3
图4-1
3．目标规划模型
例4某工厂生产两种产品A、B分两班生产，每周生产总时间为80小时，两种产品的预测销售量、生产率和赢利如下表
产品
预测售量（万件/周）
生产率（件/小时）
单位利润（元/件）
A
0.15
B
4.5
0.3
制定一合理的生产方案，要求依次满足下列目标：
（1）充分利用现有能力，避免设备闲置；
（2）周加班时间限制在10小时以内；
（3）两种产品周生产品量应满足预测销售，满足程度的权重之比等于它们单位利润之比；
（4）尽量减少加班时间．
解：
（1）建立模型
设：
每班上班时间为8小时，在上班时间内只能生产一种产品；
周末加班时间内生产哪种产品不限；
生产A产品用x班，生产B产品用y班，周加班时生产A产品用x1小时，生产B产品用y1小时．则有
（2）求解
现在求满足
（1）中第2，3个方程可看出：
，
；
将
（1）中的第1个方程代入第4个方程得：
现在就是在满足
条件下，使上式两端的取值尽量接近．显然
因此
制定方案为，生产A，B两种产品所占总时间各一半，周加班10小时全用于生产产品B．
4．最短路问题的数学模型
许多实际问题都归结为最短路问题，例如两地间的管道铺设，线路安装，道路修筑，运路选取等等；
再如工厂布局，设备更新等问题也可转化为最短路问题。
最短路问题一般描述如下：
在一个图（或者说网络）中，给定一个始点vs和一个终点vt，求vs到vt的一条路，使路长最短（即路的各边权数之和最小）。
这里介绍求最短路的常用算法：
狄克斯屈（E.D.Dijkstra）双标号法
该法是狄克斯屈在1959年提出的，适用于所有权数均为非负（即一切
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}为固定标号点集，
为临时标号点集，再令
2°
检查点vi，对其一切关联边（vi,vj）的终点
计算并令
3°
从一切
中选取并令
选取相应的弧（vi,vr）。
再令
4°
若
，则停止，
即vs到vj的最短路长，特别
即vs到vt的最短路长，而已选出的弧即给出vs到各点的最短路；
否则令
，返2°
。
注意：
若只要求vs到某一点vt的最短路，而没要求vs到其他各点的最短路，则上述步骤4°
可改为
若r=t则结束，
即为所求最短路长；
.
例5设有七个单位要求煤气公司为其铺设煤气管道，经施工单位测量，七个单位间可通管道的路线长度如表4－7所示.其中单位A距煤气公司供应网最近，为1.5km.现拟铺设地下管道，并经A与供应网连通，铺设费用为25元/m，试协助施工单位进行施工路线设计，使得费用最少，求出最小费用值.
表4－7单位:
km
j
距离
I
ABCDEFG
C
D
E
F
G
0347———
30324——
430—57—
72—02—6
—452014
——7—102
———6420
（其中的“－”表示其间无直达路线.）
先建立问题的图论模型.以七个单位为研究对象，其间有直达路线则连一条边，在相应的边旁标以相应的路长，便构成一个网络赋权图模型如图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
最小树长为13（km）。
再通过A与供应网联接，总长度为14.5km，因此总费用为
25×
14.5×
103=36.25（万元）
升级会员 