《运筹学01-线性规划引论》由会员分享，可在线阅读，更多相关《运筹学01-线性规划引论（25页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性规划引论1.1 线性规划问题及其数学模型1.2 线性规划问题的图解法1.1 线性规划问题及其数学模型(1) 线性规划问题例1、生产组织与计划问题A, B 各生产多少, 可获最大利润?可用资源煤 劳动力 仓库A B1 2 3 2 0 2单位利润40 5030 60 24解: 设产品A, B产量分别为变量x1， x2根据题意，两种产品的生产要受到可用资源的限制， 具体讲：对于煤，两种产品生产消耗量不能超过30，即：x1 + 2x2 30对于劳动力，两种产品生产的占用量不能超过60，即 ：3x1 + 2x2 60对于仓库，两种产品生产的占用量不能超过24，即：2x2 24另外，产品数不能
2、为负，即：x1，x2 0同时，我们有一个追求的目标-最大利润，即：Max Z= 40x1 +50x2综合上述讨论，在生产资源的消耗以及利润与产品产量成 线性关系的假设下，把目标函数和约束条件放在一起，可 以建立如下的数学模型：Max Z= 40x1 +50x2x1 + 2x2 30 3x1 + 2x2 602x2 24x1，x2 0s.t目标函数约束条件例2 合理配料问题求：最低成本的原料混合方案原料 A B 每单位成本1 4 1 0 22 6 1 2 5 3 1 7 1 64 2 5 3 8每单位添 加剂中维生 12 14 8 素最低含量解：设每单位添加剂中原料i的用量为xj(j =1,2,
3、3,4)根据题意：混合配料后，每单位添加剂中A的含量不得低于12，即4x1 + 6x2 + x3+2x4 12每单位添加剂中B的含量不得低于14，即x1 + x2 +7x3+5x4 14每单位添加剂中C的含量不得低于8，即2x2 + x3+3x4 8另外，原料使用量不能为负，即：x1，x2 ， x3， x4， 0同时，我们有一个追求的目标-成本最低，即：Min Z= 2x1 + 5x2 +6x3+8x4综合上述讨论，在添加剂中各维生素的含量以及成本与原 料消耗量成线性关系的假设下，把目标函数和约束条件放 在一起，可以建立如下的数学模型：目标函数约束条件Min Z= 2x1 + 5x2 +6x3
4、+8x44x1 + 6x2 + x3+2x4 12x1 + x2 + 7x3+5x4 142x2 + x3 + 3x4 8xj 0 (j =1,4)s.t2.9m钢筋架子100个，每个需用 2.1m 各1，原料长7.4m1.5m求：如何下料，使得残余料头最少。解：首先列出各种可能的下料方案；计算出每个方案可得到的不同长度钢筋的数量及残余 料头长度；确定决策变量；根据下料目标确定目标函数；根据不同长度钢筋的需要量确定约束方程。例3、合理下料问题设按第i种方案下料的原材料为xi根组合方案 1 2 3 4 5 6 7 82.9m 2 1 1 1 0 0 0 02.1m 0 2 1 0 3 2 1 0
5、1.5m 1 0 1 3 0 2 3 4合 计 7.3m 7.1m 6.5m 7.4m 6.3m 7.2m 6.6m 6.0m料 长 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m料 头 0.1m 0.3m 0.9m 0.0m 1.1m 0.2m 0.8m 1.4m例4、运输问题工 厂1 2 3 库存仓 1 2 1 3 50 2 2 2 4 30库 3 3 4 2 10需求 40 15 35运输 单价求：运输费用最小的运输方案。解：设xij为i 仓库运到j工厂的原棉数量其中：i 1，2，3j 1，2，3 Min Z= 2x11 + x12+3x13+2x21 +
6、2x22 +4x23 +3x31 +4x32 +2x33x11 + x12+ x13 50x21 + x22+ x23 30x31 + x32+ x33 10x11 + x21+ x31 = 40x12 + x22+ x32 = 15x13 + x23+ x33 = 35xij 0s.t(2) 线性规划问题的特点l决策变量： (x1 xn)T 代表某一方案， 决策者要考虑 和控制的因素非负；l目标函数：Z=(x1 xn) 为线性函数，求Z极大或极小;l约束条件：可用线性等式或不等式表示.具备以上三个要素的问题就称为 线性规划问题。目标函数约束条件(3) 线性规划模型一般形式隐含的假设l比例性：
7、决策变量变化引起目标的改变量与决策变量 改变量成正比l可加性：每个决策变量对目标和约束的影响独立于其 它变量l连续性：每个决策变量取连续值l确定性：线性规划中的参数aij , bi , cj为确定值1.2 线性规划问题的图解法定义1：满足约束(2)的X=(X1 Xn)T称为线性规划问题的 可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。例1Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 602X2 24X1 , X2 0s.t解：(1)、确定可行域 X1+2X2 30 3X1+2X2 602X2 24X1 0X2 0203010010
8、2030X2DABC2X2 24X1+2X2 303X1+2X2 60X1 0X2 0可行域(2)、求最优解最优解：X* = (15,7.5) Zmax =975Z=40X1+50X20=40X1+50X2 (0,0)， (10,-8)C点： X1+2X2 =30 3X1+2X2 =600203010102030X1X2DABC最优解 Z=975可行解 Z=0等值线例2、 Max Z=40X1+ 80X2 X1+2X2 303X1+2X2 602X2 24X1 , X2 0s.t解：(1)、确定可行域与上例完全相同 。 (2)、求最优解0203010102030DABC最优解 Z=1200最优
9、解：BC线段最优解：BC线段B点：X(1)=(6,12) C点：X(2)=(15,7.5)X=X(1)+(1-)X(2) (0 1)Max Z=1200 X1 6 15X2 12 7.5X= = +(1- )X1 =6 +(1- )15X2=12+(1- )7.5X1 =15-9X2 =7.5+4.5 (0 1)例3、 Max Z=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0s.tZ=08246X240X1-2X1+X2 22X1+X2 8X1 0X20可行域无界无有限最优解无有限最优解可行域 无上界例4、 Max Z=3X1+2X2 -X1 -X2 1X1 , X2 0无可行域无可行解-1X2-1X10s.tX2 0X1 0-X1 -X2 1直观结论n若线性规划问题有解，则可行域是一个凸多边形（ 或凸多面体）；n若线性规划问题有最优解，则q唯一最优解对应于可行域的一个顶点；q无穷多个最优解对应于可行域的一条边；n若线性规划问题有可行解，但无有限最优解，则可 行域必然是无界的；n若线性规划问题无可行解，则可行域必为空集。第一章作业6、7、8、9、10、12中任选三题
