Опорное решение транспортной задачи

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

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

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

Любое допустимое решение транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные – незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку , т. е. стоящая в i-й строке, j-м столбце, имеет номер (i, j). Каждой клетке с номером (i, j) соответствует переменная , а этой переменной соответствует вектор-условий .

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

Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В цикле любая клетка является угловой, в которой происходит поворот звена ломаной линии на 90°. Простейшие циклы изображены на рис. 6.1, где звездочкой отмечены клетки таблицы, включенные в состав цикла.

Рис 6.1

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

Доказательство. Необходимость. Пусть система, состоящая из n векторов

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

. (6.10)

Пусть . Вектор имеет две равные единице координаты с номерами и , остальные равны нулю. В равенство (6.10) должен входить еще вектор, у которого одна из этих координат равна единице и который должен умножаться на коэффициент , чтобы обеспечить равенство нулю этой координаты в линейной комбинации векторов. Пусть таким является вектор . Но этот вектор имеет кроме того координату с номером , равную единице. Следовательно, в равенство (6.10) должен также входить вектор с такой же единичной координатой и т. д.

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

( ), ( ), ( ), …, ( ),

которая образует цикл.

Достаточность. Пусть из соответствующих векторам клеток (i, j) выбрана последовательность клеток, образующих цикл ( ), ( ), ( ), ..., ( ). Нетрудно видеть, что

.

Отсюда следует линейная зависимость рассматриваемой системы векторов.

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

Метод вычеркивания

Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.

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

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

Ниже приведены примеры "вычеркиваемого" (опорного) и "невычеркиваемого" (неопорного) решений:

вычеркиваемое невычеркиваемое

Методы построения начального опорного решения.
Метод северо-западного угла

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

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

1) если то и исключается поставщик с номером i, ;

2) если то и исключается потребитель с номером j, ;

3) если то и исключается либо поставщик с номером i, , либо потребитель с номером j, .

Нулевые перевозки принято заносить в таблицу только в том случае, когда они попадают в клетку с номером (i, j), подлежащую заполнению. Если в очередную клетку таблицы (i, j) требуется поставить перевозку, а поставщик с номером i или потребитель с номером j имеет нулевые запасы или запросы, то ставится в клетку перевозка, равная нулю (базисный нуль), и после этого обычным образом исключается из рассмотрения соответствующий поставщик или потребитель. Таким образом, в таблицу заносятся только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.

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

Теорема 6.4. Решение транспортной задачи, построенное по методу северо-западного угла, является опорным.

Доказательство. Число занятых опорным решением клеток таблицы должно быть равно . На каждом шаге построения решения по методу северо-западного угла заполняется одна клетка и исключается из рассмотрения одна строка (поставщик) или один столбец (потребитель) таблицы задачи. Через шага в таблице будет занято клетки. В то же время останутся не вычеркнутыми одна строка и один столбец, а клетка одна. При заполнении этой последней клетки число занятых клеток составит

.

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

Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому опорное решение, построенное данным методом, может быть далеким от оптимального.

Пример 6.2. Составить начальное опорное решение, используя метод северо-западного угла, для транспортной задачи, исходные данные которой представлены в табл. 6.3.

Т а б л и ц а 6.3

Решение. Распределяем запасы 1-го поставщика. Так как его запасы меньше запросов первого потребителя , то в клетку (1, 1) записываем перевозку и исключаем из рассмотрения поставщика. Определяем оставшиеся неудовлетворенными запросы 1-го потребителя .

Распределяем запасы 2-го поставщика. Так как его запасы больше, оставшихся неудовлетворенными запросов 1-го потребителя , то в клетку (2, 1) записываем перевозку и исключаем из рассмотрения 1-го потребителя. Определяем оставшиеся запасы 2-го поставщика . Так как , то в клетку (2, 2) записываем и исключаем по своему усмотрению либо второго поставщика, либо второго потребителя. Пусть исключили 2-го поставщика. Вычисляем оставшиеся неудовлетворенными запросы второго потребителя =200 - 200 = 0.

Распределяем запасы 3-го поставщика. Так как
(200 > 0), то в клетку (3, 2) записываем и исключаем второго потребителя. Запасы третьего поставщика не изменились 200-0 =200. Сравниваем и (200 > 100), в клетку (3, 3) записываем , исключаем 3-го потребителя и вычисляем 200 - 100 = 100. Так как , то в клетку (3, 4) записываем . Ввиду того, что задача с правильным балансом, запасы всех поставщиков исчерпаны и запросы всех потребителей удовлетворены полностью и одновременно.

Результаты построения опорного решения приведены в
табл. 6.4.

Т а б л и ц а 6.4

Проверяем правильность построения опорного решения. Число занятых клеток должно быть равно . В табл. 6.4 занято 6 клеток. Применяя метод вычеркивания, убеждаемся, что найденное решение является вычеркиваемым (звездочкой отмечен базисный нуль).

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

Метод минимальной стоимости

Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи ,
i = 1, 2, ..., m; j = 1, 2, ..., n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости , и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы груза использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом, если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично с потребителем.

Теорема 6.5. Решение транспортной задачи, построенное по методу минимальной стоимости, является опорным.

Доказательство аналогично доказательству опорности решения, построенного по методу северо-западного угла.

Пример 6.3. Используя метод минимальной стоимости, построить начальное опорное решение транспортной задачи, исходные данные которой приведены в табл. 6.5.

Т а б л и ц а 6.5

Решение. Запишем отдельно матрицу стоимостей для того, чтобы удобнее было выбирать минимальные стоимости, вычеркивать строки и столбцы.

Среди элементов матрицы стоимостей выбираем наименьшую стоимость , отмечаем ее кружочком. Данная стоимость имеет место при перевозке груза от 1-го поставщика 1-му потребителю. В соответствующую клетку (1, 1) записываем максимально возможный объем перевозки (табл. 6.6).

Т а б л и ц а 6.6

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

В оставшейся части матрицы С минимальной является стоимость .

Максимально возможная перевозка, которую можно осуществить от 1-го поставщика 4-му потребителю равна . В соответствующую клетку таблицы записываем перевозку . Запасы первого поставщика исчерпаны, исключаем его из рассмотрения. В матрице С вычеркиваем первую строку. Запросы 4-го потребителя уменьшаем на 20, .

В оставшейся части матрицы С минимальная стоимость . Заполняем одну из двух клеток таблицы (2, 4) или (3, 2). В клетку (2, 4) запишем . Запросы 4-го потребителя удовлетворены, исключаем его из рассмотрения, вычеркиваем 4-й столбец в матрице С. Уменьшаем запасы 2-го поставщика 80 - 40 = 40.

В оставшейся части матрицы С . Запишем в клетку таблицы (3, 2) перевозку . Исключим из рассмотрения 2-го потребителя, а из матрицы С 2-й столбец. Вычисляем .

В оставшейся части матрицы С наименьшая стоимость . Запишем в клетку таблицы (3, 3) перевозку = 40. Исключим из рассмотрения 3-го поставщика, а из матрицы С 3-ю строку. Определяем
.

В матрице С остался единственный элемент . Записываем в клетку таблицы (2, 3) перевозку .

Проверяем правильность построения опорного решения. Число занятых клеток таблицы равно N = m + n - 1 = 3 + 4 - 1 = 6 (табл. 6.6). Методом вычеркивания проверяем линейную независимость векторов-условий, соответствующих положительным координатам решения. Порядок вычеркивания показан на матрице Х.

Решение является вычеркиваемым и, следовательно, опорным.