第二章线性规划 线性规划在数学上比较简单,但应用面极广 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/10x１ ＋ x２ ≤630 ―― C & D 1/2x１ ＋ 5/6x２ ≤600 ―― S x１ ＋ 2/3x２ ≤708 ―― F 1/10x１ ＋ 1/4x２ ≤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