Транспортная логистика

Цель складской системы состоит не только в том, чтобы принимать с транспорта (например, магистрального) грузопоток с одними параметрами, перерабатывать и отправлять его на другой (например, внутризаводской) с другими параметрами, но и для того, чтобы выполнять это преобразование с минимальными издержками. Издержки бывают следующих видов:

-  замороженные финансовые  средства, потраченные на покупку  материальных ресурсов;

-  расходы на содержание  специально оборудованных помещений;

-  оплата труда специального  персонала;

-  потери вследствие  порчи и хищений запасов.

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

 [ http://www.bestreferat.ru/referat-215458.html ]

Теорема. (Свойство системы ограничений транспортной задачи)

Ранг системы векторов-условий транспортной задачи равен N=k+n-1 (m — поставщики, n-потребители)

Доказательство.

Как известно из линейной алгебры для нахождения базиса системы векторов , ,…, необходимо составить однородную систему уравнений ++…+= θ ( здесь θ - нулевой вектор )

Эту систему с помощью преобразований Жордана приводят к равносильной разрешенной; в базис включают векторы , соответствующие разрешенным неизвестным. Ранг системы векторов равен числу векторов, входящих в базис, т.е. числу разрешенных неизвестных этой системы. Системе векторов-условий транспортной задачи , i=1, 2, …, k; j= 1,2, …, n соответствует однородная система уравнений =θ, где θ= - нулевой вектор (транспонированный). Запишем матрицу этой системы (она является также матрицей системы ограничений транспортной задачи):

Если к последней строке (уравнению) прибавить ( n-1) строку (уравнение), начиная с (k+1) -й, и вычесть первые k строк, то получится строка, состоящая из нулей. Это значит, что число разрешенных неизвестных в этой системе и ранг r системы векторов-условий не могут быть равны числу k+n уравнений. Следовательно, r < k+n-1. Покажем, что найдутся N = k+n-1 линейно независимых векторов-условий.   Из векторов-условий задачи выберем следующие:,…, ,…, и убедимся, что они линейно независимы. Для этого составим систему уравнений ++…++…+=θ

  Матрица этой системы, как легко показать, приводится  к единичной. Следовательно система уравнений имеет единственное нулевое решение ==…====…==θ, а система векторов линейно независима. Теорема доказана.

[ http://math.semestr.ru/transp/model_transport.php ]

 

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

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

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

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

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

Теорема.

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

§5.  Метод северо-западного угла

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

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

Заполнение таблицы транспортной задачи начинается с левого верхнего угла, поэтому и называется метод северо-западного угла.

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

       Пример 1.

Таблица 2

Решение:

1. Распределяем запасы 1-го  поставщика.

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

Пример: так как его запасы =100 меньше запросов первого потребителя =100, то в клетку (1,1) записываем перевозку =100 и исключаем из рассмотрения поставщика.

Определяем оставшиеся неудовлетворенными запросы 1-го потребителя = 150-100=50.

Таблица 3

 

	150	200	100	100
100	100				100 было - 100 надо
250
200
	150 надо - 100 было=50 осталось Осталось удовлетворить запросов на 50 единиц товара

 

2. Распределяем запасы 2-го  поставщика.

Так как его запасы = 250 больше оставшихся неудовлетворенными запросов 1-го потребителя =50, то в клетку (2,1) записываем перевозку =50 и исключаем из рассмотрения 1-го потребителя.

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

Вычисляем оставшиеся неудовлетворенными запросы второго потребителя = -=200-200=0.

Таблица 4

	150	200	100	100
100	100
250	50	200			250-50=200 200-200=0
200
	150-100-50=0

 

3. Распределяем запасы 3-го  поставщика.

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

Мы должны записать оставшиеся запросы равные нулю в клетку (3,2)

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

Таким образом, в таблицу заносятся только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.

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

Так как в предыдущем шаге мы исключили из рассмотрения второго поставщика, то в клетку (3,2) записываем =0 и исключаем второго потребителя.

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

Таблица 5

	150	200	100	100
100	100
250	50	200
200		0	100	100

 

4. Проверяем правильность  построения опорного решения.

Число занятых клеток должно быть равно N = m (поставщики) + m (потребители) - 1 = 3 + 4 – 1 = 6.

Применяя метод вычеркивания, убеждаемся, что найденное решение является "вычеркиваемым" (звездочкой отмечен базисный нуль).

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

[http://www.grandars.ru/student/vysshaya-matematika/opornoe-reshenie-transportnoy-zadachi.html ]

 

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

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

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

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

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

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

Примеры "вычеркнутого" (опорного) и "не вычеркнутого" (не опорного решений): 

Логика вычеркивания:

1. Вычеркнуть все столбцы, в которых всего одна занятая клетка (5 0 0), (0 9 0)
2. Вычеркнуть все строки, в которых всего одна занятая клетка (0 15), (2 0)
3. Повторить цикл (7) (1)

[http://www.grandars.ru/student/vysshaya-matematika/opornoe-reshenie-transportnoy-zadachi.html ]

 

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

Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C=.

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