运筹学 (Operations Research
运 筹 学 ( Operations Research )
第一章 运筹帷幄之中 线性规划及单纯形法 决胜千里之外 Linear Programming
运筹帷幄之中 决胜千里之外 线 性 规 划及单纯形法 Linear Programming 第一章
Chapter1线性规划 (Linear Programming) 本章主要内容： LP的数学模型 图解法 单纯形法 单纯形法的进一步讨论一人工变量法 数据包络法 LP模型的应用
Chapter1 线性规划 (Linear Programming) • LP的数学模型 • 图解法 • 单纯形法 • 单纯形法的进一步讨论－人工变量法 • 数据包络法 • LP模型的应用 本章主要内容：
线性规划问题的数学模型 1.规划问题 生产和经营管理中经常提出如何合理安排，使人力、 物力等各种资源得到充分利用，获得最大的效益， 这就是规划问题。 线性规划通常解决下列两类问题： ()当任务或目标确定后，如何统筹兼顾，合理安排，用 最少的资源（如资金、设备、原标材料、人工、时间等） 去完成确定的任务或目标 (2)在一定的资源条件限制下，如何组织安排生产获得最 好的经济效益（如产品量最多、利润最大）
线性规划问题的数学模型 1. 规划问题 生产和经营管理中经常提出如何合理安排，使人力、 物力等各种资源得到充分利用，获得最大的效益， 这就是规划问题。 线性规划通常解决下列两类问题： （1）当任务或目标确定后，如何统筹兼顾，合理安排，用 最少的资源 （如资金、设备、原标材料、人工、时间等） 去完成确定的任务或目标 （2）在一定的资源条件限制下，如何组织安排生产获得最 好的经济效益（如产品量最多 、利润最大.）
线性规划问题的数学模型 例1.1如图所示，如何截取x使铁皮所围成的容积最 大？ v=(a-2x}.x =0 dx 2(a-2x)x·(-2)+(a-2x)2=0
线性规划问题的数学模型 例1.1 如图所示，如何截取x使铁皮所围成的容积最 大？ x a v a x x 2 2 0 dx dv 2( 2 ) ( 2) ( 2 ) 0 2 a x x a x 6 a x
线性规划问题的数学模型 例1.2某厂生产两种产品， 解： 下表给出了单位产品所需资 1.决策变量：设产品、Ⅱ的产量 源及单位产品利润 分别为x1、x2 项目 I 每天可用能力 2.目标函数：设总利润为z,则有： 设备A(h) 0 5 15 max Z=2x+ 设备B(h) 6 2 24 3约束条件： 调试工序(h) 1 1 5 利润（元） 2 1 5x2≤15 61+2x2≤24 问：应如何安排生产计划，才 +x2≤5 能使总利润最大？ 1,x2≥0
线性规划问题的数学模型 例1.2 某厂生产两种产品， 下表给出了单位产品所需资 源及单位产品利润 项目 Ⅰ Ⅱ 每天可用能力 设备 A（h） 0 5 15 设备 B（h） 6 2 24 调试工序（h） 1 1 5 利润（元） 2 1 问：应如何安排生产计划，才 能使总利润最大？ 解： 1.决策变量：设产品I、II的产量 分别为 x1、x2 2.目标函数：设总利润为z，则有： max z = 2 x1 + x2 3.约束条件： 5x2 ≤ 15 6x1+ 2x2 ≤ 24 x1+ x2 ≤ 5 x1， x2≥0
线性规划问题的数学模型 例1.3已知资料如下表所示， 解： 问如何安排生产才能使利润 1.决策变量：设产品I、Ⅱ的产量 最大？或如何考虑利润大， 分别为x1、x2 产品好销。 2.目标函数：设总利润为z,则 有：maxz=2x1+x2 设备 利润 产品 A B 3约束条件： C D (元) 2 4 0 2 2x1+2x2≤12 x1+2x2≤8 II 2 2 0 4 3 4x, ≤16 有效台时 12 16 12 4x2≤12 x1≥0，x2≥0
线性规划问题的数学模型 例1.3 已知资料如下表所示， 问如何安排生产才能使利润 最大？或如何考虑利润大， 产品好销。 设 备 产 品 A B C D 利润 （元） Ⅰ 2 1 4 0 2 Ⅱ 2 2 0 4 3 有 效 台 时 12 8 16 12 解： 1.决策变量：设产品I、II的产量 分别为 x1、x2 2.目标函数：设总利润为z，则 有： max z = 2 x1 + x2 3.约束条件： x1 ≥ 0 , x2 ≥ 0 2x1 + 2x2 ≤ 12 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12
线性规划问题的数学模型 例1.4某厂生产三种药物， 解： 这些药物可以从四种不同的 1.决策变量：设四种原料的使用 原料中提取。下表给出了单 量分别为：x12、X3、x4 位原料可提取的药物量 2.目标函数：设总成本为z 药物 单位成本 A B C 原料 (元/吨) minz=5x1+6x2+7x3+8x4 甲 2 3 5 3约束条件： 乙 2 0 1 6 x1+2x2+63+x4≥160 丙 1 4 1 7 2 2 8 2x1 +4x3+2x4=200 要求：生产A种药物至少160 3x1+x2+3+2x4≤180 单位；B种药物恰好200单位， C种药物不超过180单位，且 1、x2、x3、x4≥0 使原料总成本最小
线性规划问题的数学模型 例1.4 某厂生产三种药物， 这些药物可以从四种不同的 原料中提取。下表给出了单 位原料可提取的药物量 解： 要求：生产A种药物至少160 单位；B种药物恰好200单位， C种药物不超过180单位，且 使原料总成本最小。 1.决策变量：设四种原料的使用 量分别为：x1、x2 、x3 、x4 2.目标函数：设总成本为z min z = 5 x1 + 6 x2 + 7 x3 + 8 x4 3.约束条件： x1 + 2x2 + x3 + x4 ≥160 2x1 +4 x3 +2 x4 ＝200 3x1 ＋x2 +x3 +2 x4 ≤180 x1、x2 、x3 、x4 ≥0
线性规划问题的数学模型 例1.5某航运局现有船只种类、数量以及计划期内各条航 线的货运量、货运成本如下表所示： 编队形式 货运成本 航线号 船队 货运量 类型 拖轮 A型 B型 (千元/队) (千吨) 驳船 驳船 1 1 2 36 25 2 1 4 36 20 3 2 4 72 40 2 4 27 20 船只种类 船只数 航线号 合同货运量 拖轮 30 1 200 A型驳船 34 2 400 B型驳船 52 问：应如何编队，才能既完成合同任务，又使总货运成本为最小？
例1.5 某航运局现有船只种类、数量以及计划期内各条航 线的货运量、货运成本如下表所示： 航线号 船队 类型 编队形式 货运成本 （千元／队） 货运量 拖轮 A型 （千吨） 驳船 B型 驳船 1 1 1 2 — 36 25 2 1 — 4 36 20 2 3 2 2 4 72 40 4 1 — 4 27 20 船只种类 船只数 拖 轮 30 A型驳船 34 B型驳船 52 航线号 合同货运量 1 200 2 400 问：应如何编队，才能既完成合同任务，又使总货运成本为最小？ 线性规划问题的数学模型
线性规划问题的数学模型 解： 设：x为第j号类型船队的队数(=1,2,3,4)， z为总货运成本 则：minz=36x1+36x2+72x3+27x4 X1+x2+2x3+X4≤30 2x1 +2x3 ≤34 4x2+4x3+4x4≤52 25x1+20x2 =200 40x3+20x4=400 x20(j=1,2,3,4)
解： 设：xj为第j号类型船队的队数（j = 1，2，3，4）， z 为总货运成本 则： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 ≤ 30 2x1 + 2x3 ≤ 34 4x2 + 4x3 + 4x4 ≤ 52 25x1+20x2 ＝200 40x3+20x4 ＝400 xj ≥ 0 （ j = 1,2,3,4） 线性规划问题的数学模型