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

Материал из ALL
Перейти к: навигация, поиск
м (Защищена страница «Алгоритм северо-западного угла» ([Редактирование=Разрешено только автоподтверждённым участникам] (бессрочно) [Пере…)
м
 
(не показано 6 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
'''Алгоритм северо-западного угла''' — это алгоритм нахождения допустимого решения для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]).
 
'''Алгоритм северо-западного угла''' — это алгоритм нахождения допустимого решения для [[Транспортная задача с промежуточными пунктами|транспортной задачи с промежуточными пунктами]] ([[ТЗПП]]).
 
== Обозначения ==
 
== Обозначения ==
−
Введём обозначения:
+
'''m''' – число промежуточных пунктов (складов)'''(m>1)''';
  
−
'''m''' – число промежуточных пунктов (складов);
+
'''n''' – число конечных пунктов (поставщиков и потребителей)'''(n>3)''';
  
−
'''n''' – число конечных пунктов (поставщиков и потребителей);
+
'''mp''' – число складов с положительными дополнительными потребностями '''(0≤mp≤m)''';
  
−
'''mp''' – число складов с положительными дополнительными потребностями;
+
'''np''' – число поставщиков (конечных пунктов c положительными значениями) '''(1<np<n)''';
  
−
'''np''' – число поставщиков;
+
'''a<sub>i</sub>''' – дополнительная потребность (со знаком, причём до '''mp''' положительные, а после нулевые или отрицательные) '''i'''-ого промежуточного пункта (склада);
−
 
+
−
'''a<sub>i</sub>''' – дополнительная потребность (со знаком) '''i'''-ого промежуточного пункта (склада);
+
  
 
'''b<sub>j</sub>''' – объём грузов (со знаком) '''j'''-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное);
 
'''b<sub>j</sub>''' – объём грузов (со знаком) '''j'''-ого конечного пункта (для поставщиков объём положительное число, для потребителей – отрицательное);
Строка 18: Строка 16:
  
 
'''z<sub>ij</sub>''' – признак базисного элемента '''(i,j)'''.
 
'''z<sub>ij</sub>''' – признак базисного элемента '''(i,j)'''.
−
== Алгоритм ==
+
== Алгоритм 1 ==
−
Входные данные: '''m; n; mp; np; {a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>m</sub>}; {b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>}'''.
+
'''Входные данные:'''  
 +
 
 +
[[файл:AB001.png]]
 +
 
 +
'''Алгоритм:'''
 +
 
 +
[[файл:АСЗУ01.png]]
 +
 
 +
'''Выходные данные:'''
 +
 
 +
[[файл:XZ001.png]]
 +
*Заметим, что при выборе новой клетки '''СЗУ(i,j)''' необходимо увеличивать индекс строки '''i''' или индекс столбца '''j'''.
 +
== Алгоритм 2 ==
 +
'''Входные данные:'''
 +
 
 +
[[файл:AB001.png]]
 +
 
 +
'''Алгоритм:'''
 +
 
 +
[[файл:СЗУ011.png]]
  
−
[[файл:АСЗУ01.JPG]]
+
'''Выходные данные:'''
  
−
Выходные данные: '''{x<sub>11</sub>, x<sub>12</sub>, ..., x<sub>mn</sub>}; {z<sub>11</sub>, z<sub>12</sub>, ..., z<sub>mn</sub>}'''.
+
[[файл:XZ001.png]]
−
* Заметим, что при выборе новой клетки СЗУ(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]]
 +
== [[Алгоритмы решения транспортных задач|Другие алгоритмы:]] ==
 +
{{Список АТЗ}}
 
== Ссылки ==
 
== Ссылки ==
−
* Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-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

Входные данные:

Файл: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, Самара-Москва, Т.1,стр.23-29.
  • Участник:Logic-samara
Источник — «https://allll.net/w/index.php?title=Алгоритм_северо-западного_угла_для_ТЗПП&oldid=122891»