s.t. 2x1+4x2≤160 3x1+2x2≤180
x1,x2≥0 X*= (50,15) max z=370
（2）影子： A ：7/4 B：1/2
（3）CBB-1-（-c3+11）≥0 CB=73/4=18.25 （4）b’ = (160+a,180), B-1 b =((3/8)a +15,50-a/4) ≥0 得到-40≤a ≤200 a=200 增加利润350 X1 X2 X3 X4
X2 15+(3/8)a 0 1 3/8 -1/4 X1 50- a/4 1 0 -1/4
1/2 -1/2
s -370- 7a/4 0 0 -7/4 第三章 3.1 解： 表3.1-1 B1 B2 B3 B4 量 A1 (10) A2 (16)
运输问题
（6） （7） （12） （10）
4
（5） （9） 9 （10）
5
A3 (5) （4） （10） 需要量
5 3 4 6 18
西北角法是优先从运价表的西北角的变量赋值当行或列分配完毕后再在表中余下部分的西北角赋值以此类推直到右下角素分配完毕。 表3.1-1西北角素是x11, x11=min｛a1, b1｝= min｛4, 5｝= 4将4填 在C11的左侧表示A14单位给B2。同时将第一行划去表示A1的产量全部运出得表3.1-2。在表3.1-2中西北角素是x21x21= min｛9, 5-4｝=1同时降第一列划去表示B1已满足需要得到表3.1-3。依次向右下角安排运量结果如表3.1-4所示。 表3.1-2 B1 B2 B3 B4 量 A1 4 (10) A2 (16)
（6） （7） （12）
（5） （9） 9 （10）
5 4
（10）
A3 (5) （4） （10） 需要量 表3.1-3 B1 B2 B3 B4 量 A1 4 (10) A2 1 (16)
5 3 4 6 18
（6） （7） （12） （10）
4
（5） （9） 9 （10）
5
A3 (5) （4） （10） 需要量 表3.1-4 B1 B2 B3 B4 量 A1 4 (10)
5 3 4 6 18
（6） （7） （12） 4
A2 1 (16) 3（10） 4（5） 1（9） 9
A3 (5) （4） （10） 需要量
5（10） 5
5 3 4 6 18
最小素法的思想是就近优先运送即最小运价cij对应的变量xij优先赋值xij=min｛ai, bj｝然后在剩下的运价中取最小运价对应的变量赋值并满足约束依次下去直到最后得到一个初始基本可行解。
表3.1-1中最小素是C32令x32=min｛a3, b2｝= min｛5, 3｝= 3同时将第二列划去得到表3.1-5。在表3.1-5中最小素为C23C31任意选取其一这里选C31令x31= min｛5-3, 5｝=2同时将第三行划去得表3.1-6。依次进行下去其结果见表3.1-7。 表3.1-5 B1 B2 B3 B4 量 A1 (10) A2 (16)
（6） （7） （12） （10）
4
（5） （9） 9
（10）
5
A3 (5) 3（4） 需要量 表3.1-6 B1 B2 B3 B4 量 A1 (10) A2 (16)
（10）
5 3 4 6 18
（6） （7） （12） （10）
4
（5） （9） 9
（10）
5
A3 (5) 3（4） 需要量
（10）
5 3 4 6 18
表3.1-7 B1 B2 B3 B4 量
A1 3 (10) （6） （7） 1（12） 4 A2 (16)
（10）
4（5） （10）
5（9） （10）
9 5
A3 2 (5) 3（4） 需要量
5 3 4 6 18
伏格尔法是最小素法的改进考虑到产地到销地的最小运价和此小运价之间的差额如果差额很大就选最小运价处险调运否
则会增加总运费。
在表3.1-1中求行差额和列差额。计算公式为
若同时将第三行与第一列划去最后即变量个数比小于3+4-1=6个因而应再x32x33,x34和x11,x12中任意选一个变量作为即变量运量为零这里选x11如表3.1-8所示。
求第二个基变量仍然是求差额因为第三行和第一列已满足所以只求u1,u2和v2v3v4即可结果见表3.1-9。此时有两个最大差额u2v2任选一个即可这里选v2.第二列最小运价为c12故x12=min｛4,3｝=3.同 时将第二列划去。这样依次下去其结果见表3.1-10。 表3.1-8
相关推荐：
loading