Транспортная задача по критерию времени

Транспортная задача является сбалансированной, если суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.

.

Если транспортная задача не сбалансирована, то возникают особенности в ее решении.

Особенности решения транспортных задач с неправильным балансом: look here

.Если суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е.

то необходимо ввести фиктивного (n+1)-го потребителя с запросами равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза

. Если суммарные запросы потребителей превосходят суммарные запасы поставщиков, т.е.

то необходимо ввести фиктивного (m+1)-го поставщика с запасами равные разности суммарных запросов потребителей и запасов поставщиков, и нулевыми стоимостями перевозок единиц груза

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

ОПОРНОЕ РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

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

Ввиду того, что ранг системы векторов условий транспортной задачи равен N=m+n-1, опорное решение не может иметь отличных от нуля координат больше, чем N.

Для проверки линейной независимости векторов условий, соответствующих координатам допустимого решения, используют циклы.

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

Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи , i=1,2,…,m; j=1,2,…,n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.

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

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