管理运筹学课件第2章线性规划

《管理运筹学课件第2章线性规划》由会员分享，可在线阅读，更多相关《管理运筹学课件第2章线性规划（28页珍藏版）》请在装配图网上搜索。

1、第 2章 线性规划 课件 2 2021/4/11 教学目标与要求 【 教学目标 】 通过对本章的学习，理解线性规划的含义、解、可行解、可行域、基 解、基可行解、最优解的定义；掌握图解法、单纯形法（包括大 M 法）；会建立线性规划数学模型；至少掌握一种软件求解 LP 【 知识结构 】 图解法（ 2 个变量） LP 基本概念与实际问题建模 单纯形法（无人工变量） 大 M 法（有人工变量） 计算机解法（ L i n go , W i n Q S B 或 E xce l ） 理 论 解 法 知 识 目 标 技 能 目 标 课件 3 2021/4/11 导入案例 最优生产计划 课件 4 2021/4/1

2、1 本章主要内容 2.1 线性规划问题与模型 2.1.1 线性规划问题的提出 2.1.2 线性规划的数学模型 2.1.3 线性规划标准模型 2.2 图解法 2.2.1 线性规划几何解的有关概念 2.2.2 图解法基本步骤 2.2.3 线性规划几何解的讨论 2.3 单纯形法 2.3.1 线性规划解的有关概念及性质 2.3.2 单纯形法 2.4 人工变量法 2.5 线性规划应用举例 案例 2-1 媒体选择问题 案例 2-2 投资计划问题 案例 2-3 自制 /外购决策问题 案例 2-4 合理下料问题 本章小结 课件 5 2021/4/11 2.1.1 线性规划问题的提出 产品甲 产品乙 生产能力

3、设备 A 设备 B 2 1 1 1 10 8 单位利润 3 2 承导入案例 设两种产品产量为 x1,x2,则有 : 12 12 12 12 m a x 3 2 2 1 0 . . 8 ,0 z x x xx s t x x xx 总利润表达式 最大化 设备 A台时占用 设备 B台时占用 生产能力 ,不 允许超过 产量非负 决策变量 （ decision variable） 目标函数 （ objective function） 约束条件 （ subject to） 三要素 当目标函数与约束条件均为决策变 量的线性函数，且变量取连续值时， 称为线性规划 LP；变量取整称为整 数线性规划 ILP；变

4、量取二进制为 0-1规划 BLP。 课件 6 2021/4/11 2.1.2 线性规划的数学模型 【 例 2.1】 （合理配料问题）由下表建立一个 LP模型求解满足动物成长 需要又使成本最低的饲料配方。 1 2 3 4 50 . 5 0 2 . 0 0 3 . 0 0 1 . 5 0 0 . 8 0 8 5x x x x x 1 2 3 4 50 . 1 0 0 . 0 6 0 . 0 4 0 . 1 5 0 . 2 0 5x x x x x 1 2 3 4 50 . 0 8 0 . 7 0 0 . 3 5 0 . 2 5 0 . 0 2 1 8x x x x x 0( 1 , 2 , 3 ,

5、 4 , 5 )jxj 1 2 3 4 5m i n 2 6 5 4 3z x x x x x 饲料 营养甲 (g/kg) 营养乙 (g/kg) 营养丙 (g/kg) 成本 (g/kg) 1 0.5 0.1 0.08 2 2 2 0.06 0.7 6 3 3 0.04 0.35 5 4 1.5 0.15 0.25 4 5 0.8 0.2 0.02 3 解 设 xi为第 i种饲料的用量，有： 满足营养甲需求 满足营养乙需求 满足营养丙需求 变量非负限制 目标是总成本最低 .st 课件 7 2021/4/11 2.1.2 线性规划的数学模型 线性规划的一般形式： 1 1 2 2 11 1 12 2

