Проверка нового плана на оптимальность

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

Пример 6.1. Решить ТЗ:

5 4 6 3 200

1 10 2 1 300

2 3 3 1 100

150 150 250 50 600

600

Условие баланса выполнено. Следовательно, имеем ТЗ закрытого типа.

Предварительный этап: находим исходный опорный план X° методом «минимального элемента».

Таблица 6.1

Число занятых клеток равно 6 и совпадает с рангом матрицы ограничений ТЗ:

r = m + n – 1 = 2 + 4 – 1 = 6.

Итерация 1. Для проверки полученного опорного плана на оптимальность находим систему потенциалов для занятых клеток (x_ij>0).

Для этого, например, полагаем U₁ = 0 (записываем U₁ = 0 слева в табл. 6.2).

Таблица 6.2

Далее, исходя из занятых клеток (1,2) и (1,3), находим V₂ = 4 – 0 = 4, V₃ = 6 – 0 = 6 (записываем сверху в таблице). На основе базисной клетки (2,3) получаем U₂ = 2 – 6 = –4, затем V₁ = 1 – (–4) = 5; U₃ = 3 – 4 = –1; V₄ = 2.

Далее вычисляем сумму потенциалов для каждой из свободных клеток и записываем их в верхнем левом углу. Так как для клеток (3,1) и (3,3) критерий оптимальности не выполняется:

U₃ + V₁ = 4 > 2,

U₃ + V₃ = 5 > 3,

то полученный опорный план не оптимальный. Так как

D₃₁ = U₃ + V₁ – C_ij = 2 = D₃₃,

то в любую из клеток, например, в (3,1), проставляем некоторое число .

Для того чтобы не нарушился баланс в 3-й строке, вычитаем из величины перевозки, стоящей в клетке (3,2), прибавляем к X₁₂ = 100, вычитаем от X₁₃, прибавляем к X₂₃ и вычитаем от X₂₁, т.е. составляем цикл:

(3,1) → (3,2) → (1,2) → (1,3) → (2,3) → (2,1) → (3,1).

Знаки «+» и «–» в клетках чередуются.

Заметим, что движение от одной клетки к другой происходит только по занятым, кроме первой, в которую проставляется. Максимальное значение равно наименьшему уменьшаемому: = 50. Если взять больше, то получаем отрицательную величину в плане перевозок, а если меньше, то нарушается опорность плана.

Новый опорный план приведен в таблице 4.3

Таблица 6.3

Итерация 2. Проверяем полученный план X⁽¹⁾ на оптимальность. Находим систему потенциалов; они записаны в таблице слева и сверху. Вычисляем сумму потенциалов для свободных клеток (записаны в левом верхнем углу клетки). Так как

U₁ + V₄ = 4 > 3,

то план X⁽¹⁾ не является оптимальным. Для построения нового опорного плана проставляем величину в клетку (1,4) и составляем цикл:

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

Определяем значение = 50, при этом две клетки (1,3) и (3,4) обращаются в нулевые. Следовательно, план Х⁽²⁾ будет вырожденным. Для дальнейшего решения необходимо оставить нуль в одной из клеток и считать ее за базисную. Целесообразнее нуль оставить в клетке с меньшей стоимостью перевозок, т.е. в клетке (3,4). Новый опорный план приведен в таблице 6.4.

Таблица 6.4

Итерация 3. Число занятых клеток равно 6. Находим значения потенциалов и их сумму для свободных клеток. Критерий оптимальности выполняется:

U_i +V_j ≤ C_ij для X_ij = 0; i = 1, m;j = 1, n;

поэтому полученный план является оптимальным:

и f (x^*) = 1500.

Пример 6.2. Решить задачу:

Решение. Объем ресурсов: 80 + 60 + 60 = 200 превышает общие потребности 30 + 70 + 60 = 160 на 40 ед., следовательно, ТЗ является задачей открытого типа. Вводим дополнительный (балансовый пункт) потребления с объемом потребностей b₄ = 40 и полагаем c₁₄ = c₂₄ = c₃₄ = 0. В результате получаем ТЗ закрытого типа.

Предварительный этап. Находим исходный опорный план методом «минимального элемента» (см. табл. 6.5).

Таблица 6.5

Данный план является вырожденным, поэтому ставим «0» – перевозку в клетку с минимальным значением c_ij, но так, чтобы не образовалось замкнутого маршрута (цикла). В нашем примере c₁₄ = c₃₄ = 0, но занять клетку (1,4) нельзя, так как образуется цикл:

(1,4) → (2,4) → (2,1) → (1,1) → (1,4).

Поэтому ставим «0» в клетку (3,4).

Итерация 1. Проверяем план на оптимальность. Положив , находим потенциалы (см. табл. 4.5). Далее находим сумму потенциалов для свободных клеток (они записаны в левом верхнем углу клетки). Так как

;

,

то полученный опорный план неоптимальный. Для клеток (1,4) и (3,1) оценки одинаковы: и , поэтому выбираем любую, например, (1,4). Проставляем в эту клетку и составляем цикл, чередуя знаки «+» и «–»; получим . Новый опорный план представлен в таблице 4.6.

Таблица 6.6

Итерация 2. Находим систему потенциалов (см. слева и сверху табл. 6.6). Сумма потенциалов для небазисных клеток записана в левом верхнем углу. Критерий оптимальности не выполняется для клетки (3,1):

.

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

Итерация 3. Найдя систему потенциалов, убеждаемся в оптимальности плана (см. табл. 6.7).

Таблица 6.7

Транспортные издержки составляют 480 и . Так как четвертый потребитель фиктивный, то 10 ед. груза останутся у первого поставщика, 30 ед. – у второго.

Пример 6.3. Методом потенциалов решите следующую ТЗ:

Прочерк между пунктами A₂ и B₂, A₃ и B₄ означает, что перевозки между указанными пунктами запрещены.

Проверяем условие баланса:

80 + 320 + 150 = 550 = 250 + 100 + 150 + 50.

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

Предварительный этап. Составляем методом «минимального элемента» исходный опорный план (табл. 6.8).

Итерация 1. Вычисляем потенциалы и проверяем план на оптимальность (см. таблицу 6.8)

Таблица 6.8

В клетке (2,3) имеем

,

т.е. план не является оптимальным. Проставляем в эту клетку и составляем замкнутый маршрут. Получаем . Опорный план приведен в таблице 4.9

Итерация 2. Проверяем план на оптимальность. Так как для всех свободных клеток:

,

то план – оптимальный и не содержит положительных перевозок по запрещенным маршрутам.

Таблица 6.9

Минимальные транспортные расходы составляют 3000.