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

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

Справочник / Студент / Линейное программирование /

Справочный материал Примеры Обратите внимание! Видео Модели Пройти тесты

Постановка транспортной задачи в матричной форме по критерию стоимости

В пунктах $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: \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: B_{1},B_{2},B_{3},B_{4},$ спрос которых равен соответственно LaTeX formula: 25, 30, 35

т. Известна матрица транспортных расходов на доставку 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: 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. Все тарифы перевозок от поставщиков к фиктивному потребителю равны нулю. Все тарифы перевозок от фиктивного поставщика к потребителям также равны нулю.

Программа для просмотра моделей (МК-плеер) Файлы для скачивания

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