运筹学-线性规划及单纯形法复习题.ppt

第1章线性规划及单纯形法 LinearProgrammingandSimplexMethod 1一般线性规划问题及其数学模型 2图解法 3单纯形法原理 5单纯形法的进一步讨论 7线性规划应用 4单纯形法的计算步骤 6数据包络分析 1 为了完成一项任务或达到一定的目的 怎样用最少的人力 物力去完成或者用最少的资源去完成较多的任务或达到一定的目的 这个过程就是规划 例一 有一正方形铁皮 如何截取x使容积为最大 x a 此为无约束极值问题 一 问题的提出 1一般线性规划问题及其数学模型 2 例二 已知资料如表所示 问如何安排生产才能使利润最大 或如何考虑利润大 产品好销 模型 maxZ 2x1 3x2 x1 0 x2 0 s t 2x1 2x2 12x1 2x2 84x1 164x2 12 此为带约束的极值问题 3 问题中总有未知的变量 需要我们去解决 要求 有目标函数及约束条件 一般有非负条件存在 由此组成规划数学模型 如果在规划问题的数学模型中 变量是连续的 数值取实数 其目标函数是线性函数 一次方 约束条件是有关变量的线性等式或不等式 这样 规划问题的数学模型是线性的 反之 就是非线性的规划问题 二 数学模型1 4 目标函数 约束条件 2 线性规划数学模型的一般形式 5 也可以记为如下形式 目标函数 约束条件 6 如将上例用表格表示如下 设变量 7 向量形式 8 矩阵形式 9 3 线性规划的标准形式 10 一般有两种方法 图解法单纯形法 两个变量 直角坐标三个变量 立体坐标 适用于任意多个变量 但需将一般形式变成标准形式 4 线性规划问题的解 一 求解方法 11 1 解的概念 可行解 满足约束条件 的解为可行解 所有解的集合为可行解的集或可行域 最优解 使目标函数 达到最大值的可行解 基 B是矩阵A中m m阶非奇异子矩阵 B 0 则B是一个基 则称Pj j 12 m 为基向量 Xj为基变量 否则为非基变量 二 线性规划问题的解 12 基本解 满足条件 但不满足条件 由基B决定的解 最多为个 基本可行解 满足非负约束条件的基本解 简称基可行解 可行基 对应于基可行解的基称为可行基 非可行解 可行解 基解 基可行解 13 例题基可行解说明 maxZ 70X1 120X2P1P2P3P4P59X1 4X2 X3 360941004X1 5X2 x4 200A 450103X1 10X2 x5 300310001Xj 0j 1 2 5这里m 3 n 5 Cmn 10 14 基 p3 p4 p5 令非基变量x1 x2 0 则基变量x3 360 x4 200 x5 300 可行解基 p2 p4 p5 令非基变量x1 0 x3 0基变量x2 90 x4 250 x5 600 非可行解基 p2 p3 p4 令非基变量x1 x5 0 则基变量x2 30 x3 240 x4 50 可行解 15 例一 2图解法 16 0 12345678 123456 作图 最优解 x1 4 x2 2 有唯一最优解 Z 14 x2 x1 42 17 例二 例三 无穷多最优解 无界解 x1 x1 x2 x2 18 x1 x2 无可行解 例四 图解法的解题思路和几何上直观得到的一些结论对于求解一般的线性规划有什么启示 19 3单纯形法原理 1 20 2 几个 1 21 引理标准形线性规划问题的可行解X x1 x2 xn T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的 22 定理2标准形线性规划的基本可行解X对应可行域 凸集 的顶点 极点 证明 1 若X不是基本可行解 X不是可行域的顶点 不失一般性 假设X的前m个分量正 故有 由引理知P1 P2 Pm线性相关 即存在一组不全为零的数 i i 1 2 m 使得 1P1 2P2 mPm 0 2 1 于是有 x1 1 P1 x2 2 P2 xm m Pm b 3 其中 的选取使得对所有xi i 0 i 1 2 m 由 3 式可知 23 X 1 x1 1 x2 2 xm m 0 0 T X 2 x1 1 x2 2 xm m 0 0 T 是线性规划的可行解 即为可行域中的点 但是点 是X 1 和X 2 的凸组合 所以不是极点 顶点 2 若X不是可行域的顶点 X不是基本可行解 如果X不是可行域内的点 即X不是可行解 当然X不是基本可行解 不妨设X是一个可行解 X x1 x2 xr 0 0 T且 但不是可行域的顶点 由于可行域是凸集 所以存在两个不同的点Y和Z 使得X aY 1 a Z 其中0 a 1 24 当xj 0时 必有yj zj 0 因此 而yj zj不全为零 故P1 P2 Pr线性相关 X不是基本可行解 定理3若线性规划有最优解 则一定有最优基本可行解 证明 见P20 21 略 25 3 初始基本可行解的确定 方法一 对于非标准形线性规划通过引入人工变量法 松驰变量或剩余变量 产生初始的基本可行解 方法二 对于标准形线性规划 通过增广矩阵的初等行变换产生一个m阶单位阵 从而得到一个初始的基本可行解 方法三 两阶段法 将在 5中讲述 26 4 初始基本可行解的转换 假设标准形线性规划的系数矩阵的秩为m 且前m列线性无关 则线性方程组的增广矩阵通过有限次初等行变换 前m列可以变换成m阶单位阵 P1P2PmPm 1PjPnb 这说明原来的第1 第2 第m列P1 P2 Pm是一个基 非基列 27 上式两边同乘以一个待确定的正数 再与式 相加 得到 记 如果基本解X0是基本可行解 并希望X 1 也是一个基本可行解 则对所有i 1 2 m 且这m个不等式中至 少要有一个等式成立 如果所有的a ij 0 则 可以取任意正数 解无界 无法构造一个新的基本可行解 只要存在某个a ij 0 令 28 则X 1 中正分量最多m个 P1 Pl 1 Pl 1 Pm Pj线性无关 构成一组新基 得到新的基本可行解X 1 5 最优基本可行解的判别 记 检验数 你可以得出什么结论 29 结论 1 当所有检验数小于或等于0时 现有基本可行解为最优解 2 基变量的检验数都等于0 3 当所有非基变量的检验数小于或等于0 且某个非基变量xj的检验数等于0 以xj为进基变量 求出的 0时 目标函数值不变 可以得到另一个最优基本可行解 从而该线性规划有无数多个最优解 4 如果存在某个非基变量对应的检验数 j 0 且Pj列的分量a ij都小于或等于0 则线性规划存在无界解 5 如果存在某个非基变量对应的检验数 j 0 且Pj列的分量a ij部分为正 则可以确定 和旋转主元a lj 选择Pj为进基 30 列 Pl为离基列 利用矩阵的初等行变换 将a lj变成1 Pj列的其它元素变成0 构造一组新基 求出相应的新的基本可行解 31 一 基本思想 将模型的一般形式变成标准形式 再根据标准型模型 从可行域中找一个基本可行解 并判断是否是最优 如果是 获得最优解 如果不是 转换到另一个基本可行解 当目标函数达到最大时 得到最优解 二 线性规划模型的标准形式 4单纯形法的计算步骤 32 例一 将下列线性规划问题化为标准形式 为无约束 无非负限制 33 解 用替换 且 将第3个约束方程两边乘以 1 将极小值问题反号 变为求极大值 标准形式如下 引入变量 34 找出一个初始可行解 是否最优 转移到另一个基本可行解 最优解 是 否 循环 核心是 变量迭代 结束 三 求解步骤 35 四 单纯形表 36 例题 37 5 单纯形法的进一步讨论 1 构造初始基本可行解的大M法 模型1 模型2 其中M为充分大的正数 38 定理 如果 是模型2的最优解 则当Y 0时 X 一定是模 型1的最优解 当Y 0时 模型1没有可行解 反之 如果X 是模型1的最优解 则 是模型2的最 优解 证明 设 是模型2的最优解 则 显然 如果X是模型1的可行解 则 X 0 T是模型2的可行解 即X 是模型1的可行解 由于Z CX CX METY CX MET0 故X 是模型1的最优解 如果Y 0 假设模型1有可行解X 则因 X 0 T是模型2的可行解 39 则有W CX METY CX 对于充分大的M不可能成立 因此模型1没有可行解 后一结论比较显然 请同学们自己证明 2 构造初始基本可行解的二阶段法 模型1 模型3 40 定理 如果 是模型3的最优基本可行解 则当Y 0时 X 一定是模型1的基本可行解 当Y 0时 模型1没有可行解 课堂思考 1 该定理与前一定理有何不同 2 如何证明 3 如何运用该定理求解标准形线性规划 3 求解标准形线性规划的流程 41 A b C 42 例题 43 44 作业 45 46 47 48 一 问题的提出实际问题中常常会碰到测定一组同类可比机构综合运作效率的问题 例如 对学校 医院 银行 法院 连锁店等系统内各分支机构部门运作效率的评价 由于测定指标的多样化 所以需要有一种科学的方法能够将各项指标进行综合归纳 避免诸如评分类方法在操作过程中过多的人为因素作用 DEA DataEnvelopmentAnalysis 方法采用的是一种相对评价技术 它能够对被测定部门的工作效果度量 从而对系统中参评机构的运作效率评定优劣 数据包络分析 DEA 49 一个评价问题示例 例 某城市有四家综合性医院 中心医院 市立医院 省医院和医大附属医院 现有他们的管理部门要对该四家医院的工作效率进行考评 测定哪家医院效率更高 50 评价一个任何一个组织机构的工作效果 通常都是经过对其 输入量 和 输出量 的比较而衡量其运作效率的 并且对 好 坏 的认定必须能够确定出一个参照标准 或者是借助于与同类机构的比较分析才能实现 否则 评价无意义 DEA方法的建模思想就是通过对各机构的输入 输出量的比较分析后 建立一个 较理想 的 复合机构 高效率 作为评价的标准 将被评机构与该 复合机构 进行对比分析 设定 复合机构 的输出量不小于某一参评机构的输出量 那么它的输入量与该参评机构输入量的比较则可反映被评机构的效率情况 如果 复合机构 用较小的输入量即可获得同样或者较多的输出 则可认定该被评机构是低效的 而按此比值量的大小就可以对各个参评机构的运作效率进行排序 二 建模思想 51 MinZ Ei i 1 n 对第i机构评价ST wi 1 权重限制 wi Oit Oit t 1 T 输出约束 wi Iis Ei Iis s 1 S 输入约束wi 0 Ei 0 变量符号限制 三 模型结构 i 1 n n i 1 n i 1 52 机构1输入指标 机构2输入指标 机构n输入指标 w1 w2 wn 复合机构 机构1输出指标 机构2输出指标 机构n输出指标 w1 w2 wn 输入 输出 DEA方法原理示意图 53 其中Ei 效率指数 复合机构 需要的输入为第i机构输入的百分比 wi 权系数 第i机构在 复合机构 中所占的权重 Oit 第i机构第t项输出指标的数值 Iis 第i机构第s项输入指标的数值 T 输出指标总数量 S 输入指标总数量 n 参评机构总数 上述模型为LP模型 若参评机构为n个 要计算每个机构的效率指数 则必须建立起n个LP模型 对第i个机构而言 若Ei 1 则第i个机构为低效 54 四 应用示例 1 输入 输出指标的设计在评价时首先要选择输入 输出指标 通常应该选择数量化的指标 且指标不宜过多 能够切实反映问题即可 本例中选择 55 输入 输出指标统计数值 输入指标统计值 医护人员数量285 20162 30275 70210 40年经费数额123 80128 70348 50154 10床位总数106 7264 21104 10104 04 指标中心医院市立医院省医院医大附属医院 输出指标统计值 指标中心医院市立医院省医院医大附属医院 就诊患者人数48 1434 6236 7233 16住院医疗人数43 1027 1145 9856 46培训护士人数253148175160培训实习医生人数41272384 56 2 建立模型 按DEA思想 首先应该构造一个 复合医院 该 复合医院 可以看作是从被评价医院种选择出 优质资产 输入 重组 而成 所以具有最优的效率 因此 首先应确定各医院 资产 在 复合医院 中的比重 比如 我们先来看省医院的运作效率模型 设w1 中心医院在复合医院中所占比重w2 市立医院在复合医院中所占比重w3 省医院在复合医院中所占比重w4 医大附属医院在复合医院中所占比重 则其DEA模型如下 57 省医院运作效率评价的DEA模型 minE st w1 w2 w3 w4 1 48 14w1 34 62w2 36 72w3 33 16w4 36 7243 10w1 27 11w2 45 98w3 56 46w4 45 98253w1 148w2 175w3 160w4 17541w1 27w2 23w3 84w4 23 285 20w1 162 30w2 275 70w3 210 40w4 275 70E123 80w1 128 70w2 348 50w3 154 10w4 348 50E106 72w1 64 21w2 104 10w3 104 04w4 104 10Ewi 0 i 1 2 3 4 E 0 输出 输入 权数 变量符号 58 最优解为 w1 0 212 w2 0 261 w3 0 000 w4 0 527E 0 905 结论分析 若E 1 则 复合医院 需要与省医院同样多的资源 方能得到不低于省医院产出量的数值 若E 1 则 复合医院 可用较少的资源 获得不低于省医院产出的数值 所以可判定省医院是低效的 问题 若E 1 是否可判定省医院一定是最优的 59 医护人员数量213 7 年经费数额141 05 床位总数94 21 就诊患者人数36 72 住院医疗人数45 98 培训护士人数176 6 培训实习医生60 复合医院 输入 输出 复合医院实际的输入 输出指标构成示意图 60 7 应用举例及Matlab求解法 例1 工业原料的合理利用 要制作100套钢筋架子 每套有长2 9m 2 1m和1 5m的钢筋各一根 已知原料长7 4m 应如何切割 使用原料最节省 扔掉的料头最小 考察如下方案的综合使用 61 解 该问题的线性规划数学模型如下 该问题要用单纯形法求解 需要添加人工变量 62 下面我们考虑如何用Matlab语言来求解线性规划问题 在Matlab语言中 标准输入形式要求目标函数为极小 约束条件为等于或小于等于 并使用矩阵或列向量的形式给出 其标准形为 利用大M法求解 得到 63 上述线性规划问题 用Matlab语言来改写 则有 64 在Matlab语言中 以矩阵作为基本计算单位 向量可以看作是矩阵的特殊情况 用 表示矩阵的分行 用 表示两个元素的分隔 用 表示矩阵整体 65 在上述式子中 c是目标函数中的系数向量 A为约束方程组 不等式组 的系数矩阵 b为约束方程组 不等式组 的右端列向量 XLB为决策向量X的下限 XUB为决策向量X的上限 x0为决策向量X的初值 nEq为约束方程中等式的个数 各参量在Matlab命令中使用的名称可以根据需要而不同 但是出现的顺序不能发生改变 66 对于前述的线性规划问题 我们已经给出了c A b 并且我们知道约束条件中等式有三个 即nEq 3 但是我们还没有给出决策向量的上限 下限和初值 决策向量的上限 下限和初值我们可以根据实际情况自己进行估计 在该问题中 我们可以设上限为每种方案最多使用100根钢筋 最少使用0根 初值可以设为全都取0 67 因此我们输入的屏幕显示为 回车后得到