RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Правила для авторов
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 2019, том 12, выпуск 1, страницы 150–155 (Mi vyuru480)  

Краткие сообщения

On the existence of an integer solution of the relaxed Weber problem for a tree network

[О существовании целочисленного решения релаксированной задачи Вебера для древовидной сети]

A. V. Panyukov

South Ural State University, Chelyabinsk, Russian Federation

Аннотация: Рассмотрена задача нахождения оптимального размещения вершин древовидной сети в монтажном пространстве, представляющем конечное множество. Критерием оптимальности является минимизация общей стоимости размещения в точках пространства и стоимости коммуникаций. Допускается размещение разных вершин дерева в одной точке монтажного пространства. Рассматриваемая проблема известна как задача Вебера для древовидной сети. В данной работе дано представление задачи Вебера как задачи о линейном программировании. Доказано, что множество оптимальных решений соответствующей релаксированной задачи Вебера для древовидной сети содержит целочисленное решение. Этот факт позволяет доказать существование седловой точки при доказательстве эффективности алгоритмов декомпозиции для задач, отличающихся от задачи Вебера наличием дополнительных ограничений.

Ключевые слова: задача размещения, линейное программирование, двойственность, релаксация, целочисленное решение, полиномиальный алгоритм, задача Вебера.

DOI: https://doi.org/10.14529/mmp190114

Полный текст: PDF файл (154 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.688
MSC: 68Q25, 90C27, 49M20
Поступила в редакцию: 03.08.2018
Язык публикации: английский

Образец цитирования: A. V. Panyukov, “On the existence of an integer solution of the relaxed Weber problem for a tree network”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 12:1 (2019), 150–155

Цитирование в формате AMSBIB
\RBibitem{Pan19}
\by A.~V.~Panyukov
\paper On the existence of an integer solution of the relaxed Weber problem for a tree network
\jour Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование
\yr 2019
\vol 12
\issue 1
\pages 150--155
\mathnet{http://mi.mathnet.ru/vyuru480}
\crossref{https://doi.org/10.14529/mmp190114}
\zmath{https://zbmath.org/?q=an:07064094}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000459600200014}
\elib{https://elibrary.ru/item.asp?id=37092215}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85064525887}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vyuru480
  • http://mi.mathnet.ru/rus/vyuru/v12/i1/p150

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:73
    Полный текст:15
    Литература:10
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020