运筹学教程课程(编辑修改稿)

运筹学教程课程(编辑修改稿)内容摘要：

, w6） =（ 1, 5, 7, 0, 0, 0） max y=35 初始解原始、对偶都不可行的问题 0xxx2xx2x5xx3x2x2x2x3zm i n3213213213213210xxxxxx2xxx2x5xxx3x2x2x2x3zm i n6543216321532143213210xxxxxx2xxx2x25xxx3x2x2x2x3zm i n654321632153214321321z x1x2x3x4x5x6RH Sz 1 3 2 2 0 0 0 0x40 1 1 1 1 0 0 4x50 2 3 1 0 1 0 5x60 2 2 1 0 0 1 2解法 1：先解决原始可行性 z x1x2x3x4x5x6RH Sz 1 7 0 0 0 2 4 18x40 1 0 0 1 1 2 5x20 0 1 0 0 1 1 7x30 2 0 1 0 2 3 16z x1x2x3x4x5x6R HSz 1 7 2 0 0 0 2 4x40 1 1 0 1 0 1 2x50 0 1 0 0 1 7x30 2 2 1 0 1 2z x1x2x3x4x5x6R HSz 1 0 0 0 7 5 1 0 17x10 1 0 0 1 1 2 5x20 0 1 0 0 1 1 7x30 0 0 1 2 0 1 6在得到原始可行解时同时得到对偶可行解，已获得最优解： （ x1, x2, x3, x4, x5, x6） =（ 5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （ w1, w2, w3, w4, w5, w6） =（ 7, 5, 10, 0, 0, 0） max y=17 z x1x2x3x4x5x6RHSz 1 3 2 2 0 0 0 0x40 1 1 1 1 0 0 4x50 2 3 1 0 1 0 5x60 2 2 1 0 0 1 2z x1x2x3x4x5x6R H Sz 1 5 0 0 2 0 0 8x30 1 1 1 1 0 0 4x50 1 2 0 1 1 0 9x60 1 1 0 1 0 1 2解法 2：先解决对偶可行性 已得到对偶可行解，再用对偶单纯形法求解 z x1x2x3x4x5x6RHSz 1 0 0 0 7 5 10 17x30 0 0 1 2 0 1 6x20 0 1 0 0 1 1 7x10 1 0 0 1 1 2 5z x1x2x3x4x5x6R H Sz 1 5 0 0 2 0 0 8x30 1/2 0 1 3/2 1/2 0 17/ 2x20 1/2 1 0 1/2 1/2 0 9/2x60 1/2 0 0 1/2 1/2 1 5/2得到原始可行解，已获得最优解： （ x1, x2, x3, x4, x5, x6） =（ 5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （ w1, w2, w3, w4, w5, w6） =（ 7, 5, 10, 0, 0, 0） max y=17 五、对偶的经济解释 原始问题是利润最大化的生产计划问题 0xxxxxxbxxaxaxabxxaxaxaxcxcxczm a xmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111222211单位产品的利润（ 元 /件） 产品产量（件） 总利润（元） 资源限量（吨） 单位产品消耗的资源（吨 /件） 剩余的资源（ 吨） 消耗的资源（吨） 对偶问题 0cwwawawacwwawawawbwbwbym i nnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211资源限量（吨） 资源价格（元 /吨） 总利润（元） 对偶问题是资源定价问题，对偶问题的最优解 w w ...、wm称为 m种资源的 影子价格（ Shadow Price） 原始和对偶问题都取得最优解时， 最大利润 max z=min y 资源影子价格的性质 ■ 影子价格越大，说明这种资源越是相对紧缺 ■ 影子价格越小，说明这种资源相对不紧缺 ■ 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于 0 种资源的边际利润第种资源的增量第最大利润的增量 iibzwiooi mmii2211 wbwbwbwbyz  mmiii2211 wbw)bb(wbwbzz  ii wbz w1 w2 wm 产品的机会成本 机会成本 表示减少一件产品所节省的资源可以增加的利润 mmjiij2j21j1 wawawawa  增加单位资源可以增加的利润 减少一件产品可以节省的资源 0xxxxbxaxaxaxabxaxaxaxabxaxaxaxas .t .xcxcxcxczm axnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211机会成本 利润 差额成本 0cwwawawacwwawawawbwbwbym i nnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211产品的差额成本（ Reduced Cost） 差额成本 =机会成本 利润 jjTjmjmj22j11jm caWc)awawaw(w  互补松弛关系的经济解释 0x0w0w0x0wx0w0x0x0w0xwjjmjmjjmjiininiini在利润最大化的生产计划中 （ 1）边际利润大于 0的资源没有剩余 （ 2）有剩余的资源边际利润等于 0 （ 3）安排生产的产品机会成本等于利润 （ 4）机会成本大于利润的产品不安排生产 第四章 运输问题 运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 西北角法、最小元素法 非基变量的检验数 闭回路法、对偶变量法 确定进基变量，调整运量，确定离基 变量 2 3 2 1 3 4 1 运输问题网络图 s2=27 s3=19 d1=22 d2=13 d3=12 d4=13 s1=14 供应量 供应地 运价 需求量 需求地 6 7 5 3 8 4 2 7 5 9 10 6 运输问题线性规划模型 0xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs .t .x6x10x9x5x7x2x4x8x3x5x7x6zm i n343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211供应地约束 需求地约束 运输问题的表格表示 1 2 3 46 7 5 31x11x12x13x14148 4 2 72x21x22x23x24275 9 10 63x31x32x33x341922 13 12 13初始基础可行解 — 西北角法 1 2 3 4 6 7 5 3 1 14 8 4 2 7 2 27 5 9 10 6 3 19 22 13 12 13 8 13 13 14 6 6 1 2 3 46 7 5 31 148 4 2 721227 155 9 10 63 1922 13 12 130初始基础可行解 — 最小元素法（ 1） 最小元素法（ 2） 1 2 3 46 7 5 311314 18 4 2 721227 155 9 10 63 1922 13 12 130 0最小元素法（ 3） 1 2 3 46 7 5 311314 18 4 2 7213 1227 25 9 10 63 1922 13 12 130 0 0最小元素法（ 4） 1 2 3 46 7 5 311314 18 4 2 7213 1227 25 9 10 631919 022 13 12 133 0 0 0最小元素法（ 5） 1 2 3 46 7 5 311 1314 08 4 2 7213 1227 25 9 10 631919 022 13 12 132 0 0 0最小元素法（ 6） 1 2 3 46 7 5 311 1314 08 4 2 722 13 1227 05 9 10 631919 022 13 12 130 0 0 01 2 3 46 7 5 3114148 4 2 728 13 6275 9 10 636131922 13 12 135 非基变量 xij的检验数 zijcij— 闭回路法 (1) z12c12=(c11c21+c22)c12=68+47=5 1 2 3 46 7 5 3114148 4 2 728 13 6275 9 10 636131922 13 12 135 闭回路法 (2) z13c13=(c11c21+c23)c13=68+25=5 5 1 2 3 46 7 5 3114148 4 2 728 13 6275 9 10 636131922 13 12 135 闭回路法 (3) z14c14=(c11c21+ c21 c23 + c33 c14)c13=(68+210+6)3=7 7 5 1 2 3 46 7 5 3114148 4 2 728 13 6275 9 10 636131922 13 12 135 闭回路法 (4) z24c24=(c23c33+ c34)c24=(210+6)7=9 9 5 7 1 2 3 46 7 5 3114148 4 2 728 13 6275 9 10 636131922 13 12 135 闭回路法 (5) z31。