管理运筹学（第三版）第二章.ppt

13管理运筹学第二章线性规划的图解法§1§2§3问题的提出图解法图解法的灵敏度分析14管理运筹学第二章线性规划的图解法一些典型的线性规划在管理上的应用合理利用线材问题:如何在保证生产的条件下,下料最少;配料问题:在原料供应量的限制下如何获取最大利润;投资问题:从投资项目中选取方案,使投资回报最大;产品生产计划:合理利用人力、物力、财力等,使获利最大;劳动力安排:用最少的劳动力来满足工作的需要;运输问题:如何制定调运方案,使总运费最小。线性规划的组成目标函数:max f 或min f ;约束条件:. (subject to),满足于;决策变量:用符号来表示可控制的因素。15管理运筹学§Ⅰ、Ⅱ两种产品的生产,生产单位产品所需的设备台时及A、B 两种原材料的消耗以及资源的限制,如表2-1 所示。表2-1ⅠⅡ资源限制300 台时400 kg250 kg设备原料A原料B单位产品获利12050 元111100 元问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多?线性规划模型目标函数:max约束条件: = 50 x1 + 100 x2x1 + x2 ≤ 3002 x1 + x2 ≤ 400x2 ≤ 250x1 , x2≥016管理运筹学§1问题的提出建模过程(1)理解要解决的问题,明确在什么条件下,要追求什么目标。(2)定义决策变量(x1 ,x2 ,…,xn),每一组值表示一个方案。(3)用决策变量的线性函数形式写出目标函数,确定最大化或最小化目标。(4)用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件。一般形式目标函数:max(min)z = c1 x1 + c2 x2 + …+ cn xn约束条件: x1 + a12 x2 + …+ a1n xn ≤(=, ≥)b1a21 x1 + a22 x2 + …+ a2n xn ≤(=, ≥)b2……am1 x1 + am2 x2 + …+ amn xn ≤(=, ≥)bmx1 ,x2 ,…,xn ≥017管理运筹学§2对于只包含两个决策变量的线性规划问题,可以在平面直角坐标系上作图表示线性规划问题的有关概念,并求解。下面通过例1 详细介绍图解法的解题过程图解法例1目标函数:maxz = 50 x1 + 100 x2约束条件:.(A)(B)(C)(D)(E)x1 + x2 ≤ 3002 x1 + x2 ≤ 400x2 ≤ 250x1 ≥ 0x2 ≥ 0得到最优解:x1 = 50,x2 = 250最优目标值z = 27 50018§2图解法(1)分别取决策变量x1,x2 为坐标向量建立直角坐标系。在直角坐标系里,图上任意一点的坐标代表了决策变量的一组值,例1 的每个约束条件都代表一个半平面(如图2-1 所示)。图2-1管理运筹学19§2图解法(2)对每个不等式(约束条件),先取其等式在坐标系中作直线,然后确定不等式所决定的半平面(如图2-1 所示)。图2-1管理运筹学20§2图解法(3)把五个图合并成一个图,取各约束条件的公共部分(如图2-1(f)所示)。图2-1管理运筹学21§2图解法(4)目标函数z = 50x1 + 100x2,当z 取某一固定值时得到一条直线,直线上的每一点都具有相同的目标函数值,称之为“等值线”。平行移动等值线,当移动到B 点时,z 在可行域内实现了最大化。A、B、C、D、E是可行域的顶点,有限个约束条件其可行域的顶点也是有限的。图2-2管理运筹学22管理运筹学§2图解法线性规划的标准化内容之一—引入松弛变量(资源的剩余量)例1 中引入s1,s2,s3,模型变化为:目标函数:max约束条件: = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3x1 + x2 + s1 = 3002 x1 + x2 + s2 = 400x2 + s3 = 250x1 , x2 , s1 , s2 , s3 ≥ 0对于最优解x1 =50,x2 = 250,s1 = 0,s2 =50,s3 = 0说明:生产50 单位Ⅰ产品和250 单位Ⅱ产品将消耗完所有可能的设备台时数及原料B,但原料A 还剩余50 千克。