Определение транспортной модели

ТРАНСПОРТНАЯ ЗАДАЧА

Транспортные задачи представляют собой специальный класс задач линейного программирования. В этих задачах обычно описывается перемещение какого-либо товара из пунктов отправления (мест производства) в пункты назначения (склады, магазины). Основная цель состоит в определении объёма перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок. При этом должны учитываться ограничения, налагаемые на объем грузов в пункте назначения (ограничения предложения) и ограничения, учитывающие потребность в грузах в пунктах назначения (ограничения спроса). В транспортной задаче предполагается, что стоимость перевозки груза по какому-либо маршруту прямо пропорциональна объёму груза, перевозимого по этому маршруту.

Несмотря на то, что транспортная задача может быть решена как обыкновенная задача линейного программирования, её специфическая структура позволяет использовать для решения упрощённый алгоритм.

Определение транспортной модели

Графическое представление условий транспортной задачи приведено на рис. 15.1. На рисунке показано m пунктов отправления и n пунктов назначения, которые представляют собой узлы сети. Дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и пункты назначения. С каждой дугой (i, j) между пунктами i и j связывается два параметра: стоимость перевозки c_ij и объём перевозимых грузов x_ij. Объём груза в пункте i равен a_i, максимальное количество груза в пункте назначения j равно b_j. Задача состоит в определении неизвестных величин x_ij, минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям предложения (a_i) и спроса (b_j).

В рамках транспортной модели могут рассматриваться также задачи управления запасами и задачи распределения оборудования для выполнения различных работ.

Рис. 15.1. Представление транспортной задачи в виде сети.

Транспортная задача может быть представлена также и в табличном виде. При таком представлении каждая строка соответствует пункту отправления, каждый столбец – пункту назначения, число в ячейке на пересечении i -й строки и j -го столбца показывается стоимость перевозки, неизвестное значение в такой ячейке – объём перевозок. В последней ячейке каждой строки записано ограничение предложения, в последней ячейке каждого столбца - ограничение спроса.

Таблица 15.1