Транспортная задача
Математическая модель транспортной задачи. Важным частным случаем задачи линейного программирования является транспортная задача.
- предложения поставщиков,
- спросы потребителей,
где т - число поставщиков, - число потребителей.
Матрица затрат
- коэффициент затрат - затраты на перевозку единицы груза от i – поставщика к j – потребителю
Тогда система ограничений примет вид
, (1)
(2)
Математическая формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (1), (2) найти такое решение , при котором значение целевой функции минимально
Произвольное допустимое решение - распределение поставок
поставка клетки
Транспортная задача, приведенная в примере, обладает важной особенностью: предложения поставщиков равны спросу потребителей, т.е.
. (7)
Такие транспортные задачи называются закрытыми. В противном случае транспортная задача называется открытой
Особенности математической модели транспортной задачи:
-
система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме);
-
коэффициенты при переменных системы ограничений равны единице или нулю;
-
каждая переменная входит в систему ограничений два раза: один раз - в систему (1) и один раз - в систему (2).
Пример 1. Имеются три поставщика и четыре потребителя. Предложения поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары "поставщик — потребитель" сведены в таблицу поставок (табл. 1).
Табл.1
Постав -щики |
Предло-жения поставщиков |
Потребители и их спрос |
|||
1 |
2 |
3 |
4 |
||
20 |
110 |
40 |
110 |
||
1 |
60 |
1
|
2
|
5
|
3
|
2 |
120 |
1
|
6
|
5
|
2
|
3 |
100 |
6
|
3
|
7
|
4
|
Уравнения балансов для каждой строки таблицы поставок, т. е.
Уравнения балансов составляем для каждого столбца таблицы поставок:
.
Рассмотрим закрытую транспортную задачу.
Модификация симплекс - метода применительно к транспортной задаче называется распределительным методом.
Число базисных переменных ТЗ равно рангу системы линейных уравнений (максимальному числу линейно независимых уравнений в системе ограничений).
Теорема 1. Ранг системы уравнений (1), (2) равен .
Основное следствие теоремы 1 - число базисных (основных) переменных закрытой транспортной задачи равно , где т - число поставщиков, п — число потребителей.
Распределение поставок называется базисным, если переменные, соответствующие заполненным клеткам, можно принять за базисные переменные.
Клетки, отвечающие базисным переменным - базисные, «заполненные» клетки;
клетки, соответствующие свободным переменным, — свободные или пустые.