规划模型ppt课件.ppt

线性规划问题 线性规划问题及其数学模型图解法Matlab计算线性规划问题 一 线性规划问题及其数学模型 线性规划在经营管理中 常常用来解决有限资源 人 财 物 的合理分配问题 在经营管理中 几乎一切问题都与有限资源的合理分配利用有关 线性规划为解决有限资源的合理分配利用提供了一个有效的数学工具 建立线性规划数学模型是解决线性规划问题的一个重要步骤 建立的线性规划数学模型是否真正的反映客观实际 数学模型本身是否正确 都直接影响求解结果 从而影响决策结果 所以 建立正确的线性规划模型尤为重要 下面举例说明线性规划数学模型的建立 一 线性规划数学模型的建立 某厂利用A B两种原料 生产甲 乙两种产品 有关数据如下 例1 产品组合问题 产品名称 甲乙 单位产品消耗原料 原料名称 可供利用的原料数量 T 日 68 1221 AB 产品售价 千元 T 32 根据市场调查 有如下资料 1 乙产品的需求量至多2T 日 2 乙产品的需求量比甲产品的需求量至多大1T 日 求该厂产值最大的生产方案 提出三个问题大家考虑 1 问题的未知数是什么 设未知数2 以什么准则进行决策 目标函数3 约束条件是什么 约束方程 这里生产方案指的是如何安排甲 乙产品的产量 显然 产量是未知数 设 甲产品的产量为x1T 日乙产品的产量为x2T 日 决策准则是产值最大 用Z代表产值 则有 Z 3x1 2x2Z是x1 x2的函数 称为目标函数 目标是求极大值 即 maxZ 3x1 2x2 约束条件 分三部分 资源限制 市场限制 非负限制 x1 2x2 62x1 x2 8x2 2x2 x1 1x1 x2 0 约束条件 资源限制 市场限制 非负限制 整理得数学模型 目标函数 minz 1000 x1 800 x2约束条件 s t x1 10 8x1 x2 1 6x1 2x2 1 4x1 0 x2 0 例3 配料问题 min 设x1 x2分别代表每粒胶丸中甲 乙两种原料的用量 某厂生产一种胶丸 已知如下资料 例4 合理下料问题 用7 4m长的钢筋 分别截取2 9m 2 1m 1 5m各至少100根 要求用料最少 设xj分别代表采用切割方案1 8所需7 4米的钢筋的数量 二 线性规划问题的共同特征 模型的三要素 每一个问题都用一组决策变量 x1 x2 xn 表示某一方案 这组决策变量的值就代表一个具体方案 一般这些变量取值都是非负的 存在一定的约束条件 这些约束条件可以用一组线性等式或线性不等式来表示 都有一个要求达到的目标 它可用决策变量的线性函数 称为目标函数 来表示 按问题的不同 要求目标函数实现最大化或最小化 三 线性规划数学模型的一般表示方式 求解线性规划问题的任务是 在满足约束条件的所有 x1 x2 xn 可行解 中求出使目标函数达到最大 小 z值的决策变量值 x1 x2 xn 最优解 1 和式 2 向量式 3 矩阵式 练习题 建立线性规划模型 某城市在一昼夜间 市内交通需要车辆数如图 对车辆的需求在昼夜间是变化的 车辆的工作制度是一天连续工作8小时 派车时间在各时间间隔的端点 一旦派出 就连续工作8小时 求保证需要的最小车辆数 车辆数 时间 0 4 7 12 16 20 24 4 8 12 4 8 12 10 8 4 派车时间在各时间间隔的端点 一旦派出 就连续工作8小时 设 各时间间隔所派车辆数为xjj 1 2 6则有 minZ x1 x2 x3 x4 x5 x6x1 x6 4x1 x2 8x2 x3 10 x3 x4 7x4 x5 12x5 x6 4x1 x2 x3 x4 x5 x6 0 二 线性规划问题及图解法 线性规划问题及其数学模型图解法Matlab计算线性规划问题 二 图解法 对模型中只含2个变量的线性规划问题 可以通过在平面上作图的方法求解 一 图解法的步骤 1 等直线法 x1 x2 0 4 Q2 4 2 Q1 Q3 Q4 4x1 16 4x2 12 x1 2x2 8 3 Q2 1 建立平面直角坐标系 4 向着目标函数的优化方向平移等值线 直至得到等值线与可行域的最后交点 这种点就对应最优解 2 找出表示每个约束的半平面 所有半平面的交集是可行域 全体可行解的集合 3 画出目标函数的等值线 2 试算法 最优解在顶点达到 O点 X1 0 X2 0 Z 0Q1 X1 4 X2 0 Z 8Q2 X1 4 X2 2 Z 14Q3 X1 2 X2 3 Z 10Q4 X1 0 X2 3 Z 6 二 线性规划问题解的存在情况 1 存在唯一最优解 如例1 2 有无穷多最优解 若将例1目标函数变为maxz 2x1 4x2 则问题变为存在无穷多最优解 如图 3 有无界解 可行域可伸展到无穷 由此目标函数值也可增大至无穷 这种情况下问题的最优解无界 产生无界解的原因是由于在建立实际问题的数学模型时遗漏了某些必要的资源约束条件 例如 maxZ 2x1 2x2s t 2x1 x2 4x1 x2 2x1 x2 0 0 x1 x2 例如 minZ 60 x1 50 x22x1 4x2 803x1 2x2 60 x1 x2 0 0 x1 x2 无界不一定无最优解 X1 10 x2 15Z 1350 模型的约束条件之间存在矛盾 建模时有错误 4 无可行解 可行域为空集 例如 maxZ x1 2x2 x1 x2 22x1 x2 4x1 x2 0 0 x1 x2 三 由图解法得到的启示 图解法虽只能用来求解只具有两个变量的线性规划问题 但它的解题思路和几何上直观得到的一些概念判断 对下面要讲的单纯形法有很大启示 1 求解线性规划问题时 解的情况有 唯一最优解 无穷多最优解 无界解 无可行解 见下页图示所示 2 若线性规划问题的可行域存在 则可行域是一个凸集 3 若线性规划问题的最优解存在 则最优解或最优解之一 如果有无穷多的话 一定是可行域的凸集的某个顶点 4 解题思路是 先找出凸集的任一顶点 计算在顶点处的目标函数值 比较周围相邻点的目标函数值是否比这个值大 如果为否 则该顶点就是最优解的点或最优解的点之一 否则转到比这个点的目标函数值更大的另一顶点 重复上述过程 一直到找出使目标函数值达到最大的顶点为止 d 可行域无界 e 可行域无界 f 可行域为空集多个最优解目标函数无界无可行解 a 可行域有界 b 可行域有界 c 可行域无界唯一最优解多个最优解唯一最优解 四 线性规划问题的标准形式 一 线性规划问题标准形式 为了使线性规划问题的解法标准 就要把一般形式化为标准形式 其一般形式如下所示 某厂利用A B两种原料 生产甲 乙两种产品 有关数据如下 练习题 用图解法求解下列问题 产品名称 甲乙 单位产品消耗原料 原料名称 可供利用的原料数量 T 日 68 221 AB 产品售价 千元 T 32 根据市场调查 有如下资料 1 乙产品的需求量至多2T 日 2 乙产品的需求量比甲产品的需求量至多大1T 日 求该厂产值最大的生产方案 maxZ 3x1 2x2x1 2x2 62x1 x2 8x2 2x2 x1 1x1 x2 0 0 x1 x2 X1 10 3 x2 4 3Z 12 67 用MATLAB优化工具箱解线性规划 命令 x linprog c A b 2 模型 minz cX 命令 x linprog c A b Aeq beq 注意 若没有不等式 存在 则令A b 命令 1 x linprog c A b Aeq beq VLB VUB 2 x linprog c A b Aeq beq VLB VUB X0 注意 1 若没有等式约束 则令Aeq beq 2 其中X0表示初始点 4 命令 x fval linprog 返回最优解 及 处的目标函数值fval 解编写M文件xxgh1 m如下 c 0 4 0 28 0 32 0 72 0 64 0 6 A 0 010 010 010 030 030 03 0 02000 0500 00 02000 050 000 03000 08 b 850 700 100 900 Aeq beq vlb 0 0 0 0 0 0 vub x fval linprog c A b Aeq beq vlb vub ToMatlab xxgh1 解 编写M文件xxgh2 m如下 c 634 A 010 b 50 Aeq 111 beq 120 vlb 30 0 20 vub x fval linprog c A b Aeq beq vlb vub ToMatlab xxgh2 整数规划的模型 分支定界法 割平面法 0 1整数规划 蒙特卡洛方法 例一 合理下料问题设用某型号的圆钢下零件A1 A2 Am的毛坯 在一根圆钢上下料的方式有B1 B2 Bn种 每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量 如表所示 怎样安排下料方式 使得即满足需要 所用的原材料又最少 设 xj表示用Bj j 1 2 n 种方式下料根数模型 整数规划一般形式 依照决策变量取整要求的不同 整数规划可分为纯整数规划 全整数规划 混合整数规划 0 1整数规划 部分或者全部为整数 纯整数规划 所有决策变量要求取非负整数 这时引进的松弛变量和剩余变量可以不要求取整数 全整数规划 除所有决策变量要求取非负整数外 系数aij和常数bi也要求取整数 这时引进的松弛变量和剩余变量也必须是整数 混合整数规划 只有一部分的决策变量要求取非负整数 另一部分可以取非负实数 0 1整数规划 所有决策变量只能取0或1两个整数 从数学模型上看整数规划似乎是线性规划的一种特殊形式 求解只需在线性规划的基础上 通过舍入取整 寻求满足整数要求的解即可 但实际上两者却有很大的不同 通过舍入得到的解 整数 也不一定就是最优解 有时甚至不能保证所得到的解是整数可行解 例 设整数规划问题如下 首先不考虑整数约束 得到线性规划问题 一般称为松弛问题 且为整数 用图解法求出最优解x1 3 2 x2 10 3且有Z 29 6 x1 x2 3 3 3 2 10 3 现求整数解 最优解 如用 舍入取整法 可得到4个点即 1 3 2 3 1 4 2 4 显然 它们都不可能是整数规划的最优解 按整数规划约束条件 其可行解肯定在线性规划问题的可行域内且为整数点 故整数规划问题的可行解集是一个有限集 如图所示 因此 可将集合内的整数点一一找出 其最大目标函数的值为最优解 此法为完全枚举法 如上例 其中 2 2 3 1 点为最大值 Z 4 目前 常用的求解整数规划的方法有 分支定界法和割平面法 对于特别的0 1规划问题采用隐枚举法 0 1型整数规划 0 1变量及其应用 0 1变量可表示逻辑关系 x 1 采取方案 x 0 不采取方案 若需要从p个约束条件中 恰好选择q个 则可引入p个0 1变量 yi 0 选择i个约束条件 yi 1 不选择i个约束条件那么 约束条件组为 Mi是充分大的数 2 0 1型整数规划的解法 n个变量有2n种组合 采用隐枚举法 列出2n种组合 先求出一个可行解 计算目标函数值 作为当前的最优解 对于其它组合 先计算目标函数值 若不如当前的最优解 就不必检验它的可行性否则 如果是可行解 则把更新为当前的最优解 采用分支定界法 搜索更快 蒙特卡洛方法 在前面介绍的分枝定界方法 算法的每一个计算步骤都是固定的 而且可以保证求得最优解 但是 当整数线性规划的决策变量数目很大时 分枝定界法的代价可能是巨大的 特别是当整数规划本身是非线性的时候 尚未有一种成熟而有效的求解方法 因为非线性规划本身的通用有效解法尚未找到 然而 由于整数规划解的数目是有限的 于是为枚举法提供了方便 当然 当决策变量数目很大 取值范围很宽情况下 企图用完全搜索 即穷举法 计算出最优值是不现实的 但是应用蒙特卡洛算法 在一定的计算量下 完全可以得出一个满意解 例已知非线性整数规划为 对该问题 目前尚无有效方法求出准确的最优解 如果用穷举法 完全搜索 试探 共需计算1005 1010个点 计算量非常大 然而概率理论能够保证 应用蒙特卡洛方法随机计算106个点 便可找到问题的满意解 解 用蒙特卡洛方法求解这个问题必须借助计算机来实现 运行程序5次 可得如