运筹学补充

1、产销不平衡问题，最小元素法设置初始调运方案时先不管虚拟的产地或销地。

例1 运输问题供需表和运价表如表1所示，求最优调运方案。

表1

由于7+4+9=20>3+6+5=14，即各产地产量之和大于各销地销量之和，添加虚拟销地B₄，其销量为20-14=6。

表2

采用最小元素法时，先不考虑虚拟的B₄列，直接对其余（即表1）的单元格设置初始调运方案，结果如下：

表3

位势法检验及空格检验数如下表所示：

表3

一步搞定，且空格检验数均大于0，表明有唯一最优解。如果将虚拟的单元格计入在内，按照最小元素法求解，首先考虑单位运价为0的单元格A₁B₄、A₂B₄或者A₃B₄，势必大大降低求解效率。

所以，在添加虚拟产地或销地时，一定要将这些虚拟的先忽略掉，或者干脆说，将虚拟单位运价设为0，只是为了标识和求目标函数值。将其设为*、在计算最小运费时不计算也完全可以。

2、在出现退化解时，可以在同时划掉的那1行和1列中的最小单位运价单元格处添0，求解速度可能最快（凭经验，缺乏理论验证）。

例2某企业和用户签订了设备交货合同，已知该企业各季度的生产能力、每台设备的生产成本和每季度末的交货量如表所示。若生产出的设备当季度不交货，每台设备每季度需支付保管维护费0.1万元，试问在遵守合同的条件下，企业应如何安排生产计划，才能使年消耗费用最低？

该问题有如下特征：

（1）产量大于销量，需假想一交货季度；

（2）第i季度生产第j季度交货的每台设备所耗费用c_ij等于生产成本加上保管费用，当j<i时，为使x_ij等于0，取c_ij=M。

在用最小元素法给出初始调运方案时，添3à4的20时，这时会同时删除第3行和第4列。注意：要在第3行和第4列中某个单元格添0，但不是任一个，只要前面划掉的单元格均不可再添0，否则会构成闭回路。但是，添哪一个最好？3à1?  3à5?  1à4？4à4?

首先尝试在非0且最小的单位运价单元格1à4处添0，其余按照“1、”的规则进行，即不管虚拟销地5，直接在1à1处添15。

迭代结束，由于存在非基变量检验数为0，该题有无穷多最优解。

这个题太特殊了，即使把中间补的0放到3à1、3à5、4à4处均可以，因为闭回路拐角怎么转都是0。不具有普遍性，换个例子。

例3某地区有三个化肥厂和四个产粮区。单位运价、供应量、需求量如表所示。确定最小运费方案。

在最小单位运价A₃ B₃处写3，同时划掉第3行和第3列。尝试在最小单位运价A₃B₂处写0，一步就达到最优解，没有闭回路调整的迭代步。

例4有三个产地A1、A2、A3生产同一种物品，该物品有三个用户B1、B2、B3。已知这三个用户的需求量分别为10、4、6。由于销售需要和客观条件限制，A1至少要发出6个单位的产品，最多只能生产11个单位的产品；A2必须发出7个单位产品，A3至少要发出4个单位的产品。

该问题有如下特征：

当A1的产量a1取最小值6，A3的产量a3最多等于7；如果A1和A3都取最大值，此时需要增设一个假想的销地B4，需用量为25-20=5。

为考虑可能出现的各种情况，将A₁和A₃两个产地的产量都分成两部分，其中一部分是必须发出的，应运至实在的需用地，而不能运往虚销点B₄，从而将这部分产品运往虚销点B₄的单位运价取为充分大的正数M，另一部分产品可以运往虚销点，但由于这时实际上不需运输，故取相应的单位运价等于0。

如果采用“1、”的策略，先不管虚拟的销地B₄，按照最小元素法有下表的初始调运方案、位势、检验数，可见一步迭代结束。

相反，如果视虚拟销地的单元格A₁^’B₄和A₃^’B₄中的0为最小元素，采用最小元素法求解，得到结果如下：