Задачи по теме «Транспортная задача»

№4.1 Имеется три пункта отправления (базы), на которых хранится груз, необходимый трём пунктам назначения и заданы тарифы перевозки в руб. за 1 т. груза (см. Таблицу 5.1).

 Таблица 5.1Условия транспортной задачи

Пункты отправления	Пункты назначения			Запасы (т.)
	2	1	3	100
	5	4	2	200
	6	2	1	300
Потребности (т.)	150	250	200

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

Решение:

1) Проверка наличия опорного решения.

В данном случае общий запас равен 100+200+300=600 т., общая потребность 150+250+200=600 т., они совпадают, т.е. задача имеет опорное и оптимальное решения и нет необходимости добавлять ни пункт назначения, ни пункт отправления.

2) Составим опорное решение. Для этого воспользуемся двумя различными методами – методом северо-западного угла и методом наименьшего элемента.

2.а) Метод северо-западного угла:

Начинаем заполнять пустую таблицу с левого верхнего угла (на географических картах это направление на северо-запад).

Первой клетке первой строки соответствует запас строки 100 т. (далее единицы измерения писать не будем) и потребность 150; Удовлетворяем потребность по максимуму возможности в количестве 100 и записываем это количество в выбранную клетку  (см. Таблицу 5.2, где в каждой клетке вместе с количеством перевезённого груза указан и тариф такой перевозки); Запас первой строки полностью истощился, остальные клетки строки заполним прочерками (аналогичны нулям, их отличие объясню ниже).

Таблица 5.2 Опорное решение ТЗ методом северо-западного угла

Пункты отправления	Пункты назначения						Запасы (т.)
	100	2	–	1	–	3	100
	50	5	150	4	–	2	200
	–	6	100	2	200	1	300
Потребности (т.)	150		250		200

 

После завершения некоторой строки каждый раз переходим к следующей строке и начинаем заполнение с самой левой незаполненной её клетки. Для первого столбца осталась неудовлетворённая потребность 150-100=50, у второй строки имеется запас 200, из них посылаем 50 в первую клетку, т.е. . Потребность первого столбца полностью удовлетворена, остальные его клетки заполним прочерками. Перейдём ко второй клетке второй строки т.к. остался запас 200-50=150, потребность второго столбца 250, т.е. запишем  и остальные клетки строки заполним прочерками. В третьей строке начинаем со второй клетки, заполним её и осталось .

Общая стоимость перевозки при таком опорном решении Х (плане перевозки) равна руб.;

2.2) Метод наименьшего элемента:

Пустую на начальном шаге таблицу начинаем заполнять с клетки, имеющей наименьший тариф (если их несколько, то можно начинать среди них сверху и слева). Имеется две клетки с наименьшим тарифом в 1, заполним по максимуму возможности верхнюю из них, задавая  (см. Таблицу 5.3). При этом исчерпан запас первой строки, остальные её элементы заполняем прочерками. Из оставшихся незаполненными клеток наименьший тариф равен 1, заполним  по максимуму потребности, при этом останется запас 100 у третьей строки и потребности третьего столбца полностью удовлетворены, т.е. его оставшиеся незаполненными клетки заполним прочерками.

 Таблица 5.3 Опорное решение ТЗ методом наименьшего элемента

Пункты отправления	Пункты назначения						Запасы (т.)
	–	2	100	1	–	3	100
	150	5	50	4	–	2	200
	–	6	100	2	200	1	300
Потребности (т.)	150		250		200

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

При таком плане перевозки общая стоимость перевозки равна  руб.

Получили два различных опорных решения (плана перевозки) с одинаковой стоимостью перевозки. Далее будем анализировать только второе т.к. обычно именно метод наименьшего элемента даёт более оптимальное решение;

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

2.3) Метод потенциалов:

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

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

    В данном случае по пяти заполненным клеткам можно составить линейную систему с таким числом уравнений от 3+3=6 неизвестных (искомых потенциалов):

                              .

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

В данном случае возьмём , тогда из условия  и  получим ;

Аналогично найдём все потенциалы (см. Таблицу 5.4).   

 

     Таблица 5.4 Проверка на оптимальность опорного решения Х₁

Потенциалы пунктов отправления	Потенциалы пунктов назначения
	–	2	100	1	–	3
	150	5	50	4	–	2
	–	6	100	2	200	1

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

в) Сдвиг по циклу:

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

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

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

                         Таблица 5.5 Сдвиг по циклу в решении Х₁

–	2	100	1	–	3
150	5	50	4		2
–	6	100	2	200	1

