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

Материал из ALL
Перейти к: навигация, поиск
м
Строка 3: Строка 3:
 
Введём обозначения:
 
Введём обозначения:
  
−
'''m''' – число промежуточных пунктов (складов);
+
'''m''' – число промежуточных пунктов (складов)'''(m>1)''';
  
−
'''n''' – число конечных пунктов (поставщиков и потребителей);
+
'''n''' – число конечных пунктов (поставщиков и потребителей)'''(n>3)''';
  
−
'''np''' – число поставщиков;
+
'''np''' – число поставщиков (конечных пунктов c положительными значениями) '''(1<np<n)''';
  
 
'''c<sub>ij</sub>''' – транспортный тариф (со знаком) на перевозку единицы продукции между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом (тариф для перевозки '''(i,j)''');
 
'''c<sub>ij</sub>''' – транспортный тариф (со знаком) на перевозку единицы продукции между '''i'''-ым промежуточным пунктом и '''j'''-ым конечным пунктом (тариф для перевозки '''(i,j)''');
Строка 22: Строка 22:
  
 
'''(i<sub>0</sub>, j<sub>0</sub>)''' – перевозка с оценкой '''Δo'''.
 
'''(i<sub>0</sub>, j<sub>0</sub>)''' – перевозка с оценкой '''Δo'''.
−
== Алгоритм ==
+
== Алгоритм 1 ==
−
Входные данные: '''m; n; np; {c<sub>11</sub>, c<sub>12</sub>, ..., c<sub>mn</sub>}; B<sub>0</sub>'''.
+
'''Входные данные:'''  
  
−
[[файл:АРП01.JPG]]
+
[[файл:BС011.png]]
  
−
Выходные данные: '''Δo; (i<sub>0</sub>, j<sub>0</sub>)'''.
+
'''Алгоритм:'''
−
* Заметим, что данный алгоритм применим для [[Классическая транспортная задача|транспортной задачи]], при этом '''np=n''', а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).
+
 
−
== Другие алгоритмы: ==
+
[[файл:РПО010.png]]
 +
 
 +
'''Выходные данные:'''  
 +
 
 +
[[файл:UVD001.png]]
 +
== Алгоритм 2 ==
 +
'''Входные данные:'''
 +
 
 +
[[файл:BС011.png]]
 +
 
 +
'''Алгоритм:'''
 +
 
 +
[[файл:РПО011.png]]
 +
 
 +
'''Выходные данные:'''
 +
 
 +
[[файл:UVD001.png]]
 +
*Заметим, что данный алгоритм применим для [[Транспортная задача|транспортной задачи]], при этом '''np=n''', а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).
 +
== [[Алгоритм|Другие алгоритмы:]] ==
 
{{Список АТЗ}}
 
{{Список АТЗ}}
 
== Ссылки ==
 
== Ссылки ==
−
* Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
+
*Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
−
* [[Участник:Logic-samara]]
+
*[[Участник:Logic-samara]]
−
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]]
+
[[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]]

Версия 13:15, 14 января 2024

Алгоритм расчёта потенциалов — это алгоритм нахождения потенциалов и оценок оптимальности для транспортной задачи с промежуточными пунктами (ТЗПП).

Обозначения

Введём обозначения:

m – число промежуточных пунктов (складов)(m>1);

n – число конечных пунктов (поставщиков и потребителей)(n>3);

np – число поставщиков (конечных пунктов c положительными значениями) (1<np<n);

cij – транспортный тариф (со знаком) на перевозку единицы продукции между i-ым промежуточным пунктом и j-ым конечным пунктом (тариф для перевозки (i,j));

B0 – базис решения (множество базисных перевозок решения);

ui – потенциал i-ого промежуточного пункта;

vj – потенциал j-ого конечного пункта;

Δij – оценка оптимальности для перевозки (i,j);

Δo – оценка оптимальности решения;

(i0, j0) – перевозка с оценкой Δo.

Алгоритм 1

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

Файл:BС011.png

Алгоритм:

Файл:РПО010.png

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

Файл:UVD001.png

Алгоритм 2

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

Файл:BС011.png

Алгоритм:

Файл:РПО011.png

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

Файл:UVD001.png

  • Заметим, что данный алгоритм применим для транспортной задачи, при этом np=n, а промежуточные пункты (склады) являются потребителями. Матрицы тарифов и оценок в алгоритме транспонированы (строки заменены на столбцы, а столбцы - на строки).

Другие алгоритмы:

Ссылки

  • Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.
  • Участник:Logic-samara
Источник — «https://allll.net/w/index.php?title=Алгоритм_расчёта_потенциалов_для_ТЗПП&oldid=122757»