极小运输问题的最大-最小和式外文翻译资料

英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

极小运输问题的最大-最小和式

Sonia Puri* · M. C. Puri

施普林格科学商业媒体股份有限公司，2006

摘要 本文研究了一种将最大-最小和式最小化的非凸优化问题。基于最大限度地求解(g 1)(lt; p)成本最小化的m个产地和n个销地的运输问题，提出了一种将凹目标函数最小化的多项式时间算法。p是阶矩阵中成对的排序递减的不同项的个数，是该最大凹函数的极小值。在有限次数的迭代中得到一个精确的全局最小值。文中还给出了该算法的数值说明和计算经验。

关键词：非凸规划、组合优化、瓶颈运输问题、全局优化

成本最小化的运输问题(CMTP)是线性规划的一个非常有用的应用，它已经找到了很多实际的应用，有大量的关于CMTP问题的文献可供参考。Tardos(1986)表明，CMTP问题在强多项式时间内是可解的，在强多项式时间内的可解性意味着存在一种算法，该算法以m和n的多项式函数为界，解决了多个步骤中的问题，产地和销地的数量和这个多项式不依赖于其他输入数据的大小。根据Orlin(1988)的观点，CMTP问题的最佳多项式运行时间是O（ logmn ( mn logmn)）。在强多项式时间内，其特殊情况为CMTP的最小成本流问题也是可解的(Hoang，1999)。类似于成本最小化运输问题，瓶颈运输问题

我们感谢加拿大新布伦斯威克-弗雷德里顿大学的教授。针对本文所讨论的问题类型。我们也感谢Ankit Khandelwal先生、Neha女士、Gupta女士和Anuradha Beniwal女士，他们对于我们实现这个算法给予了极大地帮助。

Sonia Puri ()· M. C. Puri

印度理工学院，新德里，新德里-110016，印度

电子邮件: sonia@iiml.ac.in

电子邮件: mc puri@yahoo.com

lowast;目前地址: Indian Institute of Management, Prabandh Nagar, Off Sitapur Road,

Lucknow-226013, India.

(BTP)也有许多有用的应用。在BTP中，从产地到销地的同质产品的运输是同时进行的，其主要目的是在尽可能短的时间内为销地提供所需数量的产品。许多作者已经解决了这些问题，并提出了许多解决方案(Ahuja et al .,1994;Burkand Rendl,1991)。BTP协议将整个运输时间的最小化处理在运输的多项式中：

S =

式中，(gt; 0)是产地i的产量，(gt; 0)是销地需求的数量，它们在jJ的要求是相同的;是从产地i到销地j的数量，产地i和销地j取自集合m。整体装运时间XS被定义为一个如下的可行的解决方案：

T (X)= ()

式中，是从产地i到销地j的运输时间

, 如果

0 , 否则。
显然，是凹函数并且已知T(X)也是凹函数(邦萨尔和普里,1980)。因此，BTP涉及到将凹函数最小化到一个运输多项式上，它属于凹最小化问题的一类(CMP)。由于目标函数的凹性，寻找一个最优解时只局限于一个基可行解。如果，p是两两不相同的条目在mn的时间矩阵递减排序且分别取自于递增排序的集合,,然后最小化运输成本的问题的最优基本可行解(OBFS)将提供一个关于BTP的最优可行解(OFS):

式中，, k = 1,2，hellip;,pminus;1.对于权重的数值说明其中一个可以参考Mazzola和Neebe(1993)以及Sherali(1982)。作为BTP的OFS是通过解决这个关联的CMTP获得的，它遵循的BTP也是多项式可以解决的。

另一类属于凹形最小化问题的运输问题是生产运输问题(PTP)，它涉及到一个具有固定生产成本的任意固定数量的工厂 (Hoang et al., 1996; Kuno and Utsunomiya, 2000)。Tardos(1986)的工作表明，运输多项式是一种特殊的组合结构，大大降低了复杂度，这是由于存在一个PTP的特殊情况下的强多项式时间算法的事实。

