Алгоритм северо-западного угла для ТЗПП — различия между версиями
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 5: | Строка 5: | ||
'''m''' – число промежуточных пунктов (складов)'''(m>1)'''; | '''m''' – число промежуточных пунктов (складов)'''(m>1)'''; | ||
| − | '''n''' – число конечных пунктов (поставщиков и потребителей)'''(n> | + | '''n''' – число конечных пунктов (поставщиков и потребителей)'''(n>3)'''; |
'''mp''' – число складов с положительными дополнительными потребностями '''(0≤mp≤m)'''; | '''mp''' – число складов с положительными дополнительными потребностями '''(0≤mp≤m)'''; | ||
| − | '''np''' – число поставщиков (конечных пунктов c положительными значениями) '''( | + | '''np''' – число поставщиков (конечных пунктов c положительными значениями) '''(1<np<n)'''; |
'''a<sub>i</sub>''' – дополнительная потребность (со знаком, причём до '''mp''' положительные, а после нулевые или отрицательные) '''i'''-ого промежуточного пункта (склада); | '''a<sub>i</sub>''' – дополнительная потребность (со знаком, причём до '''mp''' положительные, а после нулевые или отрицательные) '''i'''-ого промежуточного пункта (склада); | ||
| Строка 79: | Строка 79: | ||
*Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. | *Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. | ||
*[[Участник:Logic-samara]] | *[[Участник:Logic-samara]] | ||
| − | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]] | + | [[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]] |
Текущая версия на 15:18, 6 апреля 2023
Алгоритм северо-западного угла — это алгоритм нахождения допустимого решения для транспортной задачи с промежуточными пунктами (ТЗПП).
Содержание
Обозначения[править]
Введём обозначения:
m – число промежуточных пунктов (складов)(m>1);
n – число конечных пунктов (поставщиков и потребителей)(n>3);
mp – число складов с положительными дополнительными потребностями (0≤mp≤m);
np – число поставщиков (конечных пунктов c положительными значениями) (1<np<n);
ai – дополнительная потребность (со знаком, причём до mp положительные, а после нулевые или отрицательные) i-ого промежуточного пункта (склада);
bj – объём грузов (со знаком) j-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное);
xij – объём перевозки (со знаком) между i-ым промежуточным пунктом и j-ым конечным пунктом;
zij – признак базисного элемента (i,j).
Алгоритм 1[править]
Входные данные:
Алгоритм:
Выходные данные:
- Заметим, что при выборе новой клетки СЗУ(i,j) необходимо увеличивать индекс строки i или индекс столбца j.
Алгоритм 2[править]
Входные данные:
Алгоритм:
Выходные данные:
Пример АСЗУ для ТЗПП[править]
Транспортная задача[править]
Транспортная таблица[править]
Нахождение допустимого решения[править]
Допустимое решение[править]
Другие алгоритмы:[править]
- алгоритм северо-западного угла для ТЗ;
- алгоритм северо-западного угла для ТЗПП;
- алгоритм расчёта потенциалов для ТЗ;
- алгоритм расчёта потенциалов для ТЗПП;
- алгоритм перераспределения перевозок для ТЗ;
- алгоритм перераспределения перевозок для ТЗПП;
- алгоритм решения ТЗПП с запретами;
- алгоритм минимального элемента для ТТЗ;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Ссылки[править]
- Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf
- Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
- Участник:Logic-samara
