Анализ классической и линейной транспортной задач. Определение автоматических циклов с отрицательной ценой методом потенциалов. Особенность составления первоначального плана перевозок с помощью концепции северо-западного угла и наименьшей стоимости.
Аннотация к работе
Транспортная задача (задача Монжа - Канторовича) - математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) Аі …, Ам, в которых сосредоточены запасы однородных продуктов в количестве a1, ..., am единиц.Классическая транспортная задача- задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределенном количестве) со статичными данными и линеарном подходе (это основные условия задачи).Линейные транспортные задачи составляют особый класс задач линейного программирования.Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Идея метода потенциалов для решения транспортной задачи сводится к следующему.Составление первоначального плана перевозок начнем с перевозки запасов поставщика. A1. Будем за счет его запасов максимально возможно удовлетворять заказы сначала потребителя B1, затем B2 и так далее.Рассмотрим этот метод на примере: Если , то запасы поставщика Аіисчерпаны, а потребителю Вjтребуется еще единиц груза. Далее не принимая во внимание i-ю строку, снова ищем клетку с наименьшей стоимостью перевозок и заполняем ее с учетом изменившихся потребностей.