Грузовые перевозки (стр. 3 из 14)

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

Транспортная задача является одной из важнейших частных задач линейного программирования. Ее сущность состоит в следующем. В пунктах отправления 22, 17, 10 имеется однородный груз (щебень), причем объем имеющегося в пункте 22 составляет 450 тыс. т., в пункте 17 составляет 400 тыс. т., в пункте 10 составляет 350 тыс. т. Этот груз надо доставить в пункты потребления 06, 58, 62, 20, 84, 95. Задача заключается в построении такого плана перевозок, при котором потребность в грузе всех пунктов потребления будет удовлетворена, весь груз из пунктов отправления будет вывезен и при этом будет обеспечен минимум транспортной работы в тонно-километрах, что соответствует достижению наименьшего среднего расстояния перевозок груза.

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

Условия транспортной задачи можно выразить в математической форме, т. е. построить ее экономико-математическую модель.

Для построения экономико-математической модели введем следующие обозначения:

i – номер поставщика (i =1, 2, 3);

А_i – ресурсы i-го поставщика (i =1, 2, 3), т.е. количество продукции, которое поставщик может отправить потребителям;

j – номер потребителя (j =1, 2, 3, 4, 5, 6);

B_j- потребность j-го потребителя;

L_ij – расстояния между соответствующими пунктами отправлениями и получения;

Q_ij – количество продукции, поставляемое от i-го поставщика j-му потребителю.

Таким образом, экономико-математическую модель оптимального прикрепления потребителей к поставщикам имеет вид:

Объем транспортной работы должен быть минимальным

Q_ij ∙ L_ij = min

при условиях

Q_ij = А_i (i =1, 2, 3), Q_ij = B_j (j =1, 2, 3, 4, 5, 6), A_i = B_j

Q_ij ≥ 0, d_ij = L_ij - U_ij - V_ij ≥ 0

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

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

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

Таблица 2.1 – Первоначальный (опорный) план закрепления потребителей за

поставщиками

Поставщики		Потребители						Вывоз от поставщика, тыс. т.
		06	58	62	20	84	95
		V06=50	V58=80	V62=55	V20=20	V84=125	V95=100
22	U22=0

50

75

55

*250

20

*150

80

* ^-45

95

*

450

17

U17=-35

15

**100

45

* 200

100

85

90

100

105

400

10

U10=5

65

115

60

100

10

**

90

105

* 250

350

Завоз потребителям, тыс. т.

150

200

350

150

100

250

1200

Подсчитаем для опорного плана значение грузооборота:

Р=∑(Qij · ℓij), (2.1)

где i,j – текущий индекс соответственно поставщика и потребителя;

Р – грузооборот, ткм;

Qij – объем перевозок между i-ым поставщиком и j-ым потребителем, т;

ℓij – расстояние между i-ым поставщиком и j-ым потребителем, км.

Р = 50·50 + 250·55 + 150·20 + 100·15 + 200·45 + 100·90 +100·60+250·105 = 68500 ткм

Для проверки на оптимальность по методу МОДИ определим вспомогательные величины ui (для строк) и vj (для столбцов), называемые потенциалами. Для этого потенциал одного из поставщиков (например, 22) примем равным 0. Тогда все оставшиеся потенциалы определим по формуле (2):

dij = ℓij - ui - vj. (2.2)

Учитывая, что в загруженных клетках dij = 0, определим потенциалы строк и столбцов для табл. 2.1. В строке 22 загруженные клетки - 22-98, 22-20. Отсюда потенциал столбца 06 равен:

U₂₂ = 0;

V₀₆ = 50 – 0 = 50;

Потенциал столбца 62 равен:

U₂₂ = 0;

V₆₂ = 55 – 0 = 55;

Потенциал столбца 20 равен:

U₂₂ = 0;

V₂₀ = 20 – 0 = 20;

Далее по загруженной клетке 17-06 определим потенциал строки 17:

U₁₇= 15 – 50 = - 35;

по загруженной клетке 17-58 определим потенциал столбца 58:

v₅₈ = 45 – (-35) = 80;

по загруженной клетке 17-84 определим потенциал столбца 84:

v₈₄= 90 – (-35) = 125;

по загруженной клетке 10-62 определим потенциал строки 10:

U₁₀ = 60 – 55 = 5;

по загруженной клетке 17-95 определим потенциал столбца 95:

v₉₅ = 105 – 5 = 100;

Теперь рассчитаем значение параметра dij для всех свободных клеток:

d_22-58 = 75 – 0 – 80 = -5;

d_22-84 = 80 – 0 – 125 = -45

d_22-95 = 95 – 0 – 100 = -5;

d_17-62 = 100 –(-35) – 55 = 80;

d_17-20 = 85 – (-35) – 20 = 100;

d_17-95 = 105 – (-35) – 100 = 40;

d_10-06 = 65 – 5 – 50 = 10;

d_10-58 = 115 – 5 – 80 = 30;

d_10-20 = 10 – 5 – 20 = -15;

d_10-84 = 90 – 5 – 125 = -40.

В клетке 22-84 величина dij принимает значение меньше 0. Значит, этот план не оптимален. Перемещение загрузки в клетку с минимальным значением уменьшит значение грузооборота.

Для перемещения загрузки необходимо составить специальный контур, все вершины которого лежат в загруженных клетках, кроме одной, в которой dij ‹ 0 (в таблице 2.1 показан жирной линией).

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

Таблица 2.2 – Оптимальный план закрепления потребителей за поставщиками

Поставщики		Потребители						Вывоз от поставщика, тыс. т.
		06	58	62	20	84	95
		V06=5	V58=35	V62=55	V20=5	V84=80	V95= 95
22	U22=0