Транспортная задача — различия между версиями
м (Отмена правки 121645, сделанной участником Logic-samara (обс.)) |
|||
(не показано 6 промежуточных версий этого же участника) | |||
Строка 29: | Строка 29: | ||
=== Метод потенциалов === | === Метод потенциалов === | ||
− | 1.Берём решение '''Xmxn''' и базис '''Zmxn''', найденные, например, с помощью '''алгоритма северо-западного угла'''. | + | 1.Берём решение '''Xmxn''' и базис '''Zmxn''', найденные, например, с помощью '''[[Алгоритм северо-западного угла для ТЗПП|алгоритма северо-западного угла]]'''. |
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>)'''. | ||
Строка 52: | Строка 52: | ||
[[файл:ТЗ22.JPG]] | [[файл:ТЗ22.JPG]] | ||
[[файл:ТЗ23.JPG]] | [[файл:ТЗ23.JPG]] | ||
+ | == Задачи транспортного типа: == | ||
+ | {{Список ЗТТ}} | ||
== Другие задачи: == | == Другие задачи: == | ||
− | + | {{Список ЗМП}} | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
== Ссылки == | == Ссылки == | ||
* Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969. | * Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] |
Текущая версия на 11:30, 19 февраля 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