《第一章线性规划——《运筹学》教案》由会员分享，可在线阅读，更多相关《第一章线性规划——《运筹学》教案（129页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性规划LP,运筹学教案,线性规划教学大纲,基本要求： 1、了解根据经济问题列出LP数学模型； 2、熟练掌握SLP； 3、熟练掌握图解法； 4、熟练掌握基、基可行解及相关概念； 5、熟练掌握单纯形表的计算，掌握其原理； 6、掌握大M法、两阶段法； 重点：1、图解法；2、基；3、单纯形法 难点：1、基；2、单纯形法,第一讲：绪论、LP问题 的数学模型与图解法,一、LP问题的数学模型,例1：有A、B两种产品，每Kg可获利700元和1200元，其它资料如下：,问A、B各生产多少，可在资源限额内获得最大利润？,例1：数学模型,设：A、B产量分别为x1、x2 受资源的约束： 约束条件 s.t 1
2、： 9x1+ 4x2 360 用煤限制 约束条件 s.t 2： 4x1+ 5x2 200 用电限制 约束条件 s.t 3： 3x1+10x2 300 用水限制x1， x2 0数学模型的一般形式 求利润最大化： 目标函数Opt：Max Z = 7x1 +12x2利润总额最大,例1：数学模型,LP问题数学模型的三要素 变量： x1，x2 目标函数：Opt：Max Z，MinW 约束条件：s.t.,求解的误区,2、用“”求解用“”求解的结果，是把所有资源都用完，一般情况下不是最优解，而是劳命伤财的方法。,1、先尽资源能力生产利润大的产品其结果是把某一种资源消耗完毕，一般不是最优解，而会造成其余资源的
3、大量浪费。,二、LP问题求解图解法,B,3x1+10x2=300,x1,x2,9x1+4x2 = 360,4x1+5x2=200,等值线 7x1 +12x2C,图解法只能求解二维LP问题，有助于建立LP的几何概念，启发单纯形法思路。,例2：家电问题（课堂练习）,例2：某公司计划制造I，II两种家电产品，条件如下表,问该公司应制造两种家电各多少件，使利润最大,例2：数学模型,设：生产I，II家电数量分别为：x1、x2件约束条件 s.t 1： 5x2 15设备A的能力限制 约束条件 s.t 2：6x1 + 2x2 24设备B的能力限制 约束条件 s.t 3： x1 + x2 5 调试工序能力限制x
4、1， x2 0数学模型的一般形式目标函数Opt：Max Z = 2x1 +x2利润总额最大,例2：数学模型,设：生产I，II家电数量分别为：x1、x2件目标函数Opt：Max Z = 2x1 +x25x2 15 约束条件 s.t 6x1 + 2x2 24x1 + x2 5 x1， x2 0,例2：图解法,B,5x215,x1,x2,6x1 + 2x2 24,x1+x25,2x1 +x2C,Max Z = 2x1 +x25x2 15s.t 6x1 + 2x2 24x1 + x2 5x1， x2 0,作业,1、试举一个你所遇到过的运筹学问题的例子 2、习题册：1.2题,第二讲：LP问题的标准型SL
5、P 及基的相关概念,例3：污水处理厂问题,问：在环保要求下，两厂分别处理多少污水，使总费用最小？,（1）A厂产生2万m3天污水，B厂产生1.4万m3天污水； （2）污水从A厂流到B厂时，有20%能自然净化； （3）按环保要求，河流中工业污水含量应不大于0.2%； （4）A厂处理费900元万m3，B厂1000元万m3。,例3：数学模型,设：A厂处理污水x1万m3天，B厂处理x2万m3天,A厂的环保约束：（2x1 ）500 0.2%,各厂每天处理污水量不会超过污水排放总量：x1 2 ；x2 1.4（2x1）0.8,此外： x1 ，x2 0,目标函数Opt：Min Z = 900x1 +1000x2
6、,例3：数学模型,设：A厂处理污水x1万m3天，B厂处理x2万m3天目标函数Opt： Min Z = 900x1 +1000x2 x1 1 约束条件 s.t 0.8x1+x2 1.6 x1 20.8x1 + x2 3 x1， x2 0,说明：虽然x1 已确定了x10，但作为一般形式， 非负约束条件仍予以保留,例3：图解法,900x1 +1000x2 C,B,小结：线性规划的数学模型,线性规划数学模型的组成： 1、决策变量：问题中要确定的未知量 2、目标函数：实际问题所要达到的目标，表达为决策变量的函数 3、约束方程：决策变量客观上必须满足的约束线性规划的条件；决策变量的取值是连续的；目标函数是
7、线性函数；约束方程是线性等式或不等式。,1、一般形式,LP问题的数学模型的表示,其中，xj决策变量；aij技术系数； aij 系数矩阵cj价值系数；bi资源系数或右端向量；,2、紧缩形式：,（ 0，自由）,i约束方程，共m个 j变量个数，共n个,3、矩阵形式,（ 0，自由）,4、向量矩阵形式,小结：线性规划的图解法,例Max Z=x1+3x2 s.t. x1+ x26-x1+2x28x1 0, x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,小结：解的可能性,2、无界解,4、无可行解,1、唯一最优解,3、多重最优解,小结：几个基本概念,可行解：满足所有约束条件（包括
8、变量）的解；,可行域：可行解的集合称为可行域；,最优解：使目标函数达到极值的解 （理应属于可行域）。,两个几何概念,凸集：设K是n维欧氏空间的一个点集，若任意两点X(1)K，X(2)K的连线上的一切点X= X(1)+(1-)X(2)，（01），有XK，则称K是一个凸集。（集合中任意两点连线上的点都属于该集合。） 顶点：设K是凸集，XK；若X不能用不同的两点X(1) K，X(2) K（X(1)X(2)）线性表示，即对任意01，X X(1)+(1)X(2)，则称X为K的一个顶点（或极点）。,LP解的性质,定理1：线性规划的可行域是凸集定理2：若线性规划问题有唯一最优解，则该最优解 一定在可行域（凸
9、集）的顶点上,三、LP的标准型（SLP）,满足以下所有条件的LP问题称为SLP：,1、目标函数为Max型； 2、所有约束均为“=”型； 3、任意xj 0； 4、各约束右端向量非负，即bj 0。,三、LP的标准型（SLP）,1.目标函数为Max型,续例3：Opt： Min Z = 900x1 +1000x2,对Opt为Min的情形，即Min ZCX， 则令Z Z，于是得 Max Z CX,化为：MaxZ900x11000x2,满足以下所有条件的LP问题称为SLP：,三、LP的标准型（SLP）,2.所有约束条件为“”型,“”在s.t左端加上一个非负变量xn+10，称“松驰变量” “”在s.t左端减
10、去一个非负变量xn+10，称“剩余变量” 一般统称：“松驰变量”,三、LP的标准型（SLP）,3.各约束条件右端向量非负，即bj 0,如果右端bj 0，则两端同（1）,如： x1 x3 = 1 化为： x1 + x3 = 1,三、LP的标准型（SLP）,4.任意变量xj 0,1). 如果xj 0，则令xjxj，代入s.t及Opt；,2). 如果LP中存在无约束的变量（自由变量）xk，即xk取正值或取负值均可 令xk=xkxk，其中xk0，xk 0，代入s.t及Opt,续例1：将LP问题化为SLP,目标函数Opt：Max Z = 7x1 +12x29x1+ 4x2 360 约束条件 s.t 4x
11、1+ 5x2 200 3x1+10x2 300 x1， x2 0,目标函数Opt：Max Z = 7x1 +12x2 约束条件 s.t 9x1+ 4x2 + x3 360 4x1+ 5x2 + x4 200 3x1+10x2 + x5 300 x1， x2， x3， x4， x5 0,SLP: Opt： Max Z = 900x1 1000x2 x1 x3 = 1 0.8x1+ x2 x4 = 1.6 st x1 + x5 = 20.8x1 + x2 + x6 =3x1，x2，x3，x4，x5，x6 0,续例3：将LP问题化为SLP,目标函数Opt： Min Z = 900x1 +1000x2
12、 x1 1 约束条件 s.t 0.8x1+x2 1.6 x1 20.8x1 + x2 3 x1， x2 0,例：写出SLP（课堂练习）,令ZZ，x1x1，x3x3x3 MaxZ= x12x2 3x33 x32x1 + x2 + x3 x3x4 9 s.t 3x1 + x2 + 2 x32x3 x5 44x1 + 2 x2 + 3 x33x3 6x1，x2，x3，x3，x4，x5 0,小结：LP标准型（SLP）的特点,1、目标函数为Max型（这不是必须的，也有规定为Min型的）； 2、所有约束均为“=”型； 3、任意xj 0； 4、各约束右端向量非负，即bj 0。,SLP的数学表达式,或：Max
13、 Z=CX,目标函数：约束条件：,其中，i=1，2，m；j=1，2，n,或：,松驰变量的经济意义,式中，加上的x3，x4，x5称为“松驰变量”，其经济意义为：例如：当x110，x2 10时，x3230，x4110，x5170表示了该生产方案下的未被充分利用的资源即“剩余资源”，松驰变量一般不全为0；上题中，表示剩余：煤230，电110，水170,作业,习题册：1.1题,第三讲：基的进一步理解 与图解LP解的性质,四、基及其相关概念,m为约束方程的个数， n为变量的个数， 约束方程组的系数矩阵A（ m X n ）， 且m n，m为矩阵A的秩。,基,基向量，基变量,基变量基向量对应的决策变量xj为
14、基变量，记作XB 如：XB1（x1 ，x2 ，x3）T,非基向量，非基变量,非基变量非基向量对应的变量为非基变量， 记作XN如：XN1（x4 ，x5）T,续例1 任意给出该LP问题的三个基 对于给出的基B1，写出其基向量、基变量、 非基向量、非基变量,基解，基可行解，可行基,基解确定基B后，令非基变量XN=0，所得方程组AXB=b的解称为LP关于B的基解（或基本解、基础解）基可行解满足基变量为非负约束的基解可行基对应于基可行解的基，或者表述为“使基解满足非负约束的基”,如取x1 ， x2， x3为基变量，令非基变量 x4， x5 0后，仍无法求出其基解。,同理，如取x2， x4， x5为基变量，令非基变量 x1， x3 0后，仍无法求出其基解。,思考：为什么要引进基的概念； 为什么行列式B的值要不能0,基解的特征,基 解,可 行 解,基可行解： 非基变量0，同时求出的基变量的值0,基解不一定可行，可行解不一定是基解,可行解,基解,非基变量0的解，注：求出的基解的基变量完全有可能小于0,满足所有约束的解，注：可行解中没有基变量的概念，因此就有可能解中所有变量值都不为0。,
