第二章线性规圳的图解法 §1问题的提出 §2图解法 §3图解法的灵敏度分析 管理蓦
管 理 运 筹 学 1 第二章 线性规划的图解法 • §1 问题的提出 • §2 图解法 • §3 图解法的灵敏度分析
第二章线性规的图解法 在管理中一些典型的线性规划应用 合理利用线材问题:如何在保证生产的条件下,下料最少 配料问题:在原料供应量的限制下如何获取最大利润 投资问题:从投资项目中选取方案,使投资回报最大 产品生产计划:合理利用人力、物力、财力等,使获利最 大 劳动力安排:用最少的劳动力来满足工作的需要 ·运输问题:如何制定调运方案,使总运费最小 线性规划的组成: ·目标函数MaxF或MinF 约束条件s.t.( subject to)满足于 决策变量用符号来表示可控制的因素
管 理 运 筹 学 2 第二章 线性规划的图解法 在管理中一些典型的线性规划应用 • 合理利用线材问题：如何在保证生产的条件下，下料最少 • 配料问题：在原料供应量的限制下如何获取最大利润 • 投资问题：从投资项目中选取方案，使投资回报最大 • 产品生产计划：合理利用人力、物力、财力等，使获利最 大 • 劳动力安排：用最少的劳动力来满足工作的需要 • 运输问题：如何制定调运方案，使总运费最小 线性规划的组成： •目标函数 Max F 或 Min F •约束条件 s.t. (subject to) 满足于 •决策变量 用符号来表示可控制的因素
81问题的提出 例1.某工厂在计划期内要安排I、Ⅱ两种产品的生产,已知生产单位产 品所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表 资源限制 设备 原料A 2 I111 300台时 400千克 原料B 0 250千克 匚单位产品获利50元100元 问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多? 线性规划模型 目标函数:Maxz=50x1+100x2 约束条件:st.x1+x2≤300 2x1+x,≤400 2≤250 理蓦总 3
管 理 运 筹 学 3 §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
81问题的提出 建模过程 1.理解要解决的问题,了解解题的目标和条件; 2定义决策变量(x1,x2,…,xn),每一组值表示一个方 案 3用决策变量的线性函数形式写出目标函数,确定最大化或最 小化目标; 4用一组决策变量的等式或不等式表示解决问题过程中必须遵 循的约束条件 般形式 目标函数 Max (in) z=C1x+C2 x2+.+Cnn 约束条件:st.,a1x1+a12x2+…+a1nxn≤ a21x1+a22x2+…+a2nxn≤(=,≥)b2 am1x1+am2X2+…+ anX≤(=,≥)bm 运筹
管 理 运 筹 学 4 §1 问题的提出 • 建模过程 1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量（x1 ，x2 ，… ，xn ），每一组值表示一个方 案； 3.用决策变量的线性函数形式写出目标函数，确定最大化或最 小化目标； 4.用一组决策变量的等式或不等式表示解决问题过程中必须遵 循的约束条件 • 一般形式 目标函数： 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
§2图解法 对于只有两个决例目标函数 策变量的线性规划问目Mxz=50x1+100x2 题,可以在平面直角约束条件 坐标系上作图表示线st 性规划问题的有关概 +x2≤300(A) 2X1+X,≤400(B) 并求解 x2≤250(C) 下面通过例1详细 X1>0(D) 2>0(E) 讲解其方法: 得到最优解: 1=50 250 最优目标值z=27500
管 理 运 筹 学 5 例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 §2 图 解 法 对于只有两个决 策变量的线性规划问 题，可以在平面直角 坐标系上作图表示线 性规划问题的有关概 念，并求解。 下面通过例1详细 讲解其方法：
§2图解法 (1)分别取决策变量Ⅺ1,X2为坐标向量建立直角坐标系。 在直角坐标系里,图上任意一点的坐标代表了决策变量的 组值,例1的每个约束条件都代表一个半平面 X2>0 X1≥0 X1=0 管理蓦
管 理 运 筹 学 6 §2 图 解 法 (1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。 在直角坐标系里，图上任意一点的坐标代表了决策变量的 一组值，例1的每个约束条件都代表一个半平面。 x2 x1 X2≥0 X2=0 x2 x1 X1≥0 X1=0
§2图解法 (2)对每个不等式(约束条件),先取其等式在坐标系中作直 线,然后确定不等式所决定的半平面。 400 x1+x2=300 2x1+x2=400 100 100200/300 2x+x,5400116020300 X1+x2≤300 管理蓦
管 理 运 筹 学 7 §2 图 解 法 （2）对每个不等式(约束条件)，先取其等式在坐标系中作直 线，然后确定不等式所决定的半平面。 100 200 300 100 200 300 x1+x2≤300 x1+x2=300 100 2x 100 200 1+x2≤400 2x1+x2=400 300 200 300 400
§2图解法 (3)把五个图合并成一个图,取各约束条件的公共部分,如 图2-1所示。 x2=250 2x1+x2=400 300 x2=250 250 x,=300 100200300 X2=0 图2-1 理蓦总
管 理 运 筹 学 8 §2 图 解 法 （3）把五个图合并成一个图，取各约束条件的公共部分，如 图2-1所示。 100 100 x2≤250 x2=250 200 300 200 300 x1 x2 x2=0 x1=0 x2=250 x1+x2=300 2x1+x2=400 图2-1
§2图解法 (4)目标函数z=50x1+100 取某一固定值时得到一条直 线李线的年后簃朝同的 同的目标函数值,称之为 动到B点时,在可行 域内实现了最大化。A B,C,D,E是可行域的顶点,对 有限个约束条件则其可行域的顶点也是有限的。 z=10000=50x1+100x Z=27500=50X1+100 Z=2000050x1+100x2 z=0=50Xx1+100X2 图2-2 管理蓦
管 理 运 筹 学 9 §2 图 解 法 （4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直 线，直线上的每一点都具有相同的目标函数值，称之为 “等值线”。平行移动等值线，当移动到B点时，z在可行 域内实现了最大化。A，B，C，D，E是可行域的顶点，对 有限个约束条件则其可行域的顶点也是有限的。 x1 x2 z=20000=50x1+100x2 图2-2 z=27500=50x1+100x2 z=0=50x1+100x2 z=10000=50x1+100x2 C A B D E
§2图解法 线性规划的标准化内容之一: 引入松驰变量(含义是 资源的剩余量) 例1中引入s1,s2,s3模型化为 目标函数:Maxz=50x1+100x2+0s1+0s2+0 约束条件:st +x,+s1=300 2x1+x,+S,=400 x,+s3=250 ,S3≥0 对于最优解x1=50x2=250,s1=0s2=50s3=0 说明:生产50单位I产品和250单位Ⅱ产品将消耗完所有 可能的设备台时数及原料B,但对原料A则还剩余50千克。 管理蓦 10
管 理 运 筹 学 10 §2 图 解 法 • 线性规划的标准化内容之一：——引入松驰变量（含义是 资源的剩余量） 例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千克