Математическая модель транспортной задачи

Условие: 
Однородный груз сосредоточен у m поставщиков в объемах a1, a2, ... am. 
Данный груз необходимо доставить n потребителям в объемах b1, b2 ... bn. 
Известны Cij , i=1,2,...m; j=1,2,...n — стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю. 
Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными.

Исходные данные транспортной задачи записываются в виде таблицы:

Исходные данные задачи могут быть представлены в виде:

  • вектора А=(a1,a2,...,am) запасов поставщиков
  • вектора B=(b1,b2,...,bn) запросов потребителей
  • матрицы стоимостей:

Математическая  модель транспортной задачи


Переменными (неизвестными) транспортной задачи являются xij , i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому j-му потребителю. 
Эти переменные могут быть записаны в виде матрицы перевозок:

Так как произведение Cij*Xij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:

По условию задачи требуется  обеспечить минимум суммарных затрат. 
Следовательно, целевая функция задачи имеет вид: 

Система ограничений задачи состоит  из двух групп уравнений. 
Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью и имеет вид: 

Вторая группа из n уравнений  выражает требование удовлетворить  запросы всех n потребителей полностью  и имеет вид:

Учитывая условие неотрицательности объемов перевозок математическая модель выглядит следующим образом:

В рассмотренной модели транспортной задачи предполагается, что суммарные  запасы поставщиков равны суммарынм запросам потребителей, т.е.:

Такая задача называется задачей с правильным балансом, а модель задачи закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а модель задачи — открытой.

Математическая формулировка транспортной задачи такова: найти переменные задачи X=(xij), i=1,2,...,m; j=1,2,...,n, удовлетворяющие системе ограничений (цифра 2 на математической модели) , (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1)

Пример 34.1

Составить математическую модель транспортной задачи, исходные данные которой приведены в таблице 34.2

Решение: 
1. Вводим переменные задачи (матрицу перевозок): 
 
2. Записываем матрицу стоимостей: 

3. Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X.

Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.

4. Составим систему ограничений задачи. 
Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X равняться запасам второго поставщика: 
 
Это означает, что запасы поставщиков вывозятся полностью.

Суммы перевозок, стоящих в каждом столбце матрицы X, должны быть равны  запросам соответствующих потребителей: 
 
Это означает, что запросы потребителей удовлетворяются полностью.

Необходимо также учитывать, что  перевозки не могут быть отрицательными: 

Ответ: Таким образом, математическая модель рассматриваемой задачи записывается следующим образом: 
Найти переменные задачи, обеспечивающие минимум целевой функции (1) и удовлетворяющие системе ограничений (2) и условиям неотрицательности (3). 

Данная программа  предоставит Вам решение транспортной задачи. Не стоит обращать внимание на объем полученного решения. Программа рисует все таблицы, для максимального понимания процесса решения. Возможно, некоторые таблицы Вам покажутся лишними. 
Решение транспортной задачи условно можно разделить на два этапа.  
В первую очередь, программа находит начальное опорное решение одним из возможных методов:

·  методом северо-западного угла 

·  методом наименьшего элемента 

·  методом Фогеля  
Далее, если потребуется, улучшает полученное решение методом потенциалов. 
Вы можете ознакомиться с примерами работы программы, при решении транспортной задачи, приведенными выше. 
Не нужно самостоятельно вводить в условие задачи фиктивного поставщика или потребителя, программа сделает это самостоятельно (если в этом есть необходимость). 
Если вы не нуждаетесь в комментариях к решению, выберите решить “без комментариев”. 
 
Будет приятно, если Вы поймете, что транспортная задача не сложнее квадратного уравнения! 


Введите исходные данные  
целые числа и ( или ) десятичные дроби ( например -0.15   2.12   10 )


Поставщик

Потребитель

Запас

B 1

B 2

B 3

A 1

A 2

A 3

Потребность

 

Найти начальное  опорное решение

                          

Решение

                  

       

другое  количество поставщиков и потребителей 

 


 

Задача :

    

У поставщиков A1 , A2 , A3 , находится соответственно 30 , 25 , 15 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 в количествах 20 , 35 , 15 единиц соответственно.


