Решение транспортной задачи методом потенциалов
Автор: логистика вшэ • Апрель 30, 2018 • Задача • 1,212 Слов (5 Страниц) • 796 Просмотры
Решение транспортной задачи методом потенциалов
ЗАДАНИЕ.
В таблице приведены исходные данные транспортной задачи: заданы удельные транспортные расходы на перевозку единицы груза, слева указаны возможности поставщиков, а сверху – спрос потребителей. Сформулируйте экономико-математическую модель транспортной задачи, распределительным методом найдите оптимальный план перевозок.
[pic 1]
[pic 2] [pic 3] Поставщики [pic 4] [pic 5] | Возможные поставщики | [pic 6] Потребители и их спрос | ||||
I | [pic 7] [pic 8] II [pic 9] [pic 10] | III | [pic 11] [pic 12] IV [pic 13] [pic 14] | V | ||
150 | 350 | 200 | 100 | 100 | ||
I | 500 | 3 | [pic 15] 3 | 5 | [pic 16] 3 | [pic 17] 1 |
II [pic 18] | 300 | 4 | 3 [pic 19] [pic 20] | 2 | 4 [pic 21] [pic 22] | 5 |
III | 100 | 3 | 7 [pic 23] | 5 | 4 [pic 24] | 2 [pic 25] |
РЕШЕНИЕ.
Составим математическую модель транспортной задачи и проверим
задачу на замкнутость. Введем обозначения: xij – количество поставщиков, перевозимых из i- го пункта к j-му потребителю (i =1:m, j =1:n, в нашей задаче m=3, n=5); ai – возможности поставщиков (a1=500, a2=300, a3=100); bj – спрос потребителей (b1=150, b2=350, b3=200, b4=100, b5 = 100 );
cij – стоимости перевозок из пункта i в пункт j mn
размещения. Целевая функция L = ∑∑cij xij .
В нашей задаче i=1 j=1
35 L = ∑∑c x ⇒ min.
ij ij i=1 j=1
Проверим условие того, что данная модель задачи закрытая: 150+350+200+100+100=900 и 500+300+100=900.
Строим начальный опорный план перевозок методом минимальной стоимости. Начинаем с клетки (1,4) – стоимость наименьшая, ставим перевозку x14 =100 максимальную из возможных. Потребителю b4 в клетку (1,4) также ставим максимальную перевозку из возможных x14 =100 единиц груза. 200 единиц груза отправим потребителю a3 и 100 единиц груза потребителю a2 . После этого запасы поставщика a1 полностью израсходованы. Но потребитель b2 нуждается ещё в 250 единицах груза. Удовлетворим его за счёт запасов поставщика a2 , ставим в клетку (2,2) перевозку 250 единиц груза. Но в запасе у поставщика
a2 осталось 50 единиц груза, удовлетворим ими потребителя b1 . Запасы 1 поставщика a2 исчерпались. Но потребитель b1 нуждается в 100 единицах груза, удовлетворим его за счёт запасов поставщика a3 .
Итак, все запасы поставщиков распределены, все потребители удовлетворены. В результате заполним таблицу 1.
Количество базисных клеток m+n−1=3+5−1=7 - совпадает с полученным. Следовательно, план не вырожден.
Таблица 1
[pic 26]
150 | 350 | [pic 27] 200 [pic 28] | [pic 29] 100 [pic 30] | [pic 31] 100 [pic 32] | [pic 33] Ui [pic 34] | |
500 | 3 | (+) 3 100 | (-) 5 200 | 3 100 | 1 100 | 0 |
300 | 4 50 | (-) 3 250 | [pic 35] (+) 2 [pic 36] | [pic 37] 4 [pic 38] | [pic 39] 5 [pic 40] | [pic 41] 0 [pic 42] |
100 | 3 100 | 7 | 5 | 4 | 2 | -1 |
Vj | 4 | 3 | 5 [pic 43] | 3 [pic 44] | 1 [pic 45] | [pic 46] |
Найдём стоимость перевозок на X1 - плане перевозок из таблицы 1: Z1 =100⋅3+200⋅5+100⋅3+50⋅4+250⋅3+100⋅3=2850 ден.ед.
...