Транспортная задача
Имеется m-поставщиков некоторого однородного товара и n-потребителей. Известны запасы поставщиков a1,a2...a m, b,1,b2....bn-запросы потребителя. Кроме того известна стоимость перевозок от i к j. найти такой план перевозок при котором суммарная стоимость перевозок явл min.
Хij-?
F(x11,x12...xmn)=C11X12+C12X12+....+CmnXmn -->min
Если суммарные запасы поставщиков совпадают с суммарными запросами потребителя ТЗ называется закрытой, в противном случае- открытой.
Зам. Всякая закрытая ТЗ имеет оптим решение
Зам. Для решения открытой ТЗ ее предварительно преобразовывают в закрытую.
- Если сум запасы больше сум запросов вводят фиктивного потребителя(приписываем ему стоимости перевозок равные 0). Если же запасы меньше запросов вводят фиктивного поставщика с тем же условием.
В таблицу ТЗ заносятся одновременно и стоимости перевозок Cij(будем располагать их в правом верхнем углу каждой клетки),а также объемы перевозок Хij.
В отличие от предыдущих задач опорное решение ТЗ будет записываться в виде матрицы.
Х11 Х12.... Х1n
Х= X21 X22.... X 2n
Xm1 Xm2... Xmn
Для удобства в дальнейшем в ТТЗ будем проставлять только не нулевые значения перевозок Xij>0 и базисные нули. Базисным нулем будет называться значение Xij если одновременно Xij базисное и равно нулю.
Рассмотрим закрытую ТЗ
1 этап построение НОР. Основные два метода
1) метод северо западного угла
Алгоритм построение НОР методом северо западного угла
1. начинаем заполнять ТТЗ с левой верхней клетки (11). при этом берем Х11=min{a1,b1},при этом возможны два случая:
Если а1>b1, то в результате выделяется b1 единиц 1-му потребителю, его запросы исчерпываются и мы исключаем его из рассмотрения (остальные клетки первого столбца пустые) _
Соответственно у первого поставщика остается а1 =а1-b1, на след шаг переходим в клетку 12 и берем Х12=min{a1,b1}
2) если a1<b1, то первый поставщик отдает весь свой запас a1 и исключается из дальнейшего рассмотрения, а запасы потребителя уменьшаются на а1 ед. Мы переходим в клетку 21 и берем соотв X21=min{a1,d2}
Второй и последний шаг выполняется аналогично при этом:1) Заполнение ТТЗ может происходить в двух направлениях,шаг вправо и шаг вниз.2)На каждом шаге исключается из рассмотрения только один поставщик или только один потребитель.
Зам. Если на некотором шаге запасы поставщика окажутся равны запросам потребителя,то проставляем в эту клетку эти запасы- затраты, при этом на данном шаге исключаем либо поставщика либо потребителя, а оставщемуся приписывается базисный ноль, который проставляется в эту, которая является очередной в соотв с алгоритмом. Только после этого «оставшийся» исключается из рассмотрения.
метод. Метод min стоимости.
Для применения данного метода выписываем матрицу С-стоимости перевозок.
С11 С12... C1n
С= C21 C22...C2n
Cm1 Cm2..Cmn
Заполнение Ттз происходит по аналогичной схеме,но начинаем с той клетки, в кот стоимость перевозок min.
Далее исключаем или поставщика или потребителя, при этом соотв строка(столбец) вычеркивается из матрицы С.
Особенность метода min стоимости состоит в том, что клетки ТТЗ заполнены в соответствии с матрицей стоимость перевозок С. Алгоритм использование матрицы стоимости перевозок:
-на первом этапе выбираем min Сij (если их несколько берем любое). Затем присваиваем
перевозку Xij в соотв клетке ТТЗ по прежнему принципу (Xij=min). Аналогично методу серево-западного угла при этом исключ либо 1 поставщик,либо 1 потребитель и до выполнения второго шага необходимо вычеркнуть строку(столбец),соотв исключить поставщику(потребителю). Далее шаги повторяются аналогично.
Зам. При использование метода min стоимости клетки, соотв фиктивному поставщику(потребителю) заполняются в последнюю очередь
Зам. Если на очередном шаге при заполнение ТТЗ оказалось,что для клетки (i,j) ai=bj,то исключаем на данном шаге только одного поставщика(потребителя), а другому приписываем базисный ноль(0*),но соотв поставщик или потребитель на данном шаге не исключается. Исключается поставщик(потребитель) с базисным 0* в тот момент,когда в соотв с алгоритмом методом min стоимости мы попадаем в строчку(столбик),соотв данному поставщику(потребителю).
Решение, полученные методом СЗУ или min стоимости явл опорными решениями.
Док-во следует из решения ТЗ симплекс методом,при опред направленности выбора базисных переменных.
Важное свойство любого опорного решения ТЗ число базисных переменных (значит занятых клеток ТТЗ)постоянно и равно m+n-1. Док-во следует из специфического вида системы ограничений ТЗ и усл закрытости (Еаi=Ebj)
Методы проверки решения ТЗ на оптимальность, а также методы уличшения решения основаны на применение симплекс-метода.
Метод потенциалов.
1) на первом шаге каждому поставщику приписывается опред. число- потенциалы Ui,потребителю- Vj, по след правилу:
Для занятых клеток: Ui+Vj=Cij
потенциалы Ui и Vj находятся из системы m+n-1 уравнений,m+n- число неизвестных т.к неизвестных >числа ура-ний ->систама имеет бесконечно много решений, при этом чисто свободных пеерменных равно 1. Это позволяет любой из потенциалов выбрать произвольно (например U1=0), тогда остальные потенциалы находятся однозначно.
2) Для оценки оптимальности решение задаем число 
ij=Ui+Vj-Cij
Зам. Для занятых клеток ij=0, соотв можно ограничится вычислением ij только для свободных клеток.