Некоторые свойства многогранника. Задачи о P-медиане
Некоторые свойства многогранника. Задачи о P-медиане
Г.Г. Забудский, Институт информационных технологий и
прикладной математики СО РАН
1. Постановка
задачи и определения
Задачи
оптимального размещения объектов имеют много практических приложений.
Описываются различные постановки таких задач [1-8]. В данной статье
рассматривается известная NP-трудная задача оптимального размещения на графе -
задача о p-медиане [1,7-8]. Для ее исследования здесь применяется подход,
развиваемый в работах А.А. Колоколова и других [2,4-7,9] для анализа и решения
задач целочисленного программирования, основанный на разбиении допустимой
области соответствующей непрерывной задачи. В данной работе рассматривается L-
разбиение.
Задача
о p-медиане сводится к простейшей задаче размещения (ПЗР). Сводимость не
гарантирует сохранения некоторых свойств. Например, многогранник ПЗР -
квазицелочисленный, а многогранник задачи о p- медиане в общем случае является
только связноцелочисленным (квазицелочисленным при p = 1, n-1, где n - число
вершин графа) [1].
В
работе [2] доказано, что многогранник ПЗР имеет альтернирующую L-структуру. В
данной статье показано, что многогранник задачи о p-медиане также имеет
альтернирующую L -структуру.
Рассматривается
целочисленная модель задачи о p- медиане: