Метод потенциалов. 2 версия ответа.

Согласно теореме о потенциалах, каждой занятой клетке будет соответствовать уравнение . Так как всех занятых клеток должно быть , т.е. на единицу меньше, то для определения чисел и , необходимо решить систему из урав-нений с неизвестными. Система неопределенная, и, чтобы найти част-ные решения, одному из потенциалов придается произвольной числовое значение, тогда остальные потенциалы определятся однозначно. Для облегчения расчетов одному из по-тенциалов придается обычно значение, равное нулю.

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

.

Если для всех свободных клеток оценки , то опорный план перевозок явля-ется оптимальным. Если для опорного плана перевозок указанное условие оптимальности не выполняется, то за счет загрузки свободной клетки с отрицательной оценкой план перевозки улучшается. Для наиболее перспективной свободной клетки строится замк-нутый цикл с вершинами в загруженных клетках. Вершинам этого цикла условно припи-сываются знаки: свободной клетке – знак «+», следующей по часовой или против часовой стрелки занятой клетке – знак «-», следующей – снова «+» и т.д. Из поставок в клетках цикла с «отрицательными» вершинами выбирается наименьшее количество l груза, ко-торое и перемещается по клеткам этого цикла: прибавляется к поставкам в положи-тельных вершинах и вычитается из поставок в отрицательных вершинах, в результате чего баланс цикла не нарушается.

В общем случае цикл представляет собой замкнутую ломаную линию, состоящую из звеньев, пересекающихся под прямым углом. Каждое звено соединяет две клетки строки (столбца). Цикл включает одну свободную клетку, остальные клетки цикла заняты. В цикле всегда четное число клеток. Для свободной клетки всегда можно построить единственный цикл. Если из занятых клеток образуется цикл, то план перевозок не является опорным. Цикл строится лишь для свободных клеток.

Сформулируем алгоритм решения ТЗ методом потенциалов:

1) построить опорный план;

2) вычислить потенциалы поставщиков и потребителей и , решив систему уравнений вида ;

3) вычислить оценки для всех свободных клеток по формуле . Если , то полученный план является оптимальным. При этом если все , то по-лученный оптимальный план единственный. В случае, если хотя бы одна оценка , имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

Пример 17.1. В пунктах производится однородная продукция в коли-чествах единиц. Готовая продукция поставляется в пункты , потребности которых составляют единиц. Стоимость c_ij перевозки единицы продукции из пункта A_i в пункт B_j заданы матрицей :

.

Требуется:

1) методом потенциалов найти план перевозок продукции, при котором минимизируются суммарные затраты по ее изготовлению и доставке потребителям;

2) вычислить суммарные затраты f_min.

Решение.

1) Найдем суммарные запасы продукции и суммарные потребности 150+380=890; b₁+b₂+b₃+b₄=270+190+340+200=1000. Поскольку ,то есть отсутствует баланс между производимой продукцией и потребнос-тями, то мы имеем задачу открытого типа. Вводим фиктивного поставщика A₄, который имеет запас продукции в объеме (един.). Все тарифы на доставку продукции фиктивного поставщика равны нулю, т.е. c₄₁=c₄₂=c₄₃=c₄₄=0

Данные задачи заносим в таблицу 1.

Табл. 1.

Начальный опорный план получим по правилу «минимального элемента».

Загрузку начинаем с клетки, которой соответствует наименьший тариф c_ij≠0 всей матрицы тарифов. В нашем случае минимальным тарифом является с₁₄=1, который соот-ветствует клетке (1, 4). В эту клетку вписываем x₁₄=min (360; 200)=200. Исключаем четвертый столбец. У поставщика A₁ осталось еще 160 единиц продукции, которые по-местим в клетку (1, 2). Исключаем первую строку. Но потребителю B₂ необходимо еще 30 ед. продукции, которые берем у поставщика A₂, и помещаем в клетку (2, 3). Исключаем второй столбец. Оставшиеся у поставщика A₂ 120 ед. продукции помещаем в клетку (2, 3). Исключаем вторую строку. Необходимые потребителю B₃ 220 ед. продукции берем у поставщика A₃ и помещаем в клетку (3, 3). Исключаем третий столбец. В пункте A₃ оставшиеся 160 ед. продукции помещаем в клетку (3; 1). Исключаем третий столбец. Оставшиеся 110 ед. помещаем в клетку (4; 1).

Полученный нами план является невырожденным, так как выполняется условие базисных клеток: m+n-1=4+4-1=7, и число заполненных клеток тоже 7. А значит, полу-чено опорное решение, которое запишем матрицей

.

Методом потенциалов проверим, является ли полученное решение оптимальным. Для этого каждому поставщику и потребителю придается число, называемое потен-циалом. Потенциалы выбираем так, чтобы их сумма для каждой загруженной клетки была равна тарифу перевозки единицы груза, т.е.

u_i+v_j=c_ij,

где u_i – потенциал i-го поставщика;

v_j – потенциал j-го потребителя;

c_ij – тариф заполненной клетки.

В нашем случае получаем следующие уравнения:

Полагая v₄=0, получаем следующие потенциалы:

u₁=1 u₃=3 v₁= 0 v₃= 4

u₂=0 u₄=0 v₂= 2 v₄=0

Все полученные данные заносим в таблицу 2.

Далее вычисляем оценки свободных клеток по формуле: .

s₁₁=c₁₁-(u₁+v₁) =7-(1+0) =6 ³ 0 s₂₄=c₂₄-(u₂+v₄) = 8-(0+0) =8 ³ 0 s₄₂=c₄₂-(u₄+v₂) = 0-(0+2) = -2

