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

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

Обозначения

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

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

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

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

$mp$ — число складов с дополнительными потребностями, $0\leq mp\leq m$ ;

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

$a_{i}>0$ — дополнительные потребности продукции на складе $i,\forall i\in N_{mp}$ ;

$a_{mp+i}\leq 0$ — излишки продукции или нулевые остатки на складе $mp+i,\forall i\in N_{m-mp}$ ;

$b_{j}>0$ — объём поставок продукции поставщика $j,\forall j\in N_{np}$ ;

$b_{np+j}<0$ — объём потребностей (в продукции) потребителя $np+j,\forall j\in N_{n-np}$ ;

$c_{ij}>0$ — транспортный тариф на перевозку единицы продукции от поставщика $j$ на склад $i,\forall (i,j)\in {N_{m}\times N_{np}}$ ;

$c_{inp+j}<0$ — транспортный тариф на перевозку единицы продукции со склада $i$ к потребителю $np+j,\forall (i,j)\in {N_{m}\times N_{n-np}}$ ;

$x_{ij}\geq 0$ — объём перевозок продукции от поставщика $j$ на склад $i,\forall (i,j)\in {N_{m}\times N_{np}}$ ;

$x_{inp+j}\leq 0$ — объём перевозок продукции со склада $i$ к потребителю $np+j,\forall (i,j)\in {N_{m}\times N_{n-np}}$ ;

$z_{ij}$ — булева переменная обозначающая принадлежность перевозки к базису: $1$ — принадлежит базису, $0$ — не принадлежит базису, $\forall (i,j)\in {N_{m}\times N_{n}}$ ;

$A_{m}$ — вектор объёмов перевозок промежуточных пунктов (складов) $a_{i}$ ;

$B_{n}$ — вектор объёмов перевозок конечных пунктов (поставщиков и потребителей) $b_{j}$ ;

$C_{m\times n}$ — матрица тарифов $c_{ij}$ ;

$X_{m\times n}$ — матрица перевозок $x_{ij}$ ;

$Z_{m\times n}$ — матрица базисных элементов $z_{ij}$ .

Алгоритм 1

Входные данные: m, mp, n, np, A_m, B_n, C_mxn.

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.

Выходные данные: X_mxn, Z_mxn.

Алгоритм 2

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

Алгоритм 3

Пример

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

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

Допустимое решение

Другие алгоритмы

1. Алгоритм метода потенциалов для ТЗ:
   1. алгоритм северо-западного угла для ТЗ;
   2. алгоритм минимального элемента для ТЗ;
   3. алгоритм расчёта потенциалов для ТЗ;
   4. алгоритм перераспределения перевозок для ТЗ;
2. Алгоритм метода потенциалов для ТЗПП:
   1. алгоритм северо-западного угла для ТЗПП;
   2. алгоритм расчёта потенциалов для ТЗПП;
   3. алгоритм перераспределения перевозок для ТЗПП;
   4. алгоритм решения ТЗПП с запретами;
3. Алгоритм метода потенциалов для ТТЗ:
   1. алгоритм минимального элемента для ТТЗ;
   2. алгоритм расчёта потенциалов для ТТЗ;
   3. алгоритм перераспределения перевозок для ТТЗ;
4. Алгоритм метода потенциалов для ТТЗАС:
   1. алгоритм трёхгранного угла для ТТЗАС;
   2. алгоритм расчёта потенциалов для ТТЗАС;
   3. алгоритм перераспределения перевозок для ТТЗАС;
5. Алгоритм метода потенциалов для ТТЗПП:
   1. алгоритм расчёта потенциалов для ТТЗПП;
   2. алгоритм перераспределения перевозок для ТТЗПП.

Литература

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

Ссылки

• http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf стр.369-372
• Участник:Logic-samara