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

Все оценки свободных  ячеек неотрицательные, следовательно, найдено оптимальное решение.

Ответ:

X _{1 опт} =

0

30

0

5

5

15

15

0

0

S_min = 1 * 30 + 4 * 5 + 5 * 5 + 4 * 15 + 2 * 15 = 165

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

Замечание: 
Задача имеет не единственное решение, т.к. среди оценок свободных ячеек присутствуют оценки равные нулю.

·  Построим цикл для ячейки A₃B₂.

Пусть ячейка A₃B₂, для которой мы строили цикл, имеет порядковый номер один.

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

Среди ячеек цикла A₃B₁ , A₂B₂ , номера которых четные, найдем ячейку, обладающую найменьшим значением.

min = { 15, 5 } = 5

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

Общие затраты на доставку всей продукции, по-прежнему, составляют S₀ = 165 +  ₃₂ * 5 = 165 + 0 * 5 = 165 ден. ед. .

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

X _{2 опт} =

0

30

0

10

0

15

10

5

0

портной задачи условно можно разделить на два этапа.  
В первую очередь, программа находит начальное опорное решение одним из возможных методов:

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

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

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

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

A ₂

A ₃

Потребность

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

Решение

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

Задача :

У поставщиков A₁ , A₂ , A₃ , находится соответственно 30 , 25 , 15 единиц однотипной продукции, которая должна быть доставлена потребителям B₁ , B₂ , B₃ в количествах 20 , 35 , 15 единиц соответственно.

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

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

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

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

Решение :

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

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

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

1)

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

Поставщик

Потребитель

Запас

B ₁

B ₂

B ₃

A ₁

30

A ₂

25

A ₃

15

Потребность

20

35

15

2)

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