第2章 线性规划的图解法

《第2章 线性规划的图解法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章线性规划的图解法2.1问题的提出例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：产品Ⅰ产品Ⅱ资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？22.1问题的提出设第Ⅰ种产品的生产件数为x,第Ⅱ种产品的生产件1数为x,可以建立如下的线性规划模型：2maxzxx=50+10012xx+≤300122xx+≤40012st..x≤2502xx,0≥122.1问题的提出这是一

2、个典型的利润最大化的生产计划问题。其中，“max”是英文单词“maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示“满足于……”。上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x,x的取值。122.1问题的提出例2某昼夜服务的公交线路每天各时间区段内所需的工作人员数量如下：时段时间所需人数16:00~10:0060210:00~14:0070314:00~18:0060418:00~22:0050522:00~2:002062:00~6:0030设工作人员分别在各时间区段一开始时上班，并连续工作八小时，问该公

3、交线路应至少配备多少名工作人员？2.1问题的提出解：设在时段1-6开始上班的工作人员分别为x，x，x，123x，x，x，则可建立如下的线性规划模型：456minzxxxxxx=+++++123456xx+≥6016xx+≥7012xx+≥6023stx..+≥x5034xx+≥2045xx+≥3056xj≥=0,1,2,,6j2.1问题的提出所谓线性规划问题就是求一组变量(x,x,…,x)的值，它们在满足一组线12n性等式或不等式的限制条件下，使某一线性函数的值达到极大或极小。而线性规划就是研究并解决这类问题的一门理论和方法。线性

4、规划模型是由决策变量、目标函数和约束条件三要素组成。在规划问题数学模型中，决策变量为连续变量，目标函数和约束条件都是线性的。2.1问题的提出线性规划问题的共同特点：１.每一问题都用一组变量（称决策变量）表示某一方案，这些变量的一组定值就代表一个具体方案。通常这组变量的值是非负的。２.都有一个期望达到的目标，并可用一线性函数（称目标函数）表示。按研究的问题不同，要求目标函数实现极大化或极小化。３.存在一定的限制条件（称约束条件），这些条件都可以用一组线性等式或不等式表达。2.1问题的提出•一般形式max(min)zcxcx=++cx1122nnaxax

5、111+122+ax1nn≤=≥(,)b1axax211+222+ax2nn≤=≥(,)b2st..axaxm11+m22+axmnn≤=≥(,)bmxx,,,x≥012n•等价形式nmax(min)z=∑cxjjj=1n∑axijj≤=≥(,)bii,=1,2,,mst..j=1xj≥=0,1,2,,nj2.1问题的提出例3靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。第一化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这

6、种工业污水1.4万立方米，从第一化工厂排出的工业污水流到第二化工厂之前，有20%可以自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水，第一化工厂处理工业污水的成本为1000元/万立方米，第二化工厂处理工业污水的成本为800元/万立方米，问在满足环保要求的条件下，每厂各应处理多少工业污水，使得这两个工厂总的处理费用最少？2.1问题的提出2.1问题的提出解：假设第一化工厂每天处理工业污水数为x,第二化工厂1每天处理工业污水数为x,可建立如下的线性规划模型：2minzxx=100012+800minzxx=100012

7、+800(2−≤x1)50021000x1≥10.82(−+−xx12)(1.4)700≤210000.8xx12+≥1.6stx..1≤2stx..1≤2x≤1.4x≤1.422≥xx12,0≥xx,0122.1问题的提出例4某厂在今后四个月内需租用仓库堆放物资，已知各月份所需仓库面积数字列于下表，月份1234所需仓库面积(100m2)15102012仓库租借费用随合同而定，期限越长折扣越大，具体数字见下表，合同租借期限1个月2个月3个月4个月合同期内的租22800450060007300费(元/100m)租借仓库的

8、合同每月可办理，每份合同