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

Пример 2.

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

 

Решение:

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

(Таблица 7)

2. Среди элементов матрицы  стоимостей выбираем наименьшую  стоимость C11=1, отмечаем ее кружочком. Данная стоимость имеет место при перевозке груза от 1-го поставщика 1-му потребителю. В соответствующую клетку записываем максимально возможный объем перевозки: 
x11 = min {a1; b1} = min {60; 40} = 40 т.е. минимум между запасами 1-го поставщика и запросами 1-го потребителя.

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

3. В оставшейся части  матрицы C минимальной стоимостью  является стоимость C14=2. Максимально возможная перевозка, которую можно осуществить от 1-го поставщика, 4-му потребителю равна x14 = min {a1'; b4} = min {20; 60} = 20, где - это оставшиеся запасы первого поставщика. 
3.1. Запасы 1-го поставщика исчерпаны, поэтому исключаем его из рассмотрения. 
3.2. Запросы 4-го потребителя уменьшаем на 20.

4. В оставшейся части  матрицы С минимальная стоимость C24=C32=3. Заполняем одну из двух клеток таблицы (2,4) или (3,2). Пусть в клетку запишем x24  = min {a2; b4} = min {80 ; 40} = 40.

4.1. Запросы 4-го потребителя  удовлетворены. Исключаем его из  рассмотрения, вычеркивая 4-й столбец в матрице C.

4.2. Уменьшаем запасы 2-го  поставщика 80-40=40.

5. В оставшейся части  матрицы C минимальная стоимость C32=3. Запишем в клетку (3,2) таблицы перевозку x32 = min {a3; b2} = min {100; 60} =60. 
5.1. Исключим из рассмотрения 2-го потребителя. Из матрицы C исключаем 2-ой столбец.

5.2. Уменьшим запасы 3-го  поставщика 100-60=40

6. В оставшейся части  матрицы C минимальная стоимость C33=6. Запишем в клетку (3,3) таблицы перевозку x33 = min {a3'; b3} = min {40; 80} =40 
6.1. Исключим из рассмотрения 3-го поставщика, а из матрицы C 3-ю строку. 
6.2. Определяем оставшиеся запросы 3-го потребителя 80-40=40.

 

7. В матрице C остался единственный  элемент C23=8. Записываем в клетку таблицы (2,3) перевозку X23=40.

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

Вывод: Решение методом минимальной стоимости (таблица 7) является "вычеркиваемым" и, следовательно, опорным.

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

 

            §8. Метод потенциалов

 Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В., Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).   

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

Составим двойственную задачу

1. , ,…,; , ,…, – любые
2. + = ; j = , i =
3. T (u, v) = +      max

Пусть есть план = , ( j = , i = )

Теорема (критерий оптимальности): Для того чтобы допустимый план перевозок = , ( j = , i = ) в транспортной задаче был оптимальным, необходимо и достаточно, чтобы существовали такие числа , ,…,; , ,…,, что

+ = , если > 0,

+ ≤ , если = 0.

Числа и ( j = , i = ) называются потенциалами пунктов отправления и назначения соответственно.

[ http://www.math.mrsu.ru/text/courses/e-learn/3.5.htm ]

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

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

=  - + < 0

[ Высшая математика. Математическое программирование. Кузнецов А.В., Сакович В.А., Холод Н.И. ]

Пример 3.

    Построим цикл для загрузки клетки (3,1) в транспортной таблице (таблица 1 ).

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

    Фиктивный перенос по циклу может применяться при решении транспортной задачи методом потенциалов. 

                         (таблица 1)              (таблица  2)

     Приведем алгоритм метода потенциалов.

 

Шаг 0. Берут любой невырожденный опорный план перевозок, в котором отмечены m+n-1 базисных клеток (остальные клетки – свободные).

Шаг 1. Для этого плана вычисляют потенциалы ( , ) , исходя из условия: в любой базисной клетке псевдостоимости равны стоимостям:

+ = (1)

Один из платежей назначают произвольно, например, равным нулю.

Шаг 2. Рассчитывают псевдостоимости для всех свободных клеток:

= + (2)

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

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

Шаг 5. Проверяют «невырожденность» нового опорного плана. Если план вырожден, то его сводят к невырожденному, объявляя часть свободных клеток условно занятыми, и переходят к шагу 1.

Шаги 1-5 алгоритма итерационно повторяются, пока не будет найден оптимальный план.

[http://edu.nstu.ru/courses/mo_tpr/files/3.3.4.html ]

 

 

 

 

 

 

 

    Список литературы

1. http://library.tuit.uz/skanir_knigi/book/logistika2/logis_1.htm
2. http://www.coolreferat.com
3. http://nadka-patriotka.narod.ru/logistika.htm
4. Высшая математика. Математическое программирование. Кузнецов А.В., Сакович В.А., Холод Н.И.
5. http://www.bestreferat.ru/referat-215458.html
6. http://math.semestr.ru/transp/model_transport.php
7. http://www.grandars.ru/student/vysshaya-matematika/opornoe-reshenie-transportnoy-zadachi.html
8. http://www.math.mrsu.ru/text/courses/e-learn/3.5.htm
9. http://edu.nstu.ru/courses/mo_tpr/files/3.3.4.html
10. [http://www.grandars.ru/student/vysshaya-matematika/model-transportnoy-zadachi.html

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение

Пример 1.

Решить транспортную задачу

		Потребители			Запасы
Поставщики		9	5	4	25
		7	8	5	50
		3	4	6	50
Спрос		25	70	40

Решение

    Обозначим через ( i = ; j = ) количество груза перевозимого от i – го поставщика, к j – му потребителю. Тогда общая стоимость перевозок равна:

  f = = 9 + 5 + 4 + 7 + + 5 +

3 + 4 + 6

    Ограничения для поставщиков:

+ + = 25 – для 1 – го поставщика

+ + = 50 – для 2 – го поставщика

+ + = 50 – для 3 – го поставщика

    Ограничения для потребителей:

+ + ≤ 25 – для 1 – го потребителя

+ + ≤ 70 – для 2 – го потребителя

+ + ≤ 40 – для 3 – го потребителя

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

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

=

    В нашем случае:

; = 135.

Модель транспортной задачи открытая. Вводим фиктивного поставщика, у которого 10 единиц груза.

Заполняем таблицу по правилу минимального элемента. Решать задачу будем методом потенциалов. Число занятых клеток должно быть m + n – 1. Потенциал 1 – й строки принимаем равным нулю. После этого мы можем вычислить остальные потенциалы ( если известны потенциал и тариф занятой клетки, то из соотношения u + v = c легко определить известный потенциал ).

        Найдем  оценки свободных клеток:

S (1, 1) = 9 – (0 + 6) = 3                                       S (1, 3) = 5 – (0 + 7) = - 2

S (2, 1) = 7 – (1 + 6) = 0                                       S (3, 3) = 6 – (-3 + 4) = 5

S (4, 1) = 0 – (-6 + 7) = - 1                                   S (4, 3) = 0 – (-6 + 4) = 2

        Для клетки (1, 2) строим цикл.

         Найдем оценки свободных клеток:

S (1, 1) = 9 – (0 + 4) = 5                                       S (1, 3) = 4 – (0 + 2) = 2

S (2, 1) = 7 – (3 + 4) = 0                                      S (3, 3) = 6 – (-1 + 2) = 5

S (4, 1) = 0 – (-4 + 5) = - 1                                  S (4, 3) = 0 – (-4 + 2) = 2

          Для клетки (4, 2) строим цикл.

        Найдем  оценки свободных клеток:

S (1, 1) = 9 – (0 + 4) = 5                                       S (1, 3) = 4 – (0 + 2) = 2

S (2, 1) = 7 – (3 + 4) = 0                                      S (3, 3) = 6 – (-1 + 2) = 5

S (4, 1) = 0 – (-5 + 4) = - 1                                  S (4, 3) = 0 – (-5 + 2) = 3

       Оценки  свободных клеток не отрицательны, следовательно, полученный план  является оптимальным:

=

       Минимальные  транспортные издержки оптимального  плана:

min f = 5*25 + 8*10 + 5*40 + 3*25 + 4*25 = 580.

       При  реализации оптимального плана  потребитель  останется до конца не загруженным. Нехватка груза составит 10 единиц.

Пример 2.

Составить опорное решение методом северо-западного угла транспортной задачи, в которой 5 поставщиков и 5 потребителей данные записаны в таблице1.( - поставщики, – потребители )

 

                                                                                                                

                                                                                                                    Таблица 1

	50	40	30	20	10
10
20
30
40
50