第二章线性规划 线性规划在数学上比较简单,但应用面极广 1、LP干什么 问题 约束 目标 生产库存计划满足需求、资源有限 成本最小或 量最大 股票证券选择有限资金 收益最大 广告媒体选择有限预算 共知度最大 配送中心、运输「满足需求、储能有限成本最小 2、L.P的两个特征 日标+约束( constrained optimization: maximization or minimization)
Ling Xueling 第二章 线性规划 线性规划在数学上比较简单,但应用面极广 1、L.P.干什么 问题 约束 目标 生产/库存计划 满足需求、资源有限 成本最小或 产量最大 股票/证券选择 有限资金 收益最大 广告媒体选择 有限预算 共知度最大 配送中心、运输 满足需求、储能有限 成本最小 2、L.P. 的两个特征 目标 + 约束 (constrained optimization: maximization or minimization)
第一节一个最大值问题 Par公司问题提出 两种产品:中档、高档gol球袋 2、四工序:切割(C)缝制(S)装配(F)检验和包装(I&P) 3、问题:如何组织生产?中、高档产品各应计划生产多少? 调研与数据 1、生产部门一一工序、工时分析 需用工时 c D F 标准 7/10 1/2 1/10 高档 5/6 2/3 1/4 财务部门一一成本、售价分析,高档—900,中档-10.0 3、管理部门一一可用工时分析 工序 c d i& p 「可用工时 630 600 708
Ling Xueling 第一节 一个最大值问题 一、Par 公司问题提出 1、两种产品:中档、高档golf 球袋 2、四工序:切割(C)缝制(S)装配(F)检验和包装(I& P) 3、问题: 如何组织生产?中、高档产品各应计划生产多少? 二、调研与数据 1、生产部门--工序、工时分析 2、财务部门--成本、售价分析,高档-9.00,中档-10.0 3、管理部门--可用工时分析 需用工时 C & D S F I & P 标准 7/10 1/2 1 1/10 高档 1 5/6 2/3 1/4 工序 C & D S F I & P 可用工时 630 600 708 135
第一节一个最大值问题 三、问题归纳 1、假设产品全部可以销售出去 2、要求:在已有的工时约束条件下,使利润最大化的两种产品 之生产量各应是? 四、目标函数 1、建立决策变量x1,x2 2、建立o.f 3、解(任意)、可行解(满足约束)、最优解 五、(资源)约東 1、各工序可用工时约束 2、非负约束一一L.P.一般特征,可使求解大大简化
Ling Xueling 第一节 一个最大值问题 三、问题归纳 1、假设产品全部可以销售出去 2、要求:在已有的工时约束条件下,使利润最大化的两种产品 之生产量各应是? 四、目标函数 1、建立决策变量 x1 , x2 2、建立 o.f. 3、解(任意)、可行解(满足约束)、最优解 五、(资源)约束 1、各工序可用工时约束 2、非负约束--L.P. 一般特征,可使求解大大简化
第一节一个最大值问题 完整的数学表达 模型 Max Z= Max 10x, t 9x, S t 7/10x1+x2≤630 c D 1/2x1+5/6x2≤600 x1+2/3x2≤708 1/10x1+1/4x2≤135 i p x1,x2≥0 2、说明 1)因为只考虑了主要因素,模型只是现实世界的简化、近似 2)本模型之数学特征是:所有的表达式都是线性式
Ling Xueling 第一节 一个最大值问题 六、完整的数学表达 1、模型 Max Z = Max 10x1 + 9x2 s.t. 7/10x1 + x2 ≤630 ―― C & D 1/2x1 + 5/6x2 ≤600 ―― S x1 + 2/3x2 ≤708 ―― F 1/10x1 + 1/4x2 ≤135 ―― I & P x 1 , x 2 ≥ 0 2、说明 1)因为只考虑了主要因素,模型只是现实世界的简化、近似 2)本模型之数学特征是:所有的表达式都是线性式
第二节线性规划图解法 适用:仅有两个决策变量的LP问题 解点一一解的点坐标 LP.模型的几何表达 1、非负约束的表达 2、不等式约束的表达 (900,630)、(1200,700)、(708,1062)、(1350,540) 3、定义 1)可行域 2)可行解 4、of之几何表达(180,200)、(360,400)、(540.600 三、最优解几何表达及其求出(540,252 1、确定最优解触及的端点 、解联立方程得最优解坐标,即为最优解点
Ling Xueling 第二节 线性规划图解法 适用:仅有两个决策变量的 L.P. 问题 一、解点--解的点坐标 二、L.P. 模型的几何表达 1、非负约束的表达 2、不等式约束的表达 (900,630)、(1200,700)、(708,1062)、(1350,540) 3、定义 1)可行域 2)可行解 4、o.f. 之几何表达 (180,200)、(360,400)、(540,600) 三、最优解几何表达及其求出 (540,252) 1、确定最优解触及的端点 2、解联立方程得最优解坐标,即为最优解点
第二节线性规划图解法 10 2 3 4 7 10 12
Ling Xueling 第二节 线性规划图解法
第二节线性规划图解法 四、松弛变量和标准型 1、松弛变量—一能提供资源(工时)使用信息的变量 )四个约束的剩余:0 1200 2)定义( slack) LP.模型中对应“≤”约束的闲置能力称为该约束的松弛,对应 的非负变量就称为松弛变量 本例中,最优解受到第一、三约束界限,故一、三约束无松弛 2、LP模型标准型( standard form) 1)定义(除非负约束外)所有约束式都是等式的LP模型 2)意义为将线性代数引入求解多元线性规划的方法作准备 3、多余约束 不影响可行域(或:可有可无)的约束,称为多余约束 如上例中的S(第二)约東
Ling Xueling 第二节 线性规划图解法 四、松弛变量和标准型 1、松弛变量--能提供资源(工时)使用信息的变量 1)四个约束的剩余: 0 120 0 18 2)定义(slack) L.P. 模型中对应 “ ” 约束的闲置能力称为该约束的松弛,对应 的非负变量就称为松弛变量 本例中,最优解受到第一、三约束界限,故一、三约束无松弛 2、L.P. 模型标准型 (standard form) 1)定义 (除非负约束外)所有约束式都是等式的 L.P. 模型 2)意义 为将线性代数引入求解多元线性规划的方法作准备 3、多余约束 不影响可行域(或:可有可无)的约束,称为多余约束 如上例中的 S(第二)约束
第二节线性规划图解法 五、端点与最优解 1、当z=5x1+9x2时,最优解也是端点:(300,420 2、定理 若可行域有界,则LP.问题最优解总在可行域端点处 、定理的意义(单形法的依据)—一提供了求解 LP.问题的一般思路(迭代方法): 将一般LP模型化成标准型 利用初等变换求解约束之线性方程组:得到解交点 将解代入目标函数,比较它们的大小 (通过迭代)直至求得最优的解
Ling Xueling 第二节 线性规划图解法 五、端点与最优解 1、当 z = 5x1+9x2 时,最优解也是端点:(300,420) 2、定理 若可行域有界,则 L.P. 问题最优解总在可行域端点处 3、定理的意义(单形法的依据)--提供了求解 L.P. 问题的一般思路(迭代方法) : • 将一般 L.P. 模型化成标准型 • 利用初等变换求解约束之线性方程组:得到解交点 • 将解代入目标函数,比较它们的大小 • (通过迭代)直至求得最优的解
第三节线性规划图解法:最小值例子 问题及其数学模型 1、有关数据 两种产品:A或B 两种成本:2或3/每单位 两种所需工时:2或1/每单位 2、有关约束 1)为了追求规模效应,生产总数不得少于350单位 2)销售部门报告:A产品已经获得125单位的订货 3)共有600可用工时 3、问题:最小成本时两种产品的生产量? (课堂练习建立模型)
Ling Xueling 第三节 线性规划图解法:最小值例子 一、问题及其数学模型 1、有关数据 两种产品:A 或 B 两种成本:2 或 3 / 每单位 两种所需工时:2 或 1 / 每单位 2、有关约束 1)为了追求规模效应,生产总数不得少于 350 单位 2)销售部门报告:A 产品已经获得 125 单位的订货 3)共有 600 可用工时 3、问题:最小成本时两种产品的生产量? (课堂练习建立模型)
第三节线性规划图解法:最小值例子 问题及其数学模型 4、数学模型 min z=min 2X1+ 3x2 X1+x2≥350 125 2x1+x2≤600 ≥0
Ling Xueling 第三节 线性规划图解法:最小值例子 一、问题及其数学模型 4、数学模型 min z = min 2x1 + 3x2 s.t. x1 + x2 350 x1 125 2x1 + x2 600 x1 , x2 0