|
18:15
Проверка опорного решения на оптимальность
|
|
Проверка найденного опорного решения Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система m+ п действительных чисел ui и vj, удовлетворяющих условиям ui + vj = cij для занятых клеток и ui + vj - сij ≤ 0 для свободных клеток.транспортной задачи 245 на оптимальность Числа ui и vj называют потенциалами. В распределительную таблицу добавляют строку vj и столбец ui. Потенциалы ui и vj находят из равенства ui + vj = cij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например u1 = 0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал ui, то vj = сij — ui; если известен потенциал vj, то ui = cij – vj. Обозначим Δij = ui + vj - cij. Эту оценку называют оценкой свободных клеток. Если Δij ≤ 0, то опорное решение является оптимальным. Если хотя бы одна из оценок Δij > 0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому. Проверим найденное опорное решение на оптимальность, добавив в распределительную табл. 23.3 столбец ui и строку vj. Полагая u1 = 0, запишем это значение в последнем столбце таблицы.  Рассмотрим занятую клетку (3,1): u3 + v1 = 3, v1 = 2, откуда u3 = 1. Для клетки (3,3): u3 + v3 = 8, u3 = 1, v3 = 7. Для клетки (2,3): u2 + v3 = 5, v3 = 7, u2 = -2. Для клетки (2,2): u2 + v2 = 1, u2 = -2, v2 = 3. Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:  |
|
|
| Всего комментариев: 0 | |
