Транспортные задачи

Справочник / Студент / Линейное программирование / Транспортные задачи
Справочный материал Примеры Обратите внимание! Видео Модели Пройти тесты
Постановка транспортной задачи в матричной форме по критерию стоимости
В пунктах  LaTeX formula: A_{1}, A_{2}, ..., A_{m}   находится однородный груз в количествах LaTeX formula: a_{1}, a_{2}, ..., a_{m}  единиц соответственно. Этот груз необходимо доставить потребителям  LaTeX formula: B_{1}, B_{2}, ..., B_{n}   в количествах  LaTeX formula: b_{1}, b_{2}, ..., b_{n}   единиц соответственно. Известна стоимость перевозки LaTeX formula: c_{ij}  единицы груза от LaTeX formula: i-го поставщика (LaTeX formula: i=\overline{1,m}) к LaTeX formula: j-му LaTeX formula: (j=\overline{1,n}) потребителю. Требуется составить такой план перевозок, который полностью удовлетворяет спрос потребителя при минимальных суммарных транспортных издержках. 
Матрицы транспортной задачи (ТЗ) имеют вид:
1) матрица запаса груза 
LaTeX formula: A=\left [ a_{1}  LaTeX formula: a_{2}  LaTeX formula: ...   LaTeX formula: a_{m} ]; (12.27)
2) матрица потребности в грузе
LaTeX formula: B=\left [b_{1}  LaTeX formula: b_{2}  LaTeX formula: ...  LaTeX formula: b_{n}]; (12.28)
3) матрица тарифов перевозок 
LaTeX formula: C= LaTeX formula: \begin{bmatrix} c_{11} & c_{12} & ... & c_{1n} \\ c_{21} & c_{22} & ... & c_{2n} \\ ... & ... & ... & ... \\ c_{m1}& c_{m2} & ... & c_{mn} \end{bmatrix}; (12.29)
4) матрица перевозок: 
LaTeX formula: X= \begin{bmatrix} x_{11} & x_{12} & ... &x_{1n} \\ x_{21} & x_{22} & ... & x_{2n} \\ ... & ... & ... & ... \\ x_{m1}& x_{m2} & ... & x_{mn} \end{bmatrix}. (12.30)

Экономико-математическая модель задачи
Целевая функция:
LaTeX formula: min f(X)=c_{11}x_{11}+c_{12}x_{12}+...+c_{1n}x_{1n}+...+c_{m1}x_{m2}+...+c_{mn}x_{mn}, (12.31)
Система ограничений:
LaTeX formula: \sum_{j=1}^{n} x_{ij}=a_{i}  LaTeX formula: (i=\overline{1,m}), (12.32)
LaTeX formula: \sum_{i=1}^m} x_{ij}=b_{j}  LaTeX formula: (j=\overline{1,n}), (12.33)
LaTeX formula: x_{ij}\geq 0  LaTeX formula: (i=\overline{1,m};j=\overline{1,n}). (12.34)
План перевозок, удовлетворяющий условиям 12.32 – 12.33 – 12.34, называется допустимым. 
Допустимый план перевозок, минимизирующий целевую функцию 12.31, называется оптимальным.
Для того чтобы ТЗ имела допустимые планы, необходимо и достаточно выполнение равенства: 
 LaTeX formula: \sum_{i=1}^{m} a_{i}=\sum_{j=1}^{n} b_{j}. (12.35)
Модели транспортной задачи
Модель ТЗ называется закрытой, если суммарный запас груза у поставщиков равен суммарному спросу потребителей, т.е. выполняется условие 12.35.
Модель ТЗ называется открытой, если суммарный запас груза у поставщиков не равен суммарному спросу потребителей, т.е. выполняется одно из условий: 
LaTeX formula: \sum_{i=1}^{m} a_{i}>\sum_{j=1}^{n} b_{j}; (12.36)
 LaTeX formula: \sum_{i=1}^{m} a_{i}<\sum_{j=1}^{n} b_{j}. (12.37)
