大学运筹学课程知识点总结

1 用图解法求解下列线性规划问题 并指出问题具有惟一最优解 无穷多最优解 无界解还是 无可行解 83 105 120106 max 2 1 21 21 x x xx xxz 2 将下述线性规划问题化成标准形式 1 无约束4 03 2 1 232 142 224 5243min 4321 4321 4321 4321 xxxx xxxx xxxx xxxx xxxxz 解 令 zz 4 44 xxx 0 232 1422 224 55243 max 65 4 4321 6 4 4321 5 4 4321 4 4321 4 4321 xxxxxxx xxxxxx xxxxxx xxxxx xxxxxz 3 分别用图解法和单纯形法求解下述线性规划问题 并对照指出单纯形表中的各基可行解对应 图解法中的可行域的哪个顶点 0 825 943 510max 21 21 21 21 xx xx xx xxz 解 图解法 单纯形法 将原问题标准化 0 825 943 510max 4321 421 321 21 xxxx xxx xxx xxz Cj10500 CBBbx1x2x3x4 对应图解法 中的点 0 x3934103 0 x48 5 2018 5 j010500 O 点 0 x321 50 14 5 1 3 53 2 10 x18 512 501 54 j 16010 2 C 点 5x23 2015 14 3 14 10 x1110 1 72 7 j35 200 5 14 25 14 B 点 最优解为 1 3 2 0 0 最优值 Z 35 2 单纯型法步骤 转化为标准线性规划问题 找到一个初始可行解 列单纯型法步骤 转化为标准线性规划问题 找到一个初始可行解 列 出初始单纯型表 最优性检验 求出初始单纯型表 最优性检验 求 cj zjcj zj 若所有的值都小于 若所有的值都小于 0 0 则表 则表 中的解便是最优解 否则 找出最大的值的那一列 求出中的解便是最优解 否则 找出最大的值的那一列 求出 bi aijbi aij 选 选 取最小的相对应的取最小的相对应的 xijxij 作为换入基进行初等行变换 重复此步骤 作为换入基进行初等行变换 重复此步骤 4 写出下列线性规划问题的对偶问题 1 njmix njbx miax ts xcz ij j m i ij i n j ij m i n j ijij 1 10 1 1 min 1 1 11 无约束 ji ijjmi n i mjj m i ii yx njmicyy ts ybyaw 1 1 max 11 2 nnjx nnjx mmmibxa mmibxa ts xcz j j i n j jij i n j jij n j jj 1 10 2 1 1 max 1 1 11 1 1 1 1 无约束 mmiy mmiy nnjcya nnjcya ts ybw i i j m i iij j m i iij m i ii 1 2 10 1 2 1 min 1 1 1 1 1 1 1 无约束 5 给出线性规划问题 4 10 9 6 62 83 42max 321 432 21 421 4321 jx xxx xxx xx xxx ts xxxxz j 要求 1 写出其对偶问题 2 已知原问题最优解为 试根据对偶理论 T X0 4 2 2 直接求出对偶问题的最优解 解 1 4 10 1 1 43 22 9668min 31 43 4321 421 4321 jy yy yy yyyy yyy ts yyyyw j 2 因为 第四个约束取等号 根据互补松弛定理得 0 321 xxx 0 1 43 22 4 43 4321 421 y yy yyyy yyy 求得对偶问题的最优解为 最优值 min w 16 0 1 5 3 5 4 Y 例例 已已知知原原问问题题 Max z x1 2 2x2 3 3x3 4 4x4 x1 2 2x2 2 2x3 3 3x4 2 20 0 2x1 x2 3 3x3 2 2x4 2 20 0 x1 x2 x3 x4 0 和和对对偶偶问问题题 Min w 20y1 2 20 0y2 y1 2 2y2 1 1 2y1 y2 2 2 2y1 3 3y2 3 3 3y1 2 2y2 4 4 y1 y2 0 已已知知对对偶偶问问题题的的最最优优解解y1 1 2 y2 0 2 最最优优值值min w 28 求求原原问问题题的的最最优优解解及及最最优优值值 可可用用如如下下方方法法求求解解 引引入入将将原原问问题题和和对对偶偶问问题题化化为为标标准准形形式式 Max z x1 2 2x2 3 3x3 4 4x4 x1 2 2x2 2 2x3 3 3x4 x5 2 20 0 2x1 x2 3 3x3 2 2x4 x6 2 20 0 x1 x2 x3 x4 x5 x6 0 Min w 20y1 2 20 0y2 y1 2 2y2 y3 1 1 2y1 y2 y4 2 2 2y1 3 3y2 y5 3 3 3y1 2 2y2 y6 4 4 y1 y2 y3 y4 y5 y6 0 和和 1 y1 1 2 0 而而y1与与x5中中至至少少有有一一个个为为零零 故故x5 0 2 同同理理 y2 0 2 0 所所以以x6 0 3 对对偶偶问问题题的的第第一一个个约约束束条条件件在在取取最最优优值值时时 y1 2y2 1 2 2 0 0 2 2 1 1 6 6 1 1 这这就就表表示示该该约约束束条条件件的的松松弛弛变变量量 y3 1 6 1 0 0 6 6 0 0 y3与与x1中中至至少少有有一一个个为为零零 故故x1 0 4 同同理理 对对于于第第2个个约约束束条条件件在在取取得得最最优优值值时时 2y1 y2 2 1 2 0 0 2 2 2 2 6 6 2 2 y4 2 6 2 0 0 6 6 0 0 y4与与x2中中至至少少有有一一个个为为零零 故故x2 0 5 同同理理 对对于于第第3个个约约束束条条件件在在取取得得最最优优值值时时 2y1 3y2 2 1 2 3 0 0 2 2 3 3 y5 3 3 0 0 y5与与x3中中至至少少有有一一个个为为零零 故故x3 0或或者者x3 0 6 对对于于第第4个个约约束束条条件件的的分分析析也也可可得得到到x4 0或或者者x4 0 对对于于 5 和和 6 的的分分析析 对对于于确确定定原原问问题题的的最最优优解解没没有有 任任何何帮帮助助 但但从从 1 到到 4 的的分分析析中中得得知知 原原问问题题取取得得 最最优优解解时时 x5 0 0 x6 0 0 x1 0 0 x2 0 0 代代入入原原问问题题的的约约束束方方程程组组得得 2x3 3x4 20 0 3x3 2x4 20 0 解解此此方方程程组组 可可求求得得原原问问题题的的最最优优解解为为 x1 0 0 x2 0 0 x3 4 4 x4 4 4 x5 0 0 x6 0 0 弱对偶性的推论 弱对偶性的推论 1 1 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界 反之对偶问原问题任一可行解的目标函数值是其对偶问题目标函数值的下界 反之对偶问 题任一可行解的目标函数值是其原问题目标函数值的上界题任一可行解的目标函数值是其原问题目标函数值的上界 2 2 如原问题有可行解且目标函数值无界如原问题有可行解且目标函数值无界 具有无界解具有无界解 则其对偶问题无可行解 则其对偶问题无可行解 反之对偶问题有可行解且目标函数值无界 则其原问题无可行解 反之对偶问题有可行解且目标函数值无界 则其原问题无可行解 注意 本点性质的逆不成立 当对偶问题无可行解时 其原问题或具有无界解或无注意 本点性质的逆不成立 当对偶问题无可行解时 其原问题或具有无界解或无 可行解 反之亦然 可行解 反之亦然 3 3 若原问题有可行解而其对偶问题无可行解 则原问题目标函数值无界 反之对若原问题有可行解而其对偶问题无可行解 则原问题目标函数值无界 反之对 偶问题有可行解而其原问题无可行解 则对偶问题的目标函数值无界 偶问题有可行解而其原问题无可行解 则对偶问题的目标函数值无界 强对偶性强对偶性 或称对偶定理或称对偶定理 若原问题及其对偶问题均具有可行解 则两者均具有最优解 且它们最优解的若原问题及其对偶问题均具有可行解 则两者均具有最优解 且它们最优解的 目标函数值相等 目标函数值相等 互补松弛性互补松弛性 在线性规划问题的最优解中 如果对应某一约束条件的对偶变量值为非零 则在线性规划问题的最优解中 如果对应某一约束条件的对偶变量值为非零 则 该约束条件取严格等式 反之如果约束条件取严格不等式 则其对应的对偶变量一该约束条件取严格等式 反之如果约束条件取严格不等式 则其对应的对偶变量一 定为零 定为零 影子价格影子价格 资源的市场价格是其价值的客观体现 相对比较稳定 而它的影子价格则有赖于资资源的市场价格是其价值的客观体现 相对比较稳定 而它的影子价格则有赖于资 源的利用情况 是未知数 因企业生产任务 产品结构等情况发生变化 资源的影源的利用情况 是未知数 因企业生产任务 产品结构等情况发生变化 资源的影 子价格也随之改变 子价格也随之改变 影子价格是一种边际价格 影子价格是一种边际价格 资源的影子价格实际上又是一种机会成本 随着资源的买进卖出 其影子价格也将资源的影子价格实际上又是一种机会成本 随着资源的买进卖出 其影子价格也将 随之发生变化 一直到影子价格与市场价格保持同等水平时 才处于平衡状态 随之发生变化 一直到影子价格与市场价格保持同等水平时 才处于平衡状态 生产过程中如果某种资源未得到充分利用时 该种资源的影子价格为零 又当资源生产过程中如果某种资源未得到充分利用时 该种资源的影子价格为零 又当资源 的影子价格不为零时 表明该种资源在生产中已耗费完毕 的影子价格不为零时 表明该种资源在生产中已耗费完毕 影子价格反映单纯形表中各个检验数的经济意义 影子价格反映单纯形表中各个检验数的经济意义 一般说对线性规划问题的求解是确定资源的最优分配方案 而对于对偶问题的求解一般说对线性规划问题的求解是确定资源的最优分配方案 而对于对偶问题的求解 则是确定对资源的恰当估价 这种估价直接涉及资源的最有效利用则是确定对资源的恰当估价 这种估价直接涉及资源的最有效利用 对偶单纯型法 转化成标准的线性规划问题 确定换入基变量 对偶单纯型法 转化成标准的线性规划问题 确定换入基变量 bibi 小于小于 0 0 中的最中的最 小的那一排 再求 小的那一排 再求 cj zjcj zj aij aij 且 且 aij 0 aij0 d d 0 xj 0 d d 0 目标规划的图解法 先画绝对约束的可行域 然后按照优先性优目标规划的图解法 先画绝对约束的可行域 然后按照优先性优 先考虑某个目标约束 随着先考虑某个目标约束 随着 minmin 系数中系数中 d d 或者或者 d d 的增大移动曲线 画的增大移动曲线 画 出最合适的那条 直到最后出最合适的那条 直到最后 10 用割平面法解下列整数规划 1 且为整数 0 2054 62 max 21 21 21 21 xx xx xx ts xxz 解 引进松弛变量 将问题化为标准形式 用单纯形法解其松弛问题 43 x x cj1100 CBXBbx1x2x3x4 0 x36 2 1103 0 x42045015 j1100 1x1311 21 206 0 x480 3 218 3 j01 2 1 20 1x15 3105 6 1 6 1x28 301 2 31 3 j00 1 6 1 6 找出非整数解变量中分数部分最大的一个基变量 x2 并写下这一行的约束 3 2 2 3 1 3 2 432 xxx 将上式中的所有常数分写成整数与一个正的分数值之和得 3 2 2 3 1 0 3 1 1 432 xxx 将上式中的分数项移到等式右端 整数项移到等式左端得 4332 3 1 3 1 3 2 2xxxx 得到割平面约束为 3 2 3 1 3 1 43 xx 引入松弛变量 得割平面方程为 5 x 3 2 3 1 3 1 543 xxx cj11000 CBXBbx1x2x3x4x5 1x15 3105 6 1 60 1x28 301 2 31 30 0 x5 2 300 1 3 1 31 j00 1 6 1 60 j arj1 21 2 1x10100 15 2 1x240101 2 0 x320011 3 j0000 1 2 最优解为 最优值为 T X0 0 2 4 0 4max z 4 0 最优解不唯一 11 用分支定界法解下列整数规划 1 且为整数 0 2126 0 5 2max 21 21 21 21 21 xx xx xx xx xxz 解 最优解 3 1 最优值 z 7 12 匈牙利解法 见课本 145 页 13 如图 是一仓库 是商店 求一条从到的