目的和简述
Mathur和Puri(1994)也研究了CMP的特殊情况。Locatelli和Thoai(2001)也讨论了CMP的高效算法。对于凹极小化问题，本文提出了在运输多项式上将两个凹函数的和最小化的方法。假设在产地和销地的delta;( ge;m n minus; 2)个链接(称为优先链接)上涂白颜色,其余的mnminus;delta;个涂上灰色(称为非优先连接)，所以当从产地到销地的发货首先是通过阶段一的白色完成的，然后再完成阶段二的灰色链接，两个阶段的时间总和是最小的。假设运输是同时进行的，每个阶段都是正的且有限的数量，那么只要有个互不相同且详尽的颜色就可以完成了。在这两个阶段中，装运时间总和所需要的颜色是最少的。如果这两个阶段的总出货量是，那么这一阶段的运输问题的解决方法是

然后是上述问题的数学模型

其中，W为白色链接的集合，G为灰色链路和S(X)的解空间，对应于一个可行解X的阶段二的运输问题。(X)由以下式子给出：

假设= {}是以下运输问题的OFS：

式中，S是前面所说的标准的运输问题的多项式。

设为T且设为t，然后让,且.

显然，.

把中的所有链接都涂成白色，而中的链接涂成灰色的。其他链接中没有分配(非基本)。从这些颜色中，我们可以看到颜色||创建一组delta;个白色的链接并且剩下的链接涂上灰色。是一种解决方案，即在阶段一的白色链接上的装运时间是T，在阶段二的灰色链接上对应的装运时间是t。上面提到的运输问题，涂色是按照这个规则进行的。在这两个阶段中，将会产生最少的装船次数。因此,OFS在上述运输问题中，修正了最优染色方案。这是研究运输问题(MP)的一个实际应用。

显然，问题(MP)涉及到最小化两个凹函数的和，运输问题多项式的第一个是max函数:且另外一个是min函数:max函数用T(X)来定义S，它是一个凹函数(邦萨尔和普里,1980)。最小值函数 用t(X)来定义S，它是凹函数的最小值也是凹函数(Mangasarian，1969)。因此，(MP)是一种属于CMP类的极小运输问题的最大-最小和式。作为一个凹的最小化问题，它的全局最小值发生在一个极端的点S，因此，解集必须被限制到它的顶点集合。为了开发一种计算效率高的算法，问题(MP)与BTP标准有关，它们可以很容易和有效地解决随后的CMTP这类问题。首先, 最小凹函数t(·)的最小值对应于最大凹函数T(·)的最小值，
得到了最大和最小凹函数之和的上界。随后，通过求解来生成数对(T(·)、t(·))，这些数对(T(·)、t(·))是通过求解适当的CMTP来产生的，使得T(·)的当前值大于当前值t(·)且小于在前一对中的T(·)和t(·)的对应值。极小运输问题的最大-最小和式的最优解是这两个值之和中的最小的一个。在大多数情况下，比如(g 1)(lt; p)时，要解决CMTP的问题，建议的解决方案的策略包括强多项式时间算法,p是阶矩阵中成对的不同项的个数。

论文的组织如下：理论发展在第一节中提出，在此基础上在第二节提出了一种强多项式时间算法。第3节和结束语中包含了一个数值说明，第4节给出了计算经验。

1、理论的发展

如前所述，极小运输问题的最大-最小和式(MP)是:

式子中，S是标准的运输多项式。正如所讨论的(T(·) t(·))是一个凹函数，将标准的瓶颈运输问题与(MP)联系在一起是：

而 ，其中p是阶矩阵中成对的不同项的个数。

定理1.1.让为最大凹函数T(·)的值,得到一个最优的基本可行解(OBFS)的瓶颈运输问题(BP)，并且让为最小凹函数t(·)的对应值。假设是成本最小化运输问题的最优基本可行解(用表示)

式中，

如果

如果

如果 .

M是一个很大的正数且

如果且,那么是最小凹函数t(·)的最小值对应于最大凹函数T(·)的值，最大凹函数T(·)中的.

证明: 由于(BP)问题中的OFS是的一个可行解，其目标函数为负值，由此可见目标函数 .通过假设且，它满足 ,且

假设不是与最小凹函数t(·)的最小值对应的最大凹函数T(·)的最大值。因此，必须存在一个可行的解决方案，例如 ,的有限负值Z且 ,.

