|
|
| Строка 1: |
Строка 1: |
| − | [[файл:ТЗ01.JPG|thumb|300|[[Математическая модель]] ТЗ]]
| + | #redirect [[Транспортная задача]] |
| − | == Постановка задачи ==
| + | |
| − | Пусть имеется '''m''' поставщиков '''(A1,A2,…,Am)''' и '''n''' потребителей '''(B1,B2,…,Bn)''' однородного продукта. Пусть заданы объёмы поставок '''a<sub>i</sub>''' продукта поставщиком '''Ai''' и объёмы потребностей '''b<sub>j</sub>''' в продукте у потребителя '''Bj'''. Пусть известны транспортные расходы '''c<sub>ij</sub>''' на перевозку единицы продукта от поставщика '''Ai''' к потребителю '''Bj''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда классическая [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТЗ) формулируется следующим образом:
| + | |
| − | | + | |
| − | [[файл:ТЗ01.JPG]],
| + | |
| − | | + | |
| − | где '''x<sub>ij</sub>''' - объём перевозок продукта от поставщика '''Ai''' к потребителю '''Bj'''.
| + | |
| − | | + | |
| − | [[Трёхиндексная транспортная задача|Транспортную задачу]] можно представить в виде таблицы
| + | |
| − | | + | |
| − | [[файл:ТЗ3.JPG]].
| + | |
| − | | + | |
| − | == Условия разрешимости ==
| + | |
| − | Для разрешимости задачи необходимо выполнение условий баланса:
| + | |
| − | | + | |
| − | [[файл:ТЗ02.JPG]],
| + | |
| − | | + | |
| − | т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём.
| + | |
| − | | + | |
| − | == Метод решения ==
| + | |
| − | Необходимо найти начальное опорное решение, например, методом северо-западного угла.
| + | |
| − | | + | |
| − | Затем транспортная задача решается методом потенциалов.
| + | |
| − | | + | |
| − | === Метод северо-западного угла ===
| + | |
| − | Метод северо-западного угла для нахождения допустимого решения транспортной задачи состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах.
| + | |
| − | | + | |
| − | 1.Удовлетворяем потребности потребителей '''(b<sub>j</sub>>0)''' за счёт поставщиков '''(a<sub>i</sub>>0)''', т.е. назначаем соответствующие перевозки по формулам: '''x<sub>ij</sub>=min(ai,bj), ai=ai-x<sub>ij</sub>, b<sub>j</sub>=b<sub>j</sub>-x<sub>ij</sub>'''.
| + | |
| − | | + | |
| − | 2.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности.
| + | |
| − | | + | |
| − | === Метод потенциалов ===
| + | |
| − |
| + | |
| − | 1.Берём решение '''Xmxn''' и базис '''Zmxn''', найденные, например, с помощью '''алгоритма северо-западного угла'''.
| + | |
| − | | + | |
| − | 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>)''' с помощью '''[[Алгоритм расчёта потенциалов|алгоритма расчёта потенциалов]]''' и оценок оптимальности.
| + | |
| − | | + | |
| − | 4.Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''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>)'''.
| + | |
| − | Переходим к пункту 3.
| + | |
| − | | + | |
| − | == Пример ТЗ ==
| + | |
| − | [[файл:ТЗ10.JPG]]
| + | |
| − | | + | |
| − | === Нахождение допустимого решения ===
| + | |
| − | [[файл:ТЗ11.JPG]]
| + | |
| − | [[файл:ТЗ12.JPG]]
| + | |
| − | [[файл:ТЗ15.JPG]]
| + | |
| − | [[файл:ТЗ14.JPG]]
| + | |
| − | | + | |
| − | === Решение методом потенциалов ===
| + | |
| − | [[файл:ТЗ21.JPG]]
| + | |
| − | [[файл:ТЗ22.JPG]]
| + | |
| − | [[файл:ТЗ24.JPG]]
| + | |
| − | | + | |
| − | == Другие задачи: ==
| + | |
| − | *[[Каноническая задача]];
| + | |
| − | *[[Производственная задача]];
| + | |
| − | *[[Общая прямая задача линейного программирования]];
| + | |
| − | *[[Общая двойственная задача линейного программирования]];
| + | |
| − | *[[Распределительная задача]];
| + | |
| − | *[[Задача о назначениях]];
| + | |
| − | *[[Транспортная задача с промежуточными пунктами]];
| + | |
| − | *[[Трёхиндексная транспортная задача]];
| + | |
| − | *[[Задача целочисленного программирования]];
| + | |
| − | *[[Задача о рюкзаке]].
| + | |
| − | | + | |
| − | == Ссылки ==
| + | |
| − | * Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
| + | |
| − | * [[Участник:Logic-samara]]
| + | |
| − | [[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]
| + | |
