Транспортная задача. Метод северо-западного угла. Транспортная задача. Метод северозападного угла

• Название: Транспортная задача. Метод северозападного угла
• Анкор: Транспортная задача. Метод северо-западного угла
• Дата: 13.05.2021
• Размер: 227.61 Kb.
• Имя файла: kursovaaya4.docx
• Тип: Курсовая; #204704
• страница: 3 из 4

2.2 Решение задачи

Процедура нахождения оптимального плана транспортной задачи имеет два этапа. На первом этапе находят опорной план транспортной задачи. Далее последовательно улучшают найденный опорный план до получения оптимального плана.

Для нахождения первого опорного плана будем использовать – метод северо-западного угла.

Для определения оптимального плана – метод потенциалов.

Запишем исходные данные транспортной задачи в виде таблицы (Таблица 1):
Таблица 1 – Таблица исходных данных транспортной задачи

Пункты отправления Пункты назначения Запасы B1 B2 B3 A1 2 3 4 14 A2 6 8 5 66 A3 5 4 3 33 Потребности 53 35 73

Число пунктов отправления m=3, а число пунктов назначения n=3. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+3−1=5 заполненых клетках таблицы.
Наличие груза у поставщиков равно:

∑ A_i= 14+66+33= 113

Общая потребность в грузе в пунктах назначения равна:

∑ B_i= 53+35+73 =161

∑ A_i<∑ B_i. Модель транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительный пункт отправления A4 c запасами 161− 113=48. Тарифы перевозки из пункта отправления A4 во все пункты назначения полагаем равными нулю. В результате получим закрытую модель транспортной задачи (Таблица 2):
Таблица 2 – Закрытая модель транспортной задачи

Пункты отправления Пункты назначения Запасы B1 B2 B3 A1 2 3 4 14 A2 6 8 5 66 A3 5 4 3 33 A4 0 0 0 0 Потребности 53 35 73

Этап I. Нахождение первого опорного плана.

Найдем опорный план задачи методом северно-западного угла.

A₁≤B₁. Следовательно в клетку (A₁, B₁ ) помещаем число min(A₁, B₁ )=14. Запасы пункта A₁ полностью исчерпаны. Поэтому исключаем из рассмотрения строку A₁ и будем считать потребности пункта B₁ равными 53−14=39. Модель транспортной задачи (Таблица 3)
Таблица 3 –Модель транспортной задачи

Пункты отправления Пункты назначения Запасы B1 B2 B3 A1 2 [14] 3 4 0 [14] A2 6 8 5 66 [66] A3 5 4 3 33 [33] A4 0 0 0 48 [48] Потребности 39 [53] 35 [35] 73 [73] 161

A2>B1. Следовательно в клетку (A2, B1) помещаем число min(A2, B1)=39. Потребности пункта B1 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B1 и будем считать запасы пункта A2 равными 66−39=27. Модель транспортной задачи (Таблица 4)
Таблица 4 – Модель транспортной задачи

Пункты отправления Пункты назначения Запасы B1 B2 B3 A1 2 [14] 3 4 0 [14] A2 6 [39] 8 5 27 [66] A3 5 4 3 33 [33] A4 0 0 0 48 [48] Потребности 0 [53] 35 [35] 73 [73] 161

A2≤B2. Следовательно в клетку (A2, B2 ) помещаем число min(A2, B2 )=27. Запасы пункта A2 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A2 и будем считать потребности пункта B2 равными 35−27=8. Модель транспортной задачи (Таблица 5)
Таблица 5 –Модель транспортной задачи

Пункты отправления Пункты назначения Запасы B1 B2 B3 A1 2 [14] 3 4 0 [14] A2 6 [39] 8 [27] 5 0 [66] A3 5 4 3 33 [33] A4 0 0 0 48 [48] Потребности 0 [53] 8 [35] 73 [73] 161

A3>B2. Следовательно в клетку (A3, B2) помещаем число min(A3, B2)=8. Потребности пункта B2 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B2 и будем считать запасы пункта A3 равными 33−8=25. Модель транспортной задачи (Таблица 6)
Таблица 6 – Модель транспортной задачи

Пункты отправления Пункты назначения Запасы B1 B2 B3 A1 2 [14] 3 4 0 [14] A2 6 [39] 8 [27] 5 0 [66] A3 5 4 [8] 3 25 [33] A4 0 0 0 48 [48] Потребности 0 [53] 0 [35] 73 [73] 161

A3≤B3. Следовательно в клетку (A3, B3 ) помещаем число min(A3, B3 )=25. Запасы пункта A3 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A3 и будем считать потребности пункта B3 равными 73−25=48. Модель транспортной задачи (Таблица 7)
Таблица 7 – Модель транспортной задачи

Пункты отправления Пункты назначения Запасы B1 B2 B3 A1 2 [14] 3 4 0 [14] A2 6 [39] 8 [27] 5 0 [66] A3 5 4 [8] 3 [25] 0 [33] A4 0 0 0 48 [48] Потребности 0 [53] 0 [35] 48 [73] 161

A4≤B3. Следовательно в клетку (A4, B3 ) помещаем число

min(A4, B3 )=48. Запасы пункта A4 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A4 и будем считать потребности пункта B3 равными 48−48=0. Модель транспортной задачи (Таблица 8)
Таблица 8 – Модель транспортной задачи

Пункты отправления Пункты назначения Запасы B1 B2 B3 A1 2 [14] 3 4 0 [14] A2 6 [39] 8 [27] 5 0 [66] A3 5 4 [8] 3 [25] 0 [33] A4 0 0 0 [48] 0 [48] Потребности 0 [53] 0 [35] 0 [73] 161