运筹学习题课课件.pptVIP

第二章 线性规划建模及单纯形法 1、线性规划的概念 1、线性规划的概念 1、线性规划的概念 2、线性规划的图解法 例:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 2、线性规划的图解法 问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。 解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2） Max z = 1500 x1 + 2500 x2 s.t. 3x1+2x2 ≤ 65 (A) 2x1+x2 ≤ 40 (B) 3 x2 ≤ 75 (C) x1 ,x2 ≥ 0 (D, E) 2、线性规划的图解法 按照图解法的步骤在以决策变量x1 ，x2 为坐标向量的平面直角坐标系上对每个约束（包括非负约束）条件作出直线，并通过判断确定不等式所决定的半平面。各约束半平面交出来的区域即可行集或可行域如下图阴影所示。 2、线性规划的图解法 2、线性规划的图解法 3、 单 纯 形 法 例 标准形式问题： Max z =1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 ≥ 0 最优解 x1 = 5 x2 = 25 x4 = 5（松弛标量，表示B设备有5个机时的剩余） 最优值 z* = 70000 单 纯 形 表 Max z = 5x1+2x2+3x3-x4-Mx5-Mx6 s.t. x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6 =20 x1+2x2+4x3+x4 =26 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥ 0 第一阶段问题（LP - 1） Max z = - x5 - x6 s.t. x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 生产计划的问题 生产计划的问题 生产计划的问题 求 xi 的利润:利润 = 售价 - 各成本之和 可得到 xi（i=1,2,3,4,5）的利润分别为 15、10、7、13、9元。 这样我们建立如下的数学模型。 目标函数: Max 15x1+10x2+7x3+13x4+9x5 约束条件： s.t. 5x1+10x2+7x3 ≤ 8000 6x1+4x2+8x3+6x4+4x5 ≤12000 3x1+2x2+2x3+3x4+2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0 配料问题 配料问题 解：设 xij 表示第 i 种（甲、乙、丙） 产品中原料 j 的含量。这样我们 建立数学模型时，要考虑： 目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件：规格要求 4 个； 供应量限制 3 个。 Max z=-15x11+25x12+15x13-30x21+10x22-40x31-10x33 人力资源分配的问题 人力资源分配的问题 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我