线性规划及单纯形法.ppt

2020 2 10 1 运筹学 经济学院 2020 2 10 2 课堂要求 1 要求同学们上课不迟到 不早退 不得旷课 2 上课认真听讲 要求每位同学都做笔记 3 上课不得讲话 看书 玩手机等与课堂无关的内容 4 课后要求独自完成作业 不得抄袭或不做课后作业 2020 2 10 3 参考资料 1 胡运权主编 运筹学教程 第三版 清华大学出版社 2 周华任主编 运筹学解题指导 清华大学出版社 3 运筹学习题集 修订版 清华大学出版社 4 熊伟编著 运筹学 机械工业出版社 5 运筹学 数据 模型 决策 科学出版社 2020 2 10 4 教学计划以线性规划和运输问题为讲授重点 其它部分作为选讲内容 教学方法以授课为主 案例分析与上机演示为辅 而讲课中主要培养用最优化方法解决实际问题的能力 教学计划与方法 2020 2 10 5 前言 运筹学简介 运筹学是管理科学的重要理论基础和应用手段 是管理专业的重要专业基础课程之一 运筹学根据管理问题的环境条件和决策要求 建立相应的数学模型 利用数学模型对实际问题进行分析和求解 经过分析和比较 得到适合实际问题的方案 求解结果 求解结果 建立模型 求解模型 修改模型 求解结果 修改模型 2020 2 10 6 运筹学是在第二次世界大战中诞生和发展起来的 由于战争的需要 英国和美国招募了一批年轻的科学家和工程师 在军队将军的领导下研究战争中的问题 例如大规模轰炸的效果 搜索和攻击敌军潜水艇的策略 兵力和军需物质的调运等等 这些研究在战争中取得了很好的效果 当时英国把这些研究成为 作战研究 英文是OperationalResearch 在美国称为OperationsResearch 2020 2 10 7 战后这些研究成果逐渐公开发表 这些理论和方法被应用到经济计划 生产管理领域 也产生了很好的效果 这样 OperationsResearch就转义成为 作业研究 我国把OperationsResearch译成 运筹学 非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义 运筹学的内容十分广泛 包括线性规划 整数规划 动态规划 非线性规划 图论与网络优化 排队论 决策理论 库存理论等 在本课程中 结合管理学科的特点 主要介绍线性规划和运输问题 2020 2 10 8 线性规划 数学规划 非线性规划 整数规划 动态规划 学科内容 多目标规划 双层规划 组合优化 最优计数问题 网络优化 排序问题 统筹图 随机优化 对策论 排队论 库存论 决策分析 可靠性分析 运筹学的主要内容 2020 2 10 9 目录 第一章线性规划及单纯形法第二章对偶问题第三章灵敏度分析第四章线性规划的建模与应用第五章运输问题 2020 2 10 10 第一章线性规划 线性规划问题线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解 基础可行解单纯形表 2020 2 10 11 线性规划问题 生产计划问题配料问题背包问题运输问题指派问题 2020 2 10 12 1 生产计划问题 ProductionPlanning 某工厂拥有A B C三种类型的设备 生产甲 乙 丙 丁四种产品 每件产品在生产中需要占有的设备机时数 每件产品可以获得的利润以及三种设备可利用的时数如下表所示 求使得总利润最大的生产计划 2020 2 10 13 设四种产品的产量分别为x1 x2 x3 x4 总利润为z 线性规划模型为 maxz 5 24x1 7 30 x2 8 34x3 4 18x4s t 1 5x1 1 0 x2 2 4x3 1 0 x4 20001 0 x1 5 0 x2 1 0 x3 3 5x4 80001 5x1 3 0 x2 3 5x3 1 0 x4 5000 x1 x2 x3 x4 0 目标函数 约束条件 变量非负约束 这个问题的最优解为 x1 294 12件 x2 1500件 x3 0 x4 58 82件最大利润为 z 12737 06元 2020 2 10 14 2 配料问题 MaterialBlending 某工厂要用四种合金T1 T2 T3 T4为原料 经熔炼成为新的不锈钢G 这四种原料含铬 Cr 锰 Mn 和镍 Ni 的含量 这四种原料的单价以及新的不锈钢G所要求的Cr Mn Ni的最低含量 如下表 要求配100公斤不锈钢G 并假定在配制过程中没有损耗 求使得总成本最低的配料方案 2020 2 10 15 minz 115x1 97x2 82x3 76x4s t 3 21x1 4 53x2 2 19x3 1 76x4 320Cr的含量下限约束2 04x1 1 12x2 3 57x3 4 33x4 210Mn的含量下限约束5 82x1 3 06x2 4 27x3 2 73x4 430Ni的含量下限约束x1 x2 x3 x4 100物料平衡约束x1 x2 x3 x4 0 设四种原料分别选取x1 x2 x3 x4公斤 总成本为z 这个问题的最优解为 x1 26 58 x2 31 57 x3 41 84 x4 0 公斤 最低成本为z 9549 87元 问题 如果某一种成分的含量既有下限 又有上限怎么办 2020 2 10 16 3 背包问题 KnapsackProblem 一只背包最大装载重量为50公斤 现有三种物品 每种物品数量无限 每种物品每件的重量 价格如下表 求背包中装入每种物品各多少件 使背包中物品总价值最高 2020 2 10 17 设三种物品的件数各为x1 x2 x3件 总价值为z maxz 17x1 72x2 35x3s t 10 x1 41x2 20 x3 50 x1 x2 x3 0 x1 x2 x3为整数这是一个整数规划问题 IntegerProgramming 这个问题的最优解为 x1 1件 x2 0件 x3 2件 最高价值z 87元 2020 2 10 18 4 运输问题 Transportation 某种物资从两个供应地A1 A2运往三个需求地B1 B2 B3 各供应地的供应量 各需求地的需求量 每个供应地到每个需求地每吨物资的运输价格如下表 求总运费最低的运输方案 2020 2 10 19 35吨 25吨 10吨 30吨 20吨 2020 2 10 20 设从两个供应地到三个需求地的运量 吨 如下表 2020 2 10 21 minz 2x11 3x12 5x13 4x21 7x22 8x23s t x11 x12 x13 35供应地A1x21 x22 x23 25供应地A2x11 x21 10需求地B1x12 x22 30需求地B2x13 x23 20需求地B3x11 x12 x13 x21 x22 x23 0 2020 2 10 22 这个问题的最优解表示如下 最小总运费为 z 3 30 5 5 4 10 8 15 275元 30吨 5吨 10吨 15吨 2020 2 10 23 5 指派问题 AssignmentProblem 有n项任务由n个人完成 每项任务交给一个人 每人都有一项任务 由i个人完成j项任务的成本 或效益 为cij 求使总成本最小 或总效益最大 的分配方案 设 2020 2 10 24 张 王 李 赵四位老师被分配教语文 数学 物理化学四门课程 每位老师教一门课 每门课由一位老师教 根据这四位老师以往教课的情况 他们分别教四这门课程的平均成绩如下表 要求确定哪一位老师上哪一门课 使四门课的平均总成绩最高 2020 2 10 25 设 maxz 92x11 68x12 85x13 76x14 82x21 91x22 77x23 63x24 83x31 90 x32 74x33 65x34 93x41 61x42 83x43 75x44s t x11 x12 x13 x14 1 1 x21 x22 x23 x24 1 2 x31 x32 x33 x34 1 3 x41 x42 x43 x44 1 4 x11 x21 x31 x41 1 5 x12 x22 x32 x42 1 6 x13 x23 x33 x43 1 7 x14 x24 x34 x44 1 8 xij 0 1 2020 2 10 26 最优解为 x14 1 x23 1 x32 1 x41 1 maxz 336即张老师教化学 王老师教语文 李老师教数学 赵老师教语文 四门课的总分可以达到336分 2020 2 10 27 线性规划模型 min max z c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 Free 线性规划模型的目标函数必须是变量的线性函数 约束条件必须是变量的线性等式或不等式 如右的问题就不是线性规划问题 2020 2 10 28 线性规划的标准形式 目标函数为极大化 约束条件全部为等号约束 右端常数项均为非负 所有变量全部是非负的 这样的线性规划模型称为标准形式maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 2020 2 10 29 线性规划模型用矩阵和向量表示 maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 2020 2 10 30 线性规划模型用矩阵和向量表示 续 因此 线性规划模型可以写成如下矩阵和向量的形式 MaxZ CTXs t AX bX 0 2020 2 10 31 线性规划模型总结 线性规划模型的结构目标函数 max min约束条件 变量符号 0 0 Free线性规划的标准形式目标函数 max约束条件 右端常数项 0变量符号 0 MaxZ CTXs t AX bX 0 2020 2 10 32 线性规划解的概念 设线性规划 2020 2 10 33 举例 1 maxZ 8x1 10 x22x1 x2 11x1 2x2 10 x1 x2 0确定下列向量中哪些是解 可行解 求出可行域 2020 2 10 34 图解法 对于模型中只有两个变量的线性规划问题 可以通过在平面上作图的方法求解 一个线性规划问题有解 是指能找出一组xj j 1 2 n 满足约束条件 称这组xj为问题的可行解 通常线性规划问题总是含有多个可行解 称全部可行解的集合为可行域 可行域中使目标函数为最优的可行解为最优解 图解法的目的是判别线性规划问题的求解结局和存在最优解的条件下求出最优解 2020 2 10 35 图解法的步骤 1 建立具有合适刻度单位的坐标系统 2 对每一约束条件建立直线 从而确定可行域 3 确定目标函数等值线的移动方向 4 求出最优解 最优解为等值线在移动过程中与可行域的最后交点 2020 2 10 36 线性规划的图解 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 z 6 z 3 z 9 z 12 问题 1 线性规划的最优解是否可能位于可行域的内部 2 线性规划的最优解是否可能位于可行域的边界上 2020 2 10 37 举例 1 maxZ 2x1 x25x2 156x1 2x2 24x1 x2 5x1 x2 0唯一最优解2 maxZ x1 x2 2x1 x2 4x1 x2 2x1 x2 0无界解 3 maxZ 3x1 9x2x1 3x2 22 x1 x2 4x1 x2 0无穷多最优解 4 maxZ x1 x2x1 x2 12x1 2x2 4x1 x2 0无解 2020 2 10 38 线性规划可行域和最优解的几种情况 1 可行域封闭唯一最优解 2 可行域封闭多个最优解 3 可行域开放唯一最优解 4 可行域开放多个最优解 5 可行域开放目标函数无界 6 无可行解 2020 2 10 39 标准形式 2020 2 10 40 线性规划问题的标准化 极小化目标函数转化为极大化小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束右端常数项小于等于0的标准化变量小于等于0的标准化变量没有符号限制 Free 的标准化 2020 2 10 41 minz 2x1 3x2 x3令z z z 2x1 3x2 x3新的目标函数maxz 2x1 3x2 x3取得极大化的最优解时 这个最优解同时使原目标函数值取得最小化的最优解 但两个问题最优解的目标函数值相差一个负号 极小化目标函数问题转化为极大化目标函数 2020 2 10 42 例如 对于以下两个线性规划问题 minz 2x1 3x2s t x1 x2 3x2 1 A x1 x2 0 maxz 2x1 3x2s t x1 x2 3x2 1 B x1 x2 0 它们的最优解都是x1 2 x2 1 但 A 的最小化的目标函数值为minz 7 B 的最大化的目标函数值为maxz 7 2020 2 10 43 2x1 3x2 4x3 5引进松弛变量 Slackvariable x4 5 2x1 3x2 4x3 把松弛变量x4加在约束条件左边 就可以将小于等于约束变为等式 2x1 3x2 4x3 x4 5由此可以知道 松弛变量x4 0 如果有一个以上小于等于约束 要对于每一个约束引进不同的松弛变量 例如 2x1 3x2 4x3 53x1 2x2 5x3 8在两个约束中分别引进松弛变量x4 x5 02x1 3x2 4x3 x4 53x1 2x2 5x3 x5 8 小于等于约束条件转化为等号约束 2020 2 10 44 将不等式约束变为等式约束 例如 2x1 3x2 4x3 53x1 2x2 5x3 8在两个约束的左边分别减去剩余变量x4 x5 02x1 3x2 4x3 x4 53x1 2x2 5x3 x5 8 大于等于约束条件转化为等号约束 2020 2 10 45 右端常数项小于等于0的标准化 当右端常数项为小于等于0时 如 2x1 3x2 4x3 4只需不等式两边同乘以 1 不等式改好就可以了 2x1 3x2 4x3 4 2020 2 10 46 minz x1 2x2 3x3s t 2x1 3x2 4x3 53x1 2x2 5x3 8x1 0 x2 0 x3 0maxz x1 2x2 3x3s t 2x1 3x2 4x3 x4 53x1 2x2 5x3 x5 8x1 0 x2 0 x3 x4 x5 0令x2 x 2 x 2 0 代入模型maxz x1 2x 2 3x3s t 2x1 3x 2 4x3 x4 53x1 2x 2 5x3 x5 8x1 0 x 2 0 x3 x4 x5 0 变量小于等于0的的标准化 2020 2 10 47 没有符号限制的变量 用两个非负变量之差表示 例如 minz x1 2x2 3x3s t 2x1 3x2 4x3 53x1 2x2 5x3 8x1 0 x2 free x3 0先将目标函数转化为极大化 并在约束中引进松弛变量 把不等式约束变为等式 Maxz x1 2x2 3x3s t 2x1 3x2 4x3 x4 53x1 2x2 5x3 x5 8x1 0 x2 free x3 x4 x5 0 变量没有符号限制 Free 的标准化 2020 2 10 48 Maxz x1 2x2 3x3s t 2x1 3x2 4x3 x4 53x1 2x2 5x3 x5 8x1 0 x2 free x3 x4 x5 0然后 令x2 x2 x2 其中x2 x2 0 代入模型 消去x2Maxz x1 2 x 2 x 2 3x3s t 2x1 3 x 2 x 2 4x3 x4 53x1 2 x 2 x 2 5x3 x5 8x1 x 2 x 2 x3 x4 x5 0整理 得到标准形式 Maxz x1 2x 2 x 2 3x3s t 2x1 3x 2 3x 2 4x3 x4 53x1 2x 2 2x 2 5x3 x5 8x1 x 2 x 2 x3 x4 x5 0 2020 2 10 49 练习 minz 2x1 x2 4x3s t x1 x2 x3 33x1 x2 2x3 6x1 3x2 4x3 4x1 0 x3 0 2020 2 10 50 标准化的线性规划问题 有n个变量 m个约束 maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0令其中n m个变量等于零 如果剩下的m个变量的系数矩阵的行列式不等于0 这个m m的矩阵称为线性规划的一个基 等于0的n m个变量称为非基变量 m个变量称为基变量 线性规划的基本概念 基 基解 基可行解 极点 2020 2 10 51 求解m m的线性方程组 得到基变量的一组解 连同等于0的非基变量这n个变量的值称为线性规划的一个基解 如果一个基解中的所有变量都是非负的 这个基解称为基可行解 线性规划的基可行解就是可行域的极点 2020 2 10 52 解的可行性和松弛变量符号的关系 maxz 2x1 3x2s t x1 x2 4 1 x1 x2 1 2 x1 x2 0 maxz 2x1 3x2s t x1 x2 x3 4 x1 x2 x4 1x1 x2 x3 x4 0 引进松弛变量 A 1 2 5 满足所有约束条件 x3 0 5 x4 0 5B 2 1 满足 1 不满足 2 x3 1 x4 2C 1 5 3 不满足 1 满足 2 x3 0 5 x4 0 5D 3 2 不满足 1 和 2 x3 1 x4 2结论 如果一个解满足一个约束条件 相应的松弛变量大于等于0 如果一个解不满足一个约束条件 相应的松弛变量小于0 2020 2 10 53 1 找出下述线性规划问题的全部基解 指出其中的基可行解 并确定最优解 maxZ 2x1 3x2x1 x3 5x1 2x2 x4 10 x2 x5 4xi 0 2020 2 10 54 解 最优解为x1 2 x2 4 x3 3 Z 19 2020 2 10 55 maxz x1 2x2s t x1 x2 3x2 1x1 x2 0 maxz x1 2x2s t x1 x2 x3 3x2 x4 1x1 x2 x3 x4 0 x1 0 x2 0 x3 3 x4 1基可行解 x1 0 x4 0 x2 1 x3 2基可行解 x2 0 x3 0 x1 3 x4 1基可行解 x3 0 x4 0 x1 2 x2 1基可行解 x1 0 x3 0 x2 3 x4 2是基解 但不是可行解 O A B x3 0 x4 0 x2 0 x1 0 C D 可行域 2020 2 10 56 凸集和极点 1 凸集如果集合C中任意两点x1 x2 其连线上的所有点也都是集合C中的点 则称C为凸集 其中x1 x2的连线可以表示为 x1 1 x2 0 1 数学解析式为 x1 C x2 C 有 x1 1 x2 C 0 1 则C为凸集 2020 2 10 57 2 极点如果集合C中任意两点x1 x2 使x为这两点连线上的一个点 对任何x1 C x2 C 不存在x x1 1 x2 0 1 则称x为凸集的顶点 2020 2 10 58 几个基本定理 定理1 若线性规划问题存在可行解 则问题的可行域是凸集引理 线性规划问题的可行解X x1 x2 xn 为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的 所组成的矩阵是非奇异的 定理2 线性规划问题的基可行解X对应线性规划问题可行域的顶点 定理3 若线性规划问题有最优解 一定存在一个基可行解是最优解 2020 2 10 59 线性规划的代数解法 maxZ 6x1 5x2x1 3x2 902x1 x2 752x1 2x2 80 x1 x2 0 maxZ 6x1 5x2x1 3x2 x3 902x1 x2 x4 752x1 2x2 x5 80 xi 0 找一个基可行解 X 0 0 90 75 80 Z 01 Z 6x1 5x2 x1的系数C1 6大于C2 5 选择x1为新的基变量 X3 90 x1 3x2 当x3 0 X2 0时 x1 90选择x4为X4 75 2x1 x2 当x4 0 X2 0时 x1 37 5换出变量 X5 80 2x1 2x2 当x5 0 X2 0时 x1 40即x4 0 最小 2020 2 10 60 3 Z 225 2x2 3x4 x2的系数C2 2大于0 选择x2为新的基变量 X3 52 5 2 5x2 0 5x4 当x3 0 x4 0时 x2 21X1 75 2 0 5x2 0 5x4 当x1 0 x4 0时 x2 75X5 5 x2 x4 当x5 0 x4 0时 x2 5所以选择x5为换出变量 x2为换入变量 最小 则X 37 5 0 52 5 0 5 T Z 225 2X2 3X4 2 仍然用非基变量表示基变量X3 52 5 2 5x2 0 5x4 X1 75 2 0 5x2 0 5x4 X5 5 x2 x4 Z 225 2x2 3x4 2020 2 10 61 4 用非基变量表示基变量X3 40 1 5x4 2 5x5 X1 35 x4 0 5x5 X2 5 x5 x4 Z 235 x4 2x5 则X 35 5 40 0 0 T Z 235 x4 2x5为最优解 2020 2 10 62 可行域极点的数量 如果线性规划有50个变量 20个约束条件 全部是等号约束 按照以上的算法 每计算一个基础解 要从50个变量中选择30个非基变量等于0 剩下20个变量 如果相应的20 20行列式不等于0 则通过计算一个20 20的线性方程组得到基变量 要穷尽所有的基础解 最多可能要计算的线性方程组的个数为 假设每计算一个20 20线性组需要1秒钟 计算以上所有方程组需要的时间为 由于极点的个数随着约束条件的增加而很快增加 用搜索所有极点来求出线性规划最优解 实际上并不是一个可行的方法 2020 2 10 63 单纯形法原理示意图 极点4 最优解 初始极点1 极点2 极点3 其实 不必搜索可行域的每一个极点 只要从一个极点出发 沿着使目标函数改善的方向 到达下一个相邻的极点 如果相邻的所有极点都不能改善目标函数 这个极点就是最优极点 用这样的搜索策略 可以大大减少搜索极点的个数 按照这样的搜索策略建立的算法 叫做单纯形法 单纯形法可以有效地减少搜索极点的个数 目标函数改善 目标函数改善 目标函数改善 2020 2 10 64 线性规划基本概念练习 1 0 3 6 x1 x2 O A B C E F G H I 4 6 2 minz x1 2x2s t 3x1 2x2 12 1 x1 2x2 6 2 2x1 x2 4 3 x1 x2 0 1 约束条件 1 对应的直线是 对应的半平面是 约束条件 2 对应的直线是 对应的半平面是 约束条件 3 对应的直线是 对应的半平面是 2 这个线性规划的可行域是 3 对于z 2和4 分别画出目标函数等值线 4 这个线性规划的最优解位于 ACEF BCDH EGHI CDGE z 2 z 4 C D 4 2020 2 10 65 0 3 6 x1 x2 O A B C E F G H I 4 6 2 D 线性规划基本概念练习 2 5 x1等于0的直线是 x2等于0的直线是 x3等于0的直线是 x4等于0的直线是 x5等于0的直线是 6 A点对应的基变量是 非基变量是 D点对应的基变量是 非基变量是 7 A点不是可行解 是由于 0F点不是可行解 是由于 0I点不是可行解 是由于 0 4 x1 0 x2 0 x3 0 x4 0 x5 0 ODGF IOAB ACEF BCDH EGHI 8 x1 x2 x5 0 x3 x4 0的区域是 x1 x2 x3 x5 0 x4 0的区域是 x2 x3 x4 x5 0 x1 0的区域是 x1 x2 x3 x4 0 x5 0的区域是 x1 x4 x5 x3 x2 x2 x3 x5 x1 x4 x4 x5 x1 x4 ABC OACD DGH EFG 2020 2 10 66 单纯形法计算步骤 1 将非标准型线性规划化为标准型2 确定初始基可行解 一般设松弛变量为初时基可行解3 判断若所有的某一非基变量的检验数 j 0 则此解为线性规划问题的最优解 若存在某一非基变量的检验数 j 0 则问题还没有达到最优解 需要进行改进 4 改进迭代选择换入变量max cj zj cj zj 0 假设选取xk为换入变量选择换出变量 min bi aik aik 0 则假设选取cl为换出变量迭代 使得alk 1 其余aik为0 2020 2 10 67 2020 2 10 68 单纯形表求解线性规划问题 maxZ 6x1 5x2x1 3x2 902x1 x2 752x1 2x2 80 x1 x2 0 maxZ 6x1 5x2x1 3x2 x3 902x1 x2 x4 752x1 2x2 x5 80 xi 0 2020 2 10 69 2020 2 10 70 2020 2 10 71 所以把x4换出为非基变量 x1为换入变量即新的基变量 2020 2 10 72 2020 2 10 73 2020 2 10 74 2020 2 10 75 2020 2 10 76 所以把x5换出为非基变量 x2为换入变量即新的基变量 2020 2 10 77 2020 2 10 78 2020 2 10 79 2020 2 10 80 此时所有的检验数都小于等于0 所以该解为最优解 最优解为X 35 5 40 0 0 T Z 235 2020 2 10 81 Step0获得一个初始的单纯形表 确定基变量和非基变量Step1检查基变量在目标函数中的系数是否等于0 在约束条件中的系数是否是一个单位矩阵 Step2如果表中非基变量在目标函数中的系数全为负数 则已得到最优解 停止 否则选择系数为正数且绝对值最大的变量进基 转step3 Step3如果进基变量在约束条件中的系数全为负数或0 则可行域开放 目标函数无界 停止 否则选取右边常数和正的系数的最小比值 对应的基变量离基 转step4 Step4确定进基变量的列和离基变量的行交叉的元素为 主元 对单纯形表进行行变换 使主元变为1 主元所在列的其他元素变为0 将离基的基变量的位置用进基的非基变量代替 转Step2 单纯形表的算法描述 2020 2 10 82 1 maxZ 3x1 9x2x1 3x2 21 x1 x2 4x1 x2 0 maxZ 3x1 9x2x1 3x2 x3 21 x1 x2 x4 4xi 0 举例 2020 2 10 83 所以把x4换出为非基变量 x2为换入变量即新的基变量 2020 2 10 84 2020 2 10 85 2020 2 10 86 2020 2 10 87 所以把x3换出为非基变量 x1为换入变量即新的基变量 2020 2 10 88 2020 2 10 89 2020 2 10 90 此时所有的检验数都小于等于0 所以该解为最优解 最优解为X 9 4 25 4 0 0 T Z 63 由于非基变量x4的检验数 0 所以我们可以把它作为换入基变量来考虑 2020 2 10 91 2020 2 10 92 2020 2 10 93 2020 2 10 94 此时所有的检验数都小于等于0 所以该解为最优解 Z 63 2020 2 10 95 1 maxZ x1 x2 2x1 x2 4x1 x2 2x1 x2 0 maxZ x1 x2 2x1 x2 x3 4x1 x2 x4 2xi 0 举例 2020 2 10 96 所以把x3换出为非基变量 x2为换入变量即新的基变量 2020 2 10 97 2020 2 10 98 2020 2 10 99 2020 2 10 100 可以看出 的检验数为3 大于0 但是的系数列向量中的所有原数 2 1 T 都小于0 所以该题为无界解 2020 2 10 101 单纯形法的进一步讨论 一 人工变量法 大M法 约束条件 加一个剩余变量后 在加一个人工变量 加一个人工变量目标函数 人工变量的系数为 M 即罚因子若线性规划问题有最优解则人工变量必为0 2020 2 10 102 MaxZ 3x1 x2 x3x1 2x2 x3 11 4x1 x2 2x3 3 2x1 x3 1xi 0 MaxZ 3x1 x2 x3 0 x4 0 x5 Mx6 Mx7x1 2x2 x3 x4 11 4x1 x2 2x3 x5 x6 3 2x1 x3 x7 1xi 0 增加人工变量后 线性规划问题中就存在一个B为单位矩阵 后面可以根据我们前面所讲的单纯形法来进行求解 2020 2 10 103 2020 2 1