Тема 2. Транспортная задача линейного программирования

Цель практического занятия №4: Получить навыки решения транспортной задачи линейного программирования методом потенциалов

Методические указания к практическому занятию

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

Существует n пунктов отправления некоторого однородного груза и m пунктов потребления . Требуется организовать перевозки груза с минимальными общими затратами (или минимальным общим временем доставки всего груза).

Исходные параметры модели:

1. [ед.товара] – запас перевозимого товара пункте отправления ;

2. [ед.товара] – потребность в товаре в пункте потребления ;

3. [руб./ед.товара] – стоимость перевозки одной единицы товара из пункта в пункт .

Искомые параметры модели:

1.  - количество товара перевозимого из в ;

2.  - общие транспортные расходы на доставку всего товара.

Модель транспортной задачи

;	(2.5) (2.6) (2.7) (2.8)

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

Вторая группа (2.7) ограничений указывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворять спрос на продукцию в этом пункте. Наглядной формой транспортной задачи является транспортная матрица (таблица 2.9) .

Таблица 2.9

Общий вид транспортной матрицы

Пункты отправления,	Пункты потребления,				Запасы (ед. товара)
			…
			…
			…
…	…	…	…	…	…
			…
Потребность (ед. товара)			…

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

.

(2.9)

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

.

(2.10)

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

.

(2.11)

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

(2.12)

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

Пример 2.9. С двух складов нужно перевезти однородный груз в три магазина. На I складе имеется 1800 т груза, на II складе – 2600 т груза. В магазин № 1 нужно доставить 1000 т, в магазин № 2 - 1200 т, в магазин № 3 – 2200 т.

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

Таблица 2.10

Стоимость перевозки 1 т груза, тыс. руб.

Склады	Магазины			Запасы, т
	№1	№2	№3
I	2	2	3	1800
II	3	4	2	2600
Потребности, т	1000	1200	2200

Решение:

Обозначим X_ij – количество груза, которое необходимо перевезти от I – го поставщика (склада) к j – му потребителю (магазину).

Переменные:

X₁₁ – объем груза, перевозимого c I склада в магазин № 1, т;

Х₁₂ – объем груза, перевозимого cо II склада в магазин № 2, т;

Х₁₃ – объем груза, перевозимого c III склада в магазин № 3, т;

Х₂₁ – объем груза, перевозимого cо II склада в магазин № 1, т;

Х₂₂ – объем груза, перевозимого cо II склада в магазин № 2, т;

Х₂₃ – объем груза, перевозимого cо II склада в магазин № 3, т.

Ограничения:

1. по возможности I склада, т х₁₁ + х₁₂ + х₁₃ = 1800

2. по возможности II склада, т х₂₁ + х₂₂ + х₂₃ = 2600

3. по потребности магазина № 1, т х₁₁ + х₂₁ = 1000

4. по потребности магазина № 2, т х₁₂ + х₂₂ = 1200

5. по потребности магазина № 3, т х₁₂ + х₂₂ = 2200

4400 т = 4400 т

Целевая функция:

F(x) = 2х₁₁ + 2х₁₂ + 3х₁₃ + 3х₂₁ + 4х₂₂ + 2х₂₃ →min

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

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

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

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

Если существующий запас позволяет перевезти всю потребность, то

• в клетку (I,j) в качестве перевозки вписывается значение потребности ;

• j-й столбец вычеркивается, поскольку его потребность уже исчерпана;

• от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т.е. .

Если существующий запас не позволяет перевезти всю потребность, то

• в клетку (I,j) в качестве перевозки вписывается значение запаса ;

• i-я строка вычеркивается, поскольку ее запас уже исчерпан;

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

Пример 2.10. Найти опорный план методом северо-западного угла для задачи с транспортной таблицей 2.9.

Таблица 2.11

Исходная транспортная таблица примера 2.9

Пункты отправления,	Пункты потребления,				Запасы (ед. товара)
	7	8	1	2	160
	4	5	9	8	140
	9	2	3	6	170
Потребность (ед. товара)	120	50	200	110

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

Для того, чтобы сбалансировать задачу введем фиктивный пункт отправления с фиктивным запасом 10 [ед.товара] и фиктивным тарифом 0 [руб./ед.товара] (таблица 2.12) и распределим перевозки методом северо-западного угла.

Таблица 2.12

Северо-Западный опорный план задачи

Пункты отправления,	Пункты потребления,				Запасы, ед.
	120 7	40 8	1	2	160/40/0
	4	10 5	130 9	8	140/130/0
	9	2	70 3	100 6	170/100/0
	0	0	0	10 0	10/0
