26. Тз с открытой и закрытой моделью. Преобразование открытой модели в закрытую модель.

Модель ТЗ наз-ют закрытой, если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т.е. выполняется равенство

Если для ТЗ выполняется одно из условий:

То модель наз-ют открытой.

Для разрешимости ТЗ с открытой моделью необходимо преобразовать ее в закрытую. Так, при выполнении первого условия необходимо ввести фиктивный (n+1)-й пункт назначения , т.е. в матрице задачи предусматривается дополнительный столбец. Спрос фиктивного потребителя полагают равным небалансу, т.е. а все тарифы – одинаковыми, чаще всего равными нулю, т.е. (i=от 1 до m). Аналогично при выполнении второго условия вводится фиктивный поставщик , запас груза у которого равен

А тарифы дополнительной строки распределительной таблицы равны нулю, т.е. (j=от 1 до n)

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

27. Теорема о ранге матрицы системы ограничительных

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

Д-во: матрица системы ограничений имеет вид

В каждом столбце матрицы А содержатся только два элемента, равных единице, остальные элементы равны нулю. При этом, если сложить первые m строк матрицы, получим строку, элементами которой будут единицы. Этот же результат получаем, если сложить последние n строк. Обозначая i-ю строку через pi, получаем

Отсюда видно, что любая строка есть линейная комбинация остальных строк, например

Значит, не меняя ранга матрицы А, можно вычеркнуть, например, последнюю строку. Минор (m+n-1)-го порядка получившейся матрицы, составленный из столбцов коэф-ов при x1n, x2n, …, xmn, x11, x12, …, x1,n-1 отличен от нуля, что и доказывает теорему.

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

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

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

Виды циклов:

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

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

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

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

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

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

35. Признак оптимальности опорного решения ТЗ.

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

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

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