Определение оптимального плана перевозок (стр. 1 из 2)

ЛАБОРАТОРНАЯ РАБОТА

ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ПЛАНА ПЕРЕВОЗОК

(ТРАНСПОРТНАЯ ЗАДАЧА)

Цель работы

1. Познакомиться с общей постановкой транспортной задачи.

2. Решить задачу методом северо-западного угла

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

4. Дать анализ результатов расчетов

Постановка транспортной задачи

Пусть в пунктах А₁, А₂,…,А_mпроизводится некоторая однородная продукция. Таким образом, имеется mпоставщиков А_i, где

=
. Объем производства в пункте А_iсоставляет a_i единиц. Величину a_iназывают мощностью поставщика, а

- суммарной мощностью всех поставщиков. Допустим, что выпускаемая продукция потребляется в пунктах В₁, В₂, …, В_n, причем в пункте В_j, составляет b_jединиц продукции. Величина b_j называется емкостью (спросом) потребителя В_j , где

. Общий объем потребления (суммарная емкость) составляет

В практике встречаются два типа транспортных задач.

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

Такой тип задач называется закрытыми транспортными задачами.

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

Такой тип задач называется закрытыми транспортными задачами.

Рассмотрим принцип решения закрытой транспортной задачи (1 тип).

При этом предполагается:

- от каждого поставщика возможна перевозка к любому потребителю;

- стоимость перевозки единицы продукции от поставщика А_i к потребителю В_j известна и составляет C_ijденежных единиц. ( В некоторых случаях вместо стоимости перевозки может быть указано расстояние от А_i до В_j .)

Условия задачи могут быть записаны в виде таблицы 1.

Таблица 1.

Поставщики	Запасы сырья (мощность)	Потребители и их спрос
		В₁	В₂	*. . .*	*В_j*	*. . .*	В_n
		b₁	b₂	*. . .*	*b_j*	*. . .*	*b_n*
А₁	а₁	*C₁₁*	*C₁₂*	*. . .*	*C_1j*	*. . .*	*C_1n*
А₂	а₂	*C₂₁*	*C₂₂*	*. . .*	*C_2j*	*. . .*	*C_2n*
*. . .*	*. . .*	*. . .*	*. . .*	*. . .*	*. . .*	*. . .*	*. . .*
А_i	*a_i*	*C_i1*	*C_i2*	*. . .*	*C_ij*	*. . .*	*C_in*
*. . .*	*. . .*	*. . .*	*. . .*	*. . .*	*. . .*	*. . .*	*. . .*
А_m	*a_m*	*C_m1*	*C_m2*	*. . .*	*C_mj*	*. . .*	*C_mn*

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

Пусть объем перевозок из пункта А_i в пункт В_j ( от i– го поставщика к j– му потребителю) будет равен Х_ij. Тогда целевая функция будет равна

(1)

В то же время должны выполняться условия (ограничения):

, i=
; (2)

, j=
; (3)

; (4)

X_ij

0, i=
, j=
. (5)

В равенствах (2) и (3) имеется m+n уравнений с mn неизвестными, причем одно из них есть следствие других в силу того, что

. Следовательно, в равенствах (2) и (3) будет m+n-1 линейно независимых уравнений и каждая программа (план0 перевозок должна содержать не более чем m+n-1 положительных перевозок.

Принимаем условие, что клетки табл. 1. в которых объем перевозок Х_ij не равен нулю, называть базисными, а в которых Х_ij=0 – свободными. Элементы таблицы перевозок C_ij называть показателями критерия оптимальности, а совокупность C_ijХ_ij – планом перевозок.

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

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

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

Рассмотрим применение метода потенциалов на конкретном производственном примере составления оптимального плана перевозок. Пусть имеется три оптовых базы, которые поставляют сырье для пяти производственных предприятий. Условия задачи представлены в табл.2. Себестоимость перевозки сырья представлена в условных единицах.

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

Таблица 2.

Руководствуясь здравым смыслом, прикрепим поставщиков к потребителям следующим образом.

Таблица 3.

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

Стоимость транспортных работ:

Z=22

4+38

1+7

3+20

2+8

2+10

4+30

4=363 у.е.

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

При перераспределении поставок составляются цепи, для которых характерны следующие особенности:

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

2. вершинами цепи являются клетки таблицы, причем одна из вершин –свободная, а все остальные базисные;

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

4. цепь всегда имеет четное число вершин;

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

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

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

Пусть А₂ будет поставлять 1 т сырья в пункт В₁ , тогда необходимо уменьшить поставки на 1 т из А₁в В₁ и из А₂ в В₂ и увеличить из А₁ в В₂ , чтобы выполнялось условие равенства запаса сырья в базах и спроса предприятий. Уменьшая или увеличивая поставки, тем самым уменьшаем или увеличиваем значение целевой функции Z. Цепь дает возможность установить, насколько изменится стоимость транспортировки при записи поставки в 1 т , в ту клетку цепи, которая была свободной.