Транспортные задачи на перестановках: свойства оценок в методе ветвей и границ

Розглянуто комбінаторну транспортну задачу, в якій, на відміну від класичної, перевезення є переставленням заданого вектора можливих обсягів перевезень. Показано, яка функція може виступати в якості оцінки допустимої підмножини при розв’язуванні цієї задачі методом гілок та меж. У запропонованій оці...

Full description

Saved in:
Bibliographic Details
Published in:Кибернетика и системный анализ
Date:2010
Main Authors: Емец, О.А., Парфёнова, Т.А.
Format: Article
Language:Russian
Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2010
Subjects:
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/45651
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Транспортные задачи на перестановках: свойства оценок в методе ветвей и границ / О.А. Емец, Т.А. Парфёнова // Кибернетика и системный анализ. — 2010. — № 6. — С. 106–112. — Бібліогр.: 17 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
Description
Summary:Розглянуто комбінаторну транспортну задачу, в якій, на відміну від класичної, перевезення є переставленням заданого вектора можливих обсягів перевезень. Показано, яка функція може виступати в якості оцінки допустимої підмножини при розв’язуванні цієї задачі методом гілок та меж. У запропонованій оцінці виявлено властивість, що дозволяє підвищити ефективність методу гілок та меж. A combinatorial transportation problem is examined. In contrast to the classical problem, transportations are permutations of the given vector of possible volumes of transportation. A function is shown to be an estimate of the feasible subset in solving this problem by the branch and bound method. The property of the proposed estimate is revealed, which increases the efficiency of the branch and bound algorithm.
ISSN:0023-1274