Учебный вопрос № 2: Методы решения транспортных задач: метод «минимального элемента» и метод «северо-западного угла» (пример практического применения).
а) Метод «Минимального элемента»:
В методе минимального элемента выбор пунктов отправления и пунктов назначения производится, ориентируясь на тарифы перевозок, т.е. в каждом шаге нужно выбрать клетку с минимальным тарифом перевозок. Если таких клеток несколько, то выбираем одну из них. Надо отметить, что при данном методе определения заполняемой клетки, стоимость перевозок как правило бывает меньше, чем при методе северо-западного угла. Поэтому целесообразно начальный опорный план найти именно методом минимального элемента.
Рассмотрим метод минимального элемента на примере.
Пример 1. На три базы A1, A2, A3 поступил очередной груз в количествах равных 150, 100 и 100 ед. Этот груз требуется перевезти в четыре пунктов назначения B1, B2, B3, B4 в количествах 140, 100, 70 и 40.
Необходимо: найти опорный план транспортной задачи, представленной в таблице условий ниже методом минимального элемента:
|
Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n −1=3+4−1=6 заполненных клетках таблицы. Тарифы перевозок единицы груза из каждого пункта отправления во все пункты назначения задаются матрицей:
|
Наличие груза у поставщиков равно: 
.
Общая потребность в грузе в пунктах назначения равна: 
.
Модель транспортной задачи является сбалансированной. Следовательно она разрешима.
|
|
|
Минимальный тариф равный 1 находится в клетке (A1, B3). Поэтому заполняем эту клетку.
A1>B3. Следовательно в клетку (A1, B3) помещаем число 70. Потребности пункта B3 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B3 и будем считать запасы пункта A1 равными 150−70=80.
 .
|
Минимальный тариф равный 1 находится в клетке (A2, B4). Поэтому заполняем эту клетку.
A2>B4. Следовательно в клетку (A2, B4) помещаем число 40. Потребности пункта B4 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B4 и будем считать запасы пункта A2 равными 100−40=60.
 .
|
Таким образом, продолжая процедуру в m+n−1-ом шаге получим:
 .
|
Запишем полученный опорный план:
 .
|
Полученный опорный план сопоставляется с тарифами на перевозку, исходя из этого стоимость перевозок вычисляется так:
F= 2х80 + 1х70 + 3х60 + 1х40 + 3х0 + 6х100 = 1050.
б) Метод северно-западного угла.
При решении транспортной задачи методом северо-западного угла, заполнение клеток таблицы условий начинают с верхней левой клетки А1В1 (поэтому метод и называется «метод северо-западного угла»).
Рассмотрим метод на конкретном примере.
Пример 1. На три базы A1, A2, A3 поступил очередной груз в количествах равных 140, 160, 120 ед. Этот груз требуется перевезти в четыре пунктов назначения B1, B2, B3, B4 в количествах 150, 90, 100, 80.
|
|
|
Тарифы перевозок представлена матрицей
|
Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненных клетках таблицы.
Наличие груза у поставщиков равно: ∑Ai=140+160+120=420.
Общая потребность в грузе в пунктах назначения равна: ∑Bj=150+90+100+80=420.
∑Ai=∑Bj. Модель транспортной задачи является сбалансированной. Следовательно она разрешима.
Найдем опорный план задачи методом северно-западного угла.
A1≤B1. Следовательно в клетку (A1, B1 ) помещаем число min(A1, B1)=140. Запасы пункта A1 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A1 и будем считать потребности пункта B1 равными 150−140=10.
 .
|
A2>B1. Следовательно в клетку (A2, B1) помещаем число min(A2, B1)=10. Потребности пункта B1 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B1 и будем считать запасы пункта A2 равными 160−10=150.
|
Таким образом, продолжая процедуру в m+n−1-ом шаге получим:
|
Запишем полученный опорный план:
 .
|
При этом плане стоимость перевозок вычисляется так:
|
|
|
F=2·140+8·10+4·90+ 1·60+3·40+6·80=1380.
Таким образом, приведенные методики позволяют составлять обоснованные планы перевозок грузов и проводить расчеты затрат на их осуществление.
Дата добавления: 2022-01-22; просмотров: 53; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!