Решение задачи традиционными методами

Построение математической модели. Суммарные затраты, связанные с распределением объемов финансирования Х_ij из каждого i-ro источника в каждом j-ом периоде, можно записать в таком виде:m n

. (3.3.1.2)

Совокупность систем линейных ограничений (см.выше), граничных условий (3.3.1.1) и линейной целевой функции (3.3.1.2) образует математическую модель задачи, которую часто называют транспортной.

Рассмотрим один из эффективных алгоритмов решения транспортной задачи метод потенциалов. В качестве начального допустимого решения опорного плана возьмем план, приведенный в табл. 3.3.1.2.

Основой вычислительного процесса (алгоритма) этого метода является определение критерия оптимальности вида:

где C_ij – фактические затраты, связанные с выделением единицы денежных ресурсов из i-ro источника в j-ом периоде,

Z_ij – расчетные затраты, связанные с выделением единицы денежных ресурсов из i-ro источника в j-ом периоде.

Расчетные затраты Z_ij определяются только для клеток, куда финансовые ресурсы не распределены.

Если все d_ij>0 (i=1,2,..., m), (j=1,2,..., n), то полученное допустимое решение (опорный план) является оптимальным_, если нет_, то с помощью этого критерия оптимизации можно указать способ улучшения решения.

Таблица 3.3.1.2

Алгоритм решения.

Алгоритм решения включает следующие основные этапы:

1. Составление и решение системы уравнений. Вводятся условные цены –оценки единицы ресурса для каждого поставщика U_i(i=1,2,..., m) и каждого потребителя V (j=1,2,..., n). Эти оценки или, как их чаще называют_, потенциалы выступают в задаче как локальные цены (или наценки к единой цене), создающие заинтересованность в правильном распределении ресурсов. Так_, цена в пункте потребления Vj равна цене в пункте поставщика U_j плюс наценка С_ij. В нашей задаче наценка С_ij представляет собой дополнительные затраты на выделение единицы ресурса из i-ro источника в j-ом периоде. Таким образом:

V_J=U₁+C_1J.

С целью нахождения значений V_j (j=1,2,..., n) и U_i (i=1,2,..._, m) составляются уравнения для клеток, в которые распределены ресурсы в опорном плане:

V₃–U₁=C₁₃=24

V₂–U₂=C₂₂=18

V₁–U₃=C₃₁=19

V₂–U₃=C₃₂=10

V₁–U₄=C₄₁=3

V₃–U₃=C₃₃=100;

V₄–U₄=C₄₄=8.

Мы имеем 7 уравнений и 8 неизвестных, поэтому одной из искомых переменных наиболее часто встречающейся в уравнениях, для облегчения счета необходимо присвоить произвольное значение равное нулю. В нашей системе уравнений чаще всех встречается переменная U₃. Предположим, U₃ = 0. Последовательно решая соответствующие уравнения, получим: V, = 19, V₂ = 10, V₃ = 100, U, = 76, U₂=–8, U₄=16, V₄=24.

2. Определение расчетных значений Z_ij.

Z_ij=V_j–U_i

При этом используются те индексы i и j, на пересечении которых в соответствующих клетках ресурсы не распределены;

Z₁₁=V₁–U₁=19–76=–57;

Z₁₂=V₂–U₁=10–76=–66;

Z₁₄=V₄–U₁=24–76=–52;

Z₂₁=V₁–U₂=19+8=27;

Z₂₃=V₃–U₂=100+8=108;

Z₂₄=V₄–U₂=24+8=32;

Z₃₄=V₄–U₃=24+0=24;

Z₄₂=V₂–U₄=10–16=–6;

Z₄₃=V₃–U₄=100–16=84.

3. Определение значений d_t и проверка условия оптимальности.

Если все d>0 (i=1,2,..., m), (j=1,2,..., n), то полученное допустимое решение (опорный план) является оптимальным, если нет, то переходят к новому:

d₁₁=C₁₁–Z₁₁=70+57=127;

d₁₂=C₁₂–Z₁₂=38+66=104;

d₁₄=С₁₄–Z₁₄=92+52=144;

d₂₁=C₂₁–Z₂₁=58–27=31;

d₂₃=C₂₃–Z₂₃=56–108=–52;

d₂₄=C₂₄–Z₂₄=72–32=40;

d₃₄=C₃₄–Z₃₄=30–24=6;

d₄₂=C₄₂–Z₄₂=36+6=42;

d₄₃=C₄₃–Z₄₃=121–84=37.

В нашей задаче не все d₂₃>0, а это означает, что решение еще неоптимально, и мы переходим к определению нового опорного плана.

4. Определение нового опорного плана с меньшим значением целевой функции. Для этого в решение вводится та переменная X_ij, которой отвечает наименьшее отрицательное значение d_ij. Вводя ее, одновременно изменяют величины других переменных, по меньшей мере в трех заполненных клетках, чтобы не нарушались итоговые величины в строках и столбцах таблицы – a, b. Для этого строят многоугольник, одна из вершин которого находится в свободной клетке, а остальные – в заполненных ресурсами (загруженных). Для этой вершины d_ij<0 и имеет наименьшее значение. При этом все углы многоугольника должны быть прямыми. Перемещение ресурсов производят в пределах клеток, лежащих в вершинах многоугольника (рис. 3.3.1.1). Если для свободной клетки поставить знак + (плюс), а в следующей вершине – (минус), затем снова + и т.д., поочередно изменяя знак, то в нее переносится меньшее из чисел, стоящих в клетках с отрицательными знаками. В результате она, как основная переменная, исключается из опорного плана. Одновременно необходимо установить равновесие по всему многоугольнику.

Если использовать правило перераспределения ресурсов в пределах многоугольника, распределение будет выглядеть, как на рис. 3.3.1.2.

Рис. 3.3.1.1 и 3.3.1.2. Схемы перераспределения ресурсов

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

В результате построения нового допустимого решения (начального плана) способом потенциалов величина критерия оптимизации (целевой функции) будет равна:

Y = 14 х 24 + 19 х 18 + 1 х 56 + 23 X 19 + 3 X 10 + 7 х 3 + 34 х 8 = 1494.

Нахождением нового опорного плана заканчивается первое приближение (итерация). Далее все этапы повторяются.

Таблица 3.3.1.3