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

Для проверки плана на оптимальность:

1. Для занятых клеток рассчитывают потенциалы клеток U_i и Vj,
которые определяются по формуле: U_i+V_j=C_ij и записывается в специальный столбец и строку.

Первый опорный план:

Задав одной из неизвестных U_i или V_j произвольное значение, например Ui=0, находим все U_i и V_j. Так, U₁+V₁=C₁₁, откуда V₁=C₁₁-U₁.

2. Для свободных клеток рассчитывают величину: l_ij =С_ij - (U_i +V_j),
которая указывает экономию или перерасход по сравнению с предыдущим
планом при перемещении единицы груза в данную точку.

Таблица 2.

Если при задаче на максимум величины l_ij будут положительны, то план неоптимален, если же имеются отрицательные величины, то план оптимален, и его надо улучшать.

l₁₂= 14-8 =6

l₁₃= 11-8 =3

l₂₁= 6-(8+7) =9

l₂₃= 13-(8+7) =-2

l₃₂= 12-(8+4) =0

l₃₃= 4-(8+4) =-8

Так как среди значений l_ij есть положительные, то первый опорный план не оптимален (Табл. 2).

Поиск решения более близкого к оптимальному

Таблица 3.

L₂₁= 8-14 =-6

l₁₃= 11-14 =-3

l₂₁= 6-(14+1) =-9

l₂₃= 13-(14+1) =-2

l₃₂= 12-(14-2) =0

l₃₃= 4-(14-2) =-8

Так как среди значений l_ij отрицательные, то опорный план оптимален!

(таблица 3.)

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