Решение транспортных задач на ЭВМ

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

     

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

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

     

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

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

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

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

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

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

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

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

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

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

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

     Пример 2:

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

     Таблица 3

 

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

     

     1 4 6 3

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

     Таблица 4

 

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

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

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

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

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

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

     

      1 2 5 6

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

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

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

     Для удобства вычислений вершины циклов нумеруют и отмечают нечетные знаком «+», а четные знаком «-». Такой цикл называется означенным.

     

     Сдвигом по циклу на величину называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», и уменьшение объемов перевозок на ту же величину во всех не четных клетках, отмеченных знаком «-». 

     

3. МЕТОД ПОТЕНЦИАЛОВ 

     Широко  распространенным методом решения  транспортных задач является метод  потенциалов.

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

     

     Группа  равенств (2.1) используется как система  уравнений для нахождения потенциалов. Данная система уравнений имеет  m+n неизвестных i=1,2,…,m и j=1,2,…,n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.

     Группа  неравенств (2.2) используется для проверки оптимальности опорного решения. Эти  неравенства удобнее представить  в следующем виде:

      (2.3)

     Числа называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи.

     Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные.

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

       по этому  циклу.

     Алгоритм  решения транспортных задач методом  потенциалов:

1. Проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок.
2. Построить начальное опорное решение (методом минимальной стоимости или каким-либо другим методом), проверить правильность его построения по количеству занятых клеток (их должно быть m+n-1) и убедиться в линейной независимости векторов условий (используется метод вычеркивания).
3. Построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений: