Транспортная задача. Метод "северо-западного угла"
Автор: ZAOCHNAYAPSINA • Июнь 10, 2018 • Реферат • 666 Слов (3 Страниц) • 933 Просмотры
ТЕМА: ТРАНСПОРТНАЯ ЗАДАЧА. МЕТОД «СЕВЕРО-ЗАПАДНОГО УГЛА»
ВВЕДЕНИЕ
1. Оптимальные планы перевозок рассчитываются транспортными задачами путем последовательных итераций опорных планов, позволяющих выбрать из всех рассмотренных наиболее эффективный.
В общем виде транспортная задача может быть представлена в виде:
[pic 1]
[pic 2]
[pic 3]
что означает минимизацию функций цели суммарных транспортных издержек из i=(1, m) пунктов отправления в j= (1, n) пунктов назначения при тарифах на перевозку грузов (Cij) и планируемых объемах перевозок (Xij), равных имеющимся запасам (ai), адекватным уровням уровням потребителей (bj).
общее условие (1) может быть в табличном виде:[pic 4]
i=1, m | j1[pic 5] | j2 | j3 | … | jn | Запасы |
i=1 | [pic 6] | [pic 7] | [pic 8] | a1 | ||
i=2 | [pic 9] | [pic 10] | [pic 11] | [pic 12] | a2 | |
… | [pic 13] | [pic 14] | [pic 15] | … | ||
i=m | [pic 16] | am[pic 17] | ||||
Потребности | b1 | b2 | b3 | … | bn | bi |
УЧЕБНЫЙ ВОПРОС 1.
Метод «северо-западного угла»
Условие: необходимо минимизировать суммарные транспортные издержки из двух пунктов отправления с запасами товаров:
a1 = 100 ед.
a2 = 200 ед.
в три пункты назначения с потребностями на товары:
b1 = 150 ед.
b2 = 100 ед.
b3 = 50 ед.
при заданной матрице тарифов:
[pic 18]
и планируемых объемах перевозок:
[pic 19]
2. 2. Пример расчета
Запишем условие транспортной задачи в математическом виде:
- дана система ограничений:
(2)[pic 20]
- требуется среди множества решений системы уравнений наитии такое неотрицательное решение ( оптимальный план перевозок), которое минимизирует целевую функцию:
[pic 21]
при [pic 22]
Для решения системы уравнений строится исходный опорный план по правилу «северо-западного» угла.
Запишем условие транспортной задачи в табличном виде:
i=1, 2[pic 23] | 1 | 2 | 3 | Запасы |
1 | [pic 24] | [pic 25] | [pic 26] | 100 |
2 | [pic 27] | [pic 28] | [pic 29] | 200 |
Потребности | 150 | 100 | 50 | 300 |
Занесем в клетку (1,1):
[pic 30]
Ресурсы 1-го поставщика исчерпаны полностью и первая строка из расчетов исключается.
Заполняем клетку (2,1):
[pic 31]
Спрос 1-го потребителя удовлетворен полностью и первый столбец из расчетов исключается.
Остаток груза от 2-го поставщика (200-50) = 150 ед. с учетом потребности 2-го потребителя (100 ед.) помещается в клетку (2,2), т.е. X2,2 = min (150;100) = 100 ед. Вторая строка не исключается, остаток груза 50 ед. у 2-го поставщика помещается в клетку (2,3) при полном удовлетворении потребностей 2-го потребителя в 100 ед. – второй столбец исключается.
...