第二讲线性规划基础ppt课件

,湖州师范学院商学院,*,*,运筹学,（operations research,OR）绪论,第二讲 线性规划基础,商学院电子商务系,11/14/2024,1,运筹学（operations research,OR）,第二讲 线性规划基础,一.线性规划的提出与模型,二.线性规划的图解,三.线性规划标准型与解的概念,四.线性规划的基本理论,11/14/2024,2,第二讲 线性规划基础一.线性规划的提出与模型 10,一、线性规划的提出与模型,1、问题的提出,第二讲 线性规划基础,例1-1：某工厂在计划期内要安排生产甲、乙两种产品，按照工艺要求，产品甲、乙在设备A、B上所需的加工台时及原材料的消耗如表1-1所示。,资源,产品,原材料,/单位,设备,A/h,设备,B/h,单件利润,/千元,甲,1,4,0,3,乙,2,0,4,4,资源数量,8,16,12,表1-1 例1-1数据资料,11/14/2024,3,一、线性规划的提出与模型1、问题的提出第二讲 线性规,第二讲 线性规划基础,一、线性规划的提出与模型,1、问题的提出,续例1-1：问：应如何安排生产计划才能到最大利润？,用数学关系式描述这个问题,假设 ，分别表示在计划期内产品甲、乙的产量；,生产 ，的数量多少，受到各种条件限制；,生产的产品数量不能为负值,，即 ；,问：如何安排生产，使利润最大？,决策变量,约束条件,目标函数,资源,产品,原材料,/单位,设备,A/h,设备,B/h,单件利润,/千元,甲,1,4,0,3,乙,2,0,4,4,资源数量,8,16,12,11/14/2024,4,第二讲 线性规划基础一、线性规划的提出与模型1、问题,第二讲 线性规划基础,一、线性规划的提出与模型,1、问题的提出,得到本问题的数学模型为:,这就是一个最简单的线性规划模型。,11/14/2024,5,第二讲 线性规划基础一、线性规划的提出与模型1、问题,第二讲 线性规划基础,一、线性规划的提出与模型,练习题,练习题1,靠近某河流有两个化工厂,(,见图,1-1),，流经第一化工厂的河流流量为每天,500,万立方米，在两个工厂之间有一条流量为每天,200,万立方米的支流。,化工厂1每天排放含有某种有害物质的工业污水,2,万立方米，化工厂2每天排放的工业污水为,1.4,万立方米。从化工厂1排出的污水流到化工厂2前，有,20%,可自然净化。根据环保要求，河流中工业污水的含量应不大于,0.2%,。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本是,1000元/万立方米,化工厂2处理污水的成本是,800元/万立方米,。问:,在满足环保要求的条件下，每厂各应处理多少工业污水，,使两个工厂处理工业污水的总费用最小。,图1-1,11/14/2024,6,第二讲 线性规划基础一、线性规划的提出与模型练习题,第二讲 线性规划基础,一、线性规划的提出与模型,练习题1,建模型之前的分析和计算,设,：,化工厂1每天处理的污水量为,x,1,万立方米；,化工厂2每天处理的污水量为,x,2,万立方米,11/14/2024,7,第二讲 线性规划基础一、线性规划的提出与模型练习题1,第二讲 线性规划基础,一、线性规划的提出与模型,练习题1,得到本问题的数学模型为：,11/14/2024,8,第二讲 线性规划基础一、线性规划的提出与模型练习题1,第二讲 线性规划基础,一、线性规划的提出与模型,练习题2,练习题2,某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如表1-2所示。设司乘人员在各时间段一开始时上班，并连续工作8小时，问该公交线路怎样安排司乘人员，既能满足工作需要，又配备最少的司机和乘务人员？试列出该问题的线性规划模型。,班次,时间,所需人数,班次,时间,所需人数,1,6：00-10：00,60,4,18：00-22：00,50,2,10：00-14：00,70,5,22：00-2：00,20,3,14：00-18：00,60,6,2：00-6：00,30,表1-2 练习题2数据资料,11/14/2024,9,第二讲 线性规划基础一、线性规划的提出与模型练习题2,第二讲 线性规划基础,一、线性规划的提出与模型,2、线性规划的一般数学模型,一般线性规划数学模型有三个要素：,（1）决策变量集合：，通常要求非负；,（2）约束条件集合，决策变量集的一组线性等式或不等式；,（3）目标函数：，通常求最大值或最小值。,11/14/2024,10,第二讲 线性规划基础一、线性规划的提出与模型2、线性,第二讲 线性规划基础,一、线性规划的提出与模型,2、线性规划的一般数学模型,线性规划模型的一般形式为：,11/14/2024,11,第二讲 线性规划基础一、线性规划的提出与模型2、线性,第二讲 线性规划基础,一、线性规划的提出与模型,2、线性规划的一般数学模型,决策变量及各类系数之间的对应关系：,11/14/2024,12,第二讲 线性规划基础一、线性规划的提出与模型2、线性,第二讲 线性规划基础,一、线性规划的提出与模型,总结：,线性规划是求一个线性函数在满足一组线性等式或不等式方程条件下极值的数学问题的统称。,其组成部分：,1、一个反映决策目标的目标函数；,2、一组线性等式或不等式的约束方程；,3、限制决策变量取值范围的非负约束。,11/14/2024,13,第二讲 线性规划基础一、线性规划的提出与模型总结：,第二讲 线性规划基础,二、线性规划的图解法,例1是一个二维线性规划问题，因而可用作图法直观地进行求解。,11/14/2024,14,第二讲 线性规划基础二、线性规划的图解法例1是一个二,第二讲 线性规划基础,二、线性规划的图解法,目标值在（4，2）点，达到最大值14,11/14/2024,15,第二讲 线性规划基础二、线性规划的图解法目标值在（4,第二讲 线性规划基础,二、线性规划的图解法,几种特殊情况：,（1）无穷多最优解：,max z=2x,1,+4x,2,将目标函数改为：,max z=2x,1,+4x,2,当目标方程直线与某一约束直线平行时，最优值不唯一,！,11/14/2024,16,第二讲 线性规划基础二、线性规划的图解法几种特殊情况,第二讲 线性规划基础,二、线性规划的图解法,几种特殊情况：,（2）无界解：有可行域，但无最优解；,11/14/2024,17,第二讲 线性规划基础二、线性规划的图解法几种特殊情况,第二讲 线性规划基础,二、线性规划的图解法,几种特殊情况：,（3）无可行解：无可行域；,当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。,例如，,如果在例1的数学模型中增加一个约束条件:,思考：会出现什么结果？,11/14/2024,18,第二讲 线性规划基础二、线性规划的图解法几种特殊情况,第二讲 线性规划基础,二、线性规划的图解法,（3）无可行解：无可行域；,增加的约束条件,结论：该问题的可行域为空集，即无可行解，,11/14/2024,19,第二讲 线性规划基础二、线性规划的图解法（3）无可行,第二讲 线性规划基础,二、线性规划的图解法,结论：,1、当线性规划问题的可行域非空时，它是有界或无界凸多边形；,2、若线性规划问题存在最优解，它一定在有界可行域的某个顶点得到。,推广：无穷多最优解的情况？,思考：图解法给人们的启示是什么？,11/14/2024,20,第二讲 线性规划基础二、线性规划的图解法结论：,第二讲 线性规划基础,三、线性规划标准型与解的概念,1、线性规划的标准型,11/14/2024,21,第二讲 线性规划基础三、线性规划标准型与解的概念1、,第二讲 线性规划基础,三、线性规划标准型与解的概念,1、线性规划的标准型,用向量形式表示的标准形式线性规划：,11/14/2024,22,第二讲 线性规划基础三、线性规划标准型与解的概念1、,第二讲 线性规划基础,三、线性规划标准型与解的概念,1、线性规划的标准型,用矩阵形式表示的标准形式线性规划：,11/14/2024,23,第二讲 线性规划基础三、线性规划标准型与解的概念1、,第二讲 线性规划基础,三、线性规划标准型与解的概念,2、化一般模型为标准模型,(1)若要求目标函数实现最小化，即,min,z,=,CX,，,则只需将目标函数最小化变换求目标函数最大化，即令,z,=,z,，,于是得到,max,z,=,CX,。,(2)约束条件为不等式。分两种情况讨论：,若约束条件为“”型不等式，则可在不等式左端加入非负松弛变量，把原“”型不等式变为等式约束；,(3)若存在取值无约束的变量,x,k,可令:,若约束条件为“”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束。,11/14/2024,24,第二讲 线性规划基础三、线性规划标准型与解的概念2、,第二讲 线性规划基础,三、线性规划标准型与解的概念,2、化一般模型为标准模型,练习题：,例3,将例1的数学模型化为标准形式的线性规划。,11/14/2024,25,第二讲 线性规划基础三、线性规划标准型与解的概念2、,第二讲 线性规划基础,三、线性规划标准型与解的概念,2、化一般模型为标准模型,练习题：,(1)用,x,4,x,5,替换,x,3,，其中,x,4,，,x,5,0；,(2)在第一个约束不等式左端加入松弛变量,x,6,；,(3)在第二个约束不等式左端减去剩余变量,x,7,；,(4)令,z,=,z,，将求min,z,改为求max,z,11/14/2024,26,第二讲 线性规划基础三、线性规划标准型与解的概念2、,第二讲 线性规划基础,三、线性规划标准型与解的概念,2、化一般模型为标准模型,11/14/2024,27,第二讲 线性规划基础三、线性规划标准型与解的概念2、,第二讲 线性规划基础,三、线性规划标准型与解的概念,3、线性规划问题解的概念,满足约束条件(1-5)、(1-6)式的解,X,=(,x,1,x,2,，,x,n,),T,，称为线性规划问题的,可行解,，其中使目标函数达到最大值的,可行解,称为,最优解。,11/14/2024,28,第二讲 线性规划基础三、线性规划标准型与解的概念3、,第二讲 线性规划基础,三、线性规划标准型与解的概念,3、线性规划问题解的概念,11/14/2024,29,第二讲 线性规划基础三、线性规划标准型与解的概念3、,第二讲 线性规划基础,三、线性规划标准型与解的概念,3、线性规划问题解的概念,11/14/2024,30,第二讲 线性规划基础三、线性规划标准型与解的概念3、,满足非负条件的基解，称为基可行解.基可行解的非零分量的数目不大于,m,，并且都是非负的。,第二讲 线性规划基础,三、线性规划标准型与解的概念,3、线性规划问题解的概念,对应于基可行解的基，称为可行基。,约束方程组(1-5)具有的基解的数目最多是 个，一般基可行解的数目要小于基解的数目。,思考：例中基解可以有多少个？,11/14/2024,31,满足非负条件的基解，称为基可行解.基可行,第二讲 线性规划基础,线性规划问题各种解之间的关系,三、线性规划标准型与解的概念,11/14/2024,32,第二讲 线性规划基础线性规划问题各种解之间的关系三、,第二讲 线性规划基础,四、线性规划的基本理论,1、凸集、凸组合与顶点,设,S,是,n,维欧氏空间的一点集，若任意两点,X,(1),S,，,X,(2),S,的连线上的所有点,X,(1)+(1,),X,(2),S,，(0,1)，则称,K,为凸集。,11/14/2024,33,第二讲 线性规划基础四、线性规划的基本理论1、凸集、,第二讲 线性规划基础,四、线性规划的基本理论,1、凸集、凸组合与顶点,从直观上讲，凸集没有凹入部分，其内部没有空洞。,任何两个凸集的交集是凸集。,11/14/2024,34,第二讲 线性规划基础四、线性规划的基本理论1、凸集、,第二讲 线性规划基础,四、线性规划的基本理论,1、凸集、凸组合与顶点,设,X,(,1),，,X,(2),，,X,(,k,),是,n,维欧氏空