Полезные материалы:

Примеры - Математическое программирование

Транспортная задача

Имеются три пункта поставки однородного груза А1, А2, А3 и пять пунктов В1, В2, В3, В4, В5 потребления этого груза. На пунктах А1, А2, А3 находится груз в количествах 90, 70, 110 тонн. В пункты В1, В2, В3, В4, В5 требуется доставить соответственно 50, 60, 50, 40, 70 тонн груза. Расстояния в сотнях километрах между пунктами поставки и потребления приведены в матрице-таблице D:

Найти такой план перевозок, при котором общие затраты будут минимальными.

УКАЗАНИЕ. 1) Считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое этот груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах.
2) для решения задачи использовать методы северо-западного угла и потенциалов.

Решение.

Составим математическую модель задачи:

Обозначим  - количество груза, перевезенного от поставщика i к потребителю j.

Становятся очевидными следующие ограничения (т.к. весь груз должен быть вывезен, и все потребности удовлетворены полностью):
    
   
    

  

При этом должна быть минимизирована целевая функция

Построим опорный план методом северо-западного угла:

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

Построим систему потенциалов.  - потенциалы, соответствующие поставщикам,  - потенциалы, соответствующие потребителям.
Полагаем U1=0, а далее Ui + Vj = dij для занятых клеток таблицы.
U1 + V1 = 9   V1 = 9
U1 + V2 = 1   V2 = 1
U2 + V2 = 4   U2 = 3
U2 + V3 = 6   V3 = 3
U3 + V4 = 5   U3 = 0  V4 = 5
U3 + V5 = 3   V5 = 3

 

         Проверим критерий оптимальности : Ui + Vj  dij для свободных клеток.

U1 + V3 = 3>1 на 2
U1 + V4 = 5=5
U1 + V5 = 3<6
U2 + V1 = 12>6 на 6
U2 + V4 = 8=8
U2 + V5 = 6>5 на 1
U3 + V1 = 9>2 на 7
U3 + V2 = 1<9
U3 + V3 = 3=3

Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (3 , 1)

Перебросим в ячейку (3 , 1) 50 единиц груза из ячейки (1 , 1).
Чтобы компенсировать недостаток в первой строке, перебросим те же 50 единиц груза из ячейки (2 , 3) в ячейку (1 , 3).
Теперь чтобы компенсировать недостаток в строке 2, перебросим из ячейки
(3 , 5) 50 единиц в ячейку (2 , 5).

Таким образом, образовался цикл, показанный в таблице пунктиром.

Получаем новую таблицу, для которой повторяем расчет потенциалов:

Полагаем U1=0, а далее Ui + Vj = dij для занятых клеток таблицы.
U1 + V2 = 1   V2 = 1
U1 + V3 = 1   V3 = 1
U2 + V2 = 4   U2 = 3
U2 + V5 = 5   V5 = 2
U3 + V5 = 3   U3 = 1
U3 + V1 = 2   V1 = 5
U3 + V4 = 5   V4 = 4

Проверим критерий оптимальности : Ui + Vj  dij для свободных клеток.

U1 + V1 = 1<9
U1 + V4 = 4<5
U1 + V5 = 2<6
U2 + V1 = 4<6
U2 + V3 =4<6
U2 + V4 =7<8
U3 + V2 =2<9
U3 + V3 =2<3

Критерий выполнен, значит, полученное решение оптимально.
Найдем минимальную стоимость перевозок.



Учебники
Предлагаем наиболее хорошие на наш взгляд учебники для самостоятельного изучения математики и экономики Comment

Справочники
Компактные справочные материалы, формулы по различным разделам высшей математики и экономической статистики. Comment

Онлайн калькуляторы
Некоторые задачи можно решить онлайн, введя числовые значения, с подробным решением. Comment