6 x22 1 x23 5 x24 0 4 1 4 -1 3 5 1 0 0
x31 2 3
因为min(σ33)＝σ33=-1<0，所以初始方案并非最优方案，需进一步调整， x33为进基变量。 法二：用闭回路法求检验数 σ12=5-0+0-1=4；σ13=7-0+0-5=2；σ21=6-3+0-0=3；σ32=4-2+3-0+01=4（注：图中画出了非基变量x33的闭回路）；σ33=3-2+3-0+0-5=-1； σ34=0-2+3-0=1 因为min(σ33)＝σ33=-1<0，所以初始方案并非最优方案，需进一步调整， x33为进基变量。 第三步：求θ值，调整方案。 过程如下： 以X33作为进基变量。调整量θ＝min(10,20,20)=10，按照上图所示 进行调整，选择x14 作为出基变量。 方案调整后为方案二，如下： 用位势法可求出方案二非基变量检验数： 销地 销地一销地二销地三 销地四 Ui
x1 d-3 d+3
0 1 2 3 4 5 6 7 8 9 10 5 4 3 2 1 A
d+2 d-2 d+1 d-1 d+4 d-4 直线x2=2、x12x2=4分别交于C(k-4,2)
B D C
、D(2+k/2,k/4-1) 两点。 当x1≤k-4时，t= ad3-=a(4-x1+2x2)= a(4-k+4x2) ∴当k=9, x2=2, x1=5 时,min t1=3a; 当k-4≤x1≤2+k/2 时，t= ad3-+d4-= a(4-x1+2x2)+(2-x2)= (4-k)a+2+(4a-1)x2 ∴若a≥1/4时k=9, x2=5/4, x1=13/2时,min t2=3/4; 若0<a<1/4时k=9, x2=2, x1=5时,min t2=3a<3/4
产地 产地一 产地二 产地三 Vj x11 3 2 5 5 3 7 1 0 0 1 -1
6 x22 1 x23 5 x24 0 5 0 4 x33 3 4 2 -1 0
x31 2 3
因为所有非基变量检验数σij都大于零，所以方案二就是唯一最优方案。 第四步： 决策结论：产地一向销地一调拨物资10吨，产地二分别向销地二、销地 三调拨物资各10吨，产地二过剩生产的物资为10吨；产地三分别向销地 一、销地三调拨物资10吨、10吨。最小总运费＝ 10×3+10×1+10×5+10×2+10×3=140（百元）。 2、求下列线性规划问题的对偶问题： 解：根据原模型很容易判断x1是自由变量，而x2≥0。 方法一：按对称形式变换 （1）原模型可变换为如下模型： （2）按对称形式变换关系可写出它的对偶问题，模型如下：
Cj→ CB XB B-1b 0 x1 1 0 0 0 0 x2 0 0 0 1 P1 d10 -1 0 0 1 1 w2/4 w1- w2/4 w2/4 1 w2/4 1 1 -1 0 -1 -1 1 0 0 0 1 0 0 0 -1 0 -2 0 4 1 w2 2 0 -4 -1 P4 d1+ 0 1 0 0 0 d2P2 w1P3 d2+ d30 d3+ w2P3 d40 0 1 0 0 d4+ 0 0 -1 0 － 3 θ
需求量 20 10 20 （件） 要求：（1）请建立该问题的线性规划模型，然后再化为标准问题。 （2）用表上作业法求解：用最小元素法确定初始方案；用位势法验证 初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方 案。
解：
（1）设第i个产地（i=1,2,3）到第j个销地（j=1,2,3）的该种商品的数量 为xij吨，则可以建立以下模型： （2）因为总产量60（＝10+30+20）大于总需求量50（＝20+10+20）， 所以本问题不是标准运输问题。增加一个虚拟销地，它的单位运价c14
E D C
d-4 d+4 d-1 d+1 d-2 d+2
B
A 5 4 3 2 1 0 1 2 3 4 5 6 7 9 10 d+3 d-3
x1 x2 令t=5d3-+3d4当x1≤2时，t=5d3=5(4-x1+2x2)=5(10-2x1) ∴min t=30,此时对应 x1=2,x2=2 当2<x1≤5时，t=5d3+3d4-=5(4-x1+2x2)+ 3(2-x2)=-4+17x2 ∴min t=30,此时对应 x1=2,x2=2 当5<x1≤6时，t=3d4=3(2-x2) ∴min t=9/2,此时对 应x1=5,x2=1/2。 综上所述，满意解为 x1=5,x2=1/2。可见，交换目标等级，满意解发生了变化，由 (13/2,5/4)→(5,1/2)。 本小题也可以用单纯形法求解，学生可自行运算，这里略去。 (2)①用图解法。 令a=w1/w2, t= ad3-+d4-(a>0) 由（1）分析知道：满足目标P1、P2 x2 的区域为x1+2x2=k(6≤k≤9),它与
《管理运筹学》习题3及参考答案 1、某公司从三个产地A1，A2， A3将物品运往三个销地B1，B2，B3，产 量平衡表和单位运价表如表1所示。问如何调运，使得总运输费用最 小？ 表1 产销平衡表和单位运价表 销地Bj B1 B2 B3 产量 （件） 产地Ai A1 A2 A3 3 6 2 5 1 4 7 5 3 10 30 20
σj=cjzj θj 2 3 0 x1 x2 x5
σj=cj- 7 zj
∵所有非基变量检验数σj<0(j=3,4,6), ∴得到唯一最优解X*= (2,1,0,0,1)T,max z=7 即：A、B、C的产量调整为2吨、1吨、0吨，利润总和下降到7（千 元）。 4、（选做题）已知目标规划问题 用单纯形法求解时，得到如下最优表。分析目标函数分别变为①、②两 种情况时解的变化。可绘制图进行分析或者列单纯形表进行分析。
0 x1 13/2 P4 d + 3 1 3P3 3/4 d4- 5/4 0 x2 P1 P2 P3 P4
1/2 -1/2 -1/2 -1/2 1 -1 0 0 -1/4 1/4 1/4 -1/4 1/4 -1/4 -1/4 0
σj＝cj-zj
1
-1
（1） （2） （w1,w2为权重比例且都大于零） 解：①如图1所示：依次满足目标P1、P2和P3的区域是线段CEBD。方程： x1+2x2=6 C(0,3)、E(2,2)、B(5,1/2)、D (6,0)。
2 CB 2 3 0 XB x1 x2 x6 B-1b x1 1 2 -1 1 0 0 0 3 x2 0 1 0 0 1 x3 -1 2 -2 -3 1.5 2 1 1 1 0 0 0 1 1 0 0 1 0 2 -1 0 x4 4 -1 -2 -5 2.5 6 -3 2 -3 0 x5 0 x6
-1 0 1 0 [-1] 1 -1 1 0 0 1 0 -1 1 -1 -1 0
7/2 -1/2 -1/2 1/2 -4 -2
σj=cj- 10 0 zj
∵所有非基变量检验数σj<0(j=2,4,5), ∴得到唯一最优解X*= (2,0,1,0,0)T,max z=10 即：A、B、C的产量调整为2吨、0吨、1吨，利润总和上升到10（千 元）。 （2）x1为基变量，若所有非基变量检验数 即3/4≤c1≤3（千元/吨）时，原最优解不变。但c1由2变为4，，所以最 优产量计划要变化。在原最优表基础上继续迭代，直至求出新的最优产 量方案。计算过程如下： 4 3 1 0 0 θi CB XB B-1b x1 4 3 x1 1 x2 2 1 0 0 1 0 x2 0 1 0 x3 x4 x5
-1 4 -1 － 2 -1 [1] 2 -1 -13 1 3 0 -1 1 3 2
σj=cjzj 4 0 x1 3 x5 2
1 1 [1] 2
σj=cj- 12 0 zj
-1 -3 -12 0
∵所有非基变量检验数σj<0(j=2,3,4), ∴得到唯一最优解X*= (3,0,0,0,2)T,max z=12 即：A、B、C的产量调整为3吨、0吨、0吨，利润总和上升到12（千 元）。 （3）若（吨）时，上述最优基不变。 劳动力约束增加1个单位时总利润的增加量就是劳动力资源的影子价 格，显然总利润增加量＝-σ4=-(-5)=5（千元）。或者：∵，∴原问题 最优基不变。总利润增加量。（注：cBB-1就是最优表上松弛变量检验数 的相反数） （4）设生产产品D为x'4单位， ∴新产品D 不值得生产。 （5）新的设备台时约束条件：。代X*=(1,2,0,0,0)T入此条件，可知该条 件不成立。所以原问题最优表对应的产量最优方案需要改进。 由最优表第一行约束条件得到：； 由最优表第二行约束条件得到： 将上述两个表达式带入设备台时约束条件，并添加松弛变量x6，整理得 到：。将其添加到原问题最优表上，用对偶单纯形法继续迭代求解，求 解过程和结果如下：
＝c24＝c34，需求量为60-50=10。
（3）第一步：用最小元素法确定初始方案（方案不唯一，增补的零元素不能位
于同行或同列）。
方法二：伏格尔法（最接近最优解）
方法三：西北角法（初始解离最优解较远）
第二步：求非基变量检验数，验证初始方案（最小元素法求得的初始方 案）是否为最优方案。 法一：用位势法求检验数。 求解见下表所示： 销地 销地一销地二销地三 销地四 Ui 产地 产地一 产地二 产地三 Vj x11 3 3 4 5 2 7 x14 0 0 0 -1
(3)令，将上一步得到的模型整理为：
方法二：根据原问题和对偶问题的对应关系直接变换 （1）将原模型作如下变换： （2）根据上述问题和对偶问题的对应关系，直接写出其对偶问题， 即：（实际上和方法一得到的结果是一样的）