Стоимость доставки единицы продукции от поставщика A1 к указанным потребителям равна 5 , 1 , 3 ден.ед.


Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 4 , 5 , 4 ден.ед.


Стоимость доставки единицы продукции от поставщика A3 к указанным потребителям равна 2 , 3 , 4 ден.ед.


Требуется найти  оптимальное решение доставки продукции  от поставщиков к потребителям, минимизирующие стоимость доставки.


Решение :

    

Что мы будем делать?  
Найдем начальное решение методом минимального элемента. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.


Для разрешимости транспортной задачи необходимо, чтобы суммарные  запасы продукции у поставщиков  равнялись суммарной потребности  потребителей. Проверим это условие.


В нашем случае, потребность всех потребителей - 70 единиц продукции равна запасам всех поставщиков .


1)

    

Согласно условию  задачи составим таблицу. (тарифы cij располагаются в нижнем правом углу ячейки)


Поставщик

Потребитель

Запас

B 1

B 2

B 3

A 1

-

 

5  

-

 

1  

-

 

3  

30

A 2

-

 

4  

-

 

5  

-

 

4  

25

A 3

-

 

2  

-

 

3  

-

 

4  

15

Потребность

20

35

15

  

 

2)

    

Минимальный элемент  матрицы тарифов находится в  ячейке A1B2 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B2 наиболее рентабельный.


Запасы поставщика A1 составляют 30 единиц продукции. Потребность потребителя B2 составляет 35 единиц продукции. (см. таблицу пункта 1)


От поставщика A1 к потребителю B2 будем доставлять min = { 30 , 35 } = 30 единиц продукции.


Разместим в ячейку A1B2 значение равное 30


Мы полностью  израсходoвали запасы поставщика A1. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения.


Поставщик

Потребитель

Запас

B 1

B 2

B 3

A 1

-

 

5  

30

 

1  

-

 

3  

30

A 2

-

 

4  

-

 

5  

-

 

4  

25

A 3

-

 

2  

-

 

3  

-

 

4  

15

Потребность

20

35

15

  

 

3)

    

Минимальный элемент  матрицы тарифов находится в  ячейке A3B1 и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B1 наиболее рентабельный.


Запасы поставщика A3 составляют 15 единиц продукции. Потребность потребителя B1 составляет 20 единиц продукции. (см. таблицу пункта 2)


От поставщика A3 к потребителю B1 будем доставлять min = { 15 , 20 } = 15 единиц продукции.


Разместим в ячейку A3B1 значение равное 15


Мы полностью  израсходoвали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.


Поставщик

Потребитель

Запас

B 1

B 2

B 3

A 1

-

 

5  

30

 

1  

-

 

3  

30

A 2

-

 

4  

-

 

5  

-

 

4  

25

A 3

15

 

2  

-

 

3  

-

 

4  

15

Потребность

20

35

15

  

 

4)

    

Минимальный элемент  матрицы тарифов находится в  ячейке A2B1 и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B1 наиболее рентабельный.


Запасы поставщика A2 составляют 25 единиц продукции. Потребность потребителя B1 составляет 5 единиц продукции. (см. таблицу пункта 3)


От поставщика A2 к потребителю B1 будем доставлять min = { 25 , 5 } = 5 единиц продукции.


Разместим в ячейку A2B1 значение равное 5


Мы полностью  удовлетворили потребность потребителя B1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.


Поставщик

Потребитель

Запас

B 1

B 2

B 3

A 1

-

 

5  

30

 

1  

-

 

3  

30

A 2

5

 

4  

-

 

5  

-

 

4  

25

A 3

15

 

2  

-

 

3  

-

 

4  

15

Потребность

20

35

15

  

 

5)

    

Минимальный элемент  матрицы тарифов находится в  ячейке A2B3 и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B3 наиболее рентабельный.


Запасы поставщика A2 составляют 20 единиц продукции. Потребность потребителя B3 составляет 15 единиц продукции. (см. таблицу пункта 4)


От поставщика A2 к потребителю B3 будем доставлять min = { 20 , 15 } = 15 единиц продукции.


Разместим в ячейку A2B3 значение равное 15


