Построение начального опорного решения ТЗ методом двойного предпочтения.

1. Приведём задачу к закрытому виду. В каждой строке транспортной таблицы находим клетку с наименьшим тарифом и отмечаем ее *.

2. В каждом столбце находим клетку с наименьшим тарифом и отмечаем *.

3. В итоге в таблице найдутся клетки отмеченные **. Заполнение начинаем именно в такие клетки.

4. Занесём в эту клетку максимально возможный груз, который можно направить от 1-го поставщика 1-му потребителю. X=min{a1, b1}

5. Определяем остатки запасов и заявок. Вычёркиваем из рассмотрения поставщика или потребителя с нулевыми остатками.

ЗАМЕЧАНИЕ. На каждом шаге алгоритма вычёркивать можно только одного участника. Одновременно строку и столбец вычёркивать нельзя. На свой выбор вычёркиваем. Если вычеркнут поставщик, то у потребителя ставиться ставим базисный ноль. Он участвует в дальнейшем рассмотрении груза.

6. Среди оставшихся не вычеркнутых клеток вновь находим клетку с **. И снова распределяем груз, но уже туда. Если клетки помеченные ** закончились, приступаем к заполнению клеток помеченных *. В последнюю очередь заполняем непомеченные клетки. Алгоритм повторяем до тех пор пока весь груз не распределим и свободных клеток не останется.

ЗАМЕЧАНИЕ. Фиктивные поставщики и потребители с тарифами=0 рассматриваются в последнюю очередь. Их отмечать * не нужно.

7. Выписываем матрицу начального решения Х1 и находим значение целевой функции.

36. Построение начального опорного решения ТЗ методом Фогеля.

1. К исходной транспортной таблице добавляем строку и столбец (I), в который заносят разности м/ду наименьшими тарифами строки и столбца соответственно.

2. Среди полученных разностей находим наибольшую.

3. В строке или столбце с наиб разностью находим наим тариф и осуществляем заполнение этой клетки.

4. Занесём в эту клетку максимально возможный груз, который можно направить от 1-го поставщика 1-му потребителю. X=min{a1, b1}

5. Определяем остатки запасов и заявок. Вычёркиваем из рассмотрения поставщика или потребителя с нулевыми остатками.

ЗАМЕЧАНИЕ. На каждом шаге алгоритма вычёркивать можно только одного участника. Одновременно строку и столбец вычёркивать нельзя. На свой выбор вычёркиваем. Если вычеркнут поставщик, то у потребителя ставиться ставим базисный ноль. Он участвует в дальнейшем рассмотрении груза.

6. Вводим еще дополнительную строку или столбец (II) и вновь находим разности м/ду наименьшими тарифами не вычеркнутых клеток по столбцу или строке.

7. Алгоритм повторяем до тех пор пока весь груз не распределим и свободных клеток не останется.

ЗАМЕЧАНИЕ. Фиктивные поставщики и потребители с тарифами=0 рассматриваются в последнюю очередь.

8. Выписываем матрицу начального решения Х1 и находим значение целевой функции.

37. Метод потенциалов ТЗ. Проверка плана на вырожденность. Проверка решения транспортной задачи на оптимальность.

Проверка плана на вырожденность

После того как установлено начальное опорное решение его необходимо проверить на оптимальность и вырожденность.

Вырожденый план ТЗ – если число заполненных клеток не совпадает с числом m+n-1 где m – число поставщиков n – число потребителей. В этом случае число переменных системы окажется > числа уравнений, а значит система будет иметь бесконечное множество решений. Чтобы не допустить этого нужно любой вырожденный план привести к не вырожденному виду.

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

ПРЕДПОЧТЕНИЕ для заполнения отдают тем клеткам у которых наименьшие тарифы, но при этом эти клетки не должны образовывать цикл с уже заполненными.

Проверка решения транспортной задачи на оптимальность.

Введём потенциалы поставщиков и потребителей. A1, A2, A3…Am – потенциалы поставщиков. А1, А2, А3,…Аn – потенциалы потребителей. Для нахождения потенциалов составим систему уравнений. Ai+Bj=Cij.

ЗАМЕЧАНИЕ. Данные уравнения составляются только для заполненных клеток.

Заполненных клеток m+n-1 a общее число потенциалов m+n. Значит система будет иметь бесконечное множество решений, а для того чтобы было единственное решение один из потенциалов приравнивают к нулю A1=0. Получаем систему m+n уравнений с m+n неизвестных. Решив систему и найдя потенциалы занесём их на соответствующие места транспортной таблицы. Подписываем в той же клетке где и название столбцов и строк. По найденным потенциалам определяем оценки свободных клеток Дельта(ij)=альфа(i)+бета(j)-Cij. Где Дельта(ij) – оценки свободных клеток, Альфа(i) – потенциал поставщиков, Бета(j) –потенциал потребителей, Cij – тарифы.

Критерий оптимальности. План транспортной задачи для целевой функции F(x)àmin считается оптимальным если все оценки свободных клеток не положительны, если есть хоть одна положительная оценка план считается не оптимальным.