4.2 Метод потенциалов решения транспортной задачи

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

Задача 4.1. Три предприятияA₁,A_2, A₃производят однотипную продукцию в количествах соответственно 30, 60, 10 единиц. Спрос на данный вид продукции у потребителейB₁, B₂, B₃, В₄ составляет 15, 40, 25, 20 единиц. Заданные удельные издержки транспортировки груза от каждого предприятия каждому потребителю расположены в правых верхних углах клеток таблицы 4.2.

Определить план перевозок, при котором суммарная стоимость доставки грузов будет минимальна.

Таблица 4.2 – Исходные данные транспортной задачи

Предприятия	Потребители
	b1 = 15	b2 = 40	b3 = 25	b4 = 20
A1 а1 = 30	7	3	6	4
A2 а2 = 60	2	5	3	9
A3 а3=10	8	1	7	3

РЕШЕНИЕ.

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

Задача замкнутая, так как выполняется условие

= 100.

Если в какой-либо задаче условие (4.5) не выполняется (открытая модель транспортной задачи), в транспортную таблицу вводится столбец фиктивного потребителя (при ) или строка фиктивного поставщика (при). В фиктивной строке или столбцеc_ijназначаются, равныминулю. Спрос фиктивного потребителя равен. Запас продукции у фиктивного поставщика:. Наличие фиктивного поставщика интерпретируется как ввоз недостающего количества продукта извне пределов рассматриваемого района. Фиктивный потребитель – вывоз излишков продукта за пределы данного района.

2 М а т е м а т и ч е с к а я м о д е л ь з а д а ч и

Суммарная стоимость перевозок:

.

Балансовые условия:

;

;

;

;

;

;

;

.

3 С о с т а в л е н и е о п о р н о г о п л а н а

Для построения опорного решения можно использовать следующие методы: северо-западного угла, аппроксимации, минимального элемента и др.

Мы рассмотрим один из наиболее простых и эффективных методов – метод минимального элемента.

Суть метода заключается в том, что из таблицы удельных затрат на перевозки выбирают наименьшую стоимость, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i или b_j. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо строку и столбец одновременно (если a_i = b_j). Из оставшейся части таблицы вновь выбирают клетку с наименьшей стоимостью. Процесс заполнения транспортной таблицы (4.2) продолжают до тех пор, пока все запасы продукции на предприятиях не будут распределены и удовлетворен спрос потребителей, т.е. пока не будут выполнены балансовые условия (4.2), (4.3).

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

Таблица 4.3 – Опорный план транспортной задачи

Предприятия	Потребители
	b1 = 15	b2 = 40	b3 = 25	b4 = 20
A1 а1 = 30	7	3 30	6	4
A2 а2 = 60	2 15	5 10	3 25	9 10
A3 а3=10	8	1	7	3 10

4 П р о в е р к а о п о р н о г о п л а н а н а н е в ы р о ж д е н н о с т ь

Опорный план называется невырожденным, если количество занятых клеток в транспортной таблице (таблица 4.3) равноm+n-1.

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

Опорный план, составленный нами в таблице 4.3 – невырожденный, так как число занятых клеток равно

.

5 Проверк а оптималности плана методом потенциалов

Для отыскания оптимального плана используем метод потенциалов.

Теорема. Если план транспортной задачи является оптимальным, то ему соответствует система изm+n чисел u_i и v_j, удовлетворяющих условиям:

u_i + v_j = с_{i j} для ,

u_i + v_j с_{i j} для

(i= 1,2,…., m; j = 1,2,…, n).