Метод северо-западного угла для транспортной задачи с промежуточными пунктами

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

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

Обозначения

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

Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle np} — число поставщиков;

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

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

Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle 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$ на последний используемый склад, т.е. начиная с последней заполненной строки по формулам: Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle x_{ij}=b_{j},a_{i}=a_{i}-x_{ij},b_{j}=0,z_{ij}=1} .

$3$. Наконец, удовлетворяем потребности потребителей Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle 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

Другие методы

1. Метод потенциалов для ТЗ;
2. Метод минимального элемента для ТЗ;
3. Метод северо-западного угла для ТЗ;
4. Метод потенциалов для ТЗПП;
5. Метод северо-западного угла для ТЗПП;
6. Метод потенциалов для ТТЗ;
7. Метод минимального элемента для ТТЗ;
8. Метод потенциалов для ТТЗАС;
9. Метод трёхгранного угла для ТТЗАС;
10. Метод потенциалов для ТТЗПП.

Ссылки

• 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 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».