Условие разрешимости ТЗ. Закрытая модель ТЗ

Известно, что задача всегда имеет решение, если выполняется условие баланса

такую задачу называют закрытой, Если условие не выполняется – задача открытая. Если задача открытая. То вводится фиктивный пункт назначения или отправления, где приравниваются запасы и потребности, причем стоимость перевозок принимается за ноль.

53. построение первоначального опорного плана тз

Построение плана по правилу наименьшей стоимости заключается в следующем. Рассматриваем матрицу (таблицу) транспортных расходов, стоимостей, данную изначально в качестве условия задачи. Выбираем клетку с минимальной ценой перевозки (клетка с номером i, j) и помещаем в эту клетку наименьшее из чисел {a_i, b_j}. Затем исключаем из рассмотрения строку, соответствующую поставщику (если а_i меньшее), или столбец, соответствующий потребителю (если в_j меньшее). Исключение строки означает, что запасы i-го потребителя удовлетворены. Из оставшейся таблицы снова выбираем наименьшую стоимость, и т.д. продолжаем до тех пор, пока все запасы не исчерпаны, а потребности не удовлетворены. Проверьте, что сумма чисел в каждой строке получившейся таблицы равна а_i, а сумма чисел в каждом столбце равна в_j, что и требовалось. Число занятых клеток должно равняться m + n– 1, в противном случае, если занятых клеток меньше, чем m + n– 1, дополним таблицу необходимым количеством нулей (нулевых перевозок) и будем считать эти клетки с нулями занятыми так, чтобы общее количество занятых клеток равнялось равно m + n– 1. Нули поставим в клетки, соответствующие минимальной стоимости.

54. условия оптимальности опорного плана. Метод потенциалов.

Каждому поставщику (каждой строке) поставим в соответствие некоторое число

, называемое потенциалом поставщика, а каждому потребителю (каждому столбцу – некоторое число называемое потенциалом потребителя.

Числа и выбираем так, чтобы в любой занятой клетке выполнялось равенство

Невырожденный опорный план содержит m+n-1 заполненную клетку, поэтому для него можно составить систему m+n-1 независимых уравнений с m+n неизвестными. Уравнений на одно меньше, чем неизвестных, поэтому одному из неизвестных нужно придать произвольное значение, тогда m+n-1 неизвестных потенциалов определяются одназначно.

Далее для каждой свободной клетки вычислим «косвенные » тарифы и сравним их со стоимостью . Если для всех свободных клеток то план оптимальный. Если хотя бы для одной клетки не выполняется, то план неоптимален и следует переходить к новому базисному плану

55. Циклы в транспортной задаче. Построение нового опорного плана.

Циклом будем называть набор клеток матрицы перевозок, в котором две и ровно две соседние клетки расположены в одной строке или в одном столбце, и первая и последняя клетки набора лежат тоже в одной строке или столбце.
Графически нетрудно представить цикл в виде ломаной, каждое звено которой лежит в строке или в столбце, причем в каждой строке или столбце не более чем по одному звену.
Примеры:

С понятием цикла связаны важные свойства планов:

1. допустимый план является опорным, когда из занятых этим планом клеток нельзя образовать ни одного цикла;

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

Улучшение плана производится по следующей схеме. Клетки для которых называют перспективными, среди них выберем клетку с наименьшей оценкой, если таких клетокнесколько, то среди них выберем любую. Для выбранной перспективной клетки строим цикл, у которого одна из вершин находится в перспективной клетке, а остальные – в загруженных. Для каждой свободной клетки такой цикл существует, и он единственный. По этому циклу будем перераспределять груз. Перспективной клетке припишем знак +, а остальным вершинам из заполненных клеток поочередно – и +. В клетках, с вершинами со знаком – находим наименьший груз и перемещаем его по клеткам цикла, те прибавляем к поставкам в клетках со знаком + (включая перспективную) и вычитаем в клетках со знаком -.