§1问题的提出 例1.某工厂在计划期内要安排甲、乙两种产品的生产,已知生产单位产品所需的设备台时 及A、B两种原材料的消耗以及资源的限制,如下表 资源限制 设备 300台时 原料A 400千克 原料B 250千克 单位产品获利 50元 100元 问题:工厂应分别生产多少单位甲、乙产品才能使工厂获利最多? 线性规划模型: 目标函数:Maxz=50x1+100X2 约束条件:st +x2≤300 2x1+X2≤400 2≤250 0
11 §1问题的提出 例1. 某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时 及A、B两种原材料的消耗以及资源的限制，如下表： 问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？ 甲 乙 资源限制 设备 1 1 300 台时 原料 A 2 1 400 千克 原料 B 0 1 250 千克 单位产品获利 50 元 100 元 线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0
线性规模 一般形式 目标函数: Max (Min) Z=C1 XI+C2 X2+.+Cn xr 约束条件 st.a1x1+a12x2+…+a1nXn≤(=,≥)b1 +a2X+...+a2 <(=>)b amx1+am2x2+…+amXn≤(=,≥)bm >0 标准形式 目标函数: X 1X1+c2X2+…+CnXn 约束条件: t. an X1+ a1 X2+...+ aIn Xn 21X1 + tao xot. ta Xn≥0
12 线 性 规 划 模 型 • 一般形式 目标函数： Max （Min） z = c1 x1 + c2 x2 + … + cn xn 约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 • 标准形式 目标函数： Max z = c1 x1 + c2 x2 + … + cn xn 约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… …… am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0
§2图解法 例1 目标函数: Max z=50x+100x 约束条件: 0 S t X1+X2≤300(A) 30 2x1+x2≤400(B x2≤250(C x120(D)200 (E) 得到最优解: 100 250 最优目标值z=27500 10023饭40 13
13 §2 图 解 法 例1. 目标函数： 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 = 27500
选一步讨论 线性规划的标准化内容之一: 引入松驰变量(含义是资源的剩余量) 例1中引入s1,s2,s3模型化为 目标函数:Maxz=50x1+100x2+0s1+0s2+0s3 约束条件:st X1+x2+S1=300 2x1+x2+S2=400 X2+s3=250 对于最优解x1=50x2=250,s1=0s2=50s3=0 说明:生产50单位甲产品和250单位乙产品将消耗完所有可能的设备台时 数及原料B,但对原料A则还剩余50千克。 解的性质 1)线性规划的最优解如果存在,则必定有一个顶点(极点)是最优解; 2)有的线性规划问题存在无穷多个最优解的情况; 3)有的线性规划问题存在无有限最优解的情况,也称无解; 4)有的线性规划问题存在无可行解的情况 作业:P24—-1,2,3,4,5 14
14 进 一 步 讨 论 • 线性规划的标准化内容之一： —— 引入松驰变量（含义是资源的剩余量） 例1 中引入 s1， s2， s3 模型化为 目标函数：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 =250 x1 , x2 , s1 , s2 , s3 ≥ 0 对于最优解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0 说明：生产50单位甲产品和250单位乙产品将消耗完所有可能的设备台时 数及原料B，但对原料A则还剩余50千克。 解的性质： 1） 线性规划的最优解如果存在，则必定有一个顶点（极点）是最优解； 2） 有的线性规划问题存在无穷多个最优解的情况； 3） 有的线性规划问题存在无有限最优解的情况，也称无解； 4） 有的线性规划问题存在无可行解的情况。 作业：P24---1，2，3，4，5