28. Теорема о ранге матрицы коэффициентов тз

Теорема

Ранг r системы уравнений ТЗ при условии

m n ── ──

∑ ai = ∑ bi, i=1,m, j=1,n (1)

i=1 j=1

равен p+q-1.

Доказательство.

Действительно, сравним ∑ первых p уравнений. Согласно условию 1, правые части совпадают. Тогда совпадают и левые части, а сами уравнения линейно зависимы, а значит, r<= p+q-1.

Докажем, что r≥ p+q-1.

Из линейной алгебры известно, что если некоторые k переменных произвольной системы линейных уравнений можно выразить через остальные переменные системы, то ранг этой системы не меньше, чем k. Выразим переменные xik, входящие в первый столбец и первую строку таблицы.

p

xij=b1- ∑xij (8)

i=2

q

xik=a1-∑xij (9)

i=2

Подставим вместо xik его выражение из уравнения 8. Т.о., p+q-1 переменных можно выразить через остальные переменные pq-p-q+1.

r= p+q-1.

Следствие:

Число r основных (базисных) переменных закрытой модели ТЗ равно p+q-1, где p – число поставщиков, q – потребителей.

29. Нахождение исходного опорного решения транспортной задачи

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

Ввиду того, что r= p+q-1, опорное решение не может иметь отличных от нуля координат более p+q-1. Число отличных от нуля координат невырожденного опорного решения равно p+q-1, а для вырожденного опорного решения меньше.

• Метод северо-западного угла

• Метод минимальной стоимости

• Метод двойного предпочтения

• Начинают с того, что приписывают переменной x11, стоящей в северо-западном углу таблицы, минимальное из значений a1 и b1.

x11=min a1b1

Двигаются в соседнюю клетку по строке вправо, если a1>b1, или по столбцу вниз если a1<b1, полагая x12=a1-b1b2(min), x21=b1-a1a2(min). Это продолжают до тех пор, пока не исчерпаются ресурсы и потребности. Последняя заполненная клетка окажется pq. Решение, получаемое по методу сз угла – опорное решение.

Недостаток этого метода – он не учитывает значений коэффициентов затрат, но он допускает модификацию и очень удобен для работы на машине (первой берут не клетку северо-западного угла, а клетку с минимальным значением. При этом распределение поставок будет ближе к оптимальному).

• Из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai и bi. Затем из рассмотрения исключают или строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

• В каждом столбце отмечают знаком √ клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку √√. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

Цикл – набор клеток вида (i1k2,i2k1), в котором только две соседние клетки расположены в одном столбце или одной строке распределительной таблицы, причем последняя клетка находится в том же столбце или в той же строке, что и первая.

Графически циклу соответствует замкнутая ломаная линия. Допустимое решение транспортной задачи является опорным в том случае, если из занятых этим решение клеток нельзя образовать ни одного цикла. Если в распределительной таблице содержится опорное решение, то для каждой свободной клетки можно образовать только 1 цикл.