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

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

Обозначения

Введём обозначения:

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

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

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

np – число поставщиков (0<np<n);

a_i – дополнительная потребность (со знаком) i-ого промежуточного пункта (склада);

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

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

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

Алгоритм

Входные данные: m; n; mp; np; {a₁, a₂, ..., a_m}; {b₁, b₂, ..., b_n}.

Выходные данные: {x₁₁, x₁₂, ..., x_mn}; {z₁₁, z₁₂, ..., z_mn}.

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

Пример АСЗУ для ТЗПП

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

Транспортная таблица

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

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

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

• алгоритм северо-западного угла для ТЗ;
• алгоритм северо-западного угла для ТЗПП;
• алгоритм расчёта потенциалов для ТЗ;
• алгоритм расчёта потенциалов для ТЗПП;
• алгоритм перераспределения перевозок для ТЗ;
• алгоритм перераспределения перевозок для ТЗПП;
• алгоритм решения ТЗПП с запретами;
• алгоритм минимального элемента для ТТЗ;
• алгоритм расчёта потенциалов для ТТЗ;
• алгоритм перераспределения перевозок для ТТЗ.

Ссылки

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