Вестник СамГУ 2014. № 10 (121). С.48-54.
УДК 519.8
Монтлевич В.М.
О СУБМОДУЛЯРНОСТИ ФУНКЦИИ ПРИБЫЛИ В ОДНОЙ ИЗ ЗАДАЧ ПЛАНИРОВАНИЯ ПЕРЕВОЗОК
Аннотация. В статье исследуется возможность применения метода последовательных расчетов для решения транспортной задачи на максимум прибыли. Особенностью этой задачи является то, что множество потребителей заранее не определено и выбирается из более широкого множества возможных потребителей по критерию максимума прибыли. Прибыль рассчитывается на основе спроса потребителей и цен, которые определяются договором между потребителем и фирмой, выполняющей перевозки. Показано, что задача сводится к максимизации функции прибыли на булевой решетке всех подмножеств множества возможных потребителей. Доказана субмодулярность функции прибыли, чем обоснована применимость метода последовательных расчетов для решения задачи.
Ключевые слова: дискретная оптимизация, частично упорядоченное множество, решетка, субмодулярность, супермодулярность, метод последовательных р;