23. Теорема о ранге матрицы системы ограничительных уравнений тз и ее прикладное значение.

Теорема: Ранг матрицы А трансп.задачи на единицу меньше числа уравнений: r(A)=m+n-1.

24. Циклы в транспортной таблице. Свойства циклов.

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

Графическим изображением цикла является замкнутая ломаная линия (контур), звенья которой расположены только в строках и столбцах таблицы. Каждое звено соединяет две и только две соседние клетки цикла. Вершины цикла помечаются знаками «+» и «-» поочередно, начиная со свободной клетки.Таким образом, план ТЗ является опорным тогда и только тогда, когда из занятых им m+n-1 клеток нельзя образовать ни одного цикла.

25. Способы построения нач опорного плана тз (Наимен Эл-та, северо-зап угла, Фогеля)

Опорный план можно построить несколькими способами.

Правило «северо-западного угла». Суть сост в том, что 1ой загружается левая верхняя клетка (1.1). а затем двигаемся от нее по строке вправо или по столбцу вниз. В клетку (1.1) занесем меньшее из чисел а1, в1. Если закрывается строка, то след загружается клетка (2.1); если же закр-тся столбец, то след загружается клетка (1.2). Итак, каждый раз загружается клетка, соседняя либо по строке, либо по столбцу. Последней будет загружена клетка (m;n). В результате загруженные клетки расположатся вдоль диагонали (1;1) – (m;n), поэтому способ «северо-западного угла» называют еще диагональным способом.

Способ «минимального элемента». Суть: 1ой в табл загружается клетка с наимен тарифом. В клетку запис-ся max возмо знач-е поставки. Затем из рассмотрения исключают строку, соответств-ю поставщику, запасы кот полностью израсх, или столбец, соответств-й потр-лю, спрос кот полностью удовлетворен. Из оставшихся клеток табл снова выбирают клетку с наимен тарифом. Процесс распред-я заканчивается, когда все запасы поставщиков исчерпаны, а спрос потр-лей полностью удовл. В рез получаем опорный план, котй должен содержать m+n-1 загруженых клеток. В процессе заполнения таблицы могут быть одновременно исключены строка или столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос ( вырожденная задача). В этом случае в свободные клетки надо записать число 0 – «нуль-загрузку», условно считая такую клетку занятой. Однако число 0 записывается в те свободные клетки, к-рые не образуют циклов с ранее занятыми клетками.

Метод «Фогеля». Суть: по строкам и столбцам опред-ся разность между 2мя наимен тарифами. Из этих разностей выбир-ся наибольшая и в соответствующей строке (столбце) загружается клетка с наимен тарифом. Закрывающаяся строка (столбец) исключ-ся из дальнейшего рассмотрения. Описанная операция повторяется m+n-1 раз. Если наиболразность окаж-ся сразу в нескольких строках (столбцах), то выбир-т ту строку (столбец), в к-рой придется загружать клетку с наимен тарифом. Если и эти показ-ли будут одинак, то выбирают клетку, в к-рую придется записать большую поставку.

26+27+28. Признак оптим-ти опорного плана. Оценка свободной клетки трансп.таблицы. процедура преобраз-я опорного плана ТЗ в новый опорный план.

В соответствии с теорией двойственности, если xij*=0, то ui+vj<=cij, т.е.разность

- наз-ся оценкой свободной клетки и ее величина показ, как измен-ся общая ст-ть перевозок, если по маршруту (ij) провести единицу груза. Таким образом признаком оптимальности опорного плана ТЗ является неотрицательность оценок свобод.клеток. Если среди оценок есть отриц-ые, то чтобы уменьшить общую ст-ть перевозов нужно загрузить первую очередь клетку с наибол по модулю отрицат оценкой. Такую клетку наз-ют перспективной. Если в распределит-ой таблице, содержащей оптим.план, имеются своб клетки с нулевыми оценками, то задача имеет не единственный оптим.план. Загружая свободную клетку с нулевой оценкой, можно найти еще один оптим.опорный план. И так для каждой свободной клетки с нулевой оценкой.

Чтобы осуществить переход от одного опорного плана к другому необходимо загрузить перспективную клетку. Для этой клетки составляется цикл. Нужно доказать, что для каждой свободной клетки трансп.таблицы, содержащей опорный план, сущ-ет цикл, причем только единственный. Вершины цикла помечаются знаками «+» и «-» поочередно, начиная со свободной клетки. Далее выбир-ся наименьшая из загрузок клеток, отмеченная «-». Она обозначается число λ добавляется к загрузке клеток, помеченных «+», и вычитается из загрузки клеток, отмеченных «-». Клетка по к-рой выбрано число λ освобождается. Если освобождается одновременно несколько клеток, то свободной остается та, в к-рой наибольший тариф. В остальные освободившиеся вписывается загрузка 0.