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

Метод северо-западного угла для ТЗПП — метод нахождения допустимого решения ТЗПП.

Метод северо-западного угла для нахождения допустимого решения ТЗПП аналогичен одноимённому методу для транспортной задачи и состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах.

Обозначения

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

$np$ — число поставщиков;

$n-np$ — число потребителей;

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

$mp$ — число складов с дополнительными (внутренними) потребностями;

$m-mp$ — число складов с излишками продукции или нулевыми остатками;

$b_{j}>0,j=1,2,...,np$ — объём поставок продукции поставщиков;

$b_{np+j}<0,j=1,2,...,{n-np}$ — объём потребностей (в продукции) потребителей;

$a_{i}>0,i=1,2,...,m$ — дополнительные (внутренние) потребности продукции (на складе);

$a_{i}\leq 0,i=1,2,...,{m-mp}$ — излишки продукции или нулевые остатки (на складе);

$c_{ij}>0,i=1,2,...,m,j=1,2,...,{np}$ — транспортные тарифы на перевозку единицы продукции от поставщика на склад;

$c_{inp+j}<0,i=1,2,...,m,j=1,2,...,{n-np}$ — транспортные тарифы на перевозку единицы продукции со склада к потребителю;

$x_{ij}\geq 0,i=1,2,...,m,j=1,2,...,{np}$ — объём перевозок продукции от поставщика на склад;

$x_{inp+j}\leq 0,i=1,2,...,m,j=1,2,...,{n-np}$ — объём перевозок продукции со склада к потребителю;

$z_{ij},i=1,2,...,m,j=1,2,...,n$ — булевы переменные обозначающие принадлежность перевозок к базису: $1$ — принадлежит базису, $0$ — не принадлежит базису.

Алгоритм

Алгоритм заполнения клеток транспортной таблицы (распределения перевозок) для ТЗПП осуществляется в три этапа и продолжается до тех пор пока у поставщиков имеются нераспределённые положительные остатки или у потребителей имеются неудовлетворённые отрицательные потребности.

$1$. Сначала удовлетворяем дополнительные потребности складов $a_{i}>0$ за счёт поставщиков $b_{j}>0$, т.е. назначаем соответствующие положительные перевозки по формулам: $x_{ij}=\min\{a_{i},b_{j}\},a_{i}=a_{i}-x_{ij},b_{j}=b_{j}-x_{ij},z_{ij}=1$.

$2$. Затем распределяем остатки грузов от поставщиков $b_{j}>0$ на последний используемый склад, т.е. начиная с последней заполненной строки по формулам: $x_{ij}=b_{j},a_{i}=a_{i}-x_{ij},b_{j}=0,z_{ij}=1$.

$3$. Наконец, удовлетворяем потребности потребителей $b_{j}<0$, т.е. назначаем соответствующие отрицательные перевозки по формулам: $x_{ij}=\max\{a_{i},b_{j}\},a_{i}=a_{i}-x_{ij},b_{j}=b_{j}-x_{ij},z_{ij}=1$.

Литература

• Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372.

Ссылки

• Krivopalov V. Y., Krivopalov Y. A. The potential method for solving the transportation problem with transit points. New Magenta Papers. Magenta Technology, 2013. — Vol.2 — P.31-38.
• http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf стр.369-372.

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Метод северо-западного угла для ТЗПП», расположенная по адресу: — «https://ru.ruwiki.ru/wiki/Метод_северо-западного_угла_для_ТЗПП» Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».