4 Транспортная задача линейного

ПРОГРАММИРОВАНИЯ

4.1 Математическая постановка транспортной задачи

Транспортная задача является задачей линейного программирования; для её решения применяется не симплекс-метод, а более простые методы.

Транспортная задача формулируется следующим образом. Имеется mпунктов производства (отправления)A_iнекоторого однородного продукта в количествеa_i(i = 1,2,…, m) единиц соответственно. Груз необходимо доставитьn потребителямB_jв количествеb_j(j=1,2,…, n) единиц. Известнытранспортные издержкиc_ijна перевозкуединицыгруза отi-го поставщика кj-му потребителю. В различных задачах в роли транспортных издержек могут выступать расстояние, время и т.д.

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

Исходные данные транспортной задачи удобно представлять в виде таблицы:

Таблица 4.1 – Структура транспортной таблицы

B A	B1 b1	B2 b2	…	Bn bn
A1 a1	c11 x11	c12 x12	…	c1n x1n
A2 a2	c21 x21	c22 x22	…	c2n x2n
…	…	…	…	…
Am am	cm1 xm1	cm2 xm2	…	cmn xmn

Здесь – количество единиц груза, запланированных к перевозке от

i-го поставщика к j-му потребителю.

Целевая функция имеет смысл суммарных транспортных издержек

(4.1)

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

1. Весь продукт из каждого пункта производства должен быть полностью вывезен:

. (4.2)

2. Спрос каждого потребителя должен быть удовлетворен

. (4.3)

3. Объемы перевозок должны быть неотрицательными

. (4.4)

Уравнения (4.2), (4.3) получаются соответственно из строк и столбцов транспортной таблицы 4.1.

Математическая модель (4.1)-(4.4) построена в предположении, что суммарный объем производства продукта равен суммарной потребности в нем:

. (4.5)

Такая модель называется замкнутой.

Транспортная задача содержит m·nнеизвестных . Клетки таблицы 4.1, в которых находятся отличные от нуля перевозки , называют занятыми, остальные – незанятыми.

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).