Модель определения эффективного варианта доставки изделий к потребителю

Пусть на некоторых складах А1, А2, А3 имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители В1,В2,В3 должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сума затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (усл. ед.).

Проверим, является ли данная транспортная задача закрытой:

выполнено условие.

(1.9).

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

Таблица 2.

Число занятых клеток в таблице равно m+n-1=3+3−1=5, имеет место равенство (1.8), т. е. условие невырожденности выполнено. Получили опорное решение, которое запишем в виде матрицы:

X₁=.

стоимость перевозок при исходном опорном решении составляет.

L (Х_опт)=90*2+300*1+100*5+50*3+60*8=1610 усл.ед.

Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система m+n действительных чисел u_i и v_j, удовлетворяющих условиям u_i+v_j=c_ij (1.10) для занятых клеток и.

u_i+v_j-c_ij?0 (1.11).

для свободных клеток.

Числа называют u_i и v_j потенциалами. В распределительную таблицу добавляют строку v_j и столбец u_i.

Потенциалы u_i и v_j находятся из равенства u_i+v_j=c_ij, (1.12) справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например u₁=0, тогда остальные потенциалы определяются однозначно. Так, например, если известен потенциал u_i, то v_j=c_ij-u_i (1.13); если известен потенциал v_j, то u_i = c_ij-v_j. (1.14).

Обозначим ?_ij=u_i+v_j-c_ij. (1.15). Эту оценку называют оценкой свободных клеток. Если ?_ij?0 (1.16), то опорное решение является оптимальным. Если хотя бы одна из оценок ?_ij>0 (1.17), то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому [10].

Проверим опорное решение на оптимальность, добавим в распределительную таблицу столбец u_i и строку v_j.

Полагая u₁=0, запишем это значение в последнем столбце таблицы.

Таблица 3.

Рассмотрим занятую клетку первой строки, которая расположена в первом столбце (1;1), для нее выполняется условие u₁+v₁=2, откуда v₁=2. Это значение запишем в последней строке таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которой один из потенциалов известен.

Рассмотрим занятую клетку (3,1): u₃+v₁=3, v₁=2, откуда u₃=1.

Для клетки (3,3): u₃+v₃=8, u₃=1, v₃=7.

Для клетки (2,3): u₂+v₃=5, v₃=7, u₂=-2.

Для клетки (2,2): u₂+v₂=1, u₂=-2, v₂=3.

Найденные значения потенциалов заносим в таблицу.

Вычисляем оценки свободных клеток.

• ?₁₂= u₁+v₂-c₁₂=0+3−5=-2<0
• ?₁₃= u₁+v₃-c₁₃=0+7−2=5>0
• ?₂₁= u₂+v₁-c₂₁=-2+2−4=-4<0
• ?₃₂= u₃+v₂-c₃₂=1+3−6=-2<0

Получили одну оценку ?₁₃=5>0, следовательно, исходное опорное решение не является оптимальным и его можно улучшить.