Пусть необходимо перевезти некоторый однородный груз от нескольких поставщиков нескольким потребителям.
Поставщики: А1, А2, …,Аm
Их запасы: а 1, а 2, …, а m.
Потребители: В1, В2, …,Вn
Их потребности: b 1, b 2, …, b n.
Известны тарифы перевозок c ij – это стоимость перевозки 1 единицы груза от каждого поставщика Аi каждому потребителю Вj: i= 1, 2, …, m; j= 1, 2, …, n.
Обозначим поставки x ij– это количество груза, перевозимое от поставщика Аiпотребителю Вj. Очевидно, что соблюдается условие не отрицательности: x ij ≥ 0.
Общая стоимость всех перевозок Z = c11* x 11 + c12* x 12 + … + cmn* x mn. Нужно найти план перевозок { x ij}, который обеспечит минимальные общие затраты на перевозки: Z " min.
Пусть суммарные запасы поставщиковравны суммарным потребностям потребителей∑ а i = ∑ b j. В этом случае транспортная задача называется закрытой. Транспортная задача называется открытой, если нарушено условие баланса между суммарными запасами груза и суммарными потребностями, то есть ∑ а i≠∑ b j. Открытую транспортную задачу всегда легко привести к закрытой задаче путём введения фиктивного поставщика или фиктивного потребителя с недостающим количеством груза и нулевыми тарифами.
В случае, когда транспортная задача закрытая весь груз от поставщиков будет вывезен и все потребители удовлетворены.
Данные задачи и её решение удобно располагать в таблице перевозок.
Задача 31–40. Три склада обслуживают пять магазинов одинаковым товаром. Первый склад располагает a 1, второй a 2, третий a 3 единицами товара. Каждому из пяти магазинов требуется по плану соответственно b 1, b 2, b 3, b 4, b 5 единиц товара. Известны тарифы всех перевозок, заданные матрицей тарифов С.
1) Установить, является ли данная транспортная задача закрытой.
|
|
2) Составить план перевозок по методу минимального тарифа и проверить является ли он опорным.
2) Найти общую стоимость перевозок для этого плана.
3) Проверить является ли составленный план оптимальным, пользуясь методом потенциалов.
4) Составить математическую модель для данной транспортной задачи.
a 1 =110, a 2 =190, a 3 =160;
b 1 =120, b 2 = 100, b 3 =80, b 4 =70, b 5 =90.
С = 
Решение
1) Найдём суммарные запасы груза у всех поставщиков:
a 1 + a 2 + a 3 =110 + 190 + 160 = 460.
Найдём суммарные потребности в грузе для всех потребителей:
b 1 + b 2 + b 3 + b 4 + b 5 =120 + 100 + 80 + 70 + 90 = 460.
Так как суммарные запасы равны суммарным потребностям, то данная транспортная задача является закрытой.
2) Составим таблицу перевозок:
| Потр. Пост. | B1 | B2 | B3 | B4 | B5 | Запасы |
| A1 | ||||||
| A2 | ||||||
| A3 | ||||||
| Потребн. |
В углах клеток проставлены тарифы. Чтобы стоимость перевозок была наименьшей, будем вписывать как можно большие поставки в клетки с наименьшими тарифами, то есть туда, где поставки наиболее дешёвые. При этом нужно следить за количеством имеющегося груза, как у поставщиков, так и у потребителей.
Наименьший тариф 10, он соответствует клетке А2В3. Ставим в эту клетку поставку, равную 80, т. к. потребителю В3 нужно 80 ед. груза, а у поставщика А2 он имеется. Теперь потребителю В3 больше груза не нужно, а у поставщика А2 останется груз в количестве 190 – 80 = 110 ед.
Следующий наименьший по величине тариф равен 12 он соответствует клеткам А2В1 и А3В3. В клетку А3В3 поставку ставить нельзя, так как потребитель В3 в грузе больше не нуждается. В клетку А2В1 самое большое можно поставить 110 ед., так как у поставщика А2 осталось 110 ед. груза, а потребителю В1 их можно завезти. Теперь от поставщика А2 весь груз будет вывезен, а потребителю В1 нужно завезти ещё 120 – 110 = 10 ед. груза.
|
|
Следующий наименьший тариф 13, соответствует клетке А2В4, в эту клетку ничего поставить нельзя, так как от поставщика А2 весь груз уже вывезен. Оставляем эту клетку пустой.
Наименьший тариф из оставшихся 15 стоит в клетке А1В3. Эту клетку также оставляем пустой, так как потребителю В3 весь груз уже завезён.
Следующий наименьший тариф 16 находится в клетке А3В4. Наибольшая поставка, которую сюда можно поставить равна 70, так как потребителю В4 больше груза не нужно, а у поставщика А3 он имеется. У этого поставщика ещё останется груз в количестве 160 – 70 = 90 ед.
Далее следует тариф 18, который находится в клетке А1В1. Самая большая поставка, которую можно поставить в эту клетку 10 ед., так как потребителю В1 осталось завезти именно такое количество груза, а у поставщика А1 он имеется и у него останется ещё 110 – 10 = 100 ед. груза.
Наименьший тариф из оставшихся 19, оннаходится в клетке А1В4. Клетку оставляем пустой, так как потребитель В4 в грузе уже не нуждается.
Остались неудовлетворёнными потребители В2 и В5. Для них самый маленький тариф 23, соответствует клетке А1В2. Сюда можно поставить 100 ед., так как потребителю В2 нужно именно такое количество груза, а у поставщика А1 осталось как раз 100 ед. груза.
Потребителю В5 требуется 90 ед. груза, именно такое количество груза осталось у поставщика А3, ставим эту поставку в клетку А3В5.
|
|
Модель закрылась. Так будет обязательно, поскольку транспортная задача закрытая: весь груз от потребителей будет вывезен и все поставщики удовлетворены.
Внимание! Студенту не нужно описывать весь этот процесс, Достаточно просто заполнить таблицу перевозок.
Проверим, является ли составленный план опорным. Опорный план должен удовлетворять трём признакам.
а) Так как весь груз вывезен и все поставщики удовлетворены, то должны соблюдаться балансы поставок по строкам и столбцам.
Строка А1: 10 + 100 = 110; Столбец В1: 10+110 = 120;
Строка А2: 110 + 80 = 190; Столбец В2: 100 = 100;
Строка А3: 70 + 90 = 160; Столбец В3: 80 = 80;
Столбец В4: 70 = 70;
Это можно делать без записи. Столбец В5: 90 = 90.
б) Количество заполненных клеток должно быть равно «m + n – 1 », где m – количество поставщиков, n – количество потребителей. В нашем случае m + n – 1 = 3 + 5 – 1 = 7, а заполненных клеток6, то есть условие не выполняется. В этом случае в одну недостающую клетку проставим нулевую поставку и будем считать эту клетку заполненной. Для заполнения нулём выбираем клетку А3В3, так как у неё наименьший тариф, и она не образует замкнутого цикла с заполненными ранее клетками.
с) Заполненные клетки или их часть не должны образовывать замкнутых циклов. Замкнутым циклом называется любой многоугольник с прямыми углами, вершины которого лежат в клетках матрицы перевозок, а стороны в столбцах или в строках этой матрицы. Не должно быть ни одного такого многоугольника, все вершины которого лежат в заполненных клетках. Клетка А3В3, которую мы заполнили нулём, этому требованию удовлетворяет.
Полученный план поставок, содержащий 7 заполненных клеток, является допустимым опорным планом.
3) Найдём общую стоимость перевозок Z для составленного плана. Так как известны тарифы перевозок, то есть стоимость перевозки 1 ед. груза, то можно для каждой заполненной клетки найти стоимость перевозки всего груза, стоящего в этой клетке, а затем просуммировать все результаты:
Z = 10*18+100*23+110*12+80*10+0*12+70*16+90*26 = 8060 руб.
4) Проверим, является ли составленный план оптимальным, то есть, имеется ли план перевозок дешевле, чем 8 060 руб. Это можно сделать по методу потенциалов, который применим только к опорным планам.
| v 1 = 18 | v 2 = 23 | v 3 = 16 | v 4 = 20 | v 5 = 30 | |||
| Пост. Потр. | B1 | B2 | B3 | B4 | B5 | Запасы | |
| u 1 = 0 | A1 | ||||||
| u 2 = 6 | A2 | ||||||
| u 3 = 4 | A3 | ||||||
| Потребн. |
Потенциалы – это вспомогательные величины, их смысл «условные цены на товар». Обозначим их для поставщиков u 1, u 2, u 3, а для потребителей v 1, v 2, v 3, v 4, v 5 и проставим их вверху и слева (можно в предыдущей таблице). Всего потенциалов m + n = 3 + 5 = 8. Если для клетки АiВj перевозка состоялась, то цена товара у потребителя Вj будет дороже чем у поставщика Аi на стоимость перевозки 1 ед. товара, то есть v j – ui = с ij для заполненных клеток. Это условие служит для нахождения потенциалов, оно составляется для всех 7-ми заполненных клеток. Получим 7 уравнений.
1. Клетка А1В1: v 1 – u 1 = 18.
2. Клетка А1В2: v 2 – u 1 = 23.
3. Клетка А2В1: v 1 – u 2 = 12.
4. Клетка А2В3: v 3 – u 2 = 10.
5. Клетка А3В3: v 3 – u 3 = 12.
6. Клетка А3В4: v 4 – u 3 = 16.
7. Клетка А3В5: v 5 – u 3 = 26.
Так как всего потенциалов 8, а заполненных клеток только 7, то один из потенциалов (любой) задаётся произвольно. Условимся брать u 1 = 0. Остальные потенциалы находим из составленных уравнений.
Из уравнения 1: v 1 = 18 + u 1 = 18+0 = 18;
из уравнения 2: v 2 = 23 + u 1 = 23+0 = 23;
из уравнения 3: u 2 = v 1 – 12 = 18 –12 = 6;
из уравнения 4: v 3 = 10 + u 2 = 10 + 6 = 16;
из уравнения 5: u 3 = v 3 –12 = 16 – 12 = 4;
из уравнения 6: v 4 = u 3 + 16 = 4 + 16 = 20;
из уравнения 7: v 5 = u 3 + 26 = 4 + 26 = 30.
Внимание! Может оказаться, что некоторые потенциалы отрицательные, это допустимо, так как потенциалы являются лишь «условными ценами». Они зависят от произвольно взятого значения u1 = 0.
Таким образом, найдены все потенциалы: u 1=0, u 2=6, u 3=4;
v 1=18, v 2=23, v 3=16, v 4=20, v 5=30. С их помощью проверяем на оптимальность все пустые клетки. Для пустой клетка АiВj перевозка не состоялась, и поэтому цена товара у потребителя Вj не должна превышать цену у поставщика Аi, то есть v j – ui ≤ с ij для пустых клеток. Проверяем это соотношение для всех пустых клеток.
1. Клетка А1В3: v 3 – u 1 = 16 – 0 = 16 ˃ 15 = с 13 – не оптимальная.
2. Клетка А1В4: v 4 – u 1 = 20 – 0 = 20 ˃ 19 = с 14 – не оптимальная.
3. Клетка А1В5: v 5 – u 1 = 30 – 0 = 30 ˂ 36 = с 15 – оптимальная.
4. Клетка А2В2: v 2 – u 2 = 23 – 6 = 17 ˂ 32 = с 22 – оптимальная.
5. Клетка А2В4: v 4 – u 2 = 20 – 6 = 14 ˃ 13 = с 24 – не оптимальная.
6. Клетка А2В5: v 5 – u 2 = 30 – 6 = 24 ˂ 28 = с 25 – оптимальная.
7. Клетка А3В1: v 1 – u 3 = 18 – 4 = 14 ˂ 24 = с 31 – оптимальная.
8. Клетка А3В2: v 2 – u 3 = 23 – 4 = 19 ˂ 25 = с 32 – оптимальная.
План будет оптимальным, если все клетки окажутся оптимальными. Если имеется хотя бы одна не оптимальная клетка, то план не оптимальный. В решаемой задаче три не оптимальные пустые клетки: А1В3, А1В4 и А2В4. Следовательно, составленный план не оптимальный. Значит, имеется более дешёвый план перевозок, чем найденный.
Для нахождения оптимального плана можно воспользоваться надстройкой «Поиск решения», имеющейся в Excel. Для этого необходимо составить математическую модель задачи.
5) Для составления математической модели транспортной задачи, введём переменные x ij– это поставки, то есть количество груза, перевозимое от поставщика Аiпотребителю Вj, где i= 1, 2, 3; j= 1, 2, 3, 4, 5. Всего переменных 3*5 = 15. Очевидно, что все они не могут быть отрицательными.
Так как транспортная задача закрытая, должны соблюдаться балансы поставок п строкам (поставщикам) и столбцам (потребителям).