第二章-线性规划运筹学讲义.ppt

1、第二章 线性规划问题与计算机求解l 1 问题的提出l 2 图解法l 3 单纯形法l 4 计算机求解例 1(生产计划问题 ) 某工厂生产 A、 B两种产品，其成本决定于所用的材料。已知单位产品所需材料量、材料日供应量及单价如表 1-1所示。若每生产 A或 B产品一个单位，所费工资同为 30元，又 A、 B的每单位销售价分别为 120元和 150元。问：工厂应如何安排生产，才能使所获总利润最大？产 品生 产 所需原材料 材料 单 价 资 源限制日供 给给 量 kg产 品 A 产 品 B原料 a 6 2 1元 / kg 180kg原料 b 4 10 2.30元 / kg 400kg原料 c 3 5

2、14.60元 / kg 210kg销 售 单 价 (元 ) 120 150单 位 产 品利 润 (元 ) 31 22相关数据1 问题的提出产品 A利润： 120 (1.006 + 2.304 + 14.603 )(材料 ) 30(工资 ) = 31 (元 )数学模型设工厂日产 A、 B产品分别为 x1,x2单位 （决策变量）线性规划模型：目标函数： Max z = 31 x1 + 22 x2 约束条件 (subject to)： s.t. 材料的 a约束 6x1 + 2 x2 1804 x1 + 10x2 4003 x1 + 5x2 210x1 , x2 0产品 A利润： 120 (1.006

3、 + 2.304 + 14.603)(材料 ) 30（工资） = 31 (元 )产品 A利润： 150 (1.002 + 2.3010 +14.605 )(材料 ) 30（工资） = 22 (元 )1 问题的提出例 2. 某工厂在计划期内要安排 、 两种产品的生产，已知生产单位产品所需的设备台时及 A、 B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位 、 产品才能使工厂获利最多？设工厂生产产品 、 分别为 x1， x2单位， 则 线性规划模型：目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 3002 x1 + x2 400x

4、2 250x1 , x2 0产 品 产 品 设备 使用成本和 单 价 资 源限制设备 1 1 10元 / 时 300台 时原料 A 2 1 12元 / kg 400kg原料 B 0 1 18元 / kg 250kg销 售 单 价 (元 ) 84 140单 位 产 品利 润 (元 ) 50 100例 3. 某饲料公司希望用玉米、红薯两种原料来配置一种混合饲料，已知两种原料含三种营养成分和混合饲料对营养成分的要求如下表：问题：公司应任何采购两种原材料，使即满足营养要求，又使成本最少？设公司采购用于混合饲料中玉米数量 x1 kg ，红薯数量 x2 kg 线性规划模型：目标函数： Min z = 2

5、x1 + 1.8 x2 约束条件： s.t. 8 x1 + 4x2 203x1 + 6 x2 18x1 + 5x2 16x1 , x2 0营 养成分 每公斤玉米 每公斤 红 薯 饲 料 对营 养要求碳水化合物 8 4 20蛋白 质 3 6 18维 他命 1 5 16采 购 成本（元 /KG） 2 1.8线性规划问题主要类型n资源分配问题 （ resource-allocation） 以 符号表示的函数约束称为资源约束，这些限制要求使用的资源必须小于等于所能提供的资源的数量。资源分配问题的共性就是它们的函数约束全部为资源约束。例 1、 2n成本收益平衡问题 （ cost-benefit-trad

6、e-off） 以 符号表示的函数约束为收益约束，形式为收益取得的水平必须大于等于最低可接受水平。收益约束反映了管理层所规定的目标。如果所有约束均为收益约束，这一问题为成本收益平衡问题。例 3n网络配送问题 （ distribution-network） 以符号表示的函数约束称为确定需求的约束，它们表示了一定数量的确定的需求，提供的数量等于要求的数量。网络配送问题的共性就是它们的主要函数约束为一种特定形式的确定需求的约束。n混合问题 （ mixed Problem） 除以上三类以外的问题l 建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（ x1 ， x2 ， ， xn ），

7、每一组值表示一个方案； Decision variables 决策变量3.用决策变量的函数形式写出目标函数，确定最大化或最小化目标； Objective function 目标函数4.用一组决策变量的线性等式或线性不等式表示解决问题过程中必须遵循的约束条件 ; Constraints 约束l 一般形式目标函数： Max （ Min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ） b1a21 x1 + a22 x2 + + a2n xn （ =, ） b2 am1 x1 + am2 x2 + +

8、amn xn （ =, ） bmx1 ， x2 ， ， xn 0 非负性例 2.目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 (A)2 x1 + x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)得到最优解：x1 = 50， x2 = 250 最优目标值 z = 275002 图 解 法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例 1详细讲解其方法：2 图解法 画出可行域 满足约束的区域x2x1x20x2=0x2x1x10x1=0(1)分别取决策变量 x1, x2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例 1的每个约束条件都代表一个半平面。（ 2）对每个不等式 (约束条件 )，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100 200 300x1+x2300x1+x2=300100100 2002x1+x24002x1+x2=400300200300400