管理学线性规划.ppt

浙江科技学院经济管理学院管工系 运筹学 管理科学与工程系经济与管理学院 2020 4 21 2 课堂要求 1 要求学生上课不迟到 不早退 不得旷课 2 上课认真听讲 要求每位同学都做笔记 3 上课不得讲话 看书 玩手机等与课堂无关的内容 4 课后要求独自完成作业 不得抄袭或不做课后作业 2020 4 21 3 参考资料 1 胡运权主编 运筹学教程 第三版 清华大学出版社 2 周华任主编 运筹学解题指导 清华大学出版社 3 运筹学习题集 修订版 清华大学出版社 4 熊伟编著 运筹学 机械工业出版社 5 运筹学 数据 模型 决策 科学出版社 2020 4 21 4 前言 运筹学简介 运筹学是管理科学的重要理论基础和应用手段 是管理专业的重要专业基础课程之一 运筹学根据管理问题的环境条件和决策要求 建立相应的数学模型 利用数学模型对实际问题进行分析和求解 经过分析和比较 得到适合实际问题的方案 求解结果 求解结果 建立模型 求解模型 修改模型 求解结果 修改模型 2020 4 21 5 运筹学是在第二次世界大战中诞生和发展起来的 由于战争的需要 英国和美国招募了一批年轻的科学家和工程师 在军队将军的领导下研究战争中的问题 例如大规模轰炸的效果 搜索和攻击敌军潜水艇的策略 兵力和军需物质的调运等等 这些研究在战争中取得了很好的效果 当时英国把这些研究成为 作战研究 英文是OperationalResearch 在美国称为OperationsResearch 2020 4 21 6 战后这些研究成果逐渐公开发表 这些理论和方法被应用到经济计划 生产管理领域 也产生了很好的效果 这样 OperationsResearch就转义成为 作业研究 我国把OperationsResearch译成 运筹学 非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义 运筹学的内容十分广泛 包括线性规划 整数规划 动态规划 非线性规划 图论与网络优化 排队论 决策理论 库存理论等 在本课程中 结合管理学科的特点 主要介绍线性规划 对偶问题 整数规划 运输问题 动态规划 图与网络分析 2020 4 21 7 授课主要内容 目录 绪论 1 第一章线性规划 12 第二章对偶问题 10 第三章运输问题 6 第五章整数规划 6 第七章动态规划 8 第八章图与网络分析 8 上课总课时 51课时课程设计1周 下学期开学前 2020 4 21 8 第一章线性规划及单纯形法 1 1线性规划问题及其数学模型1 2图解法1 3单纯形法原理1 4单纯形法计算步骤1 5单纯形法进一步讨论 2020 4 21 9 本章学习要求 能建立实际问题的数学规划模型理解线性规划模型的特点 标准型掌握线性规划的图解法及其几何意义掌握单纯形法原理掌握运用单纯形表计算线性规划问题的步骤及解法能用二阶段法和大M法求解线性规划问题 掌握任何基可行解原表及单纯形表的对应关系 2020 4 21 10 1 1线性规划问题及其数学模型 举例说明线性规划数学模型的标准形式 2020 4 21 11 一 线性规划问题举例说明 生产计划问题配料问题背包问题运输问题指派问题下料问题 2020 4 21 12 例1 美佳公司 生产计划问题 1 确定决策变量 通常由目标问题分解设x1代表生产 种家电数量 x2代表生产 种家电数量 2 分析并表达限制条件 包括约束条件 通常由等式或不等式表示 0 x1 5x2 156x1 2x2 24x1 x2 5x1 0 x2 0 3 分析目标 是利润最大化MaxZ 2x1 x2 2020 4 21 13 例2 捷运公司 表1 2所需仓库面积 1 确定决策变量 通常由目标问题分解每个月有不同的租用方案 共有4个月需要租用仓库 则 表1 3租金与期限的关系 2020 4 21 14 1 生产计划问题 ProductionPlanning 某工厂拥有A B C三种类型的设备 生产甲 乙 丙 丁四种产品 每件产品在生产中需要占有的设备机时数 每件产品可以获得的利润以及三种设备可利用的时数如下表所示 求使得总利润最大的生产计划 设四种产品的产量分别为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 2020 4 21 15 2 配料问题 MaterialBlending 某工厂要用四种合金T1 T2 T3 T4为原料 经熔炼成为新的不锈钢G 这四种原料含铬 Cr 锰 Mn 和镍 Ni 的含量 这四种原料的单价以及新的不锈钢G所要求的Cr Mn Ni的最低含量 如下表 要求配100公斤不锈钢G 并假定在配制过程中没有损耗 求使得总成本最低的配料方案 设四种原料分别选取x1 x2 x3 x4公斤 总成本为z minz 115x1 97x2 82x3 76x4s t 3 21x1 4 53x2 2 19x3 1 76x4 3 20Cr的含量下限约束2 04x1 1 12x2 3 57x3 4 33x4 2 10Mn的含量下限约束5 82x1 3 06x2 4 27x3 2 73x4 4 30Ni的含量下限约束x1 x2 x3 x4 100物料平衡约束x1 x2 x3 x4 0 2020 4 21 16 3 背包问题 KnapsackProblem 一只背包最大装载重量为50公斤 现有三种物品 每种物品数量无限 每种物品每件的重量 价格如下表 求背包中装入每种物品各多少件 使背包中物品总价值最高 设三种物品的件数各为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 4 21 17 4 运输问题 Transportation 某种物资从两个供应地A1 A2运往三个需求地B1 B2 B3 各供应地的供应量 各需求地的需求量 每个供应地到每个需求地每吨物资的运输价格如下表 求总运费最低的运输方案 35吨 25吨 10吨 30吨 20吨 2020 4 21 18 设从两个供应地到三个需求地的运量 吨 如下表 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 4 21 19 这个问题的最优解表示如下 最小总运费为 z 3 30 5 5 4 10 8 15 275元 30吨 5吨 10吨 15吨 2020 4 21 20 5 指派问题 AssignmentProblem 有n项任务由n个人完成 每项任务交给一个人 每人都有一项任务 由i个人完成j项任务的成本 或效益 为cij 求使总成本最小 或总效益最大 的分配方案 设 2020 4 21 21 张 王 李 赵四位老师被分配教语文 数学 物理化学四门课程 每位老师教一门课 每门课由一位老师教 根据这四位老师以往教课的情况 他们分别教四这门课程的平均成绩如下表 要求确定哪一位老师上哪一门课 使四门课的平均总成绩最高 设 2020 4 21 22 设 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 4 21 23 6 下料问题现将1m长的钢切成A 0 4m B 0 3m C 0 2m长的三种钢 其中A B C三种钢分别需要20根 45根和50根 问如何进行切割使得需要的1m钢为最少 解 将1m的钢分别切成A B C三种钢的可能方案如下 设第i种方案进行切割的1m钢的为xi根 minZ 0 1x3 0 1x5 0 1x7s t 2x1 x2 x3 x4 202x2 x3 3x5 2x6 x7 45x1 x3 3x4 2x6 3x7 5x8 50 xi 0 i 1 2 8 2020 4 21 24 小结 线性规划问题要求目标函数和约束方程必须是线性函数 隐含如下假定 比例性假定 每个决策变量对目标函数的贡献与决策变量的值成比例 每个变量对约束条件左端的贡献与变量的值成比例 可加性假定 任何变量对目标函数的贡献都与其他决策变量的值无关 一个变量对每个约束条件左端的贡献与该变量的值无关 连续性假定 可除性假定 允许每个决策变量值使用分数值 确定性假定 已经确切知道每个参数 价值系数 工艺系数 右侧常数 线性规划数学模型三个要素 决策变量目标函数约束条件 2020 4 21 25 课堂习题P451 131 14 1 课后作业P461 14 2 1 15 2020 4 21 26 二 线性规划模型标准形式 min max z c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 Free 线性规划模型的目标函数必须是变量的线性函数 约束条件必须是变量的线性等式或不等式 如右的问题就不是线性规划问题 1 一般形式 2020 4 21 27 2 线性规划的标准形式 目标函数为极大化 约束条件全部为等号约束 所有变量全部是非负的 这样的线性规划模型称为标准形式maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 2020 4 21 28 3 线性规划模型用矩阵和向量表示 maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 价值系数 工艺系数矩阵 资源约束 2020 4 21 29 线性规划模型用矩阵和向量表示 续 因此 线性规划模型可以写成如下矩阵和向量的形式 MaxZ CXs t AX bX 0 2020 4 21 30 4 线性规划模型总结 线性规划模型的结构目标函数 max min约束条件 变量符号 0 0 Free线性规划的标准形式目标函数 max约束条件 变量符号 0 MaxZ CXs t AX bX 0 2020 4 21 31 5 线性规划问题的标准化 极小化目标函数转化为极大化小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束变量没有符号限制 Free 的标准化变量小于等于0的标准化 2020 4 21 32 minz 2x1 3x2 x3令z z z 2x1 3x2 x3新的目标函数maxz 2x1 3x2 x3取得极小化的最优解时 这个最优解同时使原目标函数值取得最大化的最优解 但两个问题最优解的目标函数值相差一个负号 极小化目标函数问题转化为极大化目标函数 例如 对于以下两个线性规划问题 Maxz 2x1 3x2s t x1 x2 3x2 1 A x1 x2 0 Minz 2x1 3x2s t x1 x2 3x2 1 B x1 x2 0 它们的最优解都是x1 2 x2 1 但 A 的最大化的目标函数值为maxz 7 B 的最小化的目标函数值为minz 7 2020 4 21 33 2x1 3x2 4x3 5引进松弛变量 Slackvariable x4 02x1 3x2 4x3 x4 5如果有一个以上小于等于约束 要引进不同的松弛变量 例如 2x1 3x2 4x3 53x1 2x2 5x3 8在两个约束中分别引进松弛变量x4 x5 02x1 3x2 4x3 x4 53x1 2x2 5x3 x5 8 小于等于约束条件转化为等号约束 大于等于约束条件转化为等号约束 将不等式约束变为等式约束 例如 2x1 3x2 4x3 53x1 2x2 5x3 8在两个约束的左边分别减去剩余变量x4 x5 02x1 3x2 4x3 x4 53x1 2x2 5x3 x5 8 2020 4 21 34 没有符号限制的变量 用两个非负变量之差表示 例如 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 4 21 35 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 4 21 36 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 4 21 37 课堂习题P431 2 2020 4 21 38 1 2图解法 相关概念和图解法步骤线性规划问题图解法求解的几种结果结论 2020 4 21 39 模型中只有两个变量的线性规划问题 可以通过在平面上作图的方法求解 可行解 一个线性规划问题有解 是指能找出一组xj j 1 2 n 满足约束条件 称这组xj为问题的可行解 可行域 通常线性规划问题总是含有多个可行解 全部可行解的集合为可行域 最优解 可行域中使目标函数为最优的可行解为最优解 图解法的步骤 建立坐标系 确定比例尺 画出各约束条件的边界 定出可行域 画出目标函数的一根等值线 平移得出最优解 算出目标函数最优值 1 相关概念和图解法步骤 2020 4 21 40 线性规划的图解 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 z 6 z 3 z 9 z 12 问题 1 线性规划的最优解是否可能位于可行域的内部 2 线性规划的最优解是否可能位于可行域的边界上 2020 4 21 41 唯一最优解无穷多最优解无界解 可行域无界 无解 无可行解 2 线性规划问题图解法求解的几种结果 1 唯一最优解 封闭 2 多个最优解 封闭 3 唯一最优解 开放 4 多个最优解 开放 5 目标函数无界 开放 6 无可行解 2020 4 21 42 线性规划问题解的形式 唯一最优解 无穷多最优解 无界解 无可行解 若LP的可行域存在 即有可行解 则可行域是一个凸集 若LP的最优解存在 则一定可以在可行域的某个顶点达到 如果在某两个顶点上达到最优 则该LP有无穷多最优解 用图解法求解LP时 如果可行域封闭 可比较可行域的顶点的目标函数值 得到最优解 注意用图解法如果可以得到封闭的可行域 则定有最优解存在 如果可行域不封闭 则解的三种形式都可能出现 必须用目标函数等值线的平移来判断 3 结论 2020 4 21 43 举例 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 4 21 44 课后作业P431 1 2020 4 21 45 1 3单纯形法原理 LP解的相关概念凸集及其顶点几个基本定理单纯形法迭代原理 2020 4 21 46 x3 0 x4 0 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 x2 0 x1 0 O A B C D 一 LP解的相关概念 1 可行域 可行解 最优解 2020 4 21 47 LP问题数学模型 因此 可行解 满足 1 7 1 8 的解称为LP的可行解 可行域 全部可行解的集合 最优解 使目标函数 1 6 达到最大值的可行解 2020 4 21 48 定义1 从n个变量中任取m个变量xi1 xi2 xim 若这m个变量对应的系数列向量Pi1 Pi2 Pim线性无关 即对应系数列向量行列式 0 则称B Pi1 Pi2 Pim 为基矩阵 简称基 xi1 xi2 xim为基变量 其余n m变量为非基变量 定义2 在约束方程 1 7 中 令所有非基变量为0 根据克莱姆法则 则 1 7 有唯一解 令xi1 1 xi2 2 xim m 称为一组基解 基可行解 满足 1 8 中的基解为基可行解 即基解中每一分量均非负 可行基 基可行解对应的基 退化解 基变量中有分量为0的解 线性规划的基可行解就是可行域的顶点 2 基 基变量 非基变量 基解 基可行解 可行基 2020 4 21 49 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 4 21 50 1 maxZ 2x1 3x2x1 x3 5x1 2x2 x4 10 x2 x5 4xi 0 最优解为x1 2 x2 4 x3 3 Z 19 2020 4 21 51 二 凸集和顶点 1 凸集如果集合C中任意两点x1 x2 其连线上的所有点也都是集合C中的点 则称C为凸集 其中x1 x2的连线可以表示为 x1 1 x2 0 1 数学解析式为 x1 C x2 C 有 x1 1 x2 C 0 1 则C为凸集 2 顶点如果集合C中不存在任何两个不同的点x1 x2 使x为这两点连线上的一个点 称x为顶点 对任何x1 C x2 C 不存在x x1 1 x2 0 1 则称x为凸集的顶点 2020 4 21 52 三 几个基本定理 定理1 若线性规划问题存在可行解 则问题的可行域是凸集 引理 线性规划问题的可行解X x1 x2 xn 为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的 所组成的矩阵是非奇异的 2020 4 21 53 定理2 线性规划问题的基可行解X对应线性规划问题可行域的顶点 分两步 1 顶点 基可行解2 基可行解 顶点反证法 1 假设X0是可行域的顶点 X0不是基可行解 X0的前k个分量大于0 其余为0 因不是基可行解 则存在 所以X0不是可行域的顶点 与假设矛盾 则X0必为基可行解 2020 4 21 54 2 假设X0是基可行解 X0不是顶点 假设X0是一个基可行解 设X0的前m个分量为正 令X0 x1 x2 xm 0 0 T 因为不是顶点 则X0可以表示成另外两个点X 1 X 2 的凸组合 且P1 Pm线性无关 所以X不能表示成可行域中另外两点的凸组合 与假设相矛盾 则X必为可行域的顶点 2020 4 21 55 定理3 若线性规划问题有最优解 一定存在一个基可行解是最优解 X0为LP的最优解 Z CX0 如果X0不是基可行解 则定有X 1 X0 ta X 2 X0 ta为可行解 则有CX 1 CX0 tCa CX0CX 2 CX0 tCa CX0则必有tCa 0所以X0 X 1 X 2 均为最优解 如果X 1 X 2 不是基可行解 继续下去 则必可以找到基可行解为最优解 2020 4 21 56 四 单纯形法迭代原理 迭代基础 如果LP存在最优解 则一定有一个基可行最优解 且对应LP可行域的顶点 可行 基解 最优 1 确定初始基可行解 基解 可行解 2020 4 21 57 2 最优性检验和解的判别 非基变量检验数 2020 4 21 58 由检验数可以判断解的最优性情况 1 因为所有Xj 0 当所有 j0 且所有aik 0 Pj 0 i 1 2 m 则该问题无界 4 因为所有Xj 0 当存在 j 0时 则该基可行解不是最优解 需要寻找另一个基可行解 2020 4 21 59 3 基变换 变换目的 使目标函数Z值得到改善 接近最优解 一次基变换 是从该顶点到相邻顶点 即一次基变换仅变换一个基变量 换入变量的确定 k 0 aik至少一个大于0 若 k Max j j 0 则xk为换入变量 换出变量的确定令xk 0 xj 0 j m 1 n j k则xi bi aik 0 i 1 m当aik 0时 可任取 当aik 0时 则xl为换出变量 系数变换 2020 4 21 60 以alk为主元进行初等行变换 2020 4 21 61 习题1 8 1 6 2020 4 21 62 1 4单纯形法计算步骤 求初始基可行解最优性检验基变换 2020 4 21 63 单纯形法原理 单纯形法总结 STEP0找到一个初始的基础可行解 确定基变量和非基变量 转STEP1 STEP1将目标函数和基变量分别用非基变量表示 转STEP2 STEP2如果目标函数中所有非基变量的检验数全部为非正数 则已经获得最优解 如果全为负数 则为唯一最优解 运算终止 如果有为0的非基变量检验数 则有无穷多最优解 运算终止 如果有某非基变量检验数为正 且工艺系数全非正 则无界 运算终止 否则 选取检验数为正数最大的非基变量进基 转STEP3 STEP3选择最小比值对应的基变量离基 进行系数初等行变换 得新的基可行解 转STEP1 2020 4 21 64 一 求初始基可行解 1 当约束条件为 时 直接在约束不等式左边加上非负的松弛变量 使约束方程的系数矩阵很容易找到一个单位矩阵 求出一个初始基可行解 2 当约束条件为 时 直接在约束不等式左边减去非负的剩余变量 此情况下很难找到一个单位矩阵 为求出初始基可行解 为此需要引入人工变量 以方便构成初始基可行解的一个基 为了不改变问题的性质 对引入人工变量Xi 的线性规划问题 需要在目标函数中减去MXi M为足够大的正数 称罚因子 促使Xi 最终必为0 3 当约束条件为 时 同样需要引入人工变量 以方便构成初始基可行解的一个基 目标函数需要减去罚因子 2020 4 21 65 二 最优性检验 1 若所有 j0 且所有aik 0 Pj 0 i 1 2 m 则该问题无界 计算终止 4 当存在 j 0时 且有aik 0 继续第三步 2020 4 21 66 三 基变换 用单纯形法按上述步骤求解时 可采用表格形式 这样更直观 易于避免错误 该表格称为单纯形表 2020 4 21 67 例 j 2 1 0 0 0 4 5 x1入 x4出 j 0 1 3 0 1 3 0 x2入 x5出 3 12 3 2 j 0 0 0 1 4 1 2 所以 X x1 x2 x3 T 7 2 3 2 15 2 TZ 17 2 2020 4 21 68 例 1 4 1 j 10 5 0 0 3 8 5 x1入 x4出 j 0 1 0 2 x2入 x3出 3 2 4 j 0 0 5 14 25 14 所以 X x1 x2 T 1 3 2 TZ 35 2 对应0 对应A 对应B 2020 4 21 69 课堂作业1 4 1 课后作业P431 4 2 2020 4 21 70 1 5单纯形法的进一步讨论 一 人工变量法 大M法 约束条件 减一个剩余变量后 再加一个人工变量 加一个人工变量目标函数 人工变量的系数为 M 即罚因子若线性规划问题有最优解则人工变量必为0 2020 4 21 71 MaxZ 3x1 x3x1 x2 x3 4 2x1 x2 x3 13x2 x3 9xi 0 j 1 2 3 增加人工变量后 线性规划问题中就存在一个B为单位矩阵 后面可以根据我们前面所讲的单纯形法来进行求解 MaxZ 3x1 x3 Mx6 Mx7x1 x2 x3 x4 4 2x1 x2 x3 x5 x6 13x2 x3 x7 9xi 0 j 1 7 标准化及变形 2020 4 21 72 单纯形表 j 3 2M 4M 1 0 0 3 x2入 x6出 M 0 4 1 j 6M 3 0 4M 1 0 4M x1入 x7出 3M 0 1 1 j 0 0 3 0 M 3 2 9 x3入 x1出 3 2 M 1 2 3 2 j 9 2 0 0 0 M 3 4 3 4 M 1 4 所以 X x2 x3 x4 T 5 2 3 2 0 TZ 3 2 2020 4 21 73 二 两阶段法第一阶段暂不考虑原问题是否存在基可行解 给原问题加入人工变量 并构建一个仅含人工变量的目标函数 求极小化 人工