例3-9 有A、B两种产品,都需要经过前后两道化学反应过程。每一个单位的A产品需要前道过程5小时和后道过程3小时。每一个单位的B产品而要前道过程3小时和后道过程6小时。可供利用的前道过程时间有15小时,后道过程时间有12小时。每生产一个单位的B产品的同时,会产生两个单位的副产品C,且不需要外加任何费用。副产品C最多可售出6个单位;其余的只能加以销毁,每个单位的销毁费用是3元。出售A产品每单位可获利5元,B产品每单位可获利8元,而出售副产品C每单位可获利4元。为了使获得的总利润达到最大,试建立这个问题的线性规划模型,并确定最优方案。
解:设x1,x2和x3分别是产品A、产品B和副产品C的产量,x4是副产品C
的销毁量,Z是总利润,于是这个问题的目标函数是:
maxZ?5x1?8x2?4x3?3x4?0x5?0x6?0x7
约束条件为:
x3?65x1?3x2?153x1?6x2?12x3?x4?2x2xj?0(j?1,2,3,4)经整理得一般形式的线性规划模型为:
maxZ?5x1?8x2?4x3?3x4?0x5?0x6?0x7?x3?6??5x1?3x2?15?s..t?3x1?6x2?12??2x?x?x?0234???xj?0(j?1,2,3,4)构建此问题的初始单纯形表如表3-12所示。
表3-12 Cj CB 0 XB x5 x6 x7 x4
5 8 x2 4 x3 -3 x4 0 x5 0 x6 0 x7 ?i b 6 15 12 0 0 x1 0 5 3 0 -5 0 3 6 -2 -2 1 0 0 1 -7 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 -3 zj -C j 最终单纯形表为表3-13。
29
表3-13 Cj CB 0 XB x5 x6 x2 x3 5 8 x2 4 x3 -3 x4 0 x5 0 x6 0 x7 ?i b 2 9 2 4 32 x1 -1 3.5 1/2 1 3 0 0 1 0 0 0 0 0 1 0 -1 0 0 1 7 1 0 0 0 0 0 1 0 0 0 -1/3 -1/21/6 1/3 8/3 0 8 4 zj -C j 因此,该线性规划问题的最优方案为X?(x1,x2,x3,x4)T?(0,2,4,0)T,最优值为maxZ?5x1?8x2?4x3?3x4?8?2?4?4?32。
例3-10 靠近某河流有两个化工厂,流经第一化工厂的河流流量为每天400万m3,在两个工厂之间有一条流量为每天100万m3支流。第一化工厂每天排放含有某种有害物质的工业污水3万m3。第二化工厂每天排放这种工业污水1.6万m3。从第一化工厂排出的工业污水流到第二化工厂之前,有30%可自然净化。根据环保要求,河流中工业污水的含量应不大于0.1%。这两个工厂都需各自处理一部分工业污水,第一化工厂处理工业污水的成本是1200元/万m3,第二化工厂处理工业污水的成本是600元/万m3。请问在满足环保要求的条件下,每个工厂应该处理多少工业污水,才能使这两个工厂总的工业污水处理费用最小。
解: 这个问题可用线性规划数学模型来描述。设第一化工厂每天处理工业污水量为x1万m3、第二化工厂每天处理工业污水量为x2万m3。
从第一化工厂到第二化工厂之间,河流中工业污水含量要不大干0.1%,因此可得近似关系式:
(3?x1)/400?0.1%
流经第二化工厂后,河流中的工业污水量仍要不大于0.1%,这时有近似关系式:
[0.7(3?x1)?(1.6?x2)](400?100)?0.1%
由于每个工厂每天处理的工业污水量不会大于每天的排放置,故有
x1?3,x2?1.6
该问题的目标是要求两个工厂用于处理工业污水的总费用最小,即
Z?1200x1?600x2
综合上述,该环保问题可用线性规划数学模型表示为: 目标函数
minZ?1200x1?600x2
30
约束条件:
(3?x1)/400?0.1%[0.7(3?x1)?(1.6?x2)](400?100)?0.1% 0?x1?3,0?x2?1.6为了求解这个最小化问题,我们把原目标函数改写成:
minZ?1200x1?600x2?0x3?0x4?0x5?Mx6?0x7
该问题的初始单纯形表如3-14所示。
表3-14 Cj CB 0 XB x3 x4 1200 600 x2 0 x3 0 x4 0 x5 M x6 0 x7 ?i b 3.2 3 2.6 1.6 x1 0.7 1 1 0 -1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 -1 0 -M 0 0 1 0 0 0 0 0 1 0 0 0 M x6 x7 zj -C j 2.6M M-1200 -600 最终单纯形表如表3-15所示。
表3-15 Cj CB 0 XB x3 x4 x1 x7 5 8 x2 4 x3 -3 x4 0 x5 0 x6 0 x7 ?i b 1.38 0.4 2.6 1.6 3120 x1 0 0 1 0 0 -1 0 0 1 -600 1 0 0 0 0 0 1 0 0 0 0.7 1 -1 0 -0.7 -1 1 0 0 0 0 1 0 0 1200 0 zj -C j -1200 1200-M 由于该线性规划问题是最小化问题,而检验数均非正,因此,最终表为最优单纯形表,该线性规划问题的最优方案为X?(x1,x2)T?(2.6,0)T,最优值为
minZ?1200x1?600x2?1200?2.6?3120。
例3-11 设线性规划模型的约束线性方程组为:
?2x1?x2?3x3?4x4?x5?10??3x1?2x2?x3?6x4?3x5?20 ?x?0(j?1,5)?j已知(0,10,0,0,0)和(0,0,5/4,0,25/4)是它的两个基可行解,求这两个解所对应的基。
解:考察解(5,0,0,0,0)可知,x1肯定是基变量;在方程组中,由于x4的
31
系数与x1的系数成比例,x4不能做基变量;而另外三个变量x2,x3和x5都可以作为基变量,于是,这个解所对应的基,可以是(P1,P2)、(P1,P3)、(P1,P5)。 对于解(0,0,5/4,0,25/4)而言,由于x3和x5的取值不为零,所以可作为基变量,因此它们的系数向量就是可行基的列向量,于是,这个解所对应的基是(P3,P5)。
例3-12 制造某种产品,需要A、B、C三种轴件,其规格与数量如表3-16所示。各类轴件都用6.6米长的同一种圆钢下料。若计划生产200台机床,最少要用多少根圆钢?
表3-16
轴类 A B C 规格:长度(米) 3.1 2.3 1.1 每台机床所需轴件数 2 3 4 从实际问题抽象出线性规划模型经常要求进行转化思考。首考虑一根长6.6米的圆钢截成A、B、C三种轴的毛坯有哪些具体下料方式。为此,只需找出全部省料截法,这里考虑使余料?j?1.2米的各种截法,其中1.2米是各类轴件长度中最短者。
表3-17
截法 轴类(米) A 3.1 B 2.3 C 1.1 余料(米) 一根圆钢所截各类轴件数 1 2 0 0 2 1 1 1 3 1 0 3 4 0 1 3 1 5 0 2 1 0.9 6 0 0 6 0 轴件需要量 400 600 900 0.4 0.1 0.2 现在问题归结为采用上述五种截法,需要多少根圆钢才能配成100套轴件,且使总下料根数最少?
解:设按第j种截法下料xj (j?1,2,3,4,5)根。按表3-17种的数据可以建立该问题的线性规划模型:
minZ?x1?x2?x3?x4?x5?x6?2x1?x2?x3?400?x?x?2x?600 ?245s.t??x2?3x3?3x4?x5?6x6?900?xj?0(j?1,2,6)?
32
相关推荐: