5. Занятые и свободные клетки.

Клетки таблицы транспортной задачи, в которых находится отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные – незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку , т.е. стоящая в i-й строке и j-м столбце, имеет номер (i,j). Каждой клетке с номером (i,j) соответствует переменная, которой соответствует вектор-условие.

6. Вырожденные и невырожденные планы.

В общем случае опорный план транспортной задачи состоит из m+ n−1 занятой клетки (по числу базисных переменных). Такой план называется невырожденным. Нередко при решении транспортной задачи возникает вырожденный план с меньшим числом занятых клеток (когда какие-то из базисных переменных равны 0).

7. Метод потенциалов решения тз.

Если опорный план Х=(хij) транспортной задачи является оптимальным, то существуют потенциалы поставщиков ui, i = 1, ….., m и потребителей vj, j=1,….,n, удовлетворяющие условиям :

ui+vj = cij при xij  0 (для занятых клеток), (2.2)

Δij = ui + vj – cij ≤ 0 при xij = 0 (для свободных клеток) (2.3)

Условия (2.2) образуют систему с m+n неизвестными ui, vj и, в общем случае, m+n -1 уравнений. Так как число неизвестных системы на единицу больше числа уравнений, то одну из неизвестных можно задать произвольно, а остальные найти из системы.

8. Оценки опорного плана. Условия оптимальности опорного плана.

Числа Δij = ui + vj – cij называют оценками свободных клеток. Таким образом, согласно теореме: Если опорный план Х=(хij) транспортной задачи является оптимальным, то существуют потенциалы поставщиков ui, i = 1, ….., m и потребителей vj, j=1,….,n, удовлетворяющие условиям :

ui+vj = cij при xij  0 (для занятых клеток), (2.2)

Δij = ui + vj – cij ≤ 0 при xij = 0 (для свободных клеток) (2.3)

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

9. Цикл. Перестановка по циклу.

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

В таблице выбираем свободную клетку с максимальной положительной оценкой и формируем цикл, одной из вершин которого является выбранная клетка, а остальные клетки занятые. Кроме того, сопоставим каждой вершине цикла знак и перевозку, при этом свободной клетке сопоставляем знак «+», а для остальных клеток знаки чередуются. Дальше делаем перестановку по циклу, а именно: из всех вершин, отмеченных минусом, вычтем минимум из всех перевозок, означенных этим знаком, т.е вычитаем Δ, а ко всем вершинам с «+» прибавим Δ. Таким образом с помощью цикла получаем новый опорный план.

10. Открытая модель тз. Сведения открытой модели к закрытой.

Транспортная задача m*n называется задачей с неправильным балансом, а её модель

открытой, если: m n

 ai ≠  bj

i=1 j=1

т.е суммарные запасы не равны суммарным потребностям.

Открытую задачу можно свести к закрытой:

1. Если: m n

ai bj , то вводят фиктивного потребителя Вn+1, с потребностью

i=1 j=1

m n

b n+1 = ai  bj и нулевыми тарифами перевозок в столбце.

i=1 j=1

2. Если: m n

ai  bj , то вводят фиктивного поставщика Аm+1, с запасом

i=1 j=1

n m

a m+1 = bj  ai и нулевыми тарифами перевозок в строке.

i=1 j=1