Пример 1. Решить транспортную задачу методом потенциалов.

Раздел 2. Транспортная задача

П.2.1. Замкнутая и открытая модели ТЗ

Пример 1. Решить транспортную задачу методом потенциалов.

 

bj ai

 

1. Проверим, является ли данная задача замкнутой.

Подсчитаем суммарные запасы груза и суммарные потребности заказчиков ,

.

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

2. Построим первый опорный план транспортной задачи методом северо-западного угла.

Начинаем заполнение распределительной таблицы с верхней левой клетки, то есть построение исходного опорного плана начинаем с удовлетворения потребностей первого потребителя b₁ за счет запасов первого поставщика a₁. Для этого сравниваем запас a₁ = 200 с потребностями b₁ = 150. Так как a₁ > b₁, то потребности b₁ полностью удовлетворяем за счет a₁, и в первую клетку помещаем min (200, 150)=150. У первого поставщика осталось 50 единиц груза. Так как потребности первого получателя груза полностью удовлетворены, исключим из рассмотрения первый столбец, заполнив в нем оставшиеся клетки точками. Далее заполняем таблицу по строкам слева направо и сверху вниз. Следующая самая верхняя левая незаполненная клетка – (1,2). Потребителю b₂ поставляем 50 единиц груза, оставшихся у первого поставщика. Поскольку от первого поставщика весь груз вывезен, заполняем оставшиеся клетки первой строки точками. Второму получателю, пока что, недопоставлено 80 единиц груза. Следующая незаполненная клетка – (2,2). Потребителю b₂ отправляем недостающие 80 единиц груза, при этом его потребности полностью удовлетворены, поэтому оставшиеся клетки во втором столбце заполняем точками. У второго поставщика a₂ осталось еще 100 единиц груза. Аналогичным образом заполняем оставшиеся клетки, пока не удовлетворим всех потребителей и не вывезем все запасы груза у поставщиков.

 

 

bj ai
			*	*
	*			*
	*	*

 

В результате распределения груза получим первый опорный план, в котором x₁₁ = 150, x₁₂ = 50, x₂₂ = 80, x₂₃ = 100, x₃₃ = 50, x₃₄ = 140. Эти переменные соответствуют заполненным клеткам и являются базисными, остальные переменные, соответствующие клеткам с точками, являются свободными (значения свободных переменных равны нулю). Первый опорный план можно представить в матричном виде

 

Число заполненных клеток k = 6. Это число должно равняться рангу системы ограничений r = m + n – 1 = 3 + 4 – 1 = 6. Так как k = r = 6, то построенный план является невырожденным. Подсчитаем затраты на перевозку по этому плану

 

.

 

3. Построим первое опорное решение транспортной задачи методом минимальной стоимости (минимального тарифа).

 

 

bj ai
	*	*
		*	*
	*		*

 

Найдем клетку с минимальным тарифом. Это клетка (1,3) с тарифом

c₁₃ =1. Построение исходного опорного плана начинаем с занесения поставки груза в клетку с наименьшей стоимостью c₁₃. Заполняем клетку x₁₃ = 150. Оставшиеся клетки третьего столбца заполняем точками, так как потребности третьего получателя полностью удовлетворены. У первого поставщика осталось 50 единиц груза. Ищем следующую клетку с минимальным тарифом. Таких клеток две: c₁₄ =2, c₃₂ =2. Заполним сначала клетку (3,2). Поставим в нее x₃₂=min (190, 130)=130. Второй столбец заполняем точками. У третьего поставщика осталось 60 единиц груза. Ищем следующую клетку с наименьшим тарифом – это клетка (1,4). В нее помещаем 50 единиц груза, min(50,140)=50. Первую строку заполняем точками, так как от первого поставщика вывезен весь груз. Четвертому получателю недопоставлено 90 единиц. Аналогичным образом распределяем весь имеющийся груз и получаем первый опорный план перевозок.

Подсчитаем затраты на перевозку по этому плану.

.

 

