Построение экономико-математической модели

Запишем начальные условия задачи в форме табл. 1.

Таблица 1

Обозначим через x_ij (i = ; j = ) количество продукции, которое планируется перевезти от поставщика A_i потребителю B_j, а через f - суммарные затраты на производство и перевозку.

Непосредственно в таблице подсчитываем суммарные тарифы на производство и перевозку продукции из пункта A_i (i = ) в пункт B_j (j = ).

Целевая функция задачи запишется в виде:

f = 7x₁₁ + 10x₁₂ + 9x₁₃ + 5x₁₄ + 10x₂₁ + 7x₂₂ + 12x₂₃ + 8x₂₄ +

+ 10x₃₁ + 8x₃₂ + 5x₃₃ + 7x₃₄.                                                              (1)

Запишем ограничения, накладываемые мощностями поставщиков:

x₁₁ + x₁₂ + x₁₃ + x₁₄  540;

x₂₁ + x₂₂ + x₂₃ + x₂₄  660; (2)

x₃₁ + x₃₂ + x₃₃ + x₃₄  780.

Спрос пунктов потребления выражаем в виде равенств:

x₁₁ + x₂₁ + x₃₁ = 180;

x₁₂ + x₂₂ + x₃₂ = 720;                                                                         (3)

x₁₃ + x₂₃ + x₃₃ = 360;

x₁₄ + x₂₄ + x₃₄ = 480.

Если исключить обратные перевозки, должны выполняться ограничения:

x_ij  0 (i = ; j = ). (4)

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

Сравнивая суммарную мощность поставщиков 540 + 660 + 780 = 1980 с суммарным спросом пунктов потребления 180 + 720 + 360 + 480 = 1740, видим, что эти суммы не совпадают. Имеем открытую транспортную задачу.

Часть произведенной поставщиками продукции (1980-1740 = 240 единиц) останется нераспределенной. Введем в рассмотрение фиктивного потребителя В₅ со спросом, равным небалансу, т.е. 240 единицам, с одинаковыми затратами на перевозку, равными c_i5 = 0 (i = ). Пятый столбец будем рассматривать в последнюю очередь.

Построение исходного опорного плана

Построим опорный план по правилу минимального элемента.

В клетку (1; 4) с тарифом 5 впишем число х₁₄ = 480, удовлетворив спрос потребителя В₄ - четвертый столбец исключаем из рассмотрения.

В клетку (3; 3) с тарифом 5 впишем число х₃₃ = 360, удовлетворив спрос потребителя В₃ - третий столбец исключаем из рассмотрения.

В клетку (1; 1) с тарифом 7 впишем число х₁₁ = 60, исчерпав запасы поставщика А₁ - первую строку исключаем из рассмотрения.

В клетку (2; 2) с тарифом 7 впишем число х₂₂ = 660, исчерпав запасы поставщика А₂ - вторую строку исключаем из рассмотрения.

В клетку (3; 2) с тарифом 8 впишем число х₃₂ = 60, удовлетворив спрос потребителя В₂ - второй столбец исключаем из рассмотрения

В клетку (3; 1) с тарифом 10 впишем число х₃₁ = 120, удовлетворив спрос потребителя В₁ - первый столбец исключаем из рассмотрения

Оставшуюся у поставщика А₃ продукцию в объеме 240 единиц распределяем фиктивному потребителю В₅. Окончательно получаем табл. 2.

Таблица 2

Исходным опорным планом перевозок является

Х₁ = .

Этому плану соответствует значение целевой функции:

f (X₁) = 60 · 7 + 480 · 5 + 660 · 7 + 120 · 10 + 60 · 8 + 360 · 5 =

= 420 + 240 + 4620 + 1200 + 480 + 1800 = 10920

(без учета показателей фиктивного потребителя).

Определение оптимального плана

Условие для базисных клеток m + n - 1 = 3 + 5 - 1 = 7 выполняется.

Для определения потенциалов имеем систему уравнений:

u₁ + v₁ = 7;₁ + v₄ = 5;₂ + v₂ = 7;₃ + v₁ = 10;₃ + v₂ = 8;₃ + v₃ = 5;₃ + v₅ = 0.

Поскольку число уравнений системы на 1 меньше числа потенциалов (система неопределенная), положим u₁ = 0. Найдем остальные потенциалы и впишем их в табл. 3.

v₁ = 7 - 0 = 7;         v₄ = 5 - 0 = 5; u₃ = 10 - 7 = 3;

v₂ = 8 - 3 = 5;         v₃ = 5 - 3 = 2; v₅ = 0 - 3 = -3;

u₂ = 7 - 5 = 2.

Таблица 3

Определим оценки свободных клеток и впишем их в левые верхние углы клеток:

s₁₂ = 10 - (5 + 0) = 5;     s₁₃ = 8 - (2 + 0) = 6; s₁₅ = 0 - (-3 + 0) = 3;₂₁ = 10 - (7 + 2) = 1;                                     s₂₃ = 12 - (2 + 2) = 8; s₂₄ = 8 - (5 + 2) = 1;₂₅ = 0 - (-3 + 2) = 1;                                          s₃₄ = 7 - (5 + 3) = -1.

Имеется отрицательная оценка s₃₄ = -1. Начиная с нее строим замкнутый цикл:

(3, 4)⁽⁺⁾ - (3, 1)^(-) - (1, 1)⁽⁺⁾ - (1, 4)^(-).

Минимальной загрузкой (120) среди отрицательных клеток обладает (3, 1). Вычитаем 120 из загрузки клеток (3, 1), (1, 4) и добавляем 120 к загрузке клеток (1, 1), (3, 4).

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

Таблица 3

Отрицательных оценок нет. Следовательно, получен оптимальный план:

X* = Х₁ = .

По оптимальному плану Х* следует перевезти от поставщика А₁ потребителям В₁ и В₄ продукцию в количестве 180 и 360 единиц соответственно, от поставщика А₂ потребителю В₂ - 660 единиц, от поставщика А₃ - потребителям В₂, В₃ и В₄ - 60, 360 и 120 единиц соответственно.

При этом суммарные затраты на перевозку продукции от поставщиков к потребителям будут минимальными и составят f_min = 10800 денежных единиц.

У поставщика А₃ останется невостребованными 240 единиц продукции.