В процессе решения ТЗ открытую модель всегда необходимо преобразовывать в закрытую. 
В случае, когда выполняется условие 12.36, необходимо ввести фиктивного LaTeX formula: B_{n+1}  потребителя, потребность в грузе которого составит LaTeX formula: b_{n+1}= \sum_{i=1}^{m} a_{i}-\sum_{j=1}^{n} b_{j}, а все тарифы перевозок от поставщиков к фиктивному потребителю будут равны нулю. 
В случае, когда выполняется условие 12.37, необходимо ввести фиктивного поставщика  LaTeX formula: A_{m+1}, запас груза которого составитLaTeX formula: a_{m+1}= \sum_{j=1}^{n} b_{j}-\sum_{i=1}^{m} a_{i}, а все тарифы перевозок от фиктивного поставщика к потребителям будут равны нулю.
Построение исходного опорного плана
Построение опорного плана ТЗ будем выполнять в распределительной таблице по правилу «минимального элемента»:
1) выбираем клетку с минимальным тарифом и записываем в нее максимально возможное значение поставки;
2) из рассмотрения исключаем поставщика (и соответствующую ему строку), запасы которого исчерпаны, или потребителя (и соответствующий ему столбец), запросы которого полностью удовлетворены;
3) из оставшихся клеток снова выбираем клетку с наименьшим тарифом и записываем в нее максимально возможное значение поставки и т. д. 
Как только весь груз распределен, получаем опорный план, который должен содержать LaTeX formula: m+n-1  загруженных клеток.
Метод потенциалов
Введем числа LaTeX formula: u_{i}  LaTeX formula: (i=\overline{1;m}) и  LaTeX formula: v_{j}  LaTeX formula: (j=\overline{1;n}) которые будем называть потенциалами поставщиков и потребителей соответственно. 
Сумма потенциалов загруженной клетки LaTeX formula: (i; j) равна ее тарифу: 
 LaTeX formula: c_{ij}=u_{i}+v_{j}. (12.38)
Критерий оптимальности опорного плана: если все оценки свободных клеток неотрицательные, то план оптимальный. 
Чтобы найти оценку свободной клетки LaTeX formula: (i; j), необходимо из тарифа клетки вычесть сумму ее потенциалов: 
 LaTeX formula: \Delta _{ij}=c_{ij}-(u_{i}+v_{j}). (12.39)
