Алгоритм северо-западного угла для ТЗПП — различия между версиями
м |
|||
Строка 25: | Строка 25: | ||
Выходные данные: '''{x<sub>11</sub>, x<sub>12</sub>, ..., x<sub>mn</sub>}; {z<sub>11</sub>, z<sub>12</sub>, ..., z<sub>mn</sub>}'''. | Выходные данные: '''{x<sub>11</sub>, x<sub>12</sub>, ..., x<sub>mn</sub>}; {z<sub>11</sub>, z<sub>12</sub>, ..., z<sub>mn</sub>}'''. | ||
*Заметим, что при выборе новой клетки СЗУ(i,j) необходимо увеличивать индекс строки или индекс столбца. | *Заметим, что при выборе новой клетки СЗУ(i,j) необходимо увеличивать индекс строки или индекс столбца. | ||
+ | == Пример АСЗУ для ТЗПП == | ||
+ | [[файл:ТЗПП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]] | ||
== [[Алгоритм|Другие алгоритмы:]] == | == [[Алгоритм|Другие алгоритмы:]] == | ||
{{Список АТЗ}} | {{Список АТЗ}} |
Версия 10:41, 18 июля 2022
Алгоритм северо-западного угла — это алгоритм нахождения допустимого решения для транспортной задачи с промежуточными пунктами (ТЗПП).
Содержание
Обозначения
Введём обозначения:
m – число промежуточных пунктов (складов);
n – число конечных пунктов (поставщиков и потребителей);
mp – число складов с положительными дополнительными потребностями;
np – число поставщиков;
ai – дополнительная потребность (со знаком) i-ого промежуточного пункта (склада);
bj – объём грузов (со знаком) j-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное);
xij – объём перевозки (со знаком) между i-ым промежуточным пунктом и j-ым конечным пунктом;
zij – признак базисного элемента (i,j).
Алгоритм
Входные данные: m; n; mp; np; {a1, a2, ..., am}; {b1, b2, ..., bn}.
Выходные данные: {x11, x12, ..., xmn}; {z11, z12, ..., zmn}.
- Заметим, что при выборе новой клетки СЗУ(i,j) необходимо увеличивать индекс строки или индекс столбца.
Пример АСЗУ для ТЗПП
Транспортная таблица
Нахождение допустимого решения
Допустимое решение
Другие алгоритмы:
- алгоритм северо-западного угла для ТЗ;
- алгоритм северо-западного угла для ТЗПП;
- алгоритм расчёта потенциалов для ТЗ;
- алгоритм расчёта потенциалов для ТЗПП;
- алгоритм перераспределения перевозок для ТЗ;
- алгоритм перераспределения перевозок для ТЗПП;
- алгоритм решения ТЗПП с запретами;
- алгоритм минимального элемента для ТТЗ;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Ссылки
- Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf
- Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
- Участник:Logic-samara