Алгоритм минимального элемента для ТТЗ — различия между версиями
(начало) |
м |
||
| (не показано 12 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | + | '''Алгоритм минимального элемента для ТТЗ''' — это алгоритм построения опорного решения для [[Трёхиндексная транспортная задача|трёхиндексной транспортной задачи]] ([[ТТЗ]]). | |
| − | ''' | + | == Обозначения == |
| − | == | + | Введём обозначения: |
| − | |||
| − | + | '''m''' – число поставщиков; | |
| − | + | '''n''' – число потребителей; | |
| − | |||
| − | |||
| − | |||
| − | + | '''k''' – число продуктов; | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | ''' | + | '''A<sub>i</sub>''' - '''i'''-ый поставщик, '''1≤i≤m'''; |
| − | ''' | + | '''B<sub>j</sub>''' - '''j'''-ый потребитель, '''1≤j≤n'''; |
| − | ''' | + | '''C<sub>t</sub>''' - '''t'''-ый продукт, '''1≤t≤k'''; |
| − | ''' | + | '''a<sub>it</sub>''' - объём поставок продукта '''Сt''' от поставщика '''Ai'''; |
| − | ''' | + | '''b<sub>jt</sub>''' - объём потребностей в продукте '''Сt''' у потребителя '''Bj'''; |
| − | ''' | + | '''c<sub>ij</sub>''' - объём перевозок от поставщика '''Ai''' к потребителю '''Bj'''; |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | '''d<sub>ijt</sub>''' - транспортные расходы '''d<sub>ijt</sub>''' на перевозку единицы (тариф) продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj'''; | |
| − | + | ||
| − | == | + | '''x<sub>ijt</sub>''' - объём перевозок продукта '''Ct''' от поставщика '''Ai''' к потребителю '''Bj'''; |
| − | + | ||
| − | [[файл: | + | '''B<sub>0</sub>''' – базис решения (множество базисных элементов '''(i,j,t)'''); |
| − | [[файл: | + | |
| − | + | '''do''' – минимальный тариф на множестве '''E'''; | |
| − | { | + | |
| − | == Другие | + | '''(i<sub>0</sub>, j<sub>0</sub>, t<sub>0</sub>)''' – элемент с тарифом '''do''' и перевозкой равной нулю (до перераспределения); |
| − | {{Список | + | |
| + | '''Δx''' – перераспределяемая часть перевозки; | ||
| + | |||
| + | '''(i<sub>x</sub>, j<sub>x</sub>, t<sub>x</sub>)''' – элемент с перевозкой равной приращению '''Δx''' (до перераспределения). | ||
| + | == Алгоритм == | ||
| + | Входные данные: '''m; n; k; {a<sub>11</sub>, a<sub>12</sub>, …, a<sub>mk</sub>}; {b<sub>11</sub>, b<sub>12</sub>, …, b<sub>nk</sub>}; {c<sub>11</sub>, c<sub>12</sub>, …, c<sub>mn</sub>}; {d<sub>111</sub>, d<sub>112</sub>, ..., d<sub>mnk</sub>}'''. | ||
| + | |||
| + | [[файл:АМЭ03.JPG]] | ||
| + | |||
| + | [[файл:АМЭ04.JPG]] | ||
| + | |||
| + | Выходные данные: '''{x<sub>111</sub>, x<sub>112</sub>, …, x<sub>mnk</sub>}'''; | ||
| + | ''' {x<sub>111</sub>, x<sub>112</sub>, …, x<sub>m+1 n+1 k+1</sub>}'''. | ||
| + | *Заметим, что при отсутствии опорного решения исходной задачи (после завершения работы алгоритма), возможно использование опорного решения вспомогательной задачи. Для этого нужно решить вспомогательную задачу [[Трёхиндексная транспортная задача|методом потенциалов]]. | ||
| + | == [[Алгоритм|Другие алгоритмы:]] == | ||
| + | {{Список АТЗ}} | ||
== Ссылки == | == Ссылки == | ||
| − | + | *Кривопалов Ю. А. Метод минимального элемента для нахождения опорного решения для трёхиндексной транспортной задачи. М., ВИМИ, 1990г. деп. № Д08222. | |
| − | *Кривопалов Ю. А. Метод | + | *Кривопалов Ю. А. Метод минимального элемента для нахождения опорного решения для трёхиндексной транспортной задачи. Сборник ХII конференции «Наука. Творчество» 2016, Самара, Т.1. |
| − | *Кривопалов Ю. А. Метод | ||
*[[Участник:Logic-samara]] | *[[Участник:Logic-samara]] | ||
| − | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория: | + | [[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Алгоритмы]] |
Текущая версия на 05:54, 22 марта 2025
Алгоритм минимального элемента для ТТЗ — это алгоритм построения опорного решения для трёхиндексной транспортной задачи (ТТЗ).
Содержание
Обозначения
Введём обозначения:
m – число поставщиков;
n – число потребителей;
k – число продуктов;
Ai - i-ый поставщик, 1≤i≤m;
Bj - j-ый потребитель, 1≤j≤n;
Ct - t-ый продукт, 1≤t≤k;
ait - объём поставок продукта Сt от поставщика Ai;
bjt - объём потребностей в продукте Сt у потребителя Bj;
cij - объём перевозок от поставщика Ai к потребителю Bj;
dijt - транспортные расходы dijt на перевозку единицы (тариф) продукта Ct от поставщика Ai к потребителю Bj;
xijt - объём перевозок продукта Ct от поставщика Ai к потребителю Bj;
B0 – базис решения (множество базисных элементов (i,j,t));
do – минимальный тариф на множестве E;
(i0, j0, t0) – элемент с тарифом do и перевозкой равной нулю (до перераспределения);
Δx – перераспределяемая часть перевозки;
(ix, jx, tx) – элемент с перевозкой равной приращению Δx (до перераспределения).
Алгоритм
Входные данные: m; n; k; {a11, a12, …, amk}; {b11, b12, …, bnk}; {c11, c12, …, cmn}; {d111, d112, ..., dmnk}.
Выходные данные: {x111, x112, …, xmnk}; {x111, x112, …, xm+1 n+1 k+1}.
- Заметим, что при отсутствии опорного решения исходной задачи (после завершения работы алгоритма), возможно использование опорного решения вспомогательной задачи. Для этого нужно решить вспомогательную задачу методом потенциалов.
Другие алгоритмы:
- алгоритм северо-западного угла для ТЗ;
- алгоритм северо-западного угла для ТЗПП;
- алгоритм расчёта потенциалов для ТЗ;
- алгоритм расчёта потенциалов для ТЗПП;
- алгоритм перераспределения перевозок для ТЗ;
- алгоритм перераспределения перевозок для ТЗПП;
- алгоритм решения ТЗПП с запретами;
- алгоритм минимального элемента для ТТЗ;
- алгоритм расчёта потенциалов для ТТЗ;
- алгоритм перераспределения перевозок для ТТЗ.
Ссылки
- Кривопалов Ю. А. Метод минимального элемента для нахождения опорного решения для трёхиндексной транспортной задачи. М., ВИМИ, 1990г. деп. № Д08222.
- Кривопалов Ю. А. Метод минимального элемента для нахождения опорного решения для трёхиндексной транспортной задачи. Сборник ХII конференции «Наука. Творчество» 2016, Самара, Т.1.
- Участник:Logic-samara