这与是成本最小化运输问题的OBFS相矛盾。因此,OBFS 提供了最小凹函数t(·)的最小值，对应于最大凹函数T(·)的值.

备注1.1. 作为(BP)的OBFS产生最大凹函数T(·)的值，因此，是T(·)的最小值。所以，对应于T(·)的最小值为。因此，(MP)中涉及的最大和最小凹函数之和的上界是。
下一个定理适用于成对数的生成,的最大和最小的值分别在凹函数是一个正整数且 在每一对中，最小凹函数t(·)的最小值对应于最大凹函数T(·)的值.

定理1.2. 是最小凹函数t(·)的最小值，对应于最大凹函数T(·)的值.是一个OBFS的成本最小化运输问题

式中，

如果且，那么是最小凹函数t(·)对应的最大凹函数T(·)的最小值，其中是大于正整数的正整数且

.

证明:由于存在满足且,它如下所示，这个X是一个问题的可行解产生负值的目标函数，因此.当且时，我们可以得出。这意味着 ，因为最小凹函数t(·)的最小值对应于最大凹函数T(·)的值为当，且是一个大于的正整数。因此，是最大凹函数在的值。假设并不是最小凹函数t(·)的最小值对应于最大凹函数T(·)的值因此,存在一个可行解，例如 ,在中最小凹函数t(·)的值是且是大于的正整数。这表明

这与是一个OBFS的事实相矛盾。因此，是与值对应的最小凹函数t(·)的最小值.

备注1.2. 当且时,是成本最小化运输问题的一个OBFS,很明显,是最大凹函数T(·)的最小值对应的最小凹函数t(·)的值.

备注1.3. 如果,那么显然,这意味着如果最小凹函数t(·)的最小值不低于,那么下一个更大的最大凹函数T(·)的值应该被检查。下一个定理描述了问题的全局最小化(MP)。

定理1.3. 极小运输问题的最大-最小和式的全局最小值为,或;且是最小凹函数t(·)的最小值，它对应于最大凹函数T(·)的值，由成本最小化的运输问题的OBFS产生。

证明: 假设. 又由于正整数大于正整数.假设存在一个使得,最大凹函数T(·)的最小值是,.假设。

考虑到成本最小化运输问题，它的OBFS的值为最大值凹函数T(·)的最大值和相应的最小的凹函数t(·)的最小值.通过假设因此,.这表明因为.假设,式中是一个比大的正整数.

这与是一个OBFS的事实相矛盾.

因此,.也就是说,.
因此, 在S中没有其他的解可以产生T(·) t(·)的值比更小，因此，(MP)问题的全局最小值是，是成本最小化运输问题的一个OBFS。

2.算法
步骤0 将集合放入集合,且.

步骤1.解决标准的瓶颈运输问题(BP)来寻找. 通过求最小值，最小凹函数t(·)对应的最大凹函数T(·)的值来求解最小化运输问题. 因此得到的T(·) t(·)的值的上限为
如果或,转到第5步。否则转到步骤2。

步骤2 解决成本最小化运输问题来寻找其OBFS。
如果且,那么把作为最小凹函数t(·)的最小值对应于最大凹函数T(·)的最大值记录下来。

如果或,那么就到第5步,否则转到第4步。
如果且,那么就转到第3步。

步骤3 在成本最小化运输问题中用取代(参考文献3)。也就是说,重新定义的问题为

.

如果在这个重新定义的问题的一个OBFS上的最小凹函数t(·)的值仍然是,重复这个步骤，将替换为在问题中。如果t(·)的值仍然是, 继续将替换为. 假设alpha;重复执行此步骤,最后产生的成本最小化运输问题重新定义的收益率为最小的凹函数t(·)的值.然后,记录数对.

如果或,转到步骤5。否则转到第4步。

步骤4. 转到第2步，以获得更高的k值。

步骤5. 终止。(T(·) t(·))的最优值是式中或.

备注2.1. 如果,然后成本最小化交通问题不需要被解决。
备注2.2. 权重的各种成本最小化运输问题可以参考早期文献 (M

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[23545]，资料为PDF文档或Word文档，PDF文档可免费转换为Word