Записать транспортную задачу в распределительную таблицу. Найти оптимальные планы перевозки однородного груза от поставщиков к потребителям, обеспечивающие минимальные транспортные расходы.
Индивидуальные данные.
1. Получить исходное опорное решение методами: или “северо-западного” угла, или наименьшего элемента в строке, в столбце, в таблице. Подсчитать значение целевой функции при полученном исходном опорном решении.
2. Получить оптимальное решение методом потенциалов, улучшая исходное опорное решение, полученное в п.1.
Таблица транспортных расходов на перевозку единицы однородного груза, ресурсы поставщиков и потребности потребителей:
Поставщики Ресурсы Потребители
а в г д
Потребности
50 70 80 50
Б 150 2 8 3 7
В 50 7 9 10 8
Д 50 6 2 3 4
Решение
Согласно условию нашей транспортной задачи имеем следующую распределительную таблицу:
Bj B1 B2 B3 B4
Ai
b1=50 b2=70 b3=80 b4=50
A1 a1=150
2
8
3
7
A2 a2=50
7
9
10
8
A3 a3=50
6
2
3
4
Имеется m = 3 поставщика A1, A2, A3 с ресурсами груза a1 = 150, a2 = 50, a3 = 50 и n = 4 потребителя B1, B2, B3, B4 с потребностями в этом грузе b1 = 50, b2 = 70, b3 = 80, b4 = 50. Известны стоимости перевозки единицы однородного груза cij от поставщиков Ai к потребителям Bj. Требуется так спланировать объемы перевозок xij от поставщиков Ai к потребителям Bj, чтобы транспортные расходы были бы минимальными.
Выполняем построение математической модели нашей задачи.
В общем случае условие разрешимости транспортной задачи состоит в том, что суммарные ресурсы поставщиков должны равняться суммарной потребности потребителей i=1mai = j=1nbj, то есть транспортная задача должна быть сбалансированной.
Согласно условию нашей задачи имеем:
m = 3; n = 4;
i=1mai = a1 + a2 + a3 = 150 + 50 + 50 = 250;
j=1nbj = b1 + b2 + b3 + b4 = 50 + 70 + 80 + 50 = 250.
Условие разрешимости транспортной задачи выполнено.
Таким образом, математическая модель нашей транспортной задачи имеет следующий вид:
W(X) = i=13j=14cij·xij min;
x11 + x12 + x13 + x14 = a1;
x21 + x22 + x23 + x24 = a2;
x31 + x32 + x33 + x34 = a3;
x11 + x21 + x31 = b1;
x12 + x22 + x32 = b2;
x13 + x23 + x33 = b3;
x14 + x24 + x34 = b4;
xij ≥ 0; i = 1,…,3; j = 1,…,4.
Строим исходное опорное решение методом наименьшего элемента.
В соответствии с этим методом перевозки распределяются в первую очередь в те клетки распределительной таблицы, которые имеют наименьшую стоимость
. Если же наименьшие стоимости совпадают, то клетку можно выбрать произвольно. Объем перевозки, вносимый в клетку, определяется как минимальное значение среди значений запаса и потребности xij = min(ai, bj). При этом исключается или только строка, или только столбец. Соответственно, или в столбце, или в строке образуется остаток (возможно, даже нулевой), который распределяется на последующих шагах процесса распределения на общих основаниях.
а). Наименьший элемент 2 в клетках (1, 1) и (3, 2). Выбираем произвольно и назначаем x11 = 50. Столбец B1 исключаем. Остаток a1 = 100.
б). Наименьший элемент 2 в клетке (3, 2). Назначаем x32 = 50. Строку A3 исключаем. Остаток b2 = 20.
в). Наименьший элемент 3 в клетке (1, 3). Назначаем x13 = 80. Столбец B3 исключаем. Остаток a1 = 20.
г). Наименьший элемент 7 в клетке (1, 4). Назначаем остаток x14 = 20. Строку A1 исключаем. Остаток b4 = 30.
д). Заполняем оставшиеся незаполненными x22 = 20 и x24 = 30.
Все перевозки распределены.
Исходное опорное решение X(0) нашей транспортной задачи имеет вид:
X(0) Bj B1 B2 B3 B4
Ai
b1=50 b2=70 b3=80 b4=50
A1 a1=150
2
8
3
7
50
80
20
A2 a2=50
7
9
10
8
20
30
A3 a3=50
6
2
3
4
50
Исходное опорное решение содержит 6 занятых клеток, что совпадает с m + n – 1 = 3 + 4 – 1 = 6. Следовательно, исходное опорное решение – невырожденное.
Подсчитываем значение целевой функции (стоимость полученных перевозок) при полученном исходном опорном решении:
W(X(0)) = 2·50 + 3·80 + 7·20 + 9·20 + 8·30 + 2·50 = 1000.
Применяем метод потенциалов, чтобы проверить, является ли исходное опорное решение оптимальным, а в случае неоптимальности – определить путь его улучшения
Задать вопрос
на новый заказ в Автор24.
