Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

Алгоритм северо-западного угла для ТЗПП

Материал из Циклопедии
Перейти к навигации Перейти к поиску

Алгоритм северо-западного угла — это алгоритм нахождения допустимого решения для транспортной задачи с промежуточными пунктами (ТЗПП).

Обозначения[править]

m – число промежуточных пунктов (складов)(m>1);

n – число конечных пунктов (поставщиков и потребителей)(n>3);

mp – число складов с положительными дополнительными потребностями (0≤mp≤m);

np – число поставщиков (конечных пунктов c положительными значениями) (1<np<n);

ai – дополнительная потребность (со знаком, причём до mp положительные, а после нулевые или отрицательные) i-ого промежуточного пункта (склада);

bj – объём грузов (со знаком) j-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное);

xij – объём перевозки (со знаком) между i-ым промежуточным пунктом и j-ым конечным пунктом;

zij – признак базисного элемента (i,j).

Алгоритм 1[править]

Входные данные:

AB001.png

Алгоритм:

АСЗУ01.png

Выходные данные:

XZ001.png

  • Заметим, что при выборе новой клетки СЗУ(i,j) необходимо увеличивать индекс строки i или индекс столбца j.

Алгоритм 2[править]

Входные данные:

AB001.png

Алгоритм:

СЗУ011.png

Выходные данные:

XZ001.png

Пример[править]

Транспортная задача[править]

ТЗПП01.png

Нахождение допустимого решения[править]

СЗУ01.png

Допустимое решение[править]

СЗУ02.png

Другие алгоритмы:[править]


Литература[править]

  • Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf
  • Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.

Ссылки[править]

 
Транспортная задача

Транспортная задача (классическая) • Решение симплекс-методомРешение в ExcelТранспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента)

Начальное решение

Метод северо-западного углаМетод минимальных тарифовМетод Фогеля‎

Вырожденные случаи

Вырожденность в ТЗАцикличность в ТЗ