Итак, в каждой строке и в каждом столбце таблицы заполнена хотя бы одна клетка, циклов по заполненным клеткам нет, число заполненных клеток m+n-1=6, следовательно, план опорный и невырожденный.

 

4. Проверка первого опорного плана (решения) на оптимальность. Метод потенциалов

 

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

В таблице в дополнительном столбце справа помещаем потенциалы отправителей , а в строке снизу – потенциалы получателей. Составим систему уравнений для определения потенциалов:

Из этой системы находим

 

bj ai
	*	*			=2
		*	*		=8
	*		*		=6

 

Считаем оценки для свободных клеток:

 

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

 

bj ai
	9>0 7 *	10>0 8 *			=2
		1>0 5 *	2>0 9 *		=8
	7>0 9 *		-2<0 3 *		=6

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

 

bj ai
	*	*	1 150--	2 50+	=2
		*	*		=8
	*		*+	60--	=6

 

Сроим цикл пересчета, начиная с клетки (3,3), в которую нужно поместить поставку груза (её отмечают знаком «+»), и двигаясь по занятым клеткам (в данном случае это клетки (3,4), (1,4), (1,3)), поочередно отмечая их знаками «-», «+». Если в клетку (3,3) добавили + , то в смежных по циклу клетках необходимо вычесть для сохранения баланса перевозок по третьей строке и третьему столбцу. Звенья цикла должны быть параллельны строкам или столбцам таблицы, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, а другое – в столбце. Количество вершин в цикле должно быть четно. В результате построения цикла в соответствующих строках и столбцах должно быть парное количество знаков «-», «+».

Определяем величину поставки в клетку (3,3), как минимальную величину из поставок, стоящих в отрицательных клетках, то есть . Перераспределяем по циклу поставки на величину . Значение записываем в незанятую клетку (3,3), отмеченную знаком «+», двигаясь по циклу, прибавляем эту величину к поставкам в клетках со знаком «+», вычитаем в клетках со знаком «-».

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

 

bj ai
	*	*
		*	*
	*			*

 

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

 

 

bj ai
	*	*			=0
		*	*		=6
	*			*	=2

 

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

 

 

bj ai
	9>0 7 *	8>0 8 *			=0
		-1<0 5 *	2>0 9 *		=6
	9>0 9 *			2>0 6 *	=2

 

Возьмем клетку (2,2) за начало цикла пересчета. Цикл будет проходить по клеткам (2,2), (3,2), (3,3), (1,3), (1,4), (2,4) и опять вернется в (2,2).

 

bj ai
	9>0 7 *	8>0 8 *	1 90-	2 110++	=0
		-1<0 5 *+	2>0 9 *	30-	=6
	9>0 9 *	130-	60+	2>0 6 *	=2

 

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

 

 

bj ai
	*	*
			*	*
	*			*

 

Проверяем данный опорный план на оптимальность

 

bj ai
	8>0 7 *	8>0 8 *			=0
			3>0 9 *	1>0 8 *	=5
	8>0 9 *			2>0 6 *	=2

Полученный опорный план является оптимальным, так как все оценки для свободных клеток . Выписываем оптимальный план: x₁₁ = 0; x₁₂ = 0; x₁₃ = 60; x₁₄ =140; x₂₁ = 150; x₂₂ = 30; x₂₃ = 0; x₂₄ = 0; x₃₁ = 0; x₃₂ = 100; x₃₃ = 90; x₃₄ = 0. Или в матричной форме

Высчитываем минимальные затраты на транспортировку продукции:

 

 

Пример 2.

bj ai

1. Проверим, является ли данная задача замкнутой.

Подсчитаем суммарные запасы груза и суммарные потребности заказчиков ,

.

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

 

 

bj ai

Далее решаем ТЗ как в Примере 1.

Пример 3.

bj ai

1. Проверим, является ли данная задача замкнутой.

Подсчитаем суммарные запасы груза и суммарные потребности заказчиков ,

.

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

 

 

bj ai

Далее решаем ТЗ как в Примере 1.

