运筹02线性规划与单纯形法素材.ppt

Chapter2线性规划与单纯形法 LinearProgrammingandSimplexAlgorithm 1 线性规划问题及其数学模型2 线性规划问题的几何意义3 单纯形法4 单纯形法的计算步骤5 单纯形法的进一步讨论6 应用举例 线性规划是运筹学的一个重要分支 自1947年丹捷格 G B Dantzig 提出了线性规划问题求解的方法 单纯形法之后 线性规划在理论上趋向成熟 在实用中日益广泛与深入 特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后 线性规划的适用领域更为广泛 从解决技术问题的最优化设计到工业 农业 商业 交通运输业 军事 经济计划和管理决策等领域都可以发挥作用 引言 线性规划研究的问题 如何合理地利用有限的人力 物力 财力等资源 以便得到最好的经济效果 2 1线性规划问题及其数学模型 2 1 1问题的提出 例1某工厂在计划期内要安排生产I II两种产品 已知生产单位产品所需的设备台时及A B两种原材料的损耗 如表1 1所示 表1 1 该工厂每生产一件产品 可获利2元 每生产一件产品 可获利3元 问应如何安排计划使该工厂获利最多 1 确定决策变量 2 确定目标函数 4 确定变量取值限制 3 确定约束条件 得到本问题的数学模型为 这就是一个最简单的线性规划模型 例2靠近某河流有两个化工厂 见图1 1 流经第一化工厂的河流流量为每天500万立方米 在两个工厂之间有一条流量为每天200万立方米的支流 化工厂1每天排放含有某种有害物质的工业污水2万立方米 化工厂2每天排放的工业污水为1 4万立方米 从化工厂1排出的污水流到化工厂2前 有20 可自然净化 根据环保要求 河流中工业污水的含量应不大于0 2 因此两个工厂都需处理一部分工业污水 化工厂1处理污水的成本是1000元 万立方米 化工厂2处理污水的成本是800元 万立方米 问 在满足环保要求的条件下 每厂各应处理多少工业污水 使两个工厂处理工业污水的总费用最小 1 确定决策变量设第一化工厂每天处理工业污水x1万立方米 第二化工厂每天处理工污水x2万立方米 2 确定目标函数 3 确定约束条件 从第一化工厂到第二化工厂之间 河流中工业污水含量不大于0 2 由此可得近似关系式 流经第二化工厂后 河流中的工业污水含量仍要不大于0 2 这时有近似关系式 4 确定变量取值限制 得到本问题的数学模型为 上述两个问题具有的共同特征 每一个线性规划问题都用一组决策变量 x1 x2 xn 表示某一方案 这组决策变量的值代表一个具体方案 一般这些变量的取值是非负且连续的 都有关于各种资源和资源使用情况的技术数据 并存在可以量化的约束条件 这些约束条件可以用一组线性等式或线性不等式来表示 都有一个达到某一目标的要求 可用决策变量的线性函数 称为目标函数 来表示 按问题的要求不同 要求目标函数实现最大化或最小化 决策变量及各类系数之间的对应关系 满足以上特征的数学模型 我们称之为线性规划问题 简单的说线性规划问题是求一个线性目标函数满足一组线性约束条件的极值问题 线性规划模型的一般形式 例 常山机器厂生产 两种产品 这两种产品都要分别在A B C三种不同设备上加工 按工艺资料规定 生产每件产品 需占用各设备分别为2h 4h 0h 生产每件产品 需占用各设备分别为2h 0h 5h 已知各设备计划期内用于生产这两种产品的能力分别为12h 16h 15h 又知每生产一件产品 企业能获得2元利润 每生产一件产品 企业能获得3元利润 问该企业应安排生产两种产品各多少件 使总的利润收入为最大 2 1 2线性规划的数学模型 1分析实际问题2确定决策变量3确定目标函数4找出约束条件5整理 写出数学模型 运输工具配载问题 有一辆运输卡车 载重2 5t 容积18用来装载如下两种货物 箱装件 125kg 0 4包装件 20kg 1 5请问 如何装配 卡车所装的物件个数最多 1 分析问题 这是一个运输工具的配载问题 给出了最大载重和容积 要求装最多的物件 2 确定决策变量 此问题的决策变量有两个 箱装件和包装件 因此分别设为X1 X2 3 确定目标函数 本问题的目标要求为装物件个数最多 Maxz X1 X24 找出约束条件 约束条件有两个 载重和容积约束 因此列出约束条件 容积约束 0 4X1 1 5X2 18载重约束 125X1 20X2 2500非负约束 X1 0 X2 0 5 整理 写出数学模型 南京某市场调查公司受一洗涤剂厂委托 调查消费者对新型洗衣粉的了解与反应 对不同家庭采用不同调查方式的费用见表 洗涤剂厂对市场调查公司提出了以下几个方面的具体要求 1 调查800个家庭 2 被调查家庭中 至少有300个是没有孩子的家庭 同时至少有300个是有孩子的家庭 3 至少对500个被调查家庭采用问卷式书面调查 其余家庭可用口头调查 4 在有孩子的被调查家庭中 至少有50 的家庭采用问卷式书面调查 5 在没有孩子的被调查家庭中 至少有60 的家庭采用问卷式书面调查 市场调查计划优化问题 投资问题 上海某投资公司在今后三年内有四种投资机会 第1种是3年内每年年初投资 年底可获利润20 并可将本金收回 第2种是在第一年的年初投资 第二年年底可获利润50 并将本金收回 但该项投资不得超过2000万 第3种是在第二年的年初投资 第三年年底收回本金 并获利润60 但该项目投资不得超过1500万 第4种是在第三年的年初投资 于该年年底收回本金 且获利润40 但该项投资不得超过1000万 现在该公司拿出3000万 问如何制定投资计划 使得第三年年末本利和最大 配料问题 某糖果厂用原料A B C加工成三种不同牌号的糖果甲 乙 丙 已知各种牌号糖果中A B C含量 原料成本 各种原料的每月限制用量 三种牌号糖果的单位加工费及售价如下表所示 问该厂每月应生产这三种牌号糖果各多少千克 使得该厂获利最大 试建立这个问题的线性规划的数学模型 下料问题 某建筑工地有一批长度为10米的相同型号的钢筋 今要截成长度为3米的钢筋90根 长度为4米的钢筋60根 问怎样下料 才能使所使用的原材料最省 1 每个行动方案可用一组变量 x1 xn 的值表示 这些变量一般取非负值 2 变量的变化要受某些限制 这些限制条件用一些线性等式或不等式表示 3 有一个需要优化的目标 它也是变量的线性函数 具备以上三个特点的数学模型称为线性规划 LinearProgramming 简记为LP 下料问题练习 有一批原料钢材 如钢管 钢筋 角钢 钢梁等 每根长7 4m 现需做100套钢架 每套利用长2 9m 2 1m 1 5m的钢材各一根 问如何下料 才能使所用的原料最省 有A B C三个工地 每天需要水泥各为17 18 15百袋 为此甲 乙两个水泥厂每天各生产23百袋和27百袋水泥供应这三个工地 其单位运价如下表 求最佳调运方案 线性规划模型的一般形式 Ci为价值系数 ai为技术系数 bi为限制系数 2 1 3线性规划问题的标准形式 目标函数为求最大值 约束条件为等式约束 约束方程右端常数项为非负数值 决策变量取非负数值 用向量形式表示的标准形式线性规划 价值向量 决策向量 系数向量 资源向量 用矩阵形式表示的标准形式线性规划 这时只需将目标函数最小化变换为求目标函数最大化 必须注意 尽管以上两个问题的最优解相同 但它们最优解的目标函数值却相差一个符号 如何将一般线性规划转化为标准形式的线性规划 引进一个松弛变量 把原不等式约束用两个约束来等价地替换 设约束条件为 2 约束方程为不等式有两种情况 一种是约束方程为 不等式 则可在 不等式的左端加入非负松弛变量 把原 不等式变为等式 另一种是约束方程为 不等式 则可在 不等式的左端减去一个非负剩余变量把原 不等式变为等式 引进一个剩余变量 把原不等式约束用两个约束来等价地替换 设约束条件为 4 在标准形式中 要求约束条件的右端项bi 0 否则等式两端乘以 1 下面举例说明 可以令 其中 即用两个非负变量之差来表示一个无符号限制的变量 当然的符号取决于和的相对大小 3 若存在取值无约束的变量 例3将例1的数学模型化为标准形式的线性规划 例4将下述线性规划问题化为标准形式线性规划 1 用x4 x5替换x3 其中x4 x5 0 2 在第一个约束不等式左端加入松弛变量x6 3 在第二个约束不等式左端减去剩余变量x7 4 令z z 将求minz改为求maxz 即可得到该问题的标准型 例4例4的标准型 2 1 4线性规划问题解的概念 可行解满足约束条件 1 5 1 6 式的解称为线性规划问题的可行解 其中使目标函数达到最大值的可行解称为最优解 考虑LP的标准型 称为基向量 与基向量相对应的变量称为基变量 否则称为非基变量 设A是约束方程组的维系数矩阵 其秩为m B是A中m阶非奇异子矩阵 B 0 则称B是线性规划问题的一个基 这就是说 矩阵B是由A中m个线性无关的列向量组成 为不失一般性 可设B是A中的前m列 即 2基 注 1 对应于给定的基B 基解是唯一的 2 基解中非基变量取零值 非零分量的数目不超过m 3 基解一定满足等式约束 但不一定满足非负约束 称为对应于基B的基解 令所有非基变量得到 因B可逆 该方程有唯一解 把约束方程 1 5 式写成 例在下述线性规划问题中列出全部的基并确定相应的基解 解 将该线性规划问题化为标准形 只要从A的列向量中找出3个线性无关的列向量就组成该线性规划问题的一个基 取A的第一 二 三列组成子矩阵易见 故B1是该线性规划问题的一个基 令非基变量 则约束方程变为 基变量为 非基变量 令非基变量为零 求解线性方程组 就可找出全部基解 解得 取A的第一 四 五列得到基 相应地基解 取A的第一 三 五列得到基 相应地基解 类似地取A的第一 二 四列得到基 相应地基解 取A的第一 二 五列得到基 相应地基解 对于A的第一 三 四列组成的矩阵易见 故不能作成一组基 取A的第二 三 四列得到基相应地基解取A的第二 四 五列得到基相应地基解取A的第三 四 五列得到基 相应地基解 同理 也不能作成一组基 1 基解的数目最多是个 2 基解中非零分量的个数小于m个时 该基解是退化解 3基可行解满足非负约束条件的基解称为基可行解 以下讨论时 假设不出现退化的情况 即基解中非零分量恰为m个 说明 4可行基对应于基可行解的基称为可行基 几何上 图中A B C D E F G H对应X i i 1 2 8 直观上 可行解即可行域中的点 基解是约束直线的交点 基可行解即可行域的顶点 它们之间的关系可以用图1 6表示 在下述线性规划问题列出一个基并确定相应的基解 线性规划问题的求解方法 一般有两种方法 图解法单纯形法 两个变量 直角坐标三个变量 立体坐标 适用于任意变量 但必需将一般形式变成标准形式 下面我们分析一下简单的情况 只有两个决策变量的线性规划问题 这时可以通过图解的方法来求解 图解法具有简单 直观 便于初学者窥探线性规划基本原理和几何意义等优点 2 1 2图解法 例1一个二维线性规划问题 因而可用图解法直观地进行求解 目标值在 4 2 点 达到最大值14 1 无穷多最优解 多重最优解 见图1 2 无界解 见图2 3 无可行解 见图 3 通过图解法 可观察到线性规划的解可能出现的几种情况 目标函数maxz 2x1 4x2 图1无穷多最优解 多重最优解 maxz 2x1 3x24x1 16x1 x2 0则x2 z 即存在无界解 图2无界解 当存在相互矛盾的约束条件时 线性规划问题的可行域为空集 例如 如果在例1的数学模型中增加一个约束条件 则该问题的可行域即为空集 即无可行解 无可行解的情形 图3不存在可行域 思考 1 线性规划的可行域是一个什么形状 2 最优解在什么位置获得 结论 问题 性质2有何重要意义 凸集 如果集合C中任意两个点X1 X2 其连线上的所有点也都是集合C中的点 称C为凸集 凸集 凸集 不是凸集 2 2线性规划问题的几何意义1基本概念 试判断下列图形是否凸集 凸组合 设是n维欧氏空间En中的k个点 若存在且使则称X为的凸组合 设K是凸集 若X不能用K中两个不同的点的凸组合表示为则称X是K的一个顶点或极点 2顶点 注 X是凸集K的顶点即X不可能是K中某一线段的内点 而只能是K中某一线段的端点 凸集 凸集 顶点 定理1 若线性规划问题存在可行解 则该问题的可行域是凸集 引理1 线性规划问题的可行解为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的 定理2 线性规划问题的基可行解X对应可行域 凸集 的顶点 定理3 若问题存在最优解 一定存在一个基可行解是最优解 或在某个顶点取得 定理2刻划了可行域的顶点与基可行解的对应关系 顶点是基可行解 反之 基可行解一定是顶点 但它们并非一一对应 有可能两个或几个基可行解对应于同一顶点 退化基可行解时 定理3描述了最优解在域中的位置 若最优解唯一 则最优解只能在某一顶点上达到 若具有多重最优解 则最优解是某些顶点的凸组合 从而最优解是可行域的顶点或界点 不可能是可行域的内点 若线性规划的可行解集非空且有界 则一定有最优解 若可行解集无界 则线性规划可能有最优解 也可能没有最优解 几点结论 若线性规划问题有可行解 则可行域是一个凸多边形或凸多面体 凸集 且仅有有限个顶点 极点 线性规划问题的每一个基可行解都对应于可行域上的一个顶点 极点 若线性规划问题有最优解 则最优解必可在基可行解 极点 上达到 线性规划问题的基可行解 极点 的个数是有限的 不会超过个 上述结论说明 线性规划的最优解可通过有限次运算在基可行解中获得 丹捷格教授在一次演说中 形象而风趣地说明了单纯形解法的奇效 设给70个人分配70项任务 每人一项 如果每人完成各项任务所需要付出的代价 时间 工资 都知道 要寻求代价最小的方案 所有的可行方案共有70 种 70 比还要大 如果用穷举法 逐个来比较的话 即使用个地球或个太阳的容量来装计算机 这些计算机从150亿年前开始 全部投入计算 大约要算到太阳熄灭才有答案 而用单纯形法软件 几秒钟就可以给出答案 单纯形法是求解线性规划的主要算法 1947年由美国斯坦福大学教授丹捷格 G B Dantzig 提出 2 3单纯形法 单纯形法 SimplexAlgorithm 先求出一个初始基可行解并判断它是否最优 若不是最优 再换一个基可行解并判断 直到得出最优解或无最优解 它是一种逐步逼近最优解的迭代方法 优 跨越式寻找最优解 2 3 1单纯形法的基本思路和原理 单纯形法的思路 找出一个初始可行解 是否最优 转移到另一个基本可行解 找出更大的目标函数值 最优解 是 否 循环 核心是 变量迭代 结束 关键的3步 1 找出一个初始基本可行解 单位矩阵 2 最优性检验 检验数 j 3 基变换 换入变量与换出变量 标准型 例6用单纯形法求下列线性规划的最优解 2 3 3最优性检验与解的判别 设是LP的一个基 为相应的基可行解 将约束写成非基变量表示基变量的形式 不妨设 思路 对一个给定的基可行解 把目标函数用非基变量表示 非基变量前的系数称为检验数 当所有非基变量的检验数均小于等于零时 当前解即最优解 2 3 3最优性检验与解的判别 将 1 24 式代入目标函数 令 则 法则1最优性判定法则法则2换入变量确定法则设 则xk为换入变量 法则3换出变量确定法则 bi xj 0 i 1 2 m j 1 2 n 2 4 1单纯形法的表格形式 表称为初始单纯形表 每迭代一步构造一个新单纯形表 表的说明XB列中填入基变量 这里是x1 x2 xm CB列中填入基变量的价值系数 这里是c1 c2 cm 它们是与基变量相对应的 b列中填入约束方程组右端的常数 cj行中填入变量的价值系数c1 c2 cn i列的数字是在确定换入变量后 按 规则计算后填入 最后一行称为检验数行 对应各非基变量xj的检验数是 标准型 1 取松弛变量x3 x4 x5为基变量 它对应的单位矩阵为基 这就得到初始基可行解X 0 0 0 8 16 12 T 将有关数字填入表中 得到初始单纯形表 见表1 3 表中左上角的cj是表示目标函数中各变量的价值系数 在CB列填入初始基变量的价值系数 它们都为零 表1 3 计算非基变量的检验数各非基变量的检验数为 1 c1 z1 2 0 1 0 4 0 0 2 2 c2 z2 3 0 2 0 0 0 4 3 4 以 4 为主元素进行旋转运算或迭代运算 即初等行变换 使P2变换为 0 0 1 T 在XB列中将x2替换x5 于是得到新表1 4 换人变量 换出变量 主元素 表1 4 5 检查表1 4的所有cj zj 这时有c1 z1 2 说明x1应为换入变量 重复 2 4 的计算步骤 得表1 5 换人变量 换出变量 因为还存在检验数 0 继续进行迭代 主元素 表1 5 6 表1 6最后一行的所有检验数都已为负或零 这表示目标函数值已不可能再增大 于是得到最优解 表1 6 X X 3 4 2 0 0 4 T目标函数的最大值z 14 练习1 练习2用单纯形法求下列线性规划的最优解 解 1 将问题化为标准型 加入松驰变量x3 x4则标准型为 2 求出线性规划的初始基可行解 列出初始单纯形表 检验数 3 进行最优性检验 如果表中所有检验数 则表中的基可行解就是问题的最优解 计算停止 否则继续下一步 4 从一个基可行解转换到另一个目标值更大的基可行解 列出新的单纯形表 确定换入基的变量 选择 对应的变量xj作为换入变量 当有一个以上检验数大于0时 一般选择最大的一个检验数 即 其对应的xk作为换入变量 确定换出变量 根据下式计算并选择 选最小的 对应基变量作为换出变量 用换入变量xk替换基变量中的换出变量 得到一个新的基 对应新的基可以找出一个新的基可行解 并相应地可以画出一个新的单纯形表 5 重复3 4 步直到计算结束为止 单纯形法的计算步骤 换入列 bi ai2 ai2 0 40 10 换出行 将3化为1 5 3 1 18 0 1 3 0 1 3 10 1 1 3 30 30 0 5 3 0 4 3 乘以1 3后得到 1 0 3 5 1 5 18 0 1 1 5 2 5 4 0 0 1 1 将线性规划问题化成标准型 找出或构造一个m阶单位矩阵作为初始可行基 建立初始单纯形表 计算各非基变量xj的检验数 j Cj CBPj 若所有 j 0 则问题已得到最优解 唯一最优或无穷多最优解 停止计算 否则转入下步 在大于0的检验数中 若某个 k所对应的系数列向量Pk 0 则此问题是无界解 停止计算 否则转入下步 根据max j j 0 k原则 确定xk为换入变量 进基变量 再按 规则计算 min bi aik aik 0 bl aik确定xBl为换出变量 建立新的单纯形表 此时基变量中xk取代了xBl的位置 以aik为主元素进行迭代 把xk所对应的列向量变为单位列向量 即aik变为1 同列中其它元素为0 转第 步 单纯形法的计算步骤 原问题解的类型的判断对于所有约束条件都是 0的线性规划问题的解的类型有三种 唯一最优解无穷多最优解无界解 最优性检验与解的判别 原问题具有无界解 判断原问题解的类型 一 原问题具有唯一最优解 X 4 6 4 0 0 T Z 42 判断原问题解的类型 二 判断原问题解的类型 三 原问题具有无穷多个最优解 判断原问题解的类型 四 原问题具有唯一最优解 标准型 2 5单纯形法的进一步讨论 maxz 3x1 x2 x3s t x1 2x2 x3 11 4x1 x2 2x3 3 2x1 x3 1x1 x2 x3 0 maxz 3x1 x2 x3 0 x4 0 x5x1 2x2 x3 x4 11 4x1 x2 2x3 x5 3 2x1 x3 1x1 x2 x3 x4 x5 0 2 5单纯形法的进一步讨论 设线性规划问题的约束条件 其中没有可作为初始基的单位矩阵 则分别给每个约束方程加入人工变量xn 1 xn m 得到 2 5单纯形法的进一步讨论 以xn 1 xn m为基变量 便可得到一个m m单位矩阵 令非基变x1 xn为零 便可得到一初始基可行解X 0 0 0 0 b1 b2 bm T 注 人工变量与松弛变量和剩余变量不同 松弛变量 剩余变量可以取零值 也可以取正值 而人工变量只能取零值 一旦人工变量取正值 那么有人工变量的约束方程和原始的约束方程就不等价了 这样所求得的解就不是原线性规划的解 这就要求经过基变换将人工变量从基变量中逐个替换出来 基变量中不再含有非零的人工变量 这表示原问题有解 若在最终表中当所有cj zj 0 而在其中还有某个非零人工变量 这表示原问题无可行解 如何求解含有人工变量的线性规划问题 两种方法大M法两阶段法 2 5 1人工变量法 两阶段法 两阶段法是处理人工变量的另一种方法 这种方法是将加入人工变量后的线性规划分两阶段求解 第一阶段的任务是将人工变量尽快迭代出去 从而找到一个没有人工变量的基础可行解第二阶段以第一阶段得到的基础可行解为初始解 采用原单纯型法求解若第一阶段结束时 人工变量仍在基变量中 则原问题无解 具体步骤 第一阶段 构造一个只包含人工变量的最大化目标函数 人工变量的价值系数为 1 其他变量的价值系数为0 在原约束条件下利用单纯形法求解 第二阶段 在第一阶段的最终单纯形表的基础上替换成原目标函数 去掉人工变量 继续求解 用二阶段法求解下列线性规划问题 maxz 3x1 x2 x3s t x1 2x2 x3 11 4x1 x2 2x3 3 2x1 x3 1x1 x2 x3 0 解 引入松弛变量x4 x5 标准形为 第一阶段 引入人工变量x6 x7 构造一个只包含人工变量的目标函数 maxw x6 x7x1 2x2 x3 x4 11s t 4x1 x2 2x3 x5 x6 3 2x1 x3 x7 1xj 0 j 1 2 7 用单纯形法求解得 maxz 3x1 x2 x3 0 x4 0 x5x1 2x2 x3 x4 11 4x1 x2 2x3 x5 3 2x1 x3 1x1 x2 x3 x4 x5 0 x1x2x3x4x5x6x7 CBXBb CB j i 00000 1 1 x4x6x7 0 1 1 111 211000 3 4120 110 1 2010001 0100 10 3 11 13 21 1 x4x6x3 0 10 103 20100 1 10100 11 2 1 2010001 6130 100 i 1 1 j x1x2x3x4x5x6x7 CBXBb CB j 00000 1 1 x4x2x3 000 123001 22 5 1 2010001 10100 11 2 00000 1 1 最优解为 X x1 x2 x3 x4 x5 x6 x7 T 0 1 1 12 0 0 0 T最优值 Z 0人工变量x6 x7皆为0 说明原问题具有可行解 并找到原问题的一个可行基 单位矩阵p4 p2 p3 进入第二阶段 maxz 3x1 x2 x3 x1x2x3x4x5x6x7 CBXBb CB j 00000 1 1 x4x2x3 000 123001 22 5 1 2010001 10100 11 2 00000 1 1 x1x2x3x4x5 CBXBb CB j 3 1 100 x4x2x3 0 1 1 123001 2 1 20100 10100 1 1000 1 i 12 3 000 1 3 1 3 x1x2x3 3 1 1 90012 3 4 3 j 10100 1 41001 3 2 3 x1x2x3x4x5 CBXBb CB j 3 1 100 x4x2x3 0 1 1 123001 2 1 20100 10100 1 1000 1 i 12 3 所以原线性规划问题具有唯一最优解 最优解 X 4 1 9 T最优值 Z 2 练习 两阶段法求解 无可行解的情况 最终单纯形表得基变量中 仍然有非零人工变量 则原问题无可行解 在单纯形法计算过程中 基变量有时存在两个以上相同的最小比值 这样在下一次迭代中就有一个或几个基变量等于零 这称之为退化 2 5 3退化问题 得到最优解x1 1 x2 0 x3 2 x4 1 x5 0 x6 0 其最优值为5 在单纯形法计算过程中 基变量有时存在两个以上相同的最小比值 这样在下一次迭代中就有一个或几个基变量等于零 这称之为退化 退化的出现原因是模型中存在多余的约束 使多个基可行解对应同一顶点 当存在退化问题时 就可能出现迭代计算的循环 尽管可能性极其微小 勃兰特 Bland 法则 首先我们把松弛变量 剩余变量 人工变量都用xj表示 一般松弛变量 剩余变量 的下标号列在决策变量之后 人工变量的下标号列在松弛变量 剩余变量 之后 在计算中 遵守以下两个规则 1 在所有检验数大于零的非基变量中 在存在两个和两个以上相等的检验数时 选一个下标最小的作为入基变量 2 在存在两个和两个以上最小比值时 选一个下标最小的基变量作为出基变量 这样就一定能避免出现循环 线性规划的练习题 习题一下表为求极大化的单纯形表 问表中a1 a2 c1 c2 d为何值及表中变量为哪一类型时 1 表中解为唯一最优解 2 表中解为无穷多最优解之一 3 表中解为退化的可行解 4 下一步迭代将以x1替代基变量x5 5 该问题具有无界解 6 该问题无可行解 习题二线性规划的目标函数是maxZ 在用标准的单纯形法求解的过程中 得到下表 其中a b是常数 部分数据有缺失 1 在所有的空格中填上适当的数 其中可含a b参数 2 判断以下四种情况在什么时候成立 并简要说明理由 1 此解为最优解 试写出相应的基解和目标函数值 2 此解为最优解 且此规划有无穷多最优解 3 此规划有无界解 4 此解不是最优解 且能用单纯形法得到下一个基可行解 习题三已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到的表如下所示 试求括号中未知数a l的值 ThankYou Addyourcompanyslogan 人有了知识 就会具备各种分析能力 明辨是非的能力 所以我们要勤恳读书 广泛阅读 古人说 书中自有黄金屋 通过阅读科技书籍 我们能丰富知识 培养逻辑思维能力 通过阅读文学作品 我们能提高文学鉴赏水平 培养文学情趣 通过阅读报刊 我们能增长见识 扩大自己的知识面 有许多书籍还能培养我们的道德情操 给我们巨大的精神力量 鼓舞我们前进