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

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 8 习题 营养配餐问题假定一个成年人每天至少需要从食物中摄取3000大卡的热量 55克蛋白质和800毫克的钙 市场上只有猪肉 鸡蛋 大米和白菜四种食品可供选择 它们每公斤所含的热量和营养成分以及市场价格见下表 请问如何选择才能在满足营养的前提下 使购买食品的费用最小 SchoolofBusinessECUST 每公斤食物营养表 10 营养配餐问题建模 决策变量 xj 每天购入第j种食品的公斤数目标函数 每天的食品采购成本最小约束条件 满足每天的营养要求 1 满足每天至少3000大卡的热量要求 11 2 满足每天至少摄入55克蛋白质的营养要求 3 满足每天至少摄入800毫克钙的营养要求非负约束 采购量不能为负值 12 营养配餐问题的数学模型 13 2 2线性规划的一般形式 线性规划问题是求一个线性函数 目标函数 在满足一组线性等式或不等式条件下极值的数学问题的统称 线性规划问题的一般特征 1 有一组有待决策的变量 决策变量 一般表示为x1 x2 xn 变量组的每一组取值对应于某一种决策方案 根据实际问题 通常要求变量取非负值 即 14 2 每个问题中存在若干个约束条件 约束条件可用决策变量的线性等式或线性不等式来表达 3 每个问题中有一个目标函数 这个目标函数可表示为决策变量的线性函数 要求这个目标函数在满足约束条件下实现最大化或最小化将约束条件及目标函数都是决策变量线性函数的数学规划问题称为线性规划 LP linearprogramming 15 一般的数学规划模型 线性规划模型 线性规划模型的一般形式 通常称为决策变量 为价值系数 为技术系数 为资源限制系数 16 可简写为 17 向量式 18 矩阵式 系数矩阵 右端常数 19 2 3线性规划模型的标准形式 LP模型的标准型为 其中右端常数项 20 用向量表示时 标准型可写为 用矩阵形式 可表示为 21 非标准形式 标准形式 1 目标函数 min max 2 右端常数 bi0 3 约束 不等式约束 等式约束 4 变量 不满足非负条件 满足非负条件 0 0无符号限制 自由变量 0 22 1 目标函数 min max 若目标函数为 引进新的目标函数 则 的最小值即为 从而目标函数变换为 的最大值 即 23 2 右端常数 bi0若约束条件中某线性方程式的常数项bi为负数 则将该线性方程式两端乘以 1即可 但需注意不等式变号 24 3 约束 不等式约束 等式约束 在不等式左边加上一个非负变量 松弛变量 将不等式变为等式 在不等式左边减去一个非负变量 剩余变量 将不等式变为等式 25 简例 将LP模型 化为标准型 解 对 引入变量 松弛变量 使得 式变为 对 式 引入变量 剩余变量 使得 式变为 26 于是将原LP模型化为标准形式 27 4 变量 不满足非负条件 满足非负条件 0 0 x 0 令x x 则x 0 用变量x 替换x无符号限制 自由变量 0 x无符号限制 令x x x 其中x x 0 用变量x 和x 替换x 28 例 将下列LP模型 化为标准型 无符号限制 29 30 31 3模型求解3 1图解法 线性规划问题的几何特征 32 3 1 1两个决策变量线性规划模型图解法的基本步骤 1 建立以x1 x2为坐标轴的直角坐标系 画出线性规划问题的可行域 2 任取z z0 画出对应的目标函数直线 将该直线在可行区域内平行移动 构成目标函数的等值线簇 3 目标函数值最优的等值线与可行域的交点 若存在 即为问题的最优解 可行域 满足所有约束条件的解的集合 即所有约束条件共同围成的区域 33 例用图解法求下列线性规划问题的最优解 MaxZ 3x1 5x2s t 2x1 162x2 103x1 4x2 32x1 0 x2 0 34 目标函数Z 3x1 5x2代表以Z为参数的一族平行线 最优解 35 1 惟一最优解 3 1 2线性规划问题解的几种情况 36 2 无穷多最优解 37 3 无界解 最优解无界 无 有限最优解 可行域无界 目标函数值无限增大 38 4 无可行解 可行域为空集 约