Транспортная задача — различия между версиями
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 17: | Строка 17: | ||
т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём. | т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём. | ||
| − | == Метод решения == | + | == [[Алгоритмы решения транспортных задач|Метод решения]] == |
| − | Необходимо найти начальное опорное решение, например, методом северо-западного угла. | + | Необходимо найти начальное опорное решение, например, [[Алгоритм северо-западного угла для ТЗ|методом северо-западного угла]]. |
| − | Затем транспортная задача решается методом потенциалов. | + | Затем транспортная задача решается [[Алгоритм расчёта потенциалов для ТЗ|методом потенциалов]]. |
| − | === Метод северо-западного угла === | + | === [[Алгоритм северо-западного угла для ТЗ|Метод северо-западного угла]] === |
Метод северо-западного угла для нахождения допустимого решения транспортной задачи состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах. | Метод северо-западного угла для нахождения допустимого решения транспортной задачи состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах. | ||
| Строка 27: | Строка 27: | ||
2.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности. | 2.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности. | ||
| − | === Метод потенциалов === | + | === [[Алгоритм расчёта потенциалов для ТЗ|Метод потенциалов]] === |
1.Берём решение '''Xmxn''' и базис '''Zmxn''', найденные, например, с помощью '''[[Алгоритм северо-западного угла для ТЗ|алгоритма северо-западного угла]]'''. | 1.Берём решение '''Xmxn''' и базис '''Zmxn''', найденные, например, с помощью '''[[Алгоритм северо-западного угла для ТЗ|алгоритма северо-западного угла]]'''. | ||
| Строка 33: | Строка 33: | ||
2.Определяем значение целевой функции '''L=ΣΣc<sub>ij</sub>x<sub>ij</sub>''' и базис опорного решения '''Bo={(i,j)|z<sub>ij</sub>=1}'''. | 2.Определяем значение целевой функции '''L=ΣΣc<sub>ij</sub>x<sub>ij</sub>''' и базис опорного решения '''Bo={(i,j)|z<sub>ij</sub>=1}'''. | ||
| − | 3.Определяем оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>)''' с помощью '''[[Алгоритм расчёта потенциалов для | + | 3.Определяем оценку '''Δo''' и элемент '''(i<sub>o</sub>,j<sub>o</sub>)''' с помощью '''[[Алгоритм расчёта потенциалов для ТЗ|алгоритма расчёта потенциалов и оценок оптимальности]]'''. |
4.Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxn''' - оптимальное и конец работы. | 4.Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxn''' - оптимальное и конец работы. | ||
| − | 5.Определяем оценку '''Δx''', элемент '''(i<sub>x</sub>,j<sub>x</sub>)''' и новое опорное решение '''Xmxn''' с помощью '''[[Алгоритм перераспределения перевозок для | + | 5.Определяем оценку '''Δx''', элемент '''(i<sub>x</sub>,j<sub>x</sub>)''' и новое опорное решение '''Xmxn''' с помощью '''[[Алгоритм перераспределения перевозок для ТЗ|алгоритма перераспределения перевозок]]'''. |
6.Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i<sub>x</sub>,j<sub>x</sub>)U(i<sub>o</sub>,j<sub>o</sub>)'''. | 6.Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i<sub>x</sub>,j<sub>x</sub>)U(i<sub>o</sub>,j<sub>o</sub>)'''. | ||
| Строка 62: | Строка 62: | ||
*Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969. | *Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969. | ||
*[[Участник:Logic-samara]] | *[[Участник:Logic-samara]] | ||
| − | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] | + | [[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] |
Текущая версия на 15:18, 6 апреля 2023
Транспортная задача – это задача оптимизации перевозок однородных грузов от поставщиков к потребителям.
Содержание
Постановка задачи
Пусть имеется m поставщиков (A1,A2,…,Am) и n потребителей (B1,B2,…,Bn) однородного продукта. Пусть заданы объёмы поставок ai продукта поставщиком Ai и объёмы потребностей bj в продукте у потребителя Bj. Пусть известны транспортные расходы cij на перевозку единицы продукта от поставщика Ai к потребителю Bj и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда классическая транспортная задача (ТЗ) формулируется следующим образом:
где xij - объём перевозок продукта от поставщика Ai к потребителю Bj.
Транспортную задачу можно представить в виде таблицы
Условия разрешимости
Для разрешимости задачи необходимо выполнение условий баланса:
т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём.
Метод решения
Необходимо найти начальное опорное решение, например, методом северо-западного угла.
Затем транспортная задача решается методом потенциалов.
Метод северо-западного угла
Метод северо-западного угла для нахождения допустимого решения транспортной задачи состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах.
1.Удовлетворяем потребности потребителей (bj>0) за счёт поставщиков (ai>0), т.е. назначаем соответствующие перевозки по формулам: xij=min(ai,bj), ai=ai-xij, bj=bj-xij.
2.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности.
Метод потенциалов
1.Берём решение Xmxn и базис Zmxn, найденные, например, с помощью алгоритма северо-западного угла.
2.Определяем значение целевой функции L=ΣΣcijxij и базис опорного решения Bo={(i,j)|zij=1}.
3.Определяем оценку Δo и элемент (io,jo) с помощью алгоритма расчёта потенциалов и оценок оптимальности.
4.Проверяем решение на оптимальность. Если Δo=0, то решение Xmxn - оптимальное и конец работы.
5.Определяем оценку Δx, элемент (ix,jx) и новое опорное решение Xmxn с помощью алгоритма перераспределения перевозок.
6.Определяем новое значение целевой функции L=L-ΔoΔx и новый базис Bo=Bo\(ix,jx)U(io,jo). Переходим к пункту 3.
Пример ТЗ
Нахождение допустимого решения методом северо-западного угла
Решение методом потенциалов
Другие задачи:
- Транспортная задача;
- Распределительная задача;
- Задача о назначениях;
- Транспортная задача с промежуточными пунктами;
- Транспортная задача с промежуточными пунктами с запретами;
- Транспортная задача с промежуточными пунктами и ограничением по транзиту;
- Открытая транспортная задача с промежуточными пунктами 1;
- Открытая транспортная задача с промежуточными пунктами 2;
- Открытая транспортная задача с промежуточными пунктами 3;
- Открытая транспортная задача с промежуточными пунктами 4;
- Трёхиндексная транспортная задача.
Ссылки
- Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
- Участник:Logic-samara
