Алгоритм северо-западного угла для ТЗПП — различия между версиями
| Строка 18: | Строка 18: | ||
'''z<sub>ij</sub>''' – признак базисного элемента '''(i,j)'''. | '''z<sub>ij</sub>''' – признак базисного элемента '''(i,j)'''. | ||
| − | == Алгоритм == | + | == Алгоритм 1 == |
| − | Входные данные: ''' | + | '''Входные данные:''' |
| + | |||
| + | [[файл:AB001.png]] | ||
| + | |||
| + | '''Алгоритм:''' | ||
[[файл:АСЗУ01.png]] | [[файл:АСЗУ01.png]] | ||
| − | Выходные данные: ''' | + | '''Выходные данные:''' |
| + | |||
| + | [[файл:XZ001.png]] | ||
*Заметим, что при выборе новой клетки '''СЗУ(i,j)''' необходимо увеличивать индекс строки '''i''' или индекс столбца '''j'''. | *Заметим, что при выборе новой клетки '''СЗУ(i,j)''' необходимо увеличивать индекс строки '''i''' или индекс столбца '''j'''. | ||
| + | == Алгоритм 2 == | ||
| + | '''Входные данные:''' | ||
| + | |||
| + | [[файл:AB001.png]] | ||
| + | |||
| + | '''Алгоритм:''' | ||
| + | |||
| + | [[файл:СЗУ011.png]] | ||
| + | |||
| + | '''Выходные данные:''' | ||
| + | |||
| + | [[файл:XZ001.png]] | ||
== Пример АСЗУ для ТЗПП == | == Пример АСЗУ для ТЗПП == | ||
=== Транспортная задача === | === Транспортная задача === | ||
Версия 16:07, 11 февраля 2023
Алгоритм северо-западного угла — это алгоритм нахождения допустимого решения для транспортной задачи с промежуточными пунктами (ТЗПП).
Содержание
Обозначения
Введём обозначения:
m – число промежуточных пунктов (складов)(m>1);
n – число конечных пунктов (поставщиков и потребителей)(n>1);
mp – число складов с положительными дополнительными потребностями (0≤mp≤m);
np – число поставщиков (конечных пунктов c положительными значениями) (0<np<n);
ai – дополнительная потребность (со знаком) 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