При заполнении  получим цикл (см. Таблицу 5.5) из четырёх вершин, хотя в общем случае он может оказаться более сложного вида. Подберём максимально возможное число , при котором все клетки такого цикла будут заполнены неотрицательными числами (обнулится одна или несколько клеток при положительных значениях в других). Для этого найдём минимальное число 50 среди тех, из которых вычитается .

    Составим новое опорное решение при таком =50 и проверим его на оптимальность методом потенциалов:

 

 

               Таблица 5.6 Проверка на оптимальность решения Х₂

Потенциалы пунктов отправления	Потенциалы пунктов назначения
	–	2	100	1	–	3
	150	5	–	4	50	2
	–	6	150	2	150	1

При таком плане перевозки общая стоимость перевозки равна  руб. т.е. заметно уменьшение стоимости перевозки на 50 руб.

Но и это опорное решение  не является оптимальным т.к. . Запишем в эту клетку +  и найдём новый цикл (см. Таблицу 5.7).

                        Таблица 5.7 Сдвиг по циклу в решении Х₂

	2	100-	1	–	3
150-	5	–	4	50+	2
–	6	150	2	150-	1

 

Возьмём и получим новое решение Х₃ (см. Таблицу 5.8), проверим его на оптимальность.

                Таблица 5.8 Проверка на оптимальность решения Х₃

Потенциалы пунктов отправления	Потенциалы пунктов назначения
	100	2	–	1	–	3
	50	5	–	4	150	2
	–	6	250	2	50	1

Для найденного опорного решения      в каждой его клетке выполнено т.е. это решение является оптимальным и минимальная стоимость перевозки равна       

руб.

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

 

Данную задачу можно решить на MathCADe, предварительно записав её, как задачу линейного программирования (ЗЛП). Для этого будем искать решение в виде таблицы , элементы которой являются переменными. Целевую функцию f составим в виде суммы попарных произведений тарифов на соответствующие переменные. Задав некоторые значения элементов матрицы Х, после оператора Given укажем ограничения в виде суммы по каждой строке не более запаса этой строки и суммы по каждому столбцу не менее потребности в этом столбце, добавив условие неотрицательности всех переменных. После условий запишем функцию minimize, в которой указана минимизируемая функция и все переменные для этого. Её значение – оптимальный набор переменных, при котором достигается (в окрестности начальной точки) минимум целевой функции.

 

Ответ:   Минимальная стоимость перевозки равна 1300 руб.      

 Для этого следует из  перевезти 100 т. груза в ,

                            из  перевезти 50 т.  в и 150 т. в ,
                            из  перевезти 250 т. в  и 50 т. в .

Замечание 7: Полученноё минимальное значение целевой функции (общая стоимость перевозки) может достигаться на разных решениях (планах перевозки), т.е. оптимальное решение транспортной задачи находится не всегда однозначно.

 

 

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

 

Пункты отправления	Пункты назначения								Запасы (т.)
		3		4		2		1	100
		4		5		2		4	200
		1		3		5		2	300
Потребности (т.)	100		150		150		100

а) Непосредственно заданную;

б) С учётом дополнительных условий перевозки ровно 40 т. из  в  и перевозки не менее 20 т. из  в .

Решение:

1) При поиске решения «вручную» проверим наличие опорного решения: общий запас 600 т., общая потребность 500 т. Требуется введение дополнительного пункта назначения В₅ с нулевыми тарифами и потребностью 600-500=100 т.

Решение этой задачи и полученной с учётом дополнительных условий можно выполнять «вручную», что весьма трудоёмко. В пакете MathCad  решение задачи достаточно просто:

Последний столбец говорит, что в пункте  останется 50 т. и в пункте  останется 50 т.

2) При решении задачи с дополнительными условиями

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

   

 

Ответ: а) Без дополнительных условий минимальная стоимость перевозки  при плане перевозки  и остатке 50 т. в  и остатке 50 т. в пункте ;    

б) При учёте дополнительных условий  при плане перевозки при  остатке 90 т. в  и остатке 10 т.  в пункте .

№4.3 (самостоятельно) Решить транспортную задачу

 

Пункты отправления	Пункты назначения								Запасы (т.)
		6		4		2		1	300
		4		2		2		2	200
		4		3		5		2	100
Потребности (т.)	100		200		150		150

а) Вручную с нахождением опорного плана и его оптимизацией методом потенциалов;

б) На MathCadе без дополнительных условий;

в) С учётом дополнительных условий перевозки не менее 40 т. из  в  и перевозки ровно  20 т. из  в .

Ответ: а-б) Без дополнительных условий минимальная стоимость перевозки  при плане перевозки ;

 

 в) При учёте дополнительных условий  

при плане перевозки .