6、 1 1 21 1 22 2 2 2 1 1 2 2 m a x( m in ) ( ( . ( nn nn nn m m m n n m z c x c x c x a x a x a x b a x a x a x b st a x a x a x b 或 ， ） 或 ， ） 或 ， ） 1 1 () ( ( 1 , 2 , , ) . 0( 1 , 2 , , ) n jj j n ij j i j j M ax M i n Z c x a x b i m st x j n 或 ， ） 1 1 () ( . 0( 1 , 2 , , ) n jj j n jj j j M ax M i

7、n Z c x p x b st x j n 或 ， ） () ( . 0 M ax M in Z C X A X b st X 或 ， ） 线性规划的集合形式 ： 线性规划的向量形式 ： 线性规划的矩阵形式 ： 课件 8 2021/4/11 2.1.3 线性规划的标准模型 标准形式 : 目标函数最大化、约束条件为等式、决策变量均非负、右端项非负 . 非标准形式进行如下转化 : 课件 9 2021/4/11 2.1.3 线性规划的标准模型 【例 2.2】将 LP模型转化为标准式 1 2 3 12 1 2 3 1 2 3 1 2 3 m in 3 5 9 2 3 4 . 3 2 6 0 , 0

8、, z x x x xx x x x st x x x x x x 无 约 束 11 3 3 3 3 3 : , 0 , 0 , 0 x x x x x x x x 令 1 2 3 3 12 1 2 3 3 1 2 3 3 1 2 3 3 m in 3 5 9 2 3 3 4 . 3 2 6 0 , 0 , 0 , 0 z x x x x xx x x x x st x x x x x x x x 1 2 3 3m i n m a x ( ) 3 5z z x x x x 1 2 3 33 2 6x x x x 1 2 3 3 1 2 4 1 2 3 3 5 1 2 3 3 6 1 2 3 3

9、 4 5 6 ( ) 3 5 9 2 3 3 4 . 3 2 6 , , , , , , 0 M a x Z x x x x x x x x x x x x st x x x x x x x x x x x x 解 （ 1）决策变量变为非负 （ 2）目标函数最大化 （ 3）右端项变为非负 （ 4）约束一、三添加松弛变量； 约束二减剩余变量。 课件 10 2021/4/11 2.2.1 线性规划几何解的有关概念 课件 11 2021/4/11 可行域 2.2.2 图解法基本步骤 建立直角坐标系； 图示约束条件，确定右行域； 图示目标函数一根基线，按目 标要求平行移动，与可行域相 切，切点即为最优

10、解； 求出切点坐标，并代入目标函 数求得最优值。 12 12 12 12 m a x 3 2 2 1 0 8. ,0 z x x xx xxst xx 【例 2.3】 用图解法求 LP最优解 o x1 x2 2x1+x2=10 x1+x2=8 令 3x1+2x2=12 10 5 8 8 6 4 (2,6) z=3 2+2 6=18 最优解： x1=2,x2=6 最优值： z=18 课件 12 2021/4/11 2.2.3 线性规划几何解的讨论 线性规划几何解存在四种情况：唯一最优解、无穷 多最优解、无界解、无可行解。 可行域为封闭有界区域时，可能存在唯一最优解， 无穷多最优解两种情况； 可行

11、域为非封闭无界区域时，可能存在唯一最优解， 无穷多最优解，无界解三种情况； 可行域为空集时，没有可行解，原问题没有最优解。 若线性规划存在最优解，则最优解或最优解之一肯 定能够在可行域（凸集）的某个极点找到（所谓凸 集是指集合中任何两点的连线上的点仍在集合中）。 课件 13 2021/4/11 2.3.1 线性规划解的有关概念及性质 1 2 3 4 1 2 3 1 2 4 12 m a x 3 2 0 0 2 10 8. ,0 z x x x x x x x x x xst xx = = 承导入案例 LP模型： 31 2 4 m a x 3 , 2 0 , 0 xxz x x 或 : 1 2

12、0 0 x x 若 1 3 4 1 0 1 0 0 1 8 x x 有 1 2 3 4 1 2 3 4 m a x 3 , 2 , 0 , 0 2 1 1 0 10 1 1 0 1 8 x x z x x x x x x A C X b m a x z C X A X b m a x N N B B NB z C X C X NX B X b CN CB 31 2 4 2 1 1 0 1 0 1 1 0 1 8 xx x x XN XB N B b 0 , 0NBX若 取 1BX B b则 基 基变量 非基 非基变量 B-1b基解 ;若满足 XB0,称基 可行解 . 课件 14 2021/4/

13、11 2.3.2 单纯形法 一般而言， B为 A中任一 m m阶 使 XB非负、 XN为 0的可逆矩阵，由： m a x . ,0 B B N N BN BN z C X C X B X NX b st XX 11 . ,0BN BN X B b B N Xst XX 11()B N B Nz C B b C C B N X 约束条件两端左乘 B-1得基变量的 非基变量表达： 代入目标函数，得： 常数 考察该项 1N N BC C B N 令 : 可见目标函数为非基变量的线性 函数。 当 N所有元素非正时，目标函数 值达到最大，得到了最优解。因 为任何一个非基变量入基后，不 会使目标函数值增大

14、。 若 N某元素（假设第 k个元素） 0， 则该非基变量入基，会使目标函 数值增大。 N中若有多个元素 0， 选择其中最大的（假设第 k个元素） 非基变量 xk入基，会使目标函数值 增加的更快，于是确定 xk为入基变 量， N称为检验数。 1: B N Nz C B b X则 课件 15 2021/4/11 2.3.2 单纯形法 由于基变量为 m个，有一个入基， 必然有一个出基，哪个出基呢？在 确定初始基时，选择 B为单位矩阵， 则下式 11 . ,0BN BN X B b B N Xst XX 可简化为： 即： xk入基 ,其余仍为 0，故有 . ,0BN BN X b N Xst XX 0

15、Nb N X 11 22 0 0 0 kk kk m m k k b a x b a x b a x 11 22 / / / kk kk k m m k x b a x b a x b a 12 12 m i n , , , mk k k m k bbbx a a a 即 m i n 0 ( 1 , 2 , , )ilik ik lk bba i m aa 令 当 xk的值由 0增加到 时，原来的基变 量 xl取值首先变成零，选择其为出基变 量。称 的表达式为最小比值原则。 如果所有 aik 0, xk的值可以由 0增加到 无穷，表示可行域是不封闭的，且目 标函数值随进基变量的增加可以无限 增

16、加，此时不存在有限最优解。 下面对以上讨论进行总结 . 课件 16 2021/4/11 2.3.2 单纯形法 单纯形法解题步骤 : 1. 使 LP模型右端项非负、约束符取“ =”、目标函数 max（即标准化）， 并设法在约束系数中构造一个单位矩阵 ,令其为初始基 ,该基必为可行 基，右端项即为基可行解。 2. 求检验数 .若所有检验数均不大于 0，找到最优解，计算结束；若存在 大于 0的检验数，找出最大者 k ，对应的变量 xk为入基变量。 3. 若 alk均不大于 0，则解无界，计算结束，否则找出最小比值： 对应的变量 xl为出基变量。 4. 用入基变量替换出基变量，并通过行初等变换将基变成

17、单位矩阵，右 端项即为基可行解，转第 2步。 m in 0 ( 1 , 2 , , )ilik ik lk bba i m aa 课件 17 2021/4/11 2.3.2 单纯形法 m a x k 0 存在 a ik 0 求得检验数 j 最优解 所有 j 0 某 k 0 所有 a ik 0 解无界 列出新的单 纯形表 En d LP 模型标准化 列出初始单纯形表 课件 18 2021/4/11 2.3.2 单纯形法 12 12 12 12 m a x 3 2 2 1 0 8. ,0 z x x xx xxst xx 例：承导入案例 x1 x2 x3 x4 基 cj 3 2 0 0 b x3

18、x4 0 0 2 1 1 1 1 0 0 1 10 8 cj-zj B 1 2 2 3 1 2 3 1 2 4 m a x 3 2 0 0 2 1 0 8. 0 ( 1 , 2 , 3 , 4 )j z x x x x x x x x x xst xj 标准化 TBX BX NX BCNC TBC N 基可行解 1N N BC C B N 213 2 0 0 3 211 3 2 10/2=5 8/1=8 课件 19 2021/4/11 2.3.2 单纯形法 x1 x2 x3 x4 基 cj 3 2 0 0 b x3 x4 0 0 2 1 1 1 1 0 0 1 10 8 5 8 cj-zj 3

19、 2 0 x1 x2 x3 x4 基 cj 3 2 0 0 b x1 x4 3 0 1 0 1/2 1/2 1/2 -1/2 0 1 5 3 10 6 cj-zj 1/2 -3/2 15 将入基变量替换出基变量，列出新的单纯形表，并通过初等变 换将新基变成单元阵： x1 x2 x3 x4 基 cj 3 2 0 0 b x1 x2 3 2 1 0 0 1 1 -1 -1 2 2 6 cj-zj -1 -1 18 最优解 最优值 课件 20 2021/4/11 2.4 工人变量法 用单纯形法求解 LP要求能找出一个单位阵作为初始基。因此， 当约束符均为“ ”时，把松弛变量作为初始基变量，则可直 接

20、列出单纯形表；若存在约束符为“ ”或“ =”，则不一定能 找出一个单位阵，这种情况通常要添加人工变量（ artificial variable），将所有松弛变量和人工变量作为初始基变量，则 可列出单纯形表。但原本约束已经取“ =”，因此，必须使人工 变量为 0才是可行解。故在迭代过程中如果最终单纯形表中含 有人工变量，则该 LP无可行解。采取的办法是设目标函数中人 工变量的系数为“ -M”（ M为任意大的有界正数），如果最终 单纯形表中含有人工变量，则目标函数不会实现最大化。这种 通过添加人工变量来找初始基的方法称为人工变量法。求解具 有人工变量的 LP，通常用“两阶段法”或“大 M法”来解决

21、。 下面通过例 2.3为例，说明“大 M法”的应用。 课件 21 2021/4/11 2.4 工人变量法 【例 2.4】求解 LP问题 12 12 12 12 m a x 3 2 2 1 0 8. ,0 z x x xx xxst xx = 1 2 3 12 1 2 3 1 3 m a x 3 2 0 2 10 . . 8 0 z x x x xx s t x x x x 1 2 3 4 1 2 4 1 2 3 1 4 m a x 3 2 2 1 0 . . 8 0 z x x x M x x x x s t x x x x + 0 - = += 标准化 添加人工变量 X1 X2 X3 X4

22、基 cj 3 2 0 -M B-1b 比值 X4 X3 -M 0 2 1 1 1 0 1 1 0 10 8 5 8 j=cj-zj 3 2 *M 2 1 X1 X2 X3 X4 基 cj 3 2 0 -M B-1b 比值 X1 X2 3 2 1 0 0 1 -1 1 1 -1 2 6 j=cj-zj -1 -1 18 *M -1 基 - 比值 X3 0 1/2 1/2 0 1/2 -1/2 5 3 5 8 j=cj-zj 1/2 -3/2 - 课件 22 2021/4/11 2.5 应用举例 课件 23 2021/4/11 案例 2-1 广告媒体选择 2400000 10 2 300000 1

23、80000 max jx设 各 媒 体 选 择 数 量 1 2 3 4 5m a x 6 5 9 0 3 0 4 0 2 0z x x x x x 目标函数 1 2 3 4 51 5 0 0 0 2 0 0 0 0 4 0 0 0 0 1 2 0 0 0 1 0 0 0 0 2 4 0 0 0 0 0 x x x x x 可达消费者人数 1 2 3 4 51 5 0 0 4 0 0 0 2 0 0 0 4 5 0 6 0 0 3 0 0 0 0 0 x x x x x 总费用限制 121 5 0 0 4 0 0 0 1 8 0 0 0 0 xx 电视广告费限制 1 2 1 2 3 4 51 0

24、 , 1 5 , 2 1 0 , 4 0 , 2 0 , 2 0 , 0jx x x x x x x x .st 设 各 媒 体 选 择 数 量 课件 24 2021/4/11 案例 2-2 公司投资计划 A、 B、 C、 D四个产品项目投资 6000万元。 产品项目 A: 15年每年年初投资， 当年年末收回本利 110%。 产品项目 B： 14年每年年初投资 ，次年年末收回本利 125%。 产品项目 C：第 3年年初 投资 ，第 5年年末收回本利 140%。 产品项目 D：第 2年年初进行，第 5年年末收回本利 155%。 每年投资额限制： 项目 B900万元，项目 C2400万元，项目 D

25、3000万元。 在满足各个投资项目的限制条件下，使企业在五年内获得最大的收益。 课件 25 2021/4/11 案例 2-2 公司投资计划 51 42 33 24 11 12 11 21 22 24 31 32 33 21 12 41 42 31 22 51 41 32 2 33 24 1 2 33 24 m a x 1. 1 1. 25 1. 4 1. 55 6000 1. 1 0 1. 1 1. 25 0 . . 1. 1 1. 25 0 1. 1 1. 25 0 90 0( 1 , 2 , 3 , 4) ; 24 00 ; 30 00 , , , 0( 1 i ij z x x x x

26、xx x x x x x x x x x s t x x x x x x x x i x x x x x x i , 2 , 3 , 4 , 5 ; 1 , 2 , 3 , 4)j 课件 26 2021/4/11 案例 2-3 自制 /外购计划 设 x1,x2,x3自制甲 ,乙 ,丙数量 ;x4,x5外购甲 ,乙数量 单位利润： 自制甲： 23-(3+2+3)=15 自制乙： 18-(5+1+2)=10 自制丙： 16-(4+3+2)=7 外购甲： 23-(5+2+3)=13 外购乙： 18-(6+1+2)=9 1 2 3 4 5m a x 1 5 1 0 7 1 3 9z x x x x x

27、 工时 产品甲 产品乙 产品丙 生产能力（小时） 铸造工时（小时 / 件） 5 10 7 800 0 机加工工时（小时 / 件） 6 4 8 1 2 0 0 0 装配（小时 / 件） 3 2 2 1 0 0 0 0 1 2 5 1 2 3 4 5 1 2 3 4 5 5 10 7 800 0 6 4 8 6 4 120 00 . 3 2 2 3 2 100 00 0 ( 1 , 2 , ., 5 )j x x x x x x x x st x x x x x xj 最优方案： 自制甲 1600，外购丙 600，总利润 29400 课件 27 2021/4/11 案例 2-4 合理下料问题 7.

28、4米条材 ,截 2.9,2.1,1.5米 100套 ,如何下料所用钢材最省 ? 1 2 3 4 5 6 7 8 1 2 3 4 2 3 5 6 7 1 3 4 6 7 8 m in 2 100 2 3 2 100 . 3 2 3 4 100 0 ( 1 , 2 , , 8 )j z x x x x x x x x x x x x x x x x x st x x x x x x xj 且 为 整 数 优化结果：第 1种方式截取 10根，第 2种方式截取 50根， 第 4种方式截取 30根，各种 规格圆钢正好 100根。 课件 28 2021/4/11 本章小结 本章主要内容包括线性规划问题 ，

29、 线性规划模型的特性与结构；线性 规划模型的图解法和单纯形法；注重于利用应用案例的分析实现对实 际系统进行描述与建模 ， 并运用计算机求解 。 线性规划问题是指可以建构线性规划模型的一类实际问题 。 许多实际 经济管理问题可以归为线性规划问题 ， 通过线性规划模型实现资源的 优化配置 。 线性规划模型具有如下特点：决策变量表示要寻求的方案 ， 每一组值 就是一个方案；约束条件是用等式或不等式表示的限制条件；一定有 一个最优的目标 ， 最大或最小；所有函数都是线性的 。 线性规划模型具有一般表达式的结构 。 为了便于线性规划模型的求解 ， 将模型一般表达式转化为标准形式 。 线性规划模型的求解方法包括几何学的图解法和代数学的单纯形法 。 要求熟练掌握 . 建立线性规划模型是线性规划的关键 ， 利用经济管理中的媒体选择问 题 、 投资计划问题 、 自制与外购问题 、 合理下料问题详细阐述了线性 规划模型的建立 ， 计算机求解和解的分析 。