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

1、第2章 线性规划,课件,2,2020/9/7,教学目标与要求,【教学目标】 通过对本章的学习，理解线性规划的含义、解、可行解、可行域、基解、基可行解、最优解的定义；掌握图解法、单纯形法（包括大M法）；会建立线性规划数学模型；至少掌握一种软件求解LP 【知识结构】,课件,3,2020/9/7,导入案例最优生产计划,课件,4,2020/9/7,本章主要内容,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、 单纯形法 2.3.1 线性规划解的有关概念及性质 2.3.2 单纯形法 2.4 人工变量法 2.5 线性规划应用举例 案例2-1 媒体选择问题 案例2-2 投资计划问题 案例2-3 自制/外购决策问题 案例2-4 合理下料问题 本章小结,课件,5,2020/9/7,2.1.1 线性规划问题的提出,承导入案例,设两种产品产量为x1,x2,则有:,决策变量（decision variable）,目标函数（objective function）,约束条件（subject to）,当目标函数与约束条件均为决策变量的线性函数，且变量取连续值时，称为线性规划LP；变量取整称为整数线性规划ILP；变量取二

3、进制为0-1规划BLP。,课件,6,2020/9/7,2.1.2 线性规划的数学模型,【例2.1】（合理配料问题）由下表建立一个LP模型求解满足动物成长需要又使成本最低的饲料配方。,解 设xi为第i种饲料的用量，有：,满足营养甲需求,满足营养乙需求,满足营养丙需求,变量非负限制,目标是总成本最低,课件,7,2020/9/7,2.1.2 线性规划的数学模型,线性规划的一般形式：,线性规划的集合形式 ：,线性规划的向量形式 ：,线性规划的矩阵形式 ：,课件,8,2020/9/7,2.1.3 线性规划的标准模型,标准形式: 目标函数最大化、约束条件为等式、决策变量均非负、右端项非负. 非标准形式进行

4、如下转化:,课件,9,2020/9/7,2.1.3 线性规划的标准模型,【例2.2】将LP模型转化为标准式,解 （1）决策变量变为非负,（2）目标函数最大化,（3）右端项变为非负,（4）约束一、三添加松弛变量；约束二减剩余变量。,课件,10,2020/9/7,2.2.1 线性规划几何解的有关概念,课件,11,2020/9/7,2.2.2 图解法基本步骤,建立直角坐标系； 图示约束条件，确定右行域； 图示目标函数一根基线，按目标要求平行移动，与可行域相切，切点即为最优解； 求出切点坐标，并代入目标函数求得最优值。,【例2.3】用图解法求LP最优解,2x1+x2=10,x1+x2=8,令3x1+2

5、x2=12,10,5,8,8,6,4,(2,6),z=32+26=18,最优解：x1=2,x2=6 最优值：z=18,课件,12,2020/9/7,2.2.3 线性规划几何解的讨论,线性规划几何解存在四种情况：唯一最优解、无穷多最优解、无界解、无可行解。可行域为封闭有界区域时，可能存在唯一最优解，无穷多最优解两种情况；可行域为非封闭无界区域时，可能存在唯一最优解，无穷多最优解，无界解三种情况；可行域为空集时，没有可行解，原问题没有最优解。 若线性规划存在最优解，则最优解或最优解之一肯定能够在可行域（凸集）的某个极点找到（所谓凸集是指集合中任何两点的连线上的点仍在集合中）。,课件,13,2020

6、/9/7,2.3.1 线性规划解的有关概念及性质,承导入案例LP模型：,CN,CB,XN,XB,N,B,b,课件,14,2020/9/7,2.3.2 单纯形法,一般而言，B为A中任一mm阶使XB非负、XN为0的可逆矩阵，由：,约束条件两端左乘B-1得基变量的非基变量表达：,代入目标函数，得：,常数,考察该项,可见目标函数为非基变量的线性函数。 当N所有元素非正时，目标函数值达到最大，得到了最优解。因为任何一个非基变量入基后，不会使目标函数值增大。 若N某元素（假设第k个元素）0，则该非基变量入基，会使目标函数值增大。N中若有多个元素0，选择其中最大的（假设第k个元素）非基变量xk入基，会使目标

