На трех базах A1, A2, A3 имеется однородный груз в количестве: a1 = 280 т – на базе A1, a2 = 300 т – на базе A2, a3 = 220 т – на базе A3. Полученный груз требуется перевезти в пять пунктов: b1 = 170 т – в пункт B1, b2 = 120 т – в пункт B2, b3 = 190 т – в пункт B3, b4 = 140 т – в пункт B4, b5 = 180 т – в пункт B5.
Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов C:
C11 = 28 C12 = 12 C13 = 7 C14 = 18 C15 = 7
C = C21 = 35 C22 = 14 C23 = 12 C24 = 15 C25 = 3 .
C31 = 30 C32 = 16 C33 = 11 C34 = 25 C35 = 15
где Cij – стоимость перевозки 1 т груза от поставщика под номером i (i = 1,2,3) к потребителю под номером j (j = 1,2,3,4,5), в тыс. руб.
Составить математическую модель задачи. Спланировать перевозки так, чтобы их общая стоимость была минимальной. При нахождении оптимального плана использовать метод потенциалов.
Решение
1). Составление математической модели задачи.
Используем следующие обозначения: xij – объемы перевозок груза (тонн) между поставщиками Ai (i = 1,…,m) и потребителями Bj; (j = 1,…,n), где m и n – количество поставщиков и потребителей соответственно.
Исходные данные задачи представляем в виде распределительной таблицы:
Потребители B1 B2 B3 B4 B5
Поставщики
b1=170 b2=120 b3=190 b4=140 b5=180
A1 a1=280
28
12
7
18
7
x11
x12
x13
x14
x15
A2 a2=300
35
14
12
15
3
x21
x22
x23
x24
x25
A3 a3=220
30
16
11
25
15
x31
x32
x33
x34
x35
В общем случае условие разрешимости транспортной задачи состоит в том, что сумма запасов поставщиков в пунктах отправления должна быть равна суммарной потребности потребителей в пунктах назначения i=1mai = j=1nbj, то есть транспортная задача должна быть закрытой.
Согласно условию нашей задачи имеем:
m = 3; n = 5;
i=1mai = a1 + a2 + a3 = 280 + 300 + 220 = 800 тонн;
j=1nbj = b1 + b2 + b3 + b4 + b5 = 170 + 120 + 190 + 140 + 180 = 800 тонн.
Таким образом, условие разрешимости транспортной задачи выполнено.
В этом случае экономико-математическая модель транспортной задачи в сжатой форме записи имеет следующий вид:
найти совокупность неотрицательных значений переменных xij ≥ 0, минимизирующих целевую функцию Z(X) = i=1mj=1nCij·xij min при ограничениях по запасам поставщиков j=1nxij = ai, i = 1,…,m и потребностям потребителей i=1mxij = bj, j = 1,…,n.
Экономико-математическая модель транспортной задачи в развернутой форме записи имеет следующий вид:
найти совокупность неотрицательных значений переменных xij ≥ 0 (i = 1,2,3; j = 1,2,3,4,5), минимизирующих целевую функцию
Z(X) = 28·x11 + 12·x12 + 7·x13 + 18·x14 + 7·x15 +
+ 35·x21 + 14·x22 + 12·x23 + 15·x24 + 3·x25 +
+ 30·x31 + 16·x32 + 11·x33 + 25·x34 + 15·x35 min
при ограничениях по запасам поставщиков
x11 + x12 + x13 + x14 + x15 = 280; x21 + x22 + x23 + x24 + x25 = 300;
x31 + x32 + x33 + x34 + x35 = 220
и по потребностям потребителей
x11 + x21 + x31 = 170; x12 + x22 + x32 = 120; x13 + x23 + x33 = 190;
x14 + x24 + x34 = 140; x15 + x25 + x35 = 180.
2). Построение начального опорного решения методом минимального элемента.
В соответствии с этим методом перевозки распределяются в первую очередь в те клетки распределительной таблицы, которые имеют минимальный тариф. Если же минимальные тарифы совпадают, то клетку можно выбрать произвольно
. Объем перевозки, вносимый в клетку, определяется как минимальное значение среди значений запаса и потребности xij = min(ai, bj). При этом исключается или только строка, или только столбец. Соответственно, или в столбце, или в строке образуется остаток (возможно, даже нулевой), который распределяется на последующих шагах процесса распределения на общих основаниях.
а). Минимальный элемент 3 в клетке (2, 5). Назначаем x25 = 180. Столбец B5 исключаем. Остаток a2 = 120.
б). Минимальный элемент 7 в клетке (1, 3). Назначаем x13 = 190. Столбец B3 исключаем. Остаток a1 = 90.
в). Минимальный элемент 12 в клетке (1, 2). Назначаем остаток x12 = 90. Строку A1 исключаем. Остаток b2 = 30.
г). Минимальный элемент 14 в клетке (2, 2). Назначаем остаток x22 = 30. Столбец B2 исключаем. Остаток a2 = 90.
д). Минимальный элемент 15 в клетке (2, 4). Назначаем остаток x24 = 90. Строку A2 исключаем. Остаток b4 = 50.
е). Заполняем оставшиеся незаполненными x31 = 170 и x34 = 50.
Все перевозки распределены.
Начальный опорный план X(0) нашей транспортной задачи, полученный по методу минимального элемента, имеет вид:
X(0) Потребители B1 B2 B3 B4 B5
Поставщики
b1=170 b2=120 b3=190 b4=140 b5=180
A1 a1=280
28
12
7
18
7
90
190
A2 a2=300
35
14
12
15
3
30
90
180
A3 a3=220
30
16
11
25
15
170
50
Начальный опорный план содержит m + n – 1 = 3 + 5 – 1 = 7 занятых клеток, следовательно, опорный план – невырожденный.
Стоимость полученных перевозок по заполненным клеткам:
Z(X(0)) = 12·90+7·190+14·30+15·90+3·180+30·170+25·50 = 11070.
3). Применение метода потанциалов.
Метод потенциалов позволяет проверить, является ли опорный план оптимальным. При этом для каждого из пунктов отправления и назначения определяются потенциалы ui и vj (i = 1,2,3; j = 1,2,3,4,5) соответственно.
Опорний план является оптимальным, если:
1) для каждой заполненной клетки таблицы выполняется условие ui + vj = cij, где cij – тарифы, соответствующие заполненным клеткам;
2) для каждой незаполненной клетки таблицы выполняется условие ui + vj – cij ≤ 0.
Определяем потенциалы ui и vj для начального опорного плана X(0).
Шаг 1). Положим u1 = 0.
Шаг 2). Для заполненной клетки (1, 2); v2 = c12 – u1 = 12 – 0 = 12.
Шаг 3). Для заполненной клетки (1, 3); v3 = c13 – u1 = 7 – 0 = 7.
Шаг 4). Для заполненной клетки (2, 2); u2 = c22 – v2 = 14 – 12 = 2.
Шаг 5). Для заполненной клетки (2, 4); v4 = c24 – u2 = 15 – 2 = 13.
Шаг 6). Для заполненной клетки (2, 5); v5 = c25 – u2 = 3 – 2 = 1.
Шаг 7). Для заполненной клетки (3, 4); u3 = c34 – v4 = 25 – 13 = 12.
Шаг 8). Для заполненной клетки (3, 1); v1 = c31 – u3 = 30 – 12 = 18.
Найденные потенциалы заносим в таблицу (в скобках указан номер шага их вычисления)
Задать вопрос
на новый заказ в Автор24.
