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

Версия 08:59, 8 июля 2017

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

Обозначения

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

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

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

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

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

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) необходимо увеличивать индекс строки или индекс столбца.

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

Ссылки

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