`
第一章 线性规划与单纯形法
(liner program and simplex algorithm)
第一节 线性规划问题及其数学模型
1. 问题的提出
线性规划问题有两大类型，各举例如下：
例1．某工厂在计划期内要安排生产Ⅰ和Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示，该厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该厂获利最多？
Ⅰ Ⅱ 1 2 设备 8台时 4 0 16 Kg 原材料A 0 4 12 Kg 原材料B 解：对这样的问题用数学的语言来描述，就称为建立数学模型，简称建模。数学模型指用数学方法(字母、符号、数字等)对研究对象的数量关系所进行的定量描述。
该问题是要求如何安排生产方案，即生产多少Ⅰ和Ⅱ两种产品，才能使所获得的利润最大，为此，设Ⅰ和Ⅱ两种产品的产量分别为x1和x2，x1和x2称为决策变量，显然，x1和x2的产量越大，所获得利润也越大，但x1和x2的产量要受到材料设备等资源的约束。如对于设备资源，生产Ⅰ和Ⅱ两种产品消耗的总台时数为x1＋2 x2不能超过设备的有效台时数，即必须要满足下列条件：
x1?2x2?8
同样地，对于原材料A、B，也需满足下列条件：
4x1?164x2?12
由于x1和x2是产品的产量，所以，x1和x2的取值自然限制在：
1
x1?0,x2?0
在满足上述各个条件后，再考虑如何使得总利润z?2x1?3x2最大(总利润为产品Ⅰ和Ⅱ的利润之和)，即maxz?2x1?3x2，这里，max表示要求最大值。所以，该生产计划问题的数学模型可表示为：
maxz?2x1?3x2?x1?2x2?8? ?4x1?16s.t.??4x2?12??x1、x2?0用数学语言描述，就是求一组x1、x2的值，使之在满足下列约束条件条件下：
x1?2x2?84x1?164x2?12x1、x2?0
使目标函数z?2x1?3x2的值尽量大。
这里，s.t.是subject to的缩写，表示受约束于┅。
例2．靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500
3
万m,在两个工厂之间有一条流量为每天200万支流，第一化工厂每天
3
排放含有某种有害物质的工业污水2万m，第二化工厂每天排放含有这
3
种有害物质的工业污水1.4万m。从第一化工厂排出的工业污水流到第二化工厂之前，有20％可自然净化，根据环保要求，河流中工业污水的含量应不大于0.2%，这两个工厂都需要各自处理一部分工业污水，第一
3
化工厂处理工业污水的成本是1000元/万m，第二化工厂处理工业污水
3
的成本是800元/万m，现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小？
2
工厂1
工厂2 500万m
200万m
解：该问题是问两个工厂各应处理多少污水，使得污水处理费用最小。
3
设第一化工厂每天处理污水为x1万m，第二化工厂每天处理污水为x2
3
万m，显然，两个工厂处理污水越少，费用就越小，但处理污水量，必须要满足环保要求，受环保标准的限制，环保要求两个工厂附近河流的污水含量都不得大于0 .2％,所以，对第一化工厂处理污水量x1必须满足下列要求：
33 2?x1500?0.2% ?x1?1
同样，对第二化工厂，处理污水量x2也必须满足：
0.8(2?x1)?(1.4?x2)700?0.2% ? 0.8x1?x2?1.6
由于两个工厂每天处理污水量不会大于各自的排放量，所以有，
x1?2,x2?1.4 两个工厂处理污水量又自然限制于：x1?0,x2?0
在这些要求下，使得总费用z?1000x1?800x2最小，记为
minz?1000x1?800x2。所以，该环保问题的数学模型为：
minz?1000x1?800x2?x1?1?0.8x1?x2?1.6??s.t.?x1?2?x?1.4?2??x1、x2?0
线性规划所研究的两类问题，一类是所谓“增产”问题：现有的资
3
源一定，如何安排使用，使得创造的利润、收益等最大，如例1；另一类是所谓“节约”问题：任务一定，如何统筹安排，以尽可能少的资源去完成，如例2。所有的线性规划问题，尽管各个问题的具体内容不同，但都可归结为这两类问题。
例3 （房地产开发）某房屋开发公司拟根据市场的需求修建二居室、三居室和四居室住宅。公司要求其规划部门确定各类住宅的户数，以获得最大利润。约束如下：
工程造价不超过900万元； 总户数不能少于350户；
基于市场分析，各类住宅在总户数中所占比例为：二居室不大于20％，三居室不大于60％，四居室不大于40％；
各类住宅造价（户）：二居室 2万元，三居室 2.5万元，4居室 3万元
各类住宅利润（户）：二居室 2000元，三居室 3000元，4居室 4000元。
分析：这是一个在资源一定的情况下的求收益最大的问题，即“增产”问题。
决策变量：设拟修建的二居室、三居室和四居室的户数分别为x,x,x.
123约束：
2x1?2.5x2?3x3?900x1?x2?x3?350x1?20%?x1?x2?x3?x2?60%?x1?x2?x3?x3?40%?x1?x2?x3?
目标函数：z?0.2x1?0.3x2?0.4x3
要求寻找使得公司预计利润最大的开发方案，此问题的数学模型为：Maxz?0.2x1?0.3x2?0.4x3
s.t.
2x1?2.5x2?3x3?900x1?x2?x3?350x1?20%?x1?x2?x3?x2?60%?x1?x2?x3?
4
相关推荐：
loading