14.Определение закрытой модели тз. Критерий существования решения тз.

ТЕОРЕМА 1:Транспортная задача имеет решения тогда, и только тогда, когда (1)

1. – называется условием баланса.

Док-во. Необходимость. Пусть решение транспортной задачи существует ,

, . ,

Достаточность. Пусть выполняется условие баланса (1) . Построим след. план перевозок

,

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

Замечание Транспортная задача, для которой выполняется условие (1) называется закрытой, в противном случае – открытой.

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

1. если , то вводим фиктивный пункт производства с запасами продукции в нем в кол-ве и нулевыми стоимостями перевозок из него.

2. Если то вводим фиктивный пункт потребления с потребностямипродукции в нем

и нулевыми стоимостями перевозок в него.

15.Исследование множества клеток транспортной таблицы.

Множество всех клеток трансп. табл. обозначим

Опред. Цепью назовем последовательность клеток, в которой каждые две соседние клетки лежат в одной строке или в одном столбце, но ни в одной строке и ни в одном столбце нет трех послед. клеток.

Опред. Циклом наз. цепь, крайние клетки которой лежат в одной строке или в одном столбце.

Замеч. Если в трансп. табл. соседние клетки соединить отрезками прямых (звеньями цепи), то соседние звенья всегда будут перпендикулярны.

Опред. Мн-во клеток наз. базисным , полным, если их кол-во равно и из его элементов невозможно создать ни одного цикла.

Все остальные клетки наз. небазисными

Опред. План перевозок из i в j наз. базисным, если все перевозки за исключением равны 0, а остальные находятся в клетках, составляющих базисные множества клеток.

Опред. Перевозки , где (i,j) наз. базисными, а если (i,j) , то небазисными.

Опред. Базисный план наз. невырожденным, если все базисные перевозки строго >0, в противном случае – вырожденным.

Св-ва базисного множества клеток:

1. В каждой строке и каждом столбце трансп. табл. обязательно найдется базисная клетка.В противном случае не будет выполнено какое-либо из огр зад.

2. Найдется строка или столбец, в котором есть ровно 1 базисная клетка.

Док-во. От противного. Пусть в каждой строке 2 базисных клеток и в каждом столбце 2 базисных клеток, тогда если посчитать все клетки по строкам то их кол-во получится 2m, а если по столбцам, то 2n. Следовательно всех клеток m+n. Но по определению их должно быть . Следовательно предположение неверно.

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

4. Любую пару из строк и столбцов можно соединить единственной цепьб из элементов базисного множества клеток.

5. Добавление небазисной клетки к небазисному множеству создает цикл.