ТРАНСПОРТНАЯ ЗАДАЧА. Необходимые сведения
 Скачать 134.6 Kb.
|
Важным частным случаем задачи линейного программирования является транспортная задача. Необходимо определить план перевозок некоторого однородного груза, минимизирующий затраты на общую стоимость перевозок, из m пунктов отправления (производства) А1, А2, …Am. в n пуктов потребления В1, В2, …, Вn. Введем следующие переменные: ai – величина предложения продукта в пункте i, i = 1, …,m; bj – величина спроса на продукт в пункте j, j = 1, …,n; cij – затраты на транспортировку единицы продукта из пункта i в пункт j; xij – количество продукта, перевозимого из пункта i в пункт j. Тогда транспортную задачу можно представить в виде таблицы 1. Т а б л и ц а 2.1
В сделанных обозначениях математическую модель транспортной задачи можно записать следующим образом:  (2.1) (2.2) (2.3)Существует несколько вариантов транспортной задачи.
Общий спрос равен общему предложению:  Это равенство является необходимым и достаточным условием существования допустимого плана задачи (2.1) – (2.3).
а) Пусть существует излишек продукта, т.е.  б) Пусть существует дефицит продукта, т.е.  Такую задачу можно свести к закрытой задаче, вводя дополнительный столбец (строку), равный по величине имеющейся разности между общим спросом и общей потребностью, тарифы cijкоторого считают условно равными нулю.
Если объем перевозок между пунктами i и jзадан, то в задаче (2.1) – (2.3) вводится дополнительное ограничение xij = vij, где vij – заданный объем перевозок.
Если объем перевозок из пункта i в j пункт ограничен величиной wij, то в задаче (2.1) – (2.3) вводится дополнительное ограничение xij ≤ wij. Все приведенные выше модели описывают транспортную задачу в виде задачи линейного программирования. В этой форме она может быть решена стандартными средствами ЛП, например, с помощью симплекс-метода. Однако специфичная форма системы ограничений данной задачи (в виде уравнений-равенств) позволяет существенно упростить обычный симплекс-метод. Такой метод решения транспортной задачи (ТЗ) называют распределительным, или методом потенциалов. По аналогии с общим случаем ЗЛП, решение в нем осуществляется по трем шагам:
Методы нахождения первоначального распределения поставок Все существующие методы нахождения опорных планов отличаются только способом выбора клетки для заполнения. Само заполнение происходит одинаково независимо от используемого метода. Следует помнить, что перед нахождением опорного плана транспортная задача должна быть сбалансирована (приведена к закрытой модели).
На каждом шаге этого метода из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов. Для того чтобы заполнить клетку (i,j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке  с текущей потребностью в рассматриваемом j-м столбце  .Если существующий запас позволяет перевезти всю потребность, то
Если существующий запас не позволяет перевезти всю потребность, то
Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы. Если на некотором шаге вычеркиваются одновременно строка и столбец, то либо по строке, либо по столбцу рядом необходимо записать «0»-поставку и при дальнейших расчетах считать эту клетку условно заполненной.
На каждом шаге этого метода из всех не вычеркнутых клеток транспортной матрицы выбирается клетка с минимальной стоимостью перевозки mincij.. Заполнение выбранной клетки производится по правилам, описанным выше. Метод потенциалов решения транспортной задачи Распределение поставок называется базисным, если переменные, соответствующие заполненным клеткам, можно принять за основные (базисные) переменные. Клетки, соответствующие свободным переменным, остаются незаполненными (пустыми). Теорема: число r базисных переменных закрытой транспортной задачи равно m+n-1, где m – число поставщиков, n – число потребителей. Критерий оптимальности опорного решения ТЗ: распределение поставок оптимально тогда и только тогда, когда оценки всех свободных клеток неотрицательны. Теорема о потенциалах: Оценка свободной клетки не изменится, если к коэффициентам затрат некоторой строки (столбца) таблицы поставок прибавить некоторое число. Это число, прибавляемое к коэффициентам затрат выделенной строки (столбца), будем называть потенциалом данной строки (столбца). Следствие (правило нахождения оценок свободных клеток): к коэффициентам затрат таблицы поставок в каждой строке и столбце надо прибавить такие числа (потенциалы), чтобы коэффициенты затрат в заполненных клетках стали равными нулю. Полученные при этом коэффициенты затрат свободных клеток равны оценкам этих клеток. При переходе к следующему опорному решению, т.е. в результате ввода нового элемента в базис, нарушается общий баланс ресурсов и потребностей. Для того чтобы привести его в норму, необходимо преобразовать некоторые базисные элементы по какому-нибудь замкнутому циклу для сохранения баланса по строкам и столбцам таблицы поставок. Циклом пересчета называется такой цикл в таблице с базисным распределением поставок, при котором одна из его вершин лежит в свободной клетке, а остальные – в заполненных. Цикл пересчета называется означенным, если в его вершинах расставлены знаки «+» и «-» так, что в свободной клетке стоит знак «+», а соседние вершины имеют противоположные знаки. Объем поставки, передаваемой по циклу, определяют, как наименьшее из чисел, стоящих в вершинах цикла со знаком «-». Циклы встречаются самые разные. Например, следующих видов: Рис.2.1. Виды циклов пересчета в распределении поставок транспортной задачи |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ТРАНСПОРТНАЯ ЗАДАЧА
).
).