Транспортная задача и метод потенциалов

из "Экономико-математические модели и методы "

Транспортная задача является специальным типом задач линейного программирования. Экономическая постановка этой задачи следующая. Имеется т поставщиков и п потребителей некоторой продукции. Заданы тарифы (стоимость) перевозок единицы продукции от поставщиков к потребителям, известны объемы запасов у поставщиков и потребности каждого потребителя в продукции. [c.60]
Требуется составить план поставок продукции от поставщиков к потребителям так, чтобы суммарная стоимость перевозок была минимальной. [c.60]
Здесь Ху - объем, с у - тариф поставки продукции от г-го поставщика к у -му потребителю, bj - потребности потребителей в продукции, а - запасы продукции у поставщиков. [c.60]
что (4.24) является задачей линейного программирования со специальной матрицей. В задаче (4.24) имеется тп неизвестных Ху и т + п уравнений. [c.60]
Решение транспортной задачи называется оптимальным планом перевозок (поставок) продукции. [c.61]
Задача (4.24) называется сбалансированной (закрытой), если суммарный объем потребностей равен суммарному объему предложения продукции, т.е. [c.61]
Если условие (4.25) не выполняется, то задача называется открытой. Для решения открытую задачу преобразуют в закрытую. Для этого в задачу вводят либо фиктивного поставщика недостающего объема продукции (если потребности больше предложения), либо фиктивного потребителя лишней продукции (если предложение больше потребностей), тарифы которых полагаются равными нулю. [c.61]
При решении задачи используется свойство, которое состоит в том, что ранг матрицы А задачи (4.24) на единицу меньше числа уравнений г(А) = т + п — 1. С учетом этого число ненулевых переменных Ху 0 в опорном плане будет не больше (т + п- 1). [c.61]
Если число ненулевых Ху в опорном плане равно (т + п - 1), то план называется невырожденным, иначе - вырожденным. [c.61]
Для решения задачи (4.24) составляется табл. 4.4. [c.61]
В случае открытой задачи в таблицу вводят либо фиктивного поставщика, либо фиктивного потребителя, с целью получения равенства (4.25), с соответствующим объемом продукции. Поэтому будем считать, что в таблице выполняется соотношение (4.25). [c.61]
Алгоритм решения задачи (4.24) состоит из двух частей построение начального опорного плана (набора чисел Х 0), удовлетворяющих соотношениям (4.24)) и построение оптимального плана. [c.61]
При решении первой задачи осуществляют заполнение табл. 4.4, а при решении второй задачи ее преобразование по определенному алгоритму. [c.62]
Метод северо-западного угла отличается от метода минимального элемента тем, что клетки заполняют последовательно по строкам, начиная с элемента ХП. [c.62]
Для построения оптимального плана перевозок используется метод потенциалов, который является формой симплекс-алгоритма. [c.62]
Здесь могут быть два варианта. [c.62]
Вариант 1. Если опорный план вырожден, то в свободные клетки с минимальными значениями Су записывают перечеркнутые нули % (фиктивные поставки), пока не получат невырожденный план. Число 0 считается очень малой положительной величиной. [c.62]
Дальше задача решается методом потенциалов. [c.62]
Неизвестные и , v/ называются индексами (потенциалами). [c.62]

Вернуться к основной статье