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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31. Алгоритм метода потенциалов.

Алгоритм:

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

2. Условие задачи записывается в форме транспорт.таблицы

3. Строится начальный опорный план

4. Определяются потенциалы пост-ков и потреб-лей

5. Вычисляются оценки свободных клеток. Если все они не отрицательные – план оптимальный и нужно выписать ответ. Матрицу перевозок Х и определить величину затрат на транспортировку. Если план не явл-ся оптимальным, т.е.среди оценок есть отриц-ые, то выбир-т перспективную клетку с наибольшей по величине отриц. оценкой и переходят по величине к след.

6. Загруж-т перспективную клетку. Оформл-т нов.опорн.план в виде трансп.таблицы. Переходят к пункту 4.