《线性规划概念与数学模型.ppt》由会员分享，可在线阅读，更多相关《线性规划概念与数学模型.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章、第一章、线性规划线性规划1、线性规划问题及其数学模型、线性规划问题及其数学模型2、线性规划的几何意义、线性规划的几何意义3、线性规划的求解单纯形法、线性规划的求解单纯形法一、线性规划问题：生产计划问题（例一、线性规划问题：生产计划问题（例1）甲乙设备128台时原材料A4016千克原材料B0412千克甲、乙产品每件获利分别为2、3元，如何安排获利最多？第一节、第一节、线性规划问题及其数学模型线性规划问题及其数学模型 如何制定生产计划，使两种产品总如何制定生产计划，使两种产品总利润最大？利润最大？问题讨论问题讨论何为生产计划？何为生产计划？总利润如何描述？总利润如何描述？还要考虑什么因素？
2、还要考虑什么因素？有什么需要注意的地方（技巧）？有什么需要注意的地方（技巧）？最终得到的数学模型是什么？最终得到的数学模型是什么？二、线性规划的定义和数学描述（模型）二、线性规划的定义和数学描述（模型）1定定义义：对对于于求求取取一一组组变变量量xj j(j=1,2,.,n)，使使之之既既满满足足线线性性约约束束条条件件，又又使使具具有有线线性性表表达达式式的的目目标标函函数数取取得得极极大大值值或或极极小小值值的的一一类类最最优优化问题称为化问题称为线性规划问题线性规划问题，简称，简称线性规划线性规划。2.线性规划模型的特点：线性规划模型的特点：用用一一组组未未知知变变量量表表示示要要求求的
3、的方方案案，这这组组未知变量称为未知变量称为决策变量决策变量；存在一定的存在一定的限制条件限制条件，且为线性表达式；，且为线性表达式；有有一一个个目目标标要要求求（最最大大化化，当当然然也也可可以以是是最最小小化化），目目标标表表示示为为未未知知变变量量的的线线性表达式，称之为性表达式，称之为目标函数目标函数；对决策变量有对决策变量有非负要求非负要求。三三LP的数学描述的数学描述(数学模型数学模型)：一般形式一般形式 二、二、线性规划的图解法线性规划的图解法 解的几何表示解的几何表示 1什么是图解法？什么是图解法？线线性性规规划划的的图图解解法法就就是是用用几几何何作作图图的的方法方法分析并求
4、出其最优解分析并求出其最优解的过程。的过程。求求解解的的思思路路是是：先先将将约约束束条条件件加加以以图图解解，求求得得满满足足所所有有约约束束条条件件的的解解的的集集合合（即即可可行行域域），然然后后结结合合目目标标函函数数的的要要求求从可行域中找出最优解。从可行域中找出最优解。可行解：满足所有约束条件的解可行解：满足所有约束条件的解图解法举例图解法举例 实施图解法，以求出最优生产计划（实施图解法，以求出最优生产计划（最优解最优解）例例1 maxZ=2x1+3x2s.t.工时工时原材料原材料 由于线性规划模型中只有两个决策变量，由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就
5、可进行图解因此只需建立平面直角坐标系就可进行图解.第第第第一一一一步步步步：建建立立平平面面直直角角坐坐标标系系，标标出出坐坐坐坐标标标标原原原原 点点点点,坐标轴的指向坐标轴的指向坐标轴的指向坐标轴的指向和和单位长度单位长度单位长度单位长度。用用x1轴轴表表示示产产品品甲甲的的产产量量，用用x2轴轴表表示示产产品品乙乙的产量。的产量。第二步：第二步：第二步：第二步：对约束条件加以图解。对约束条件加以图解。第三步：第三步：第三步：第三步：画出目标函数等值线，结合目标画出目标函数等值线，结合目标函数的要求求出最优解最优生产方案。函数的要求求出最优解最优生产方案。约束条件的图解约束条件的图解:每一
6、个约束不等式在平面直角坐标系中都每一个约束不等式在平面直角坐标系中都代表一个半平面，只要代表一个半平面，只要先画出该半平面的边先画出该半平面的边先画出该半平面的边先画出该半平面的边界界界界，然后，然后确定是哪个半平面确定是哪个半平面确定是哪个半平面确定是哪个半平面。?以第一个约束条件（工时）以第一个约束条件（工时）x1+2 x2 8 为例为例 说明约束条件的图解过程。说明约束条件的图解过程。怎么画边界怎么画边界怎么画边界怎么画边界 怎么确定怎么确定怎么确定怎么确定 半平面半平面半平面半平面 如如果果全全部部的的劳劳动动工工时时都都用用来来生生产产甲甲 产产品品而而不不生生产产乙乙产产品品，那那
7、么么甲甲产产品品的的最最大大可可能能产产量量为为8吨吨，计计算算过过程为：程为：x1+20 8 x1 8 这这个个结结果果对对应应着着下下图图中中的的点点B(8,0),同同样样我我们们可可以以找找到到B产产品品最最大大可可能能生生产产量量对对应应的的点点A(0,4)。连连接接A、B两点得到约束两点得到约束 x1+2 x2 8 所代表的半平面所代表的半平面 的边界的边界:x1+2x2 8，即直线即直线AB。12345678912345x1+2x2=8ABAB三个约束条件及非负条件三个约束条件及非负条件三个约束条件及非负条件三个约束条件及非负条件x x1 1,x,x2 2 0 0所代表的公共部分所
8、代表的公共部分所代表的公共部分所代表的公共部分图中阴影区，就是满足所有约束条件和非负条件的点的图中阴影区，就是满足所有约束条件和非负条件的点的图中阴影区，就是满足所有约束条件和非负条件的点的图中阴影区，就是满足所有约束条件和非负条件的点的集合，即集合，即集合，即集合，即可行域可行域可行域可行域。在这个区域中的每一个点都对应着一个可。在这个区域中的每一个点都对应着一个可。在这个区域中的每一个点都对应着一个可。在这个区域中的每一个点都对应着一个可行的生产方案。行的生产方案。行的生产方案。行的生产方案。第第第第二二二二、三三三三个个个个约约约约束束束束条件的边界条件的边界条件的边界条件的边界 直线直
9、线直线直线CDCD，EF:EF:4x 4x1 1=16,4x=16,4x2 2=12=1212345678912345EF4x2=124x1=16ABCDx1+4x2=8 令令 Z=2x1+3x2=c,其其中中c c为为为为任任任任选选选选的的的的一一一一个个个个常常常常数数数数，在在图图中中画画出出直直线线 2x1+3x2=c,这这条条直直线线上上的的点点即即对对应应着着一一个个可可行行的的生生产产方方案，即使两种产品的总利润达到案，即使两种产品的总利润达到c。这这样样的的直直线线有有无无数数条条，而而且且相相互互平平行行，称称这这样样的的直直线线为为目目目目标标标标函函函函数数数数等等等等
10、值值值值线线线线。只只只只要要要要画画出出两两两两条条条条目目目目标标标标函函函函数数数数等等等等值值值值线线线线，比比如如令令c0和和c=6，就能看出，就能看出 目标函数值递增的方向目标函数值递增的方向目标函数值递增的方向目标函数值递增的方向，用用箭头标出箭头标出箭头标出箭头标出这个方向。这个方向。图中两条虚线图中两条虚线 l1和和l2就就 分别代表分别代表 目标函数等值线目标函数等值线 2x1+3x2=0 和和 2x1+3x2=6,箭头表示使两种产品的总箭头表示使两种产品的总 利润递增的方向。利润递增的方向。12345678912345x1+2x2=8ABDC4x1=16l1l2l3FEB
11、A4x1=12 沿着箭头沿着箭头沿着箭头沿着箭头的方向的方向平移平移平移平移目标函数等值线，使其目标函数等值线，使其达达达达到可行域中的最远点到可行域中的最远点到可行域中的最远点到可行域中的最远点QQ2 2,QQ2 2点就是要求的最优点，点就是要求的最优点，它对应的相应坐标它对应的相应坐标 x1=4,x2=2 就是最有利的产品就是最有利的产品组合，即生产组合，即生产甲甲产品产品4件件，乙乙产品产品2件能使两种产件能使两种产品的总利润达到最大值品的总利润达到最大值 Zmax=2 4+3 2=14(元元)，x x1 1=4,x=4,x2 2=2=2就是线性规划模型的就是线性规划模型的最优解最优解最
12、优解最优解，Z Zmaxmax=14=14就是相应的目标函数最优值就是相应的目标函数最优值就是相应的目标函数最优值就是相应的目标函数最优值 尽尽尽尽管管管管最最最最优优优优点点点点的的的的对对对对应应应应坐坐坐坐标标标标可可可可以以以以直直直直接接接接从从从从图图图图中中中中给给给给出出出出，但但但但是是是是在在在在大大大大多多多多数数数数情情情情况况况况下下下下，对对对对实实实实际际际际问问问问题题题题精精精精确确确确地地地地看看看看出出出出一一一一个个个个解解解解答答答答是是是是比比比比较较较较困困困困难难难难的的的的。所所所所以以以以，通通通通常常常常总总总总是是是是用用用用解解解解联联
13、联联立立立立方方方方程程程程的的的的方方方方法法法法求求求求出出出出最最最最优优优优解解解解的的的的精精精精确值。确值。确值。确值。比比比比如如如如QQ2 2点点点点对对对对应应应应的的的的坐坐坐坐标标标标值值值值我我我我们们们们可可可可以以以以通通通通过过过过求求求求解解解解下下下下面面面面的的的的联联联联立立立立方方方方程程程程，即即即即求求求求直直直直线线线线ABAB和和和和CDCD的的的的交交交交点来求得。点来求得。点来求得。点来求得。直线直线直线直线AB:xAB:x1 1+2x+2x2 2=8=8 直线直线直线直线CD:4xCD:4x1 1=16=16 0 1 2 3 4 5 6 7
14、 8 9 x1 5 4 3 2 1x2（8，0）C=6（0，4）C=0s.t.Q2（4，2）一般线性规划解的几种不同情形：一般线性规划解的几种不同情形：无穷多最优解（多重最优解）无穷多最优解（多重最优解）无界解无界解无可行解无可行解 0 1 2 3 4 5 6 7 8 9 x1 5 4 3 2 1x2-2 -14x1=124x1=16x1+2x2=8-2x1+x2=4二、二、线性规划的标准型线性规划的标准型 1、LP标准型的概念标准型的概念 （1）什么是）什么是LP的标准型？的标准型？标准格式！标准格式！（2）LP标准型的特点标准型的特点 目标函数约定是极大化目标函数约定是极大化目标函数约定是
15、极大化目标函数约定是极大化Max(Max(或极小化或极小化或极小化或极小化Min);Min);约束条件均用等式表示约束条件均用等式表示约束条件均用等式表示约束条件均用等式表示;决策变量限于取非负值决策变量限于取非负值决策变量限于取非负值决策变量限于取非负值;右端常数均为非负值右端常数均为非负值右端常数均为非负值右端常数均为非负值;2LP的数学描述的数学描述(数学模型数学模型)：（1）标准形式）标准形式（2）紧缩形式）紧缩形式（3）向量）向量矩阵形式：矩阵形式：其中：其中：（4）矩阵形式）矩阵形式其中其中 :3、LP问题的标准化问题的标准化（为了问题的求解）（为了问题的求解）MinZ=CXMin
16、Z=CXMaxZ=-CXMaxZ=-CXZ=-ZZ=-Z（2）约束条件的标准化约束条件的标准化&约束条件是约束条件是约束条件是约束条件是 类型，类型，类型，类型，左边加非负松弛变量左边加非负松弛变量左边加非负松弛变量左边加非负松弛变量,变为变为变为变为等式；等式；等式；等式；&约束条件是约束条件是约束条件是约束条件是 类型，类型，类型，类型，左边减非负剩余变量左边减非负剩余变量左边减非负剩余变量左边减非负剩余变量,变为变为变为变为等式；等式；等式；等式；&变量符号不限，变量符号不限，变量符号不限，变量符号不限，引入引入引入引入新变量新变量新变量新变量（1）目标函数的标准化）目标函数的标准化 将
17、下面的线性规划问题化为标准型：将下面的线性规划问题化为标准型：讨论：讨论：如何下手？标准化过程排序如何下手？标准化过程排序-课堂练习课堂练习1 x3；约约束束1引引松松弛弛变变量量；约约束束2引引剩剩余余变变量量；约束约束3变号；变号；目标函数标准化，引入变换目标函数标准化，引入变换Z=-Z；整理；整理；令令四、四、线性规划的各种解线性规划的各种解可行解可行解：满足满足LP约束条件的解约束条件的解 称为称为LP的可行解的可行解,其中使目标函数达到最大（或最小）值的可其中使目标函数达到最大（或最小）值的可行解为行解为最优解最优解。可行域可行域：所有可行解的集合。所有可行解的集合。最优值最优值：与
18、与LP问题最优解问题最优解x*对应的目标函数的取值对应的目标函数的取值Zmax叫最优值。叫最优值。n n 注意注意：LPLP问题求解结果包括两部分：问题求解结果包括两部分：最优解最优解x x*（列列向量）向量）最优值最优值Z Zmaxmax（数值）（数值）n基基 设设LP标准型中约束方程组系数矩阵标准型中约束方程组系数矩阵A是是mn阶矩阵，阶矩阵，秩秩为为m，B是是A中中mm阶非奇异子阶非奇异子矩阵（矩阵（|B|0），则称），则称B是是LP问题的一个基问题的一个基。x1，x2，x3（P1，P2，P3）n基向量基向量：设设B为为LP问题的一个基，即问题的一个基，即 B=(Pr1,Pr2,Prm)
19、。则称线性独立列向量。则称线性独立列向量Prj=(a1,rj,a2,rj,an,rj)T,j=1,2,m 为基向量。因此，一个基对应为基向量。因此，一个基对应m个个基向量。基向量。n基变量基变量,非基变量非基变量：与基向量与基向量Prj对应的决策变对应的决策变量量 xrj(j=1,2,m)称基变量；其他称基变量；其他n-m个决策变量个决策变量xrj(j=m+1,m+2,n)称为非基变量。称为非基变量。基本解基本解:设设B是是LP问题的一个基，令与问题的一个基，令与B的列的列不不相对相对应的应的n-m个决策变量个决策变量(即非基变量即非基变量)等于等于 0，对应方程组，对应方程组的解称为方程组的
20、解称为方程组AX=b关于基关于基B的解，也叫的解，也叫LP问题的一问题的一个基本解个基本解.注意注意：可以看出可以看出,有一个基就有一个基本解，基本解有一个基就有一个基本解，基本解的个数等于基的个数，总是小于等于的个数等于基的个数，总是小于等于 。当一个基。当一个基解中的非零分量小于解中的非零分量小于m时，该基解是一个退化解。时，该基解是一个退化解。基可行解基可行解：满足非负条件的基本解叫基可行解，其满足非负条件的基本解叫基可行解，其对应的基称为对应的基称为可行基可行基。基本可行解的非零分量均为正。基本可行解的非零分量均为正分量，分量的个数分量，分量的个数m。n解的关系解的关系可行解可行解 基
21、本解基本解基本基本 可行解可行解 基本解与基本可行解的几何意义基本解与基本可行解的几何意义求解线性规划问题：求解线性规划问题：讨论求取基本解的步骤：讨论求取基本解的步骤：将线性规划标准化；将线性规划标准化；s.t.AX=b 1)1)寻找基寻找基(不超过不超过 个个););2)2)确定基变量与非基变量；确定基变量与非基变量；例如，基变量例如，基变量(x3,x4,x5)3)3)令非基变量取值为令非基变量取值为0 0；令令x1=x2=0 4)(4)(基变量基变量,非基变量非基变量)构成基本解。构成基本解。(0,0,4,2,2)(0,0,4,2,2)然后按照基本解的定义：然后按照基本解的定义：H(6,
22、4,-6,0,0)T,C(3,1,0,3,0)T,B(2,2,0,0,2)T,D(2,0,2,4,0)T,F(-2,0,6,0,4)T,I(4,0,0,6,-2)T,E(0,-2,6,6,0)T,A(0,1,3,0,3)T,G(0,4,0,-8,6)T,O(0,0,4,2,2)T.对于上例对于上例,共有共有10个基本解个基本解求得的基本解和图解法对照，找出相应的点。求得的基本解和图解法对照，找出相应的点。为何为何红点和绿点红点和绿点是基本解却不是基本可行解是基本解却不是基本可行解?12343210X2X1x1-x2=2-x1+2x2=2x1+x2=4Z=0Z=14IDBACHFEG 结论：结论：(1)基本解基本解对应所有可行域边界及其延对应所有可行域边界及其延 长线、坐标轴之间的长线、坐标轴之间的交点交点；(2)基本可行解基本可行解对应可行域的对应可行域的顶点顶点。第一节第一节 总总 结结LP定义，模型特点，定义，模型特点，图解法图解法标准型概念及其作用标准型概念及其作用标准型特点及四种形式标准型特点及四种形式标准化步骤标准化步骤n LP的提出与定义的提出与定义n LP数学描述数学描述可行解可行解基解（基解（基基）基可行解（基可行解（可行基可行基）n LP问题的解问题的解课后作业课后作业:P44页1.1题的4个小题，1.3题的（1）题