Метод северозападног угла

Метод северозападног угла представља једно од могућих иницијалних распоређивања доставки у транспортном проблему. Карактерише га то што се са распоређивањем започиње од северозападног тј. горњег левог угла транспортне матрице и продужава се увек надесно, док се цела колона не засити или њен снабдевач исцрпи. Након тога се прелази на следећи ред и алгоритам се на њему понавља. Зависно од једнакости количине понуде и потражње, може се десити да не продају сви продавци сву своју робу (тржиште оријентисано ка потрошачима) као и да не буду задовољени сви потраживачи (тржиште оријентисано ка продавцима).

Пример[уреди | уреди извор]

Рецимо да достављачи редом располажу са 12, 5 и 2 пакета, а да наручиоци редом очекују 4, 2, 10, 2 и 1 пакет. У том случају би полазна матрица изгледала овако:

{\begin{matrix}\Box &\Box &\Box &\Box &\Box &12&\\\Box &\Box &\Box &\Box &\Box &5&\\\Box &\Box &\Box &\Box &\Box &2&\\4&2&10&2&1&&\\\end{matrix}}

Уз вертикалу се налазе достављачи, са бројем доставки којима располажу, а хоризонтално су поређани поручиоци са бројевима очекиваних пакета. Празна поља представљају доставке које још нису обављене. Алгоритам започиње од горњег левог угла, у кога се пише минимум од броја испод његовог реда односно поред његове колоне. У овом случају, то су бројеви 4 и 12, чији је минимум број четири.

{\begin{matrix}{\mathit {4}}&\Box &\Box &\Box &\Box &12&\\\Box &\Box &\Box &\Box &\Box &5&\\\Box &\Box &\Box &\Box &\Box &2&\\4&2&10&2&1&&\\\end{matrix}}

Овај број се сада одузима и од расположивих доставки достављача и од потреба поручиоца.

{\begin{matrix}{\mathit {4}}&\Box &\Box &\Box &\Box &8&\\\Box &\Box &\Box &\Box &\Box &5&\\\Box &\Box &\Box &\Box &\Box &2&\\0&2&10&2&1&&\\\end{matrix}}

Први поручилац је овим задовољен, но први достављач још увек има добара. Она даље бивају распоређена на другог поручиоца на исти начин:

{\begin{matrix}{\mathit {4}}&{\mathit {2}}&\Box &\Box &\Box &6&\\\Box &\Box &\Box &\Box &\Box &5&\\\Box &\Box &\Box &\Box &\Box &2&\\0&0&10&2&1&&\\\end{matrix}}

Преостала добра првог добављача бивају распоређена на трећег поручиоца:

{\begin{matrix}{\mathit {4}}&{\mathit {2}}&{\mathit {6}}&\Box &\Box &0&\\\Box &\Box &\Box &\Box &\Box &5&\\\Box &\Box &\Box &\Box &\Box &2&\\0&0&4&2&1&&\\\end{matrix}}

Трећи поручилац још увек има потребу за четири испоруке. Оне ће сада бити преузете од другог испоручиоца коме након тога остаје једна слободна:

{\begin{matrix}{\mathit {4}}&{\mathit {2}}&{\mathit {6}}&\Box &\Box &0&\\\Box &\Box &{\mathit {4}}&\Box &\Box &1&\\\Box &\Box &\Box &\Box &\Box &2&\\0&0&0&2&1&&\\\end{matrix}}

Та једна бива распоређена на четвртог поручиоца који након тога има потребу за још једном која бива узета од трећег достављача. Након тога њему остаје само једна која бива преузета од петог поручиоца. Тиме је и завршено формирање иницијалне табеле и може да почне прераспоређивање испорука према ценама достављања.

{\begin{matrix}{\mathit {4}}&{\mathit {2}}&{\mathit {6}}&\Box &\Box &0&\\\Box &\Box &{\mathit {4}}&{\mathit {1}}&\Box &0&\\\Box &\Box &\Box &{\mathit {1}}&{\mathit {1}}&0&\\0&0&0&0&0&&\\\end{matrix}}

Овде се већ види да распоређивање може трајати произвољан број поља у некој колони или реду, зависно од броја добара којим располажу достављачи као и броја доставки које треба извршити до поручилаца.

Види још[уреди | уреди извор]