Транспортная задача — различия между версиями
(Новая страница: «[[Математическая модель ТЗ]] == Постановка задачи == Пусть имеется '''m''' п…») |
|||
Строка 1: | Строка 1: | ||
[[файл:ТЗ01.JPG|thumb|300|[[Математическая модель]] ТЗ]] | [[файл:ТЗ01.JPG|thumb|300|[[Математическая модель]] ТЗ]] | ||
+ | '''Транспортная задача''' – это задача оптимизации перевозок однородных грузов от поставщиков к потребителям. | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть имеется '''m''' поставщиков '''(A1,A2,…,Am)''' и '''n''' потребителей '''(B1,B2,…,Bn)''' однородного продукта. Пусть заданы объёмы поставок '''a<sub>i</sub>''' продукта поставщиком '''Ai''' и объёмы потребностей '''b<sub>j</sub>''' в продукте у потребителя '''Bj'''. Пусть известны транспортные расходы '''c<sub>ij</sub>''' на перевозку единицы продукта от поставщика '''Ai''' к потребителю '''Bj''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда классическая [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТЗ) формулируется следующим образом: | Пусть имеется '''m''' поставщиков '''(A1,A2,…,Am)''' и '''n''' потребителей '''(B1,B2,…,Bn)''' однородного продукта. Пусть заданы объёмы поставок '''a<sub>i</sub>''' продукта поставщиком '''Ai''' и объёмы потребностей '''b<sub>j</sub>''' в продукте у потребителя '''Bj'''. Пусть известны транспортные расходы '''c<sub>ij</sub>''' на перевозку единицы продукта от поставщика '''Ai''' к потребителю '''Bj''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда классическая [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТЗ) формулируется следующим образом: | ||
Строка 9: | Строка 10: | ||
[[Трёхиндексная транспортная задача|Транспортную задачу]] можно представить в виде таблицы | [[Трёхиндексная транспортная задача|Транспортную задачу]] можно представить в виде таблицы | ||
− | [[файл: | + | [[файл:ТЗ3.JPG]]. |
− | + | ||
== Условия разрешимости == | == Условия разрешимости == | ||
Для разрешимости задачи необходимо выполнение условий баланса: | Для разрешимости задачи необходимо выполнение условий баланса: | ||
Строка 17: | Строка 17: | ||
т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём. | т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём. | ||
− | |||
== Метод решения == | == Метод решения == | ||
Необходимо найти начальное опорное решение, например, методом северо-западного угла. | Необходимо найти начальное опорное решение, например, методом северо-западного угла. | ||
Затем транспортная задача решается методом потенциалов. | Затем транспортная задача решается методом потенциалов. | ||
− | |||
=== Метод северо-западного угла === | === Метод северо-западного угла === | ||
Метод северо-западного угла для нахождения допустимого решения транспортной задачи состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах. | Метод северо-западного угла для нахождения допустимого решения транспортной задачи состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах. | ||
Строка 29: | Строка 27: | ||
2.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности. | 2.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности. | ||
− | |||
=== Метод потенциалов === | === Метод потенциалов === | ||
Строка 44: | Строка 41: | ||
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>)'''. | ||
Переходим к пункту 3. | Переходим к пункту 3. | ||
− | |||
== Пример ТЗ == | == Пример ТЗ == | ||
[[файл:ТЗ10.JPG]] | [[файл:ТЗ10.JPG]] | ||
− | |||
=== Нахождение допустимого решения === | === Нахождение допустимого решения === | ||
[[файл:ТЗ11.JPG]] | [[файл:ТЗ11.JPG]] | ||
[[файл:ТЗ12.JPG]] | [[файл:ТЗ12.JPG]] | ||
− | [[файл: | + | [[файл:ТЗ15.JPG]] |
[[файл:ТЗ14.JPG]] | [[файл:ТЗ14.JPG]] | ||
− | |||
=== Решение методом потенциалов === | === Решение методом потенциалов === | ||
[[файл:ТЗ21.JPG]] | [[файл:ТЗ21.JPG]] | ||
[[файл:ТЗ22.JPG]] | [[файл:ТЗ22.JPG]] | ||
− | [[файл: | + | [[файл:ТЗ24.JPG]] |
− | + | ||
== Другие задачи: == | == Другие задачи: == | ||
*[[Каноническая задача]]; | *[[Каноническая задача]]; | ||
Строка 70: | Строка 63: | ||
*[[Задача целочисленного программирования]]; | *[[Задача целочисленного программирования]]; | ||
*[[Задача о рюкзаке]]. | *[[Задача о рюкзаке]]. | ||
− | |||
== Ссылки == | == Ссылки == | ||
* Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969. | * Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]] |
Версия 18:52, 13 января 2016
Транспортная задача – это задача оптимизации перевозок однородных грузов от поставщиков к потребителям.
Содержание
Постановка задачи
Пусть имеется 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.
Пример ТЗ
Нахождение допустимого решения
Решение методом потенциалов
Другие задачи:
- Каноническая задача;
- Производственная задача;
- Общая прямая задача линейного программирования;
- Общая двойственная задача линейного программирования;
- Распределительная задача;
- Задача о назначениях;
- Транспортная задача с промежуточными пунктами;
- Трёхиндексная транспортная задача;
- Задача целочисленного программирования;
- Задача о рюкзаке.
Ссылки
- Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
- Участник:Logic-samara