相同装卸工情况下装卸工问题的最优解

The Optimal Solution to the Equal Loader Problem

装卸工问题是一个新的NP困难的组合最优化问题,寻找其性能优良的近似算法是有重要的理论意义和实用价值的.相同装卸工情况下装卸工问题的系数矩阵是全么模矩阵,利用全么模矩阵的性质可以证明这种情况下的装卸工问题是多项式可解的.然而用全么模阵的性质还不能得到解的表达式.对这种情况下一辆货车的装卸工问题,用对偶单纯形法可得到最优解和最优值的解析表达式,从而可以把这个可解问题的最优值作为一般装卸工问题的近似值.这对于分析近似算法的性态是非常重要的.

The olader problem is a new strongly Np-hard combinatorial optimization problem. It is very meaningful in terms of both theory and applicatoins to find approximation algorithms with good performance measuzes. The case of the problem occuzs when the loader capabilities and operational conditions at the customer sites are all the same such that each loadle can haudle the same amount of the workload, this case of the problem is sumply called the equal loader problem which coefficient matrix is a tofally unimodular one. So, the equal loader problem is polynomially solvable according to properties of tofally unimodulal matrixes. However we still don＇t know the expression of its solution from properties of totally unimodular matrixes. We study the equal loader poblem with one truck, and get the analytic expression of its op9timum, which is the approximation solution to the general loader problems and is important for analyzing proformance measures of appromation algorithms.