《运筹学》复习参考资料知识点及习题
－540 －450 －720 0 0 －M －M CB XB －M －M －M －540 －720 －540 －720 －450 b 70 30 y1 3 （9） －12M y2 5 5 －10M y3 9 3 －12M y4 －1 0 y5 0 －1 y6 1 0 －M 0 1 0 －M 0 1/8 －1/24 y7 0 1 －M 0 θL 70/3 30/9=10/3 y6 y7 M M －M 1/3 －1/9 12M－540↑ 10M－450 12M－720 －M 60 10/3 15/2 5/6 0 1 0 0 1 －540 0 －1 12/5 －360 10/3 5/9 （8） 1/3 －1 0 y6 y1 －1/3 60/8=2.5 1/9 M/3－60 －M/3+60 10/3/1/3 =10 15/2/5/12 =18 5/6/5/12 =2 -300+10/3M -8M－180 －M －M/3+60 -150+10/3M 8M-540↑ M －1/8 1/24 M/3－60 y3 y1 5/12 （5/12） －572 125↑ 0 1 －450 0 1 0 1/24 －1/8 －1/24 1/8 20/3 2 －720 －135/2 475/12 －135/2 －75/2 0 1 0 －720 0 *
135/2 －475/12 135/2－M 75/2－M 1/6 1/6 1/6 －1/6 3/10 －15 15－M y3 y2 1/10 －3/10 －1/10 75 －75 15 －15 －75 75－M －5700 －180 20∴该对偶问题的最优解是y=（0，2，，0，0）T
3最优目标函数值min w =－（－5700）=5700
16 / 27
《运筹学》复习参考资料知识点及习题
五、运输规划问题：
运输规划问题的特殊解法——“表上作业法”解题步骤：
1、找出初始调运方案。即在(m×n)产销平衡表上给出m+n-1个数字格。（最小元素法） 2、（对空格）求检验数。判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。（闭回路法）
3、对方案进行改善，找出新的调运方案。（根据检验结果选择入基变量，用表上闭回路法调整——即迭代计算，得新的基本可行解）
4、重复2、3，再检验、再迭代，直到求得最优调运方案。
类型一：供求平衡的运输规划问题（又称“供需平衡”、“产销平衡”）
引例：某钢铁公司有三个铁矿和四个炼铁厂，铁矿的年产矿石量分别为100万吨、80万吨和50万吨，炼铁厂年需矿石量分别为50万吨、70万吨、80万吨和30万吨，这三个铁矿与四个炼铁厂的距离如下：
距 炼 铁 厂 B1 B2 B3 B4 铁 矿 离 A1 A2 A3 15 20 3 30 70 8 14 20 12 3 20 15 问：该公司应如何组织运输，既满足各炼铁厂需要，又使总的运输费用为最小（按吨.公里计）？
解：用“表上作业法”求解。
⑴先用最低费用法（最小元素法）求此问题的初始基础可行解：
17 / 27
《运筹学》复习参考资料知识点及习题
费 用 产 地 销 地 产量 B1 15 70 12 50 20 30 20 B2 －67 × 20 50 70 3 B3 80 44 × 33 × 80 30 20 25 B4 －65 Si 100 A1 A2 A3 销量 8 3 14 20 × 80 30 －10 50 × 30 53 × dj ∴初始方案： A1
80 20
230 230 B1
A2
B3
30 20 30
B1 B2 B3
A3
50
B2
Z=15×20+3×80+70×30+8×20+20×30+3×50=3550（吨.公里） ⑵对⑴的初始可行解进行迭代（表上闭回路法），求最优解：
18 / 27
《运筹学》复习参考资料知识点及习题
费 用 产 地 销 地 产量 B1 15 70 12 50 20 －53 20 B2 －14 × 3 B3 80 －9 × －20 × 80 30 20 25 B4 －12 Si 100 A1 A2 A3 销量 8 3 70 14 20 × 80 30 －10 50 × 30 × 50 30 20 dj 230 230 用表上闭回路法调整后，从上表可看出，所有检验数σ＜0，已得最优解。 ∴最优方案： A1
80 20
B1
A2
B3
50
B2
A3
30
B1
30
B4
20
B2
Z=15×20+3×80+8×50+20×30+12×30+3×20=1960（吨.公里）
解法分析：①如何求检验数并由此确定入基变量？有数字的空格称为“基格”、打×的空格称为“空格”，标号为偶数的顶点称为偶点、标号为奇数的顶点称为奇点，出发点算0故为偶点。找出所有空格的闭回路后计算它们的检验数?ij??c??cij奇点偶点ij，必须?ij≤0，才得到最优解。否则，应选所有?中正的最大者对应的变量xj为入基变量进行迭代（调整）。②检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇点均减去奇点中的最小运量。③重复以上两步，再检验、再调整，直到求得最优运输方案。
类型二：供求不平衡的运输规划问题
19 / 27
《运筹学》复习参考资料知识点及习题
若?si??dj，则是供大于求（供过于求）问题，可设一虚销地Bn+1，令
i?1j?1mnci,n+1=0，dn+1=?si??dj，转化为产销平衡问题。若?si??dj，则是供小
i?1j?1i?1j?1mnmn于求（供不应求）问题，可设一虚产地Am+1，令cm+1,j=0，sm+1=?dj??si，
j?1i?1nm转化为产销平衡问题。
（，2，…，m；，2，…，n） 六、工作指派问题：
工作指派问题的数学模型——假定有n项工作需要完成，恰好有n个人每人可
去完成其中一项工作，效果要好。
工作指派问题的特殊解法——“匈牙利法”（考！！）解题步骤：
1、使系数矩阵（效率矩阵）各行、各列出现零元素。
作法：①行约简—系数矩阵各行元素减去所在行的最小元素，②列约简—再从所得矩阵的各列减去所在列最小元素。
2、试求最优解。如能找出n个位于不同行不同列的零元素，令对应的xij= 1，其余xij = 0，得最优解，结束；否则下一步。
作法：由独立0元素的行（列）开始，独立0元素处画（ ）标记 ，在有（ ）的行列中划去（也可打*）其它0元素；再在剩余的0元素中重复此做法，直至不能标记（ ）为止。 3、作能覆盖所有0元素的最少数直线集合。
作法：① 对没有（ ）的行打√号；②对已打√号的行中所有0元素的所在列打√号；③再对打有√号的列中0元素的所在行打√号；④重复②、③直到得不出新的打√号的行(列)为止；⑤对没有打√号的行画一横线，对打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数。⑥未被直线覆盖的最小元素为cij,在未被直线覆盖处减去cij,在直线交叉处加上
cij。
4、重复2、3，直到求得最优解。
类型一：求极小值的匈牙利法：（重点掌握这种基本问题）
20 / 27
运筹学复习参考资料知识点及习题