Если среди оценок окажутся отрицательные, то клетку, которой соответствует наименьшая отрицательная оценка, называют перспективной. 
План перевозок можно улучшить, перераспределяя максимально возможное количество груза по циклу, который образует перспективная клетка с другими загруженными клетками. Пример перераспределения груза приведен на рисунке 12.6.
Решение ТЗ удобно представлять в распределительной таблице:
Пример 1. Решите транспортную задачу (в таблице указаны тарифы перевозок):
Решение. Имеем закрытую модель задачи 12.35.
По правилу минимального элемента заполняем распределительную таблицу 12.1. 
Наименьшие затраты на перевозку (LaTeX formula: 2 ден. ед.) соответствуют маршруту LaTeX formula: A_{3}-B_{1}, поэтому  LaTeX formula: x_{31}=min(110;100)=100, следовательно, LaTeX formula: x_{11}=0,  LaTeX formula: x_{21}=0, а соответствующие клетки таблицы свободны. 
Из оставшихся тарифов наименьший (LaTeX formula: 3 ден. ед.) соответствует маршруту LaTeX formula: A_{1}-B_{2}, поэтому LaTeX formula: x_{12}=min(40;40)=40, следовательно, LaTeX formula: x_{13}=0,  LaTeX formula: x_{22}=0,  LaTeX formula: x_{23}=0, а соответствующие клетки таблицы свободны. 
Следующим рассматриваем маршрут LaTeX formula: A_{2}-B_{3}. Тогда LaTeX formula: x_{23}=min(60;50)=50, а LaTeX formula: x_{33}=10.
Таблица 12.1
Опорный план должен содержать LaTeX formula: m+n-1=3+3-1=5  загруженных клеток. Так как полученный план содержит LaTeX formula: 4 загруженные клетки (одновременно исключались первая строка и второй столбец), в одну их свободных клеток запишем число LaTeX formula: 0, и эту клетку будем считать условно загруженной. Например, пусть  LaTeX formula: x_{22}=0 (таблица 12.2).
Заполним таблицу 12.2. Найдем потенциалы поставщиков и потребителей. 
Полагая один из потенциалов известным, например, LaTeX formula: u_{1}=0, по формуле 12.38 получим: 
LaTeX formula: v_{2}=3-0=3, LaTeX formula: u_{2}=4-3=1, LaTeX formula: v_{3}=7-1=6, LaTeX formula: u_3=8-6=2, LaTeX formula: v_{1}=2-2=0. 
По формуле 12.39 найдем оценки свободных клеток: 
LaTeX formula: \Delta _{11}=4-(0+0)=4,\Delta _{13}=9-(6+0)=3, 
LaTeX formula: \Delta _{21}=6-(0+1)=5,\Delta _{32}=5-(3+2)=0. 
Таблица 12.2
Так как среди оценок свободных отсутствуют отрицательные, то полученный план перевозок оптимальный.
План перевозок:  LaTeX formula: X^{*}=\begin{pmatrix} 0 &40 &0 \\ 0 & 0 &50 \\ 100 &0 & 10 \end{pmatrix}.
Стоимость перевозок: 
LaTeX formula: f(X^{*})=40\cdot 3+50\cdot 7+100\cdot 2+10\cdot 8=750  (ден. ед.).
Ответ: LaTeX formula: f(X^{*})=750 ден. ед., LaTeX formula: X^{*}=\begin{pmatrix} 0 &40 &0 \\ 0 & 0 &50 \\ 100 &0 & 10 \end{pmatrix}.
Пример 2. Требуется перевезти овощи из трех складов LaTeX formula: A_{1},A_{2},A_{3}, запас которых соответственно равен LaTeX formula: 50, 40 и LaTeX formula: 30т, четырем заводам LaTeX formula: B_{1},B_{2},B_{3},B_{4}, спрос которых равен соответственно LaTeX formula: 25, 30, 35 и LaTeX formula: 40 т. Известна матрица транспортных расходов на доставку LaTeX formula: 1 т овощей от поставщиков к потребителям: LaTeX formula: \left [ c_{ij} \right ]=\begin{bmatrix} 6 & 5 & 4 & 3\\ 6 & 2& 8 & 7\\ 5 & 5 & 6& 3 \end{bmatrix} . 
Определите оптимальный план перевозок, минимизирующий суммарные транспортные расходы. 
Решение. Найдем суммарный запас овощей: LaTeX formula: 50+40+30=120.
Найдем суммарный спрос на овощи: LaTeX formula: 25+30+35+40=130 . 
Так как спрос превышает запас, то имеем открытую модель ТЗ и поэтому вводим фиктивного поставщика LaTeX formula: A_{4}полагая, что у него имеется в запасе LaTeX formula: 10 т овощей. 
По правилу минимального элемента заполняем распределительную таблицу 12.3. 
Наименьшие затраты на перевозку (LaTeX formula: 2 ден. ед.) соответствуют маршруту LaTeX formula: A_{2}-B_{2}, поэтому LaTeX formula: x_{22}=min(30;40)=30, следовательно,  LaTeX formula: x_{12}=0, LaTeX formula: x_{32}=0, LaTeX formula: x_{42}=0, а соответствующие клетки таблицы свободны. 
Из оставшихся тарифов наименьший (LaTeX formula: 3 ден. ед.) соответствует маршрутам LaTeX formula: A_{1}-B_{4}  и LaTeX formula: A_{3}-B_{4}. Если выберем первый маршрут, то LaTeX formula: x_{14}=min(50;40)=40, следовательно, LaTeX formula: x_{24}=0, LaTeX formula: x_{34}=0, LaTeX formula: x_{44}=0, LaTeX formula: x_{44}=0, а соответствующие клетки таблицы свободны. 
Следующим рассматриваем маршрут LaTeX formula: A_{1}-B_{3}. Тогда LaTeX formula: x_{13}=min(10;35)=10, следовательно,  LaTeX formula: x_{11}=0, LaTeX formula: x_{12}=0, а соответствующие клетки таблицы свободны. 
Далее выбираем маршрут LaTeX formula: A_{3}-B_{1}. Тогда LaTeX formula: x_{31}=min(30;25)=25, следовательно, LaTeX formula: x_{21}=0,x_{41}=0, а соответствующие клетки таблицы свободны. 
Далее выбираем маршрут LaTeX formula: A_{3}-B_{3}. Тогда LaTeX formula: x_{33}=min(5;25)=5, следовательно, LaTeX formula: x_{34}=0, а соответствующая клетка свободна. 
Далее выбираем маршрут LaTeX formula: A_{2}-B_{3}. Тогда  LaTeX formula: x_{23}=min(10;20)=10, x_{43}=10. 
Таблица 12.3
Заполним таблицу 12.4. Найдем потенциалы поставщиков и потребителей. 
Полагая один из потенциалов известным, например, LaTeX formula: u_{1}=0, по формуле 12.38 получим:
 LaTeX formula: v_{3}=4-0=4, LaTeX formula: v_{4}=3-0=3, LaTeX formula: u_{2}=8-4=4, 