s₁₃=c₁₃-(u₁+v₃) = 6-(1+4) =1 ³ 0 s₃₂=c₃₂-(u₃+v₂) = 5-(3+2) = 0 s₄₃=c₄₃-(u₄+v₃) = 0-(0+4) = -4

s₂₁=c₂₁-(u₂+v₁) = 5-(0+0) =5 ³ 0 s₃₄=c₃₄-(u₃+v₄) = 9-(3+0) = 6 ³ 0 s₄₄=c₄₄-(u₄+v₄) = 0-(0+0) = 0

Так как s₄₂<0, и s₄₃<0 то полученный план не является оптимальным. Наиболее потенциальной клеткой является клетка (4; 3). Поэтому строим для клетки (4; 3) замк-нутый цикл, который в таблице 2 выделяем пунктирной линией:

(4, 3)→(3, 3)→(3, 1)→(4, 1).

Свободной клетке условно приписываем знак «+», тогда следующей клетке по ходу часовой стрелки – знак «-» и т.д., знаки чередуются.

В отрицательных вершинах цикла определяем наименьшую загрузку клетки, т.е.

min (x₃₃, x₄₁)=min (220, 110)=110.

Количество продукции, равное 110ед., прибавляем к поставкам в клетках со знаком «+» и вычитаем из поставок в клетках со знаком «-».

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

Проверяем, является ли полученный план оптимальным. Для этого каждому поставщику и потребителю придаем число – потенциал. Вычисляем потенциалы так же, как это делали выше:

.

Полагая v₃=0, получаем следующие потенциалы, которые заносим в таблицу 4:

u₁=5 u₃=7 v₁= -4 v₃= 0

u₂=4 u₄=0 v₂= -2 v₄= -4

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

s₁₁=7-(5-4) =6 ³ 0 s₂₄=8-(4-4) = 8 ³ 0 s₄₁=0-(0-4) = 4 ³ 0

s₁₃=6-(5+0) =1 ³ 0 s₃₂=5-(7-2) = 0 s₄₂=0-(0-2) =2 ³ 0

s₂₁=5-(4-4) =5 ³ 0 s₃₄=9-(7-4) = 6 ³ 0 s₄₄=0-(0-4) = 4 ³ 0

Поскольку все s_ij>0, то полученный план является оптимальным, который можно представить в виде матрицы

.

2) Суммарные затраты f_min при этом будут составлять:

Потребитель B₃ не дополучил 110 единиц продукции.

Ответ: , f_min=2800 ден.ед.

Вопрос 25. Понятия контуpа пеpесчета (цикла) . Пpизнак оптимальности плана.

После того, как получено допустимое решение, его надо проверить на оптимальность с помощью метода потенциалов. Перед проверкой убеждаемся, что число заполненных клеток равно соотношению m+n-1. В нашей таблице их 3+3-1=5.

Признак оптимальности: решение оптимально, если во всех свободных клетках выполняется неравенство: α_i + c_ij ≥ β_j, где α_i и β_j – потенциалы, c_ij – тарифы перевозок. Вычислим α_i и β_j с помощью выше указанного неравенства:

Принято считать, что α₁ всегда равно 0. Если не сделать это допущение, то задача не будет иметь решение. Вычисления остальных значений потенциалов производят по базовым (заполненным) клеткам:
α₁ = 0
β₁ = 3 + 0 = 3
β₂ = 2 + 0 = 2
α₂ = 2 — 1 = 1
α₃ = 2 — 3 = -1
β₃ = -1 + 3 = 2

Проверку на оптимальность делают по свободным клеткам с помощью этого же неравенства:
А₁В₃: 0 + 1 ≥ 2 – нет
А₂В₁: 1 + 1 ≥ 3 – нет
А₂В₃: 1 + 4 ≥ 2 – да
А₃В₁: -1 + 2 ≥ 3 – нет

В результате проверки мы выявили три недостаточные клетки. Находим цикл пересчета:

цикл пересчета – это ход ладьи по базовым клеткам с чередованием знаков «+» и «-», начиная с недостаточной клетки и замыкаясь в ней же.

В клетках с минусовыми отметками выбирает минимальное число. В нашем случае это число равно 100. Пересчет делают следующим образом: где стоит знак «-» это число отнимают, а где «+» то прибавляют. Значения, не входящие в цикл пересчета переписывают без изменений. Получает таблицу, в которой соотношение m+n-1 не выполняется, и поэтому выбираем клетку с минимальным тарифом и, проставляя в ней ноль, считаем ее условно базовой:

Вначале транспортные расходы составляли 1400 у.е. Считаем сейчас:
f₂ = 2×100 + 2×150 + 1×100 + 3×200 = 1200 у.е.
Уменьшение этого показателя говорит о том, что мы на верном пути.

Полученное решение снова проверяем на оптимальность:

Проверка выявляет одну недостаточную клетку, для которой находим цикл пересчета:
А₁В₁: 0 + 3 ≥ 0 – да
А₁В₃: 1 + 0 ≥ 1 – да
А₂В₁: 1 + 1 ≥ 0 – да
А₃В₂: -2 + 3 ≥ 2 – нет

В отрицательных клетках из двух значений выбираем число 150, которое отнимаем, где знак «-» и прибавляем где знак «+»:

Транспортные расходы:
f₃ = 2×100 + 3×150 + 1×100 + 1×150 + 3×50 = 1050 у.е.

Проверяем снова на оптимальность и убеждаемся, что найден оптимальный план:
А₁В₁: 0 + 3 ≥ 0 – да
А₁В₂: 0 + 2 ≥ 1 – да
А₂В₁: 0 + 1 ≥ 0 – да
А₂В₃: 0 + 4 ≥ 1 – да

Ответ: f = 1050 у.е.

Вторая версия

Ответа

Не нашли, что искали? Воспользуйтесь поиском по сайту: