Изменения
[[файл:ТЗ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''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда классическая [[Транспортная задача с промежуточными пунктами|транспортная задача]] (ТЗ) формулируется следующим образом:
[[Трёхиндексная транспортная задача|Транспортную задачу]] можно представить в виде таблицы
[[файл:ТЗ03ТЗ3.JPG]].
== Условия разрешимости ==
Для разрешимости задачи необходимо выполнение условий баланса:
т.е. необходимо, чтобы объём поставок продукта равнялся объёму потребностей в нём.
== Метод решения ==
Необходимо найти начальное опорное решение, например, методом северо-западного угла.
Затем транспортная задача решается методом потенциалов.
=== Метод северо-западного угла ===
Метод северо-западного угла для нахождения допустимого решения транспортной задачи состоит в последовательном назначении перевозок для клеток транспортной таблицы, находящихся в верхних (северных) строках и в левых (западных) столбцах.
2.Процесс заполнения клеток (распределения перевозок) для ТЗ продолжается до тех пор пока у поставщиков имеются нераспределённые остатки и у потребителей имеются неудовлетворённые потребности.
=== Метод потенциалов ===
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]]
[[файл:ТЗ13ТЗ15.JPG]]
[[файл:ТЗ14.JPG]]
=== Решение методом потенциалов ===
[[файл:ТЗ21.JPG]]
[[файл:ТЗ22.JPG]]
[[файл:ТЗ23ТЗ24.JPG]]
== Другие задачи: ==
*[[Каноническая задача]];
*[[Задача целочисленного программирования]];
*[[Задача о рюкзаке]].
== Ссылки ==
* Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа, М.,1969.
* [[Участник:Logic-samara]]
[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]