Потребность, ед.	120/0	50/10/0	200/70/0	110/10/0	480=480

Соответствующая целевая функция (общие затраты на перевозку) не учитывает фиктивные перевозки, поскольку они реально не были выполнены

F [руб.].

6. Решение транспортной задачи методом потенциалов

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

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

Для получения первоначального исходного плана перевозок используем правило «северо-западного» угла (таблица 2.13). При этом количество занятых клеток должно составить:

m + n – 1 = 2 + 3 – 1 = 4 ,

где m – количество поставщиков;

n – количество потребителей.

х₁₁ = 1000 т х₂₂ = 400 т

х₁₂ = 800 т х₂₃ = 2200 т

F (x) = 2*1000 + 2*800 + 4*400 + 2*2200 = 9600 т. р

Таблица 2.13

Первоначальный опорный план задачи

Склады	магазины			Запас Qi
	№1	№2	№3
I	2 1 000	2 8 00	3	1800
II	3	4 400	2 2200	2600
Спрос bj	1000	1200	2200	4400=4400

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

1. Исследуется план на оптимальность следующим образом:

По каждой строке и столбцу определяют потенциалы по формуле:

Для занятых клеток (1.1) (1.2) (2.2) (2.3)

V_j + U_i = C_ij (2.13)

V_j – потенциал столбца

U_i – потенциал строки

C_ij – тариф (показатель) занятой клетки

1.1) V₁ + U₁ = 2 V₁ = 2 U₁ = 0

1.2) V₂ + U₁ = 2 V₂ = 2

2.2) V₂ + U₂ = 4 U₂ = 2

2.3) V₃ + U₂ = 2 V₃ = 0

Для свободных клеток (1.3) (2.1) определяется характеристика

d_ij= C_ij — (V_j + U_i) (2.14)

d_ij – характеристика свободной клетки;

V_j – потенциал столбца;

U_i – потенциал строки;

C_ij – тариф свободной клетки.

При решении задачи на min целевой функции d_ij  0

1.3) d_1.3= 3 — (V₃ + U₁) = 3 — (0 — 0) = + 3

2.1) d_2.1= 3 — (V₁ + U₂) = 3 — (2 + 2) = — 1

т.к. d_2.1 = — 1, следовательно, план в табл. 2.13 не оптимальный улучшаем его путем сдвига по циклу (табл. 2.14).

4) План улучшается за счет клетки с отрицательной характеристикой 2.1)

Для этого в цикле кл. 2.1 просматривают объемы в отрицательных вершинах (1000 и 400) и выбирают наименьший (400), производят сдвиг по циклу. Этот наименьший объем прибавляют к объемам в положительных вершинах, а от объемов в отрицательных вершинах вычитают, т.е. получим новый план (табл. 2.15).

Таблица 2.14

План задачи после первой итерации

Склады	магазины			Запас Qi
	№1	№2	№3
I	2 1 000 —	2 + 800	3	1800	i = 1
II	+ 3	— 4 400	2 2200	2600	i = 2
Спрос bj	1000	1200	2200	4400
	j = 1	j = 2	j = 3

Таблица 2.15

План задачи после второй итерации

Склады	магазины			Запас, Qi
	№1	№2	№3
I	2 600	2 1200	3	1800
II	3 400 +	4	2 2200	2600
Спрос, bj	1000	1200	2200	4400

х₁₁ = 600 т х₂₂ = 400 т

х₁₂ = 1200 т х₂₃ = 2200 т

F (x) = 2*600 + 2*1200 + 3*400 + 2*2200 = 9600 тыс. руб.

Потенциалы занятых клеток:

1.1) V₁ + U₁ = 2 V₁ = 2 U₁ = 0

1.2) V₂ + U₁ = 2 V₂ = 2

2.2) V₁ + U₂ = 3 U₂ = 1

2.3) V₃ + U₂ = 2 V₃ = 1

Характеристики свободных клеток:

d_1.3= 3 — (V₃ + U₁) = 3 — (1 — 0) = + 2

d_2.2= 4 — (V₂ + U₂) = 4 — (2 + 1) = + 1

т.к. dij  0, то план в таблице 2.15 оптимальный.

Анализ оптимального плана:

Груз с I склада 1800 т будет доставлен в количестве 600 т в магазин 1 и 1200 т в магазин 2. Со II склада 2600 т будут доставлены в магазин 1 в количестве 400 т и в магазин 3 - 2200 т. Затраты на перевозку составят 9200 тыс. руб.