1-1 线性规划-问题、模型与图解法

1,1-1线性规划-问题、模型及图解法,2,线性规划的发展,20世纪30年代前苏联数学家康特洛维奇提出解乘数法(1975年诺贝尔经济学奖)1947美国空军数学顾问丹捷格线性规划单纯形法冯.诺依曼对偶理论库恩塔克盖尔严格证明,3,概要,1问题描述2建模2.1建模三要素2.2一般形式2.3标准形式3模型求解3.1图解法3.1.1方法步骤3.1.2解的几种情况3.2基本概念与理论3.3单纯形法3.3.1单纯形法的一般思路+例子3.3.2单纯形表结构+例子3.3.3单纯形法的计算步骤,4,3.4大M法3.5两阶段法4几种特殊情况4.1无可行解4.2无界解4.3多重最优解4.4进基变量的相持4.5出基变量的相持,5,1问题描述-线性规划经典问题,生产计划问题某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,6,2建模,2.1建模三要素变量目标函数约束条件,（1）理解要解决的问题，了解解题的目标和条件；（2）定义决策变量（x1，x2，xn），每一组值表示一个方案；（3）用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；（4）用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件,7,SchoolofBusinessECUST,习题：营养配餐问题假定一个成年人每天至少需要从食物中摄取3000大卡的热量、55克蛋白质和800毫克的钙。市场上只有猪肉、鸡蛋、大米和白菜四种食品可供选择，它们每公斤所含的热量和营养成分以及市场价格见下表。请问如何选择才能在满足营养的前提下，使购买食品的费用最小？,SchoolofBusinessECUST,每公斤食物营养表,SchoolofBusinessECUST,营养配餐问题建模,决策变量：xj每天购入第j种食品的公斤数目标函数：每天的食品采购成本最小约束条件：满足每天的营养要求(1)满足每天至少3000大卡的热量要求,SchoolofBusinessECUST,(2)满足每天至少摄入55克蛋白质的营养要求(3)满足每天至少摄入800毫克钙的营养要求非负约束：采购量不能为负值,SchoolofBusinessECUST,营养配餐问题的数学模型,SchoolofBusinessECUST,2.2线性规划的一般形式,线性规划问题是求一个线性函数(目标函数)在满足一组线性等式或不等式条件下极值的数学问题的统称。线性规划问题的一般特征：(1)有一组有待决策的变量(决策变量)，一般表示为x1,x2,.,xn，变量组的每一组取值对应于某一种决策方案，根据实际问题，通常要求变量取非负值，即,SchoolofBusinessECUST,(2)每个问题中存在若干个约束条件，约束条件可用决策变量的线性等式或线性不等式来表达。(3)每个问题中有一个目标函数，这个目标函数可表示为决策变量的线性函数。要求这个目标函数在满足约束条件下实现最大化或最小化将约束条件及目标函数都是决策变量线性函数的数学规划问题称为线性规划(LP,linearprogramming),SchoolofBusinessECUST,一般的数学规划模型,线性规划模型,线性规划模型的一般形式,通常称为决策变量，为价值系数，为技术系数,为资源限制系数。,SchoolofBusinessECUST,可简写为：,SchoolofBusinessECUST,向量式,SchoolofBusinessECUST,矩阵式,系数矩阵,右端常数,SchoolofBusinessECUST,2.3线性规划模型的标准形式,LP模型的标准型为：,其中右端常数项,SchoolofBusinessECUST,用向量表示时，标准型可写为：,用矩阵形式，可表示为：,SchoolofBusinessECUST,非标准形式标准形式,(1)目标函数：minmax(2)右端常数：bi0(3)约束：不等式约束等式约束=(4)变量：不满足非负条件满足非负条件00无符号限制(自由变量)0,SchoolofBusinessECUST,(1)目标函数：minmax,若目标函数为,引进新的目标函数,则,的最小值即为,从而目标函数变换为：,的最大值，即：,SchoolofBusinessECUST,(2)右端常数：bi0若约束条件中某线性方程式的常数项bi为负数，则将该线性方程式两端乘以-1即可，但需注意不等式变号。,SchoolofBusinessECUST,(3)约束：不等式约束等式约束=：在不等式左边加上一个非负变量(松弛变量)，将不等式变为等式。=：在不等式左边减去一个非负变量(剩余变量)，将不等式变为等式。,SchoolofBusinessECUST,简例：,将LP模型,化为标准型。,解：对,引入变量(松弛变量),使得式变为：,对式,引入变量(剩余变量),使得式变为：,SchoolofBusinessECUST,于是将原LP模型化为标准形式：,SchoolofBusinessECUST,(4)变量：不满足非负条件满足非负条件00：x0,令x=-x,则x0,用变量x替换x无符号限制(自由变量)0：x无符号限制,令x=xx,其中x,x0。用变量x和x替换x,SchoolofBusinessECUST,例,将下列LP模型：,化为标准型。,无符号限制,SchoolofBusinessECUST,SchoolofBusinessECUST,31,3模型求解3.1图解法(线性规划问题的几何特征),SchoolofBusinessECUST,3.1.1两个决策变量线性规划模型图解法的基本步骤：(1)建立以x1,x2为坐标轴的直角坐标系，画出线性规划问题的可行域；(2)任取z=z0,画出对应的目标函数直线,将该直线在可行区域内平行移动，构成目标函数的等值线簇；(3)目标函数值最优的等值线与可行域的交点(若存在)即为问题的最优解。,可行域：满足所有约束条件的解的集合，即所有约束条件共同围成的区域。,SchoolofBusinessECUST,例用图解法求下列线性规划问题的最优解,MaxZ=3x1+5x2s.t.2x1162x2103x1+4x232x10,x20,SchoolofBusinessECUST,目标函数Z=3x1+5x2代表以Z为参数的一族平行线。,最优解：,35,(1)惟一最优解,3.1.2线性规划问题解的几种情况,SchoolofBusinessECUST,(2)无穷多最优解,SchoolofBusinessECUST,(3)无界解：最优解无界，无“有限最优解”,可行域无界，目标函数值无限增大,SchoolofBusinessECUST,(4)无可行解：可行域