Мы полностью  удовлетворили потребность потребителя B3. Вычеркиваем столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.


Поставщик

Потребитель

Запас

B 1

B 2

B 3

A 1

-

 

5  

30

 

1  

-

 

3  

30

A 2

5

 

4  

-

 

5  

15

 

4  

25

A 3

15

 

2  

-

 

3  

-

 

4  

15

Потребность

20

35

15

  

 

6)

    

Минимальный элемент  матрицы тарифов находится в  ячейке A2B2 и равен 5, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B2 наиболее рентабельный.


Запасы поставщика A2 составляют 5 единиц продукции. Потребность потребителя B2 составляет 5 единиц продукции. (см. таблицу пункта 5)


От поставщика A2 к потребителю B2 будем доставлять 5 единиц продукции.


Разместим в ячейку A2B2 значение равное 5


Мы полностью  израсходoвали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.


Поставщик

Потребитель

Запас

B 1

B 2

B 3

A 1

-

 

5  

30

 

1  

-

 

3  

30

A 2

5

 

4  

5

 

5  

15

 

4  

25

A 3

15

 

2  

-

 

3  

-

 

4  

15

Потребность

20

35

15

  

 

Заполненные нами ячейки будем называть базисными, остальные - свободными.


Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.


Количество базисных ячеек (задействованных маршрутов) равно 5, что и требовалось.


Мы нашли начальное  решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.


S0 = 1 * 30 + 4 * 5 + 5 * 5 + 4 * 15 + 2 * 15 = 165 ден. ед.


Общие затраты на доставку всей продукции, для начального решения , составляют 165 ден. ед. .


Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:


·  Находим потенциалы поставщиков и потребителей для имеющегося решения.


·  Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.


·  Выбираем свободную ячейку (с отрицательной оценкой), выбор которой, позволяет максимально снизить общую стоимость доставки всей продукции на данном шаге решения.


·  Находим новое решение, как минимум, не хуже предыдущего.


·  Вычисляем общую стоимость доставки всей продукции для нового решения.


Шаг 1

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.


Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. 
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя. 
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.  
(ui + vj = cij, где cij - тариф клетки AiBj)  
Поскольку, число базисных клеток - 5, а общее количество потенциалов равно 6, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.


Примем u2 = 0.


v1 + u2 = c21

v1 + u2 = 4

v1 = 4 - 0 = 4


v2 + u2 = c22

v2 + u2 = 5

v2 = 5 - 0 = 5


v3 + u2 = c23

v3 + u2 = 4

v3 = 4 - 0 = 4


v1 + u3 = c31

v1 + u3 = 2

u3 = 2 - 4 = -2


v2 + u1 = c12

v2 + u1 = 1

u1 = 1 - 5 = -4

Поставщик

Потребитель

U j

B 1

B 2

B 3

A 1

-

 

5  

30

 

1  

-

 

3  

u 1 = -4

A 2

5

 

4  

5

 

5  

15

 

4  

u 2 = 0

A 3

15

 

2  

-

 

3  

-

 

4  

u 3 = -2

V i

v 1 = 4

v 2 = 5

v 3 = 4

  

Найдем оценки свободных  ячеек следующим образом (в таблице  они располагаются в нижнем левом  углу ячейки):


11 = c11 - ( u1 + v1 ) = 5 - ( -4 + 4 ) = 5


13 = c13 - ( u1 + v3 ) = 3 - ( -4 + 4 ) = 3


32 = c32 - ( u3 + v2 ) = 3 - ( -2 + 5 ) = 0


33 = c33 - ( u3 + v3 ) = 4 - ( -2 + 4 ) = 2

Поставщик

Потребитель

U j

B 1

B 2

B 3

A 1

-

5

5  

30

 

1  

-

3

3  

u 1 = -4

A 2

5

 

4  

5

 

5  

15

 

4  

u 2 = 0

A 3

15

 

2  

-

0

3  

-

2

4  

u 3 = -2

V i

v 1 = 4

v 2 = 5

v 3 = 4

  

Математическая модель транспортной задачи 📙 Контрольная → 🆔 85917

Математическая модель транспортной задачи 📙 Контрольная → 🆔 85917

Математическая модель транспортной задачи