Выпуклые матрицы и многомерная задача о ранце общей лестничной структуры

Выпуклые матрицы и многомерная задача о ранце общей лестничной структуры

ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2016. № 6

problems. For multidimensional knapsack problems with

convex constraint matrices of the generalized ladder structure

we proposed the decomposition solution method, which

makes it possible to significantly increase the solved problems

dimension. Decomposition is exposed on the constraints and

the objective function. In the general case, the iteration loop

consists of solving various knapsack problems with two con-

straints with at least one common variable. After solving the

knapsack problem with two constraints, it is equivalently

replaced by a combination of the two knapsack problems with

one constraint each. It is done by modifying the coefficients

of the objective function for the common variables. The

method has an additional advantage — it does not accumu-

late computation errors, since in each cycle the objective

function coefficients restore their values. Numerical example

is given to illustrate the proposed method

REFERENCES

[1] Taha Hamdy A. Operations research: An Introduction. Prentice Hall, Inc., 1997.

[2] Kagirov R.R. Multiple Knapsack problem: new solving methods.

Vestnik SibGAU

[Vestnik

of the Reshetnev Siberian State Aerospace University], 2007, iss. 3, pp. 16–20 (in Russ.).

[3] Fedorin A.N. Mnogokriterial'nye zadachi rantsevogo tipa: razrabotka i sravnitel'nyy analiz

algoritmov. Avtoreferat diss. kand. tekh. nauk [Multicriteria problems of knapsack type:

Development and comparative analysis of algorithms. Cand. tech. sci. diss. abstr.]. Nizhniy

Novgorod, 2010.

[4] Dumbadze L.G. Razrabotka metodov i algoritmov v zadachakh optimal'nogo ispol'zova-

niya i razvitiya setey. Avtoreferat diss. kand. fiz.-mat. nauk [Development of methods and al-

gorithms in the problems of network optimal use and development. Cand. phys.-math. sci.

diss. abstr.]. Moscow, 2007.

[5] Batishchev D.I., Kogan D.I., Leykin M.V. Decisions synthesis algorithms for multicriteria

many-dimensional Knapsack problem.

Informatsionnye tekhnologii

[Information Techno-

logies], 2004, no. 1.

[6] Mamedov

K.Sh.

, Mamedov N.N. Algorithms for constructing multidimensional Knapsack

problem guaranteed solutions and guaranteed approximate solution.

Problemy upravleniya i

informatiki

[Journal of Automation and Information Sciences], 2014, no. 5, pp. 30–37

(in Russ.).

[7] Korbut A.A., Sigal

I.Kh.

Exact and greedy solutions of the Knapsack problem: The ratio of

values of objective functions.

Journal of Computer and Systems Sciences International

, 2010,

vol. 49, no. 5, pp. 757–764. DOI: 10.1134/S1064230710050102

[8] Galim'yanova N.N., Korbut A.A., Sigal

I.Kh

. Ratios of optimal values of objective functions

of the Knapsack problem and its linear relaxation.

Journal of Computer and Systems Sciences

International

, 2009, vol. 48, no. 6, pp. 906–913. DOI: 10.1134/S1064230709060070

[9] Dyubin G.N., Korbut A.A. Average behavior of greedy algorithms for the minimization

Knapsack problem: General coefficient distributions.

Comput. Math. and Math. Phys.

, 2008,

vol. 48, no. 9, pp. 1521–1535. DOI: 10.1134/S0965542508090042