Необходимо доставить от поставщиков () некоторый однородный груз в объеме единиц потребителям () с минимальными транспортными издержками. Потребность в данном товаре каждого j- го потребителя известна и составляет единиц. Известны также - величины стоимости перевозки единицы груза от i– го поставщика к j– му потребителю.
Транспортная задача, для которой выполняется условие
, (3.60)
называется закрытой, в противном случае – открытой.
Обозначим количество единиц поставляемого груза от i– го поставщика к j– му потребителю через и занесем все данные в таблицу:
Таблица 3.31. Исходные данные в общем виде для транспортной задачи
Поставщики | Потребители | Запасы | |||||
1 | 2 | … | j | … | n | ||
1 | … | … | |||||
2 | … | … | |||||
… | … | … | … | … | … | … | … |
i | … | … | |||||
… | … | … | … | … | … | … | … |
m | … | … | |||||
Спрос потребителей | … | … |
Учитывая, что решение открытой транспортной задачи сводится к решению закрытой, сформулируем математическую модель закрытой задачи.
|
|
Математическое отражение цели задачи – минимизация суммарных затрат на перевозку груза – имеет вид
(3.61)
Ограничения задачи:
1.Груз от каждого поставщика должен быть вывезен полностью в силу условия (1):
(3.62)
2.Спрос каждого потребителя в продукции должен быть удовлетворен:
(3.63)
3.Объемы перевозок должны быть неотрицательными:
, (). (3.64)
Определение. Всякое неотрицательное решение систем линейных уравнений (3.62) и (3.63), где (), определяемое матрицей , называется планом транспортной задачи.
3.5.2. Методы построения исходного опорного плана
Теорема 3.9. Ранг матрицы из коэффициентов при неизвестных системы ограничений транспортной задачи равен m+n-1, где m и n - количество поставщиков и потребителей соответственно.
Из теоремы следует, что опорное решение задачи должно содержать m+n-1 базисных и mn-(m+n-1) небазисных, равных нулю неизвестных.
Определение. Циклом, или замкнутым контуром, называется последовательность клеток (i, j) таблицы 3.31 транспортной задачи, в которой каждые две рядом стоящие клетки находятся в одной строке или в одном столбце, при этом первая и последняя клетки совпадают.
Например, μ=[(1,2),(1,4),(3,4),(3,2),(1,2)] есть цикл (таблица 3.32).
Циклы могут быть самой разнообразной конфигурации, однако количество вершин в них всегда четно, и повороты линий цикла производятся только под прямым углом.
Таблица 3.32. Цикл транспортной задачи
j i | 1 | 2 | 3 | 4 |
1 | ||||
2 | ||||
3 |
Решение транспортной задачи будет ацикличным, если в таблице с этим решением невозможно построить ни одного цикла, в вершинах которого были бы все занятые клетки, или если для любой свободной клетки таблицы можно построить только один цикл, содержащий эту свободную клетку, а остальные вершины будут в занятых клетках. Опорное решение транспортной задачи должно быть ацикличным.
|
|
Если в опорном решении транспортной задачи число отличных от нуля неизвестных равно m+n-1, то решение называется невырожденным, а если их меньше, то вырожденным.