ch3线性规划及其对偶问题修改后.ppt

第3章线性规划 LinearProgramming 1 线性规划 LinearProgramming 是最优化方法中理论完整 方法成熟 应用最广泛的一个分支 线性规划问题最早是前苏联学者康德洛维奇 L V Kantorovich 于1939年提出的 1952年 美国国家标准局 NBS 在当时的SEAC电子计算机上首次实现单纯形算法 1947年G B Dantzig提出了单纯形方法 Simplexmethod 2 LinearProgramming常研究两类问题 一类是当一项任务确定后 如何统筹安排 尽量做到以最少的人力 物力资源去完成 另一类是已有一定数量的人力 物力资源 如何安排使用它们 使完成的任务 或创造的财富 利润 最多 3 3 1线性规划的数学模型基本原理 4 线性规划数学模型的一般形式为 3 1 1线性规划模型的标准形及其转化 我们常考察以下两种形式的线性规划问题 称以下的形式为标准形式 StandardForm 记 称D标准形线性规划问题 3 3 的可行域 5 6 简化式为 向量形式为 1 极小化目标函数的问题 设目标函数为 令 则 尽管以上两个问题的最优解相同 但他们最优解的目标函数值却相差一个符号 即 7 化为标准形式线性规划问题 2 约束条件不是等式的问题 设约束条件为 引入松弛变量 当约束条件为 则同样令 约束条件成为 8 松弛变量的经济意义是还有没被利用的资源 例3 1将以下线性规划问题转化为标准形式 将目标函数转换成极大化 并分别对约束 1 2 引进松弛变量x4 x5 得到以下标准形式的线性规划问题 3 变量无符号限制的问题 在标准形式中 每一个变量都有非负约束 当一个变量xj没有非负约束时 称为自由变量 可以令 其中 即用两个非负变量之差来表示一个无符号限制的变量 的符号取决于和的大小 10 例3 2将以下线性规划问题转化为标准形式 令 引进松弛变量并令得到以下等价的标准形式 图解法的基本思想是先将约束条件加以图解 求得满足约束条件的可行域 然后结合目标函数从可行域中求得最优解 对于只有两个变量的线性规划问题 可以在二维直角坐标平面上表示线性规划问题 3 1 2线性规划的图解法 例3 3求解下列线性规划问题 其中满足约束 3 4 的点位于坐标平面上直线靠近原点的一侧 满足约束 3 5 的点位于坐标平面上直线的靠近原点的一侧 变量x1 x2的非负约束表明满足约束条件的点同时应位于第一象限内 如图中阴影部分所示 令z z0为某一确定的目标函数值 取一组不同的z0值 在图上得到一组相应的平行线 称为目标函数等值线 在同一条等值线上的点 相应的可行解的目标函数值相等 在图中 给出了z 0 z 3 z 6 等一组目标函数等值线 对于目标函数极大化问题 这一组目标函数等值线沿目标函数增大而平行移动的方向 即目标函数梯度方向 就是目标函数的系数向量C c1 c2 cn 对于极小化问题 目标函数则沿 C方向平行移动 14 目标函数等值线在平行移动过程中与可行域的最后一个交点是点 这就是线性规划问题的最优解 这个最优解可以由两直线 线性规划问题的可行域是一个凸多边形 线性规划的可行域以及最优解具有以下性质 1 若线性规划的可行域非空 则可行域必定为一凸集 2 若线性规划有最优解 则最优解至少位于一个极点上 在一般的n维空间中 n个变量 m个约束的线性规划问题的可行域也应具备这一性质 15 的交点求得最优解的目标函数值为 线性规划的可行域和最优解的几种可能的情况 可行域为封闭的有界区域 1 有唯一的最优解 2 有一个以上的最优解 16 可行域为非封闭的无界区域 1 有唯一的最优解 2 有一个以上的最优解 17 目标函数无界 即虽有可行解 但在可行域中 目标函数可以无限增大或无限减小 因而没有最优解 可行域为空集 因而没有可行解 18 考察标准形式 StandardForm 线性规划问题 记 称为标准形线性规划问题的可行域 19 定义3 1 1 线性规划的基 Basis 对于线性规划的约束条件 3 1 3线性规划的概念与基本定理 设A的秩为m B是A矩阵中的一个非奇异的m阶子矩阵 则称B为线性规划的一个基矩阵 简称为基 设B是线性规划的一个基 则A可以表示为A B N x也可相应地分成 20 其中xB为m维向量 称为基变量 其分量与基B的列向量对应 xN为n m维向量 称为非基变量 其分量与非基矩阵N的列对应 这时约束等式Ax b可表示为 或 若取确定的值 则有唯一的值与之对应 特别 取 这时有 21 定义3 1 2 基解 BasicSolution 基可行解 BasicFeasibleSolution 和可行基 FeasibleBasis 各类解的关系 线性规划的解 称为线性规划与基B对应的基解 若其中B 1b 0 则称以上的基解为一基可行解 相应的基B称为可行基 定理3 1设x是标准型线性规划问题的可行解 x为其基可行解的充分必要条件是 x的正分量所对应的系数列向量线性无关 23 定理3 2 线性规划问题几何理论基本定理 设x为标准型线性规划问题的可行解 x为其的基可行解的充分必要条件是x为可行域D的极点 推论 标准型线性规划问题的可行域最多具有有限个极点 证明 由基解的定义可知 标准型线性规划问题的基解个数最多为 个 而基可行解集合只是基解集合的一个子集 即极点集合只是基解集合的一个子集 所以极点的个数 24 定理3 3若标准型线性规划问题存在可行解 则它一定存在基可行解 定理3 4若标准型线性规划问题存在最优解 则必存在基可行解是最优解 线性规划问题的各种解与其极点有着密切的关系 特别是有下面的对应关系 基可行解可行域 凸集 D的极点 3 2单纯形方法 SimplexMethod 将顶点逐点转移 根据LP的标准形 从可行域中一个基本可行解 一个顶点 开始 转移到另一个基本可行解 同时使目标函数值逐步优化 增大 当目标函数值达到最优值时 问题就得到了最优解 线性规划的基本定理表明 一个线性规划问题若有最优解 则一定有最优的基可行解 而且基可行解的个数不会超过个 25 问题 如何找到第一个基本可行解 如何判断是否为最优解 如何从一个基本可行解 另一个尚未检查到的基本可行解 最简单方法 基解中取零的变量个数不少于n m个 令自由变量取值为零相应得到的解 由r A m 解出m个基本变量 剩下的n m个变量为自由取值的变量 称为自由变量 26 单纯形法的基本思想是 给出一种规则 使由标准型线性规划问题一个基可行解 极点 转移到另一个基可行解 目标函数值是增大的 而且两个基可行解之间的转换是容易实现的 经过有限次迭代 即可求得所需的最优基可行解 27 单纯形方法的经济解释 例3 4 假设某工厂生产A B C三种产品 每吨利润分别为4万元 1万元 5万元 生产单位产品所需的工时及原材料如表所示 若供应的原材料每年不超过3000吨 所能利用的劳动力年总工时不超过8000小时 问如何制定年生产计划 使三种产品总利润最大 28 解 用x1 x2 x3表示三种产品A B C的产量 则有线性规划问题 化为标准形式为 29 目标函数中松弛变量的价值系数为0 其经济意义是没有被利用的资源 约束条件的系数矩阵为 30 取基矩阵 基矩阵不惟一 对应于基矩阵的基变量为 目标函数用非基变量表示为 当工厂未做生产时 此时 工时和原材料都没被利用 取 31 工厂不产生利润 z 0 得一个基解 由于目标函数中非基变量的系数都为正 若将非基变量变为基变量 也就是说安排产品生产 就可以增加工厂的利润 首先应选获利最大的产品投产 取目标函数中系数 贡献系数 最大的非基变量转化为基变量 本例取x3 由 且x1 x2 0 有 32 取 这表明生产750吨产品C 刚好将3000吨原材料用完 此时x5 0 但用去工时750 4 3000小时 工时x4还有5000小时仍未被利用 得新基可行解 从经济意义看 3000吨原材料生产了750吨产品C 化简为 33 即x3变为基变量 x5变为非基变量 也称为用x3置换x5故有 令非基变量 得 并得基矩阵 34 约束条件的系数矩阵化为 由于目标函数中非基变量x1的系数仍然为正 若将非基变量x1变为基变量 也就是说增加产品A的生产 还可以增加工厂的利润 与前面类似地推算得 35 即 由于目标函数中非基变量的系数全为负 这些变量的增加 将导致工厂的利润减少 得最佳生产方案为 36 最优解为 最优值为 约束条件的系数矩阵可化为 现考查标准型线性规划问题 设系数矩阵A的秩为m 设是基变量 是非基变量 则基矩阵为 非基向量构成的矩阵为 37 3 2 1单纯形法的计算步骤 系数矩阵A分解为A B N 其中N叫作非基矩阵 把向量x和c也分别作相应的分解 其中xB cB表示与基变量对应的m维列向量 xN cN表示与非基变量对应的n m维列向量 约束方程组Ax b可表示为 即 38 解得 代入目标函数有 原线性规划问题可表示为 39 令 则有 40 原线性规划问题又可表示为 线性规划的这种形式叫作与基变量对应的规范式 典式 41 若基变量为 设基变量的下标集为 与基变量对应的规范式为 其中 T表示非基变量的下标集 即T 1 2 n S 42 由线性规划的规范式 令非基变量 得到一个基解 其中 当时 是基可行解 在与基变量对应的规范式中 因为是单位向量 所以当时 43 定义3 2 1称为变量xj的判别数或检验数 写成向量形式为 即 44 设x 0 是线性规划 3 6 对应于基B p1 p2 pm 的基可行解 与基变量x1 x2 xm对应的规范式中 若x 0 的全体检验数非正 即 j 0 j 1 2 n则x 0 是 3 6 的最优解 45 定理3 5 最优性条件 定理3 6设x 0 是线性规划 3 6 对应于基B p1 p2 pm 的基可行解 与基变量x1 x2 xm对应的规范式中 若存在 k 0 且对所有的i 1 2 m有 ik 0 则线性规划问题 3 6 无最优解 由定理3 5和定理3 6可以知道 对于某个基可行解 在它的规范式中 若所有判别数非正 则是最优解 若其中某个分量的判别数为正 且规范式中与相对应的列向量中所有分量都是非正时 该线性规划无最优解 46 设是 3 6 对应于基B p1 p2 pm 的基可行解 在规范式中若所有的正检验数 j j m 1 m 2 n 其对应变量xj的系数 1j 2j mj中至少有一个大于零时 就应迭代到另一个基可行解 新基是在原有基的基础上修改而得到的 其具体做法是 在原来的非基变量中选取一个变量 让它变为基变量 再从原来的基变量中选一个 让它变为非基变量 构成一个新的基可行解 47 1 确定进入基的变量 任意一个与正判别数相对应的变量都可以作为进入基的变量 一般令 则xk取为进入基的变量 pk为进入基的向量 由 3 9 式知 当与 k对应的xk变为基变量时 它的值将由零变为正数 目标函数值会有所上升 48 2 确定离开基的变量 设已确定xk为进基变量 由式 3 8 令 则有 当时 对于任意的总有 当时 取 49 此时 并且显然满足 也就是说 我们得到了一个新的可行解 50 可以证明变量组是一组基变量 设是基变量 是非基变量 总结单纯形法的基本理论 令 设则 如果是基可行解 当不成立 不妨设以及不成立 说明 不是最优解 那么怎样从转化到另一个基可行解 1 确定进入基的变量 一般令 选取为进入基变量 2 确定离开基的变量 要保证所有为非负数 选取为离基变量 定义3 2 2若基可行解中存在值为0的基变量 则称此基可行解为退化的基可行解 相应的基称为退化的可行基 基变量均取正值的基可行解称为非退化的基可行解 相应的基称为非退化的可行基 定义3 2 3若线性规划问题 3 6 的所有基可行解都是非退化的 则称 3 6 为非退化的 55 定理3 7设x是线性规划 3 6 的一个基可行解 若x是非退化的 按上述方法得到新的基可行解 满足 由定理可知 若线性规划 3 6 的所有基可行解都是非退化的 则每次迭代都使目标函数值有所增加 已经出现过的基可行解在迭代过程中不会再出现 而基可行解只有有限个 因此 经过有限次迭代 一定可以得到一个基可行解x 对于这个x 或者它的全部判别数非正 或者存在正判别数 k 0 但对应的列向量 ik中所有分量都小于或等于零 也就是说 对于非退化的线性规划问题经过有限步一定可以使迭代停止 上述求解线性规划的方法叫单纯形法 56 单纯形法的迭代步骤 设已经确定了为进入基的向量 为离开基的向量 得到一个新的基 对于这个新基 需要给出对应的规范式 算法 单纯形法 1 写出初始基可行解 并计算检验数 2 若所有的检验数 则得到了最优解 停 否则转3 57 4 令 用取代得到新基 5 以 lk为主元进行旋转变换 得到新的基可行解及检验数 对于j 1 2 n 转2 58 将线性规划 1 写成表格形式 左上端 左列 顶行 求解线性规划即可以运用如下的运算 1 顶行以下部分进行行交换 2 顶行以下某一行乘一非零常数 3 顶行以下的行进行倍加运算 4 将顶线以下乘常数后加至顶行 包括左上端 上 59 右行 当表格具有如下特点 1 中心部位具有单位子块 2 左列元素非负 3 顶行相应于单位子块位置的元素为0 4 顶行其它元素非正 则从表格中立即可以读出线性规划的最优解和最优值 最优解的读法为 单位子块中1所对应的变量取相应左列的值 不在单位子块位置中的变量取值0 而左上端元素的负值为线性规划 3 6 的最优值 60 例3 5线性规划 经过运算最后得到表 61 此表具备了四个特点 于是从表上就可读出最优解 单位子块由第一 二列构成 第一列中的1对应的变量x1为取值为左列中的3 第二列中的1对应的变量为x2取值为左列中的8 不在单位子块位置的变量x3 x4均取值0 即最优解 3 8 0 0 T 最优值即为21 当目前的基可行解不是最优解 如何过渡到另一个基可行解呢 62 单纯形法就是保证第 1 2 3 三个特点不被破坏的条件下 逐步得出第 4 个特点的具体步骤 由于x2基变量 首先将其对应的检验数变为0后得表 63 单纯形法的步骤 前提 设当前的表格已具备第 1 2 3 三个特点 设一般为 64 具体的如表 1 从顶行正元素中任选一个 设为 这一步称为选择进基变量 令 65 2 从所选元素对应列 列 顶线以下的正元素中按下列规则选定一元素 3 利用初等行变换 把变为1 该列的其它元素变为0 类似于Gauss Jordan消去法 4 若顶行元素均非正 算法终止 否则回 1 66 由定理3 7 在已知一个基可行解 初始基可行解 的前提下 使用单纯形求解线性规划时 若每次迭代得出的基可行解的基变量均大于零 即非退化 则算法必有限步终止 67 例3 6用单纯形法求解 解 先化为标准形 68 列成表格 69 70 3 2 2初始基可行解的求法 用单纯形法求解线性规划问题 首先需要确定一个初始基可行解 以便使迭代计算能够进行下去 而实际的问题可能是 约束方程组的系数矩阵中不含单位矩阵 71 1 大M法 设原线性规划问题的标准形式如下 3 10 引入人工变量 记 构造新的线性规划问题 3 11 其中是一个充分大的数 问题 3 10 与 3 11 的解之间有如下的关系 72 定理3 8设是问题 3 11 的最优解 若y 0 则x 是问题 3 10 的最优解 若y 0 则问题 3 10 没有可行解 反之 若x 是问题 3 10 的最优解 则是问题 3 11 的最优解 73 定理3 8表明 为了得到问题 3 10 的最优解 只需去求解问题 3 11 而问题 3 11 的初始基本可行解是明显的 实际计算中 在手算时只要把M作为一个足够大的正数来处理即可 而在计算机上运算时 可赋以足够大的具体正数 例3 7求解下列线性规划问题 74 列成表格 75 增加人工变量得 64 3 2 3101 2101 76 100 00 22 12 3 11 300 8 32 1 31 7 0 5 30 5 6 M 31 1 2 301 61 20 4 31 1 61 2 最优解 最优值 77 例3 8求解下列线性规划问题 78 此问题的可行域为空集 该线性规划问题无解 现用大M法来求解 解 引进松弛变量和人工变量 得新线性规划问题 79 列成表格 80 23 00 1 1111010 0 1 M M 20 此时人工变量x5 0 原线性规划问题无可行解 2 两阶段法 设要求解的线性规划问题为 3 10 引入人工变量 记 构造一个新的线性规划问题 3 12 问题 3 10 与 3 12 的解之间有如下关系 81 定理3 9若问题 3 12 的最优基可行解为 则x 为问题 3 10 的一个基可行解 若问题 3 12 的最优基可行解为 且y 0 则问题 3 10 没有可行解 82 定理3 9说明 为了获得问题 3 10 的一个初始基可行解 可以先求解辅助问题 3 12 从它的最优基可行解 即可得到问题 3 10 的一个基可行解 将求解问题 3 10 分为两阶段 阶段1 求解辅助线性规划问题 3 12 它的初始基可行解是明显的 阶段2 求解原线性规划问题 3 10 83 例3 9求解如下线性规划问题 解 增加人工变量x6 x7得辅助线性规划问题 84 将f x g x 改写为 85 86 最优解 最优值 P33 习题1 1用图解法求解线性规划问题 1 习题1 3用单纯形法线性规划问题 1 和 3 87 3 3对偶问题的基本原理 对于同一个实际问题 从不同的角度进行分析和研究 可以根据同样的条件和数据构成两个不同的问题 一个是求目标函数的最小值 另一个是求另一个目标函数的最大值 它们之间存在着确定的关系 当有限的最优解存在时 二者的最优值必定相等 研究两个互为对偶的线性规划问题的解之间的这些关系就构成了线性规划的对偶理论 88 3 3 1对偶问题提出 例3 10设某工厂有m种设备 B1 B2 Bm 一年内各设备的生产能力 有效台时数 为b1 b2 bm 利用这些设备可以加工n种产品 A1 A2 An 单位产品的利润分别为c1 c2 cn 第j种产品需要在第i种设备上加工的台时数为aij 问在设备能力容许的条件下怎样安排生产计划 使全年收入最多 89 解 设x1 x2 xn为各产品的计划年产量 z为全年总收入 则问题归结为解下面的线性规划问题 假设该厂用这些设备承担对外加工任务 需要给各种设备制订价格 收费标准 订价原则有两条 一是用这些设备仍加工原来的第j种产品Aj 每件 时 工厂收入不少于cj 二是工厂全年对外加工的收入尽量少 否则将得不到加工任务 90 设第i种设备Bi的单位台时的单价为yi 全年加工总收入为w 则问题归结为解下面的线性规划问题 第一个问题称为原始线性规划 变量中的称为原始变量 第二个规划问题称为第一个规划问题的对偶规划 中的称为对偶变量 91 定义3 3 1设线性规划 及另一个线性规划 LP 3 13 DP 3 14 其中A是m n矩阵 则称线性规划问题 3 14 是线性规划问题 3 13 的对偶线性规划 称问题 3 13 为原始线性规划 它们合起来称为一对对称的对偶线性规划问题 92 93 如原问题 的对偶问题为 定理3 10 对合性 对偶线性规划问题的对偶问题是原始线性规划问题 证明 设原始线性规划问题为 3 13 对偶问题 3 14 3 14 等价于 其对偶线性规划为 它又等价于 3 13 94 3 3 2原问题与对偶问题的表达形式和关系 定理3 11若线性规划问题 3 13 的第个约束为等式约束 即 则其对偶线性规划 3 14 中对应的第k个变量yk为自由变量 95 定理3 12若规划问题 3 13 的第l个变量xl是自由变量 则其对偶规划 3 14 中对应的第l个约束为等式约束 等式约束线性规划 3 15 的对偶规划为 3 16 这对对偶线性规划又叫做非对称形式的对偶线性规划问题 96 事实上将标准型线性规划改写为 97 由对称对偶线性规划的结论得其对偶规划为 98 如原问题 的对偶问题为 99 对混合约束的线性规划问题 其中A1是m1 n阶矩阵 A2是m2 n阶矩阵 A3是m3 n阶矩阵 b1 b2 b3分别是m1维 m2维 m3维列向量 c也是n维列向量 x是n维列向量 为给出对偶问题 先引入松弛变量 有等价形式 100 其中xs是m1个松弛变量组成的m1维列向量 xt是m3个松弛变量组成的m3维列向量 即 101 由等式约束对偶问题的结论 有对偶问题 102 即对偶规划问题为 其中y1 y2 y3分别是m1维 m2维 m3维列向量 例3 11写出下列线性规划的对偶规划 103 解 设对偶变量为 此时 其对偶线性规划为 自由变量则其对偶为 104 105 最大化问题的 约束 对最小化问题的 约束 相应的对偶规划问题的变量有非负限制 即要求 对最大化问题的 约束 最小化问题的 约束 相应的对偶规划问题的变量有非正限制 即要求 对原问题的 约束 相应的对偶规划问题的变量无符号限制 即自由变量 由前面三种形式的对偶问题可得到一般的规则 若原问题是最小化问题 则对偶问题是最大化问题 若原问题是最大化问题 则对偶问题是最小化问题 在原问题和对偶问题中 约束右端向量与目标函数中系数向量恰好对换 106 最大化问题的非正限制变量 对最小化问题的非负限制变量 相应的对偶规划问题的约束为 型不等式约束 对最大化问题的非负限制变量 最小化问题的非正限制变量 相应的对偶规划问题的约束为 型不等式约束 对原问题的无符号限制变量 即自由变量 相应的对偶规划问题中为等式约束 定理3 13 弱对偶性 若是原始线性规划 3 15 的可行解 是对偶线性规划 3 16 的可行解 则有 107 证明 因为分别是 3 15 3 16 的可行解 所以有 3 3 3对偶理论 推论若是原始线性规划问题的可行解 是其对偶问题的可行解 且 则与分别是原始线性规划问题与其对偶问题的最优解 定理3 14 对偶性 若原始线性规划问题与对偶线性规划问题之一有最优解 则另一个也有最优解 并且它们目标函数的最优值相等 证明 由对称性 只需证明原规划问题有最优解的情况即可 设是原规划问题的最优基可行解 对应的基矩阵为 目标函数为对应的检验数 则令则 即是对哦问题的可行解 并且 由推论可得是对偶问题的最优解 108 109 定理3 15若原始线性规划问题与对偶线性规划问题之一具有无界的目标函数值 则另一个无可行解 定理3 16设B是原始线性规划问题 3 15 的一个基矩阵 对应的基解满足最优性条件 则对偶线性规划问题 3 16 有可行解 而且 定理4 8 互补松弛性 设x y分别是原始线性规划问题 3 15 与对偶规划问题 3 16 的可行解 x y分别是 3 15 和 3 16 的最优解的充分必要条件为 110 两个互为对偶的线性规划问题的解之间有如下几种可能情况 1 两个问题都有最优解 且目标函数的最优值相等 2 两个问题都不存在最优解 3 一个问题存在可行解 但目标函数在可行域上无界 另一个规划问题不存在可行解 3 3 4对偶单纯形法 用单纯形法解线性规划 是从一个基可行解开始 检验它的检验数是否全部非正 如果所有检验数非正 这时可行解就是最优解 如果存在正检验数 则迭代到另一个基可行解 当求出了线性规划的最优解时 相当于求出了一个基矩阵B 使得基变量 而且检验数向量满足 111 满足条件 说明与基矩阵B对应的基解是线性规划的可行解 满足条件说明是其对偶线性规划的可行解 单纯形法可以解释为 从一个基解迭代到另一个基解 迭代过程中始终保持基解的可行性 但不保证是其对偶线性规划的可行解 而是逐步满足其对偶规划解的可行性 当是其对偶规划的可行解时 相应的基可行解就是问题的最优解 求解线性规划的过程也可以从线性规划问题的一个基解出发 迭代过程中不要求基解满足可行性 即允许基解中存在负分量 但是要求始终保持基解的判别数是非正的 即始终保持为其对偶线性规划的可行解 逐步减少基解中的负分量的个数 当基解中没有负分量时就得到了问题的最优解 这种迭代方法就是对偶单纯形法 112 对偶单纯形法的迭代仍然是以 lk为主元的旋转变换 但是它也有自己的特点 它是首先确定离开基的变量 即首先确定xl 然后确定进入基的变量 即确定xk 1 最优性的判别 已知线性规划问题的一个基B及与它对应的基解为 并且此基解的所有判别数非正 若则所得到的基解为最优解 113 2 确定离开基的变量 令 则xl为离开基的变量 对应的向量pl为离基向量 若存在且所有系数 则线性规划问题没有可行解 否则设是问题的可行解 则满足 这与是可行解矛盾 114 3 确定进入基的变量 设进入基的变量为xk 分析xk必须满足什么条件 才能使迭代后的基解仍保持所有的判别数非正 用xk替换xl后 其规范式中的目标函数为 为了保持判别数非正 应该有 115 为使第一式成立要求 从而对于第二式 当时恒成立 当时 要求 令 则xk为进基变量 pk为进基向量 利用上述原则选取离基变量与进基变量 若每次迭代均有 则迭代前的目标函数值f0与迭代后的目标函数值满足 116 算法 对偶单纯形法 设 3 15 的初始基矩阵为B 对应的基解为 该基解的所有判别数非正 2 若存在且 则线性规划问题无可行解 停 否则令 计算 3 以为主元进行旋转变换 得到新的基解 转 1 117 1 若 则得最优解 停 否则转2 转 3 例3 12求解线性规划问题 解法1两阶段法 见例3 9 118 解法2对偶单纯形法 原问题等价于 即 有单纯形表 119 原线性规划的最优解为 最优值为 120 121 在前面讨论的线性规划问题中 我们总是假定约束条件系数矩阵A 约束条件右侧常数b和目标函数的价值系数向量C中的元素均为常数 保持不变 在应用中 这些系数常常是通过估计 预测或人为决策而得到 不可能十分准确或一成不变 例如市场条件改变就会导致价值系数跟着变化 随着工艺条件的改变 单位资源消耗量aij也会发生变化 资源限制量bi通常取决于现有条件或决策人的决策 随着条件的改变 以及决策人根据投入资源的经济效果分析而采用新的决策 其数值也会发生变化 3 4线性规划的灵敏度分析 灵敏度分析是要在求得最优解以后 解决以下几方面的问题 1 线性规划问题中的各系数在什么范围内变化 不会影响已获得的最优基 2 如果系数的变化超过以上范围 如何在原来最优解的基础上求得新的最优解 3 当线性规划问题增加一个新的变量或新的约束 如何在原来最优解的基础上获得新的最优解 122 3 4 1目标函数的系数发生变化 当目标函数系数ck的数值发生变化时 只会影响最优解中检验数的值 而不会影响基变量的值 也即是说 目标函数系数中的元素发生变化只会影响最优解的对偶可行性而不会影响原问题的可行性 123 1 当xk是非基变量时 设xk在目标函数中的系数从ck变化成为 此时ck的变化只影响到非基变量xk的检验数 对规范式中其它非基变量的检验数和约束方程组中的所有系数都无影响 此时 当即 则原来的最优解仍是最优解 且目标函数的最优值保持不变 当即原来的最优基已不再是最优基了 将xk作为换入变量 进行单纯形迭代就可得到新的最优基和最优解 124 例3 13设有线性规划问题 1 问c2 1在什么范围内变化 原来的最优基保持不变 2 当时最优基是否变化 如果变化 求新的最优基和最优解 125 解 通过单纯形方法计算得最终单纯形表为 此时 当时 有 即x2在目标函数中的系数从原来的值增加到2时 最优基保持不变 此时最优解以及目标函数的最优值也不会变化 126 当时 已超出保持最优解不变的范围 因此最优基已发生了变化 此时单纯形表变化为 x2作为换入变量 x5作为换出变量有 最优解最优值 127 2 当xk是基变量时 当即时最优解不变 即 此时最优解仍为 但目标函数的最优值却为 增加量为 当基变量xk的系数由ck变为 此时ck的变化将影响所有非基变量的检验数 设非基变量的检验数为 则 128 例3 14设有线性规划问题 对c1 1进行灵敏度分析 129 解 通过计算得到最优单纯形表为 当即时 最优基保持不变 当的变化超出以上范围时 至少有一个检验数不满足最优解条件 用单纯形方法继续迭代就可得到新的最优基和最优解 130 例3 15分析下来参数规划中当t变化时最优解的变化情况 131 解 先化为标准形 132 令t 0 用单纯性法进行求解 列成表格 133 134 下面将C的变化直接反映到最终表中 当时 最优解最优值 3 4 2约束条件右边的常数发生变化 当右边常数由bk变为时 此时 规范式的检验数保持不变 右侧常数的变化只影响了最优基的可行性而不会影响其对偶可行性 设基阵 新的基解 则 其分量为由有 B仍是最优基矩阵 基变量仍是原来的基变量但其取值发生了改变 135 例3 16对例3 14的线性规划问题的第一个约束条件右边常数b1 9进行灵敏度分析 解 即时 原来的最优基保持不变 当超过上述范围时 如取有 此时的单纯形表为 136 用对偶单纯形法求解有 最优解 最优值14 137 3 4 3增加一个新的变量 设在原线性规划问题中增加一个新变量xn 1 该变量在目标函数中的系数为cn 1 约束矩阵中的系数向量为 此时只需在原问题的最后单纯形表中增加一列 若 则原最优基 基变量 最优值保持不变 即增加变量xn 1对改进目标函数值没有帮助 若 则以xn 1为换入变量 继续用单纯形方法迭代 138 例3 17在例3 13的线性规划问题中 增加一个新变量x6 它在目标函数中的系数c6 1 约束条件中的系数向量为p6 1 2 T 求新的最优基和最优解 解 在原最终单纯形表中增加一列有 139 取x6为换入变量 x5为换出变量进行迭代有 最优基B p1 p6 最优解 16 0 0 0 0 10 T 最优值22 140 3 4 4增加一个新约束条件 当增加约束条件后 原最优解满足该约束条件 则原最优解仍是新问题最优解 若原最优解不满足新增加的约束条件 需重新迭代计算以寻求新的最优解 解 增加松弛变量x6 在原最终单纯形表中增加一行有 例3 18对例3 13的线性规划问题中 增加一个约束条件 x1 2x3 2 求新的最优基和最优解 141 用对偶单纯形法求解有 新的最优解为 10 3 0 8 3 0 22 3 0 T 最优值为28 3 142 3 3 5约束条件系数矩阵A的元素发生变化 设A中的某个元素ark变成了 而其它系数保持不变 当xk为非基变量时 元素ark的变化只影响到一个检验数 变化后的判别数为 其中yr是向量的第r个元素 为保持最优基不变 只需 143 由此可得 1 若 则当时最优基阵 最优解 最优值不变 2 若 则当时最优基阵B 最优解 最优值不变 3 若yr 0 则 ark可取任意值 144 例3 19在例3 14的线性规划问题中 对变量x2在第一个约束条件中的系数a12 1进行灵敏度分析 解 从该问题的最终单纯形表中可得 即时 原来的最优基保持不变 当xk为基变量时 此时原最优解的可行性以及最优性都可能遭到破坏 一般来说 需用单纯形方法从头到尾加以重新计算 以寻求最优基和最优解 145 3 5 1整数规划的概念及数学模型 整数规划 IntergerProgramming 是最优化问题的一个分支 它研究的是一类要求部分变量或全部变量取整数的最优化问题 1 全整数规划 AllIntergerProgramming 要求所有的决策变量都是取整数值 称之为纯整数规划 2 混合整数规划问题 MixedIntergerProgramming 仅要求一部分决策变量取整数值 3 0 1规划 决策变量只能取0或1 146 3 5整数线性规划 例3 19 分配问题 设有m项工作需要交由m个人去完成 已知第i项工作交与第j个人完成时所用的时间为aij i j 1 2 m 要求每项工作只能交与其中一个人完成 每个人只能完成其中一项工作 问应如何分配才能使所用的总时间最少 解 设变量 有 147 例3 20设某物资有m个生产点 第i个生产点的产量为ai i 1 2 m 该物资销往n个销售点 第j个销售点的销售量为bj j 1 2 n 且 已知从各生产点到各需求点 需经p个中转站之一进行转运 若启用第k个中转站 不管转运量为多少均需发生固定费用fk 已知第k个中转站转运的最大容量为qk 用cik和dkj分别表示从i到k和从k到j的单位物资的运输费用 试制定调运方案 使总运费为最小 解 设 xik第i个生产点到第k个中转站转运物资数量 ykj第k个中转站运往第j个销售点的物资数量 148 得 149 例3 21现有一批每根长度为l的圆钢 需要截取n种不同长度的零件毛坯 长度为ai的毛坯需要mi段 i 1 2 n 为了方便 每根圆钢只截取一种长度的毛坯 问应当怎样截取才能使动用的圆钢数目最少 解 设用xi根长度为l的圆钢来截取长度为ai的毛坯 又设为每根l长的圆钢用来截成长ai的毛坯时可以得到的最多段数 则有 形如 其中A c b中的元素都为整数 3 17 151 在 3 17 中去掉xj为整数的条件就得到了线性规划问题了 这很容易给读者一个误导 似乎整数线性规划就是线性规划的一个特殊情形 152 这一点在表面上看是成立的 但实际上二者有本质上的区别 第一 线性规划的可行域是凸集 而整数线性规划的可行域常常不是凸集 第二 整数线性规划问题中的变量取整数 因此最优化问题只是在离散的整数点处才有意义 在具体求解整数规划时 能不能在先不考虑整数要求的条件下求解 然后通过直接把分数或小数 取整 来得到整数规划的解呢 这种方法常常是不行的 因为 取整 后得到的整数解不一定是可行解 那就更不一定是最优解了 因此对整数规划问题需要有专门的求解方法 本章只介绍两种常见的方法 3 5 2割平面法 CuttingPlaneMethod 基本思想是 在求解整数线性规划 3 17 时 先不考虑整数的条件 将其当作线性规划问题来求解 若线性规划问题的最优解恰为整数解 则这个整数解就是 3 17 的最优解 否则 设法在问题中增加一个适当的约束条件 称之为割平面 将包含该非整数最优解的一部分从可行域中割去 但保留任何一个整数可行解 这样进行下去 直到新的可行域的某个整数解恰好是问题 3 17 的整数最优解为止 153 割平面法是R E Gomory于1958年首先提出来的 所以又称为Gomory割平面法 假设去掉整数线性规划 3 17 中的整数条件后得到的线性规划为 3 18 称 3 18 为 3 17 对应的线性规划 设为 3 18 的最优解 并设分量为非整数的基变量 由最终的单纯形表可写出第r个约束方程为 3 19 其中T表示非基变量的下标集 154 将和分解为整数部分和非负分数之和 即 其中 x 表示不超过x的最大整数 将上二式代入约束方程 3 19 有 当所有的变量都取非负整数时 上式的左端是整数 为使等式成立上式的右端必须是整数 155 由有 由于右端是小于1的整数 故有 3 20 3 20 是所有变量都取非负整数时必须满足的条件 称之为割平面方程 将其添加到整数线性规划 3 17 中有 3 21 156 将割平面方程的系数和常数均化为整数并引入松弛变量xn 1 0 xn 1为整数 3 22 将约束条件增添到前面得到的最终单纯形表中 增加一个约束条件和一个变量 157 由于割平面方程仅是得出整数解的必要条件 所以不能保证一次切割就能达到整数解 常常需要经过多次切割 迭代 最终得到 3 17 的整数解 另外线性规划的某一个最优解可能有多个分数分量 由前面的分