Задача 2.1.1. Автотранспортная фирма “Карланд” обеспечивает доставку одних и тех же строительных блоков с двух железобетонных заводов АО “Бетон” на три строительных площадки. На первую площадку требуется доставить b₁, на вторую — b₂ и на третью — b₃ бетонных блоков. С первого завода должны быть отгружены a₁, со второго — a₂ бетонных блока. Тарифы на перевозку одного блока с каждого из заводов на соответствующую площадку приведены по вариантам:

Таблица 2.1.1.а

Площад-ка	№ 1	№ 2	№ 3	Отгрузка
Завод 1				a1 = 120
Завод 2				a2 = 100
Заказ	b1 = 70	b2 = 80	b3 = 70

Таблица 2.1.1.b

Площад-ка	№1	№2	№3	Отгрузка
Завод 1				a1 = 150
Завод 2				a2 = 100
Заказ	b1 =110	b2 = 80	b3 = 60

Таблица 2.1.1.c

Площад-ка	№ 1	№ 2	№ 3	Отгрузка
Завод 1				a1 = 120
Завод 2				a2 = 80
Заказ	b1 = 70	b2 = 80	b3 = 50

Таблица 2.1.1.d

Площад-ка	№ 1	№ 2	№ 3	Отгрузка
Завод 1				a1 = 150
Завод 2				a2 = 100
Заказ	b1 = 50	b2 = 80	b3 =120

Таблица 2.1.1.e

Площад-ка	№ 1	№ 2	№ 3	Отгрузка
Завод 1				a1 = 100
Завод 2				a2 = 140
Заказ	b1 = 80	b2 = 90	b3 =70

Выполните следующие задания:

1. Составьте математическую модель ТЗ.

2. Выпишите матрицу системы ограничений.

3. Определите ранг полученной матрицы.

4. Найдите первый опорный план

а) методом северо-западного угла;

б) методом минимальных тарифов.

5. Решите задачу методом потенциалов.

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

Таблица 2.1.2.а

Магазины Склады	№1	№2	№3	№4	№5	Объём запаса
Химки
Сходня
Ховри-но
Заявки

 

Таблица 2.1.2.б

Магазины Склады	№1	№2	№3	№4	№5	Объём запаса
Химки
Сходня
Ховри-но
Заявки

Таблица 2.1.2.в

Магазины Склады	№1	№2	№3	№4	№5	Объём запаса
Химки
Сходня
Ховри-но
Заявки

Таблица 2.1.2.г

Магазины Склады	№1	№2	№3	№4	№5	Объём запаса
Химки
Сходня
Ховри-но
Заявки

Таблица 2.1.2.д

Магазины Склады	№1	№2	№3	№4	№5	Объём запаса
Химки
Сходня
Ховри-но
Заявки

 

 

Таблица 2.1.2.е

Магазины Склады	№1	№2	№3	№4	№5	Объём запаса
Химки
Сходня
Ховри-но
Заявки

Таблица 2.1.2.ж

Магазины Склады	№1	№2	№3	№4	№5	Объём запаса
Химки
Сходня
Ховри-но
Заявки

Таблица 2.1.2.з.

Магазины Склады	№1	№2	№3	№4	№5	Объём запаса
Химки
Сходня
Ховри-но
Заявки

Таблица 2.1.2.и

Магазины Склады	№1	№2	№3	№4	№5	Объём запаса
Химки
Сходня
Ховри-но
Заявки

Таблица 2.1.2.к

Магазины Склады	№1	№2	№3	№4	№5	Объём запаса
Химки
Сходня
Ховри-но
Заявки

Выполните задания 1 — 5 задачи 2.1.1.

 

Задача 2.1.3. Решить транспортную задачу методом потенциалов:

(а)

bj ai

 

 

(б)

bj ai

(в)

bj ai

 

 

(г)

bj ai

(д)

bj ai

(e)

bj ai

Задача 2.1.4. Решить открытую транспортную задачу:

(а)

bj ai

 

(б)

bj ai

 

(в)

bj ai

 

(г)

bj ai

(д)

bj ai