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

Пример. Имеется m=2 пункта производства А1, А2, и n=3 пункта потребления В1, В2, В3 некоторого продукта. Перевозка из пунктов производства в пункты потребления 1 ед. продукции обходится в некоторую сумму, указанную в тарифной матрице.

Известно количество производимого продукта в каждом пункте производства и количество потребляемого в пункте потребления.

Составить план перевозок, при котором затраты минимальны.

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

1. Обозначаем Х1 – количество продукта, перевозимого из А1 в В1

Х2 – из А1в В2

Х3 – из А1 в В3

Х4 – из А2 в В1

Х5 – из А2 в В2

Х6 – из А2 в В3

Для запоминания закономерности нумерации Х_j приведем схему:

В1 В2 В3

А1 х1 х2 х3

А2 х4 х5 х6

2. Общие затраты на перевозку будут равны

q = 10x1 + 5x2 + 6x3 + 7x4 + 8x5 +12x6 → min

3.1 Ограничения на вывоз: из каждого пункта производства нельзя вывезти больше, чем там производят. Из А1 надо вывезти в В1 – ч1 ед., в В2- х2 ед., в В3 – х3 ед. Следовательно: Х1+ Х2 +Х3 ≤ 50. Аналогично для А2: Х4+ Х5 +Х6 ≤ 40.

3.2 Ограничения на привоз: в каждый пункт потребления нельзя привозить меньше, чем там потребляют.

В1: х1+х4 ≥ 30

В2: х2+х5 ≥ 30

В3: х3+х6 ≥ 25

Запишем общую систему ограничений, оставляя пустые места для нулевых элементов:

х1 + х2 + х3 ≤ 50

х4 + х5 + х6 ≤ 40

х1+ х4 ≥ 30

х2 + х5 ≥ 30

х3 + х6 ≥ 25

q = 10x1 + 5x2 + 6x3 + 7x4 + 8x5 +12x6 → min

Следует помнить, что при вводе пустые места надо заполнять нулями, т. е. 1-я строка 1 1 1 0 0 0 < 50 и т. д.

Замечание. Типичная ошибка: при составлении модели коэффициенты целевой функции матрицы (тариф на перевозку 10, 5 и т. д.) заносят в ограничения. Следует помнить, в ограничениях на ввоз вывоз коэффициенты могут быть равны только 1 или 0, а тарифные коэффициенты встречаются только в целевой функции.

ЛЕКЦИЯ №5.