LaTeX formula: u_{3}=6-4=2, LaTeX formula: u_{4}=0-4=-4,v_{1}=5-2=3,v_{3}=2-4=-2.
По формуле 12.39 найдем оценки свободных клеток: 
LaTeX formula: \Delta _{11}=6-(3+0)=3, LaTeX formula: \Delta _{12}=5-(0-2)=7, 
LaTeX formula: \Delta _{21}=6-(4+3)=-1, LaTeX formula: \Delta _{24}=7-(4+3)=0, 
LaTeX formula: \Delta _{32}=5-(2-2)=5, LaTeX formula: \Delta _{34}=3-(2+3)=-2, 
LaTeX formula: \Delta _{41}=0-(-4+3)=1, LaTeX formula: \Delta _{42}=0-(-4-2)=6,
 LaTeX formula: \Delta _{44}=0-(-4+3)=1.
Таблица 12.4
Поскольку имеем две отрицательные оценки, то опорный план задачи не оптимальный. 
Клетку с оценкой LaTeX formula: \Delta _{34}=-2  считаем перспективной. Она образует цикл с клетками LaTeX formula: (3; 3), (1; 3) и LaTeX formula: (1; 4). Перемещая по циклу LaTeX formula: 5 т груза, получим новый план перевозок, представленный в таблице 12.5. 
Таблица 12.5
Выполняя аналогичные преобразования, заполним таблицы 12.6 – 12.8.
Таблица 12.6
Таблица 12.7 
Таблица 12.8
План перевозок: LaTeX formula: X^{*}=\begin{pmatrix} 0 &0 &35 &15 \\ 10 & 30 &0 &0 \\ 5 &0 &0 &25 \end{pmatrix}.
При этом потребитель LaTeX formula: B_{1} не получит LaTeX formula: 10 т овощей.
Стоимость перевозок: 
LaTeX formula: f(X^{*})=35\cdot 4+15\cdot 3+10\cdot 6+30\cdot 2+5\cdot 5+25\cdot 3=405  (ден. ед.).
Ответ: LaTeX formula: f(X^{*})=405 ден. ед., LaTeX formula: X^{*}=\begin{pmatrix} 0 &0 &35 &15 \\ 10 & 30 &0 &0 \\ 5 &0 &0 &25 \end{pmatrix}.
1. В случае, когда из распределительной таблицы одновременно исключается строка и столбец, задача считается вырожденной. Тогда в свободные клетки записывают число LaTeX formula: 0 и такие клетки условно считают загруженными (нуль-загрузка).
2. Все тарифы перевозок от поставщиков к фиктивному потребителю равны нулю. Все тарифы перевозок от фиктивного поставщика к потребителям также равны нулю.
Программа для просмотра моделей (МК-плеер)
© Сиротина И.К., 2013—2026