Алгоритм северо-западного угла для ТЗПП — различия между версиями
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
м |
||
(не показано 8 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
'''Алгоритм северо-западного угла''' — это алгоритм нахождения допустимого решения для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]). | '''Алгоритм северо-западного угла''' — это алгоритм нахождения допустимого решения для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]). | ||
+ | == Обозначения == | ||
+ | '''m''' – число промежуточных пунктов (складов)'''(m>1)'''; | ||
− | + | '''n''' – число конечных пунктов (поставщиков и потребителей)'''(n>3)'''; | |
− | ''' | + | '''mp''' – число складов с положительными дополнительными потребностями '''(0≤mp≤m)'''; |
− | ''' | + | '''np''' – число поставщиков (конечных пунктов c положительными значениями) '''(1<np<n)'''; |
− | + | '''a<sub>i</sub>''' – дополнительная потребность (со знаком, причём до '''mp''' положительные, а после нулевые или отрицательные) '''i'''-ого промежуточного пункта (склада); | |
− | + | ||
− | + | ||
− | + | ||
− | '''a<sub>i</sub>''' – дополнительная потребность (со знаком) '''i'''-ого промежуточного пункта (склада); | + | |
'''b<sub>j</sub>''' – объём грузов (со знаком) '''j'''-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное); | '''b<sub>j</sub>''' – объём грузов (со знаком) '''j'''-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное); | ||
Строка 19: | Строка 16: | ||
'''z<sub>ij</sub>''' – признак базисного элемента '''(i,j)'''. | '''z<sub>ij</sub>''' – признак базисного элемента '''(i,j)'''. | ||
+ | == Алгоритм 1 == | ||
+ | '''Входные данные:''' | ||
+ | |||
+ | [[файл:AB001.png]] | ||
+ | |||
+ | '''Алгоритм:''' | ||
+ | |||
+ | [[файл:АСЗУ01.png]] | ||
+ | |||
+ | '''Выходные данные:''' | ||
− | == Алгоритм == | + | [[файл:XZ001.png]] |
− | Входные данные: ''' | + | *Заметим, что при выборе новой клетки '''СЗУ(i,j)''' необходимо увеличивать индекс строки '''i''' или индекс столбца '''j'''. |
+ | == Алгоритм 2 == | ||
+ | '''Входные данные:''' | ||
− | [[файл: | + | [[файл:AB001.png]] |
− | + | '''Алгоритм:''' | |
− | + | [[файл:СЗУ011.png]] | |
− | + | '''Выходные данные:''' | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
+ | [[файл:XZ001.png]] | ||
+ | == Пример АСЗУ для ТЗПП == | ||
+ | === Транспортная задача === | ||
+ | [[файл:ТЗПП01.png]] | ||
+ | === Транспортная таблица === | ||
+ | [[файл:СЗУ00.png]] | ||
+ | === Нахождение допустимого решения === | ||
+ | [[файл:СЗУ11.png]] | ||
+ | [[файл:СЗУ01.png]] | ||
+ | [[файл:СЗУ12.png]] | ||
+ | [[файл:СЗУ02.png]] | ||
+ | [[файл:СЗУ13.png]] | ||
+ | [[файл:СЗУ03.png]] | ||
+ | [[файл:СЗУ14.png]] | ||
+ | [[файл:СЗУ04.png]] | ||
+ | [[файл:СЗУ15.png]] | ||
+ | [[файл:СЗУ05.png]] | ||
+ | [[файл:СЗУ16.png]] | ||
+ | [[файл:СЗУ06.png]] | ||
+ | [[файл:СЗУ17.png]] | ||
+ | [[файл:СЗУ07.png]] | ||
+ | [[файл:СЗУ18.png]] | ||
+ | [[файл:СЗУ08.png]] | ||
+ | [[файл:СЗУ19.png]] | ||
+ | [[файл:СЗУ09.png]] | ||
+ | [[файл:СЗУ20.png]] | ||
+ | [[файл:СЗУ10.png]] | ||
+ | [[файл:СЗУ21.png]] | ||
+ | [[файл:СЗУ22.png]] | ||
+ | === Допустимое решение === | ||
+ | [[файл:МП00.png]] | ||
+ | == [[Алгоритмы решения транспортных задач|Другие алгоритмы:]] == | ||
+ | {{Список АТЗ}} | ||
== Ссылки == | == Ссылки == | ||
− | * Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf | + | *Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf |
− | * Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. | + | *Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29. |
− | * [[Участник:Logic-samara]] | + | *[[Участник:Logic-samara]] |
− | [[Категория:Транспортная задача]][[Категория:Алгоритмы]] | + | [[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]] |
Текущая версия на 12:06, 16 января 2024
Алгоритм северо-западного угла — это алгоритм нахождения допустимого решения для транспортной задачи с промежуточными пунктами (ТЗПП).
Содержание
Обозначения
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
Входные данные:
Алгоритм:
Выходные данные:
Пример АСЗУ для ТЗПП
Транспортная задача
Транспортная таблица
Нахождение допустимого решения
Файл:СЗУ11.png Файл:СЗУ01.png Файл:СЗУ12.png Файл:СЗУ02.png Файл:СЗУ13.png Файл:СЗУ03.png Файл:СЗУ14.png Файл:СЗУ04.png Файл:СЗУ15.png Файл:СЗУ05.png Файл:СЗУ16.png Файл:СЗУ06.png Файл:СЗУ17.png Файл:СЗУ07.png Файл:СЗУ18.png Файл:СЗУ08.png Файл:СЗУ19.png Файл:СЗУ09.png Файл:СЗУ20.png Файл:СЗУ10.png Файл:СЗУ21.png Файл:СЗУ22.png
Допустимое решение
Другие алгоритмы:
- алгоритм северо-западного угла для ТЗ;
- алгоритм расчёта потенциалов для ТЗ;
- алгоритм перераспределения перевозок для ТЗ;
- алгоритм северо-западного угла для ТЗПП;
- алгоритм расчёта потенциалов для ТЗПП;
- алгоритм перераспределения перевозок для ТЗПП;
- алгоритм решения ТЗПП с запретами;
- алгоритм минимального элемента для ТТЗ;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Ссылки
- Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf
- Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
- Участник:Logic-samara