2015-04-01
364
Необходимо доставить от поставщиков 
(
) некоторый однородный груз в объеме 
единиц потребителям 
(
) с минимальными транспортными издержками. Потребность в данном товаре каждого 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, то решение называется невырожденным, а если их меньше, то вырожденным.