7、函数值增加的更快，于是确定xk为入基变量， N称为检验数。,课件,15,2020/9/7,2.3.2 单纯形法,由于基变量为m个，有一个入基，必然有一个出基，哪个出基呢？在确定初始基时，选择B为单位矩阵，则下式,可简化为：,即：,xk入基,其余仍为0，故有,当xk的值由0增加到时，原来的基变量xl取值首先变成零，选择其为出基变量。称的表达式为最小比值原则。 如果所有aik 0, xk的值可以由0增加到无穷，表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时不存在有限最优解。 下面对以上讨论进行总结.,课件,16,2020/9/7,2.3.2 单纯形法,单纯形法解题步骤: 使L

8、P模型右端项非负、约束符取“=”、目标函数max（即标准化），并设法在约束系数中构造一个单位矩阵,令其为初始基,该基必为可行基，右端项即为基可行解。 求检验数.若所有检验数均不大于0，找到最优解，计算结束；若存在大于0的检验数，找出最大者k ，对应的变量xk为入基变量。 若alk均不大于0，则解无界，计算结束，否则找出最小比值：对应的变量xl为出基变量。 用入基变量替换出基变量，并通过行初等变换将基变成单位矩阵，右端项即为基可行解，转第2步。,课件,17,2020/9/7,2.3.2 单纯形法,课件,18,2020/9/7,2.3.2 单纯形法,例：承导入案例,标准化,3,2,10/2=5,8

9、/1=8, ,课件,19,2020/9/7,2.3.2 单纯形法,将入基变量替换出基变量，列出新的单纯形表，并通过初等变换将新基变成单元阵：,最优值,课件,20,2020/9/7,2.4 工人变量法,用单纯形法求解LP要求能找出一个单位阵作为初始基。因此，当约束符均为“”时，把松弛变量作为初始基变量，则可直接列出单纯形表；若存在约束符为“”或“=”，则不一定能找出一个单位阵，这种情况通常要添加人工变量（artificial variable），将所有松弛变量和人工变量作为初始基变量，则可列出单纯形表。但原本约束已经取“=”，因此，必须使人工变量为0才是可行解。故在迭代过程中如果最终单纯形表中含

10、有人工变量，则该LP无可行解。采取的办法是设目标函数中人工变量的系数为“-M”（M为任意大的有界正数），如果最终单纯形表中含有人工变量，则目标函数不会实现最大化。这种通过添加人工变量来找初始基的方法称为人工变量法。求解具有人工变量的LP，通常用“两阶段法”或“大M法”来解决。下面通过例2.3为例，说明“大M法”的应用。,课件,21,2020/9/7,2.4 工人变量法,【例2.4】求解LP问题,标准化,添加人工变量,课件,22,2020/9/7,2.5 应用举例,课件,23,2020/9/7,案例2-1 广告媒体选择,2400000,300000,max,目标函数,可达消费者人数,总费用限制,

11、电视广告费限制,课件,24,2020/9/7,案例2-2 公司投资计划,A、B、C、D四个产品项目投资6000万元。 产品项目A: 15年每年年初投资，当年年末收回本利110%。 产品项目B：14年每年年初投资，次年年末收回本利125%。 产品项目C：第3年年初投资，第5年年末收回本利140%。 产品项目D：第2年年初进行，第5年年末收回本利155%。 每年投资额限制：项目B900万元，项目C2400万元，项目D3000万元。 在满足各个投资项目的限制条件下，使企业在五年内获得最大的收益。,课件,25,2020/9/7,案例2-2 公司投资计划,课件,26,2020/9/7,案例2-3 自制/

12、外购计划,设 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,最优方案： 自制甲1600，外购丙600，总利润29400,课件,27,2020/9/7,案例2-4 合理下料问题,7.4米条材,截2.9,2.1,1.5米100套,如何下料所用钢材最省?,优化结果：第1种方式截取10根，第2种方式截取50根，第4种方式截取30根，各种规格圆钢正好100根。,课件,28,2020/9/7,本章小结,本章主要内容包括线性规划问题，线性规划模型的特性与结构；线性规划模型的图解法和单纯形法；注重于利用应用案例的分析实现对实际系统进行描述与建模，并运用计算机求解。 线性规划问题是指可以建构线性规划模型的一类实际问题。许多实际经济管理问题可以归为线性规划问题，通过线性规划模型实现资源的优化配置。 线性规划模型具有如下特点：决策变量表示要寻求的方案，每一组值就是一个方案；约束条件是用等式或不等式表示的