Четверг, 08.12.2016, 23:06
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 47
Гостей: 47
Пользователей: 0
» »
18:15
Проверка опорного решения на оптимальность
Проверка найденного опорного решения
транспортной задачи 245 на оптимальность

Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система m+ п действительных чисел ui и vj, удовлетворяющих условиям ui + vj = cij для занятых клеток и ui + vj - сij ≤ 0 для свободных клеток.
Числа 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, запишем это значение в последнем столбце таблицы.

Рассмотрим занятую клетку первой строки, которая расположена в первом столбце (1,1), для нее выполняется условие u1 + v1 = 2, откуда v1 = 2. Это значение запишем в последней строке таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которой один из потенциалов известен.
 Рассмотрим занятую клетку (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.
Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:

Получили одну оценку Δ13 = 5 > 0, следовательно, исходное опорное решение не является оптимальным и его можно улучшить.
Категория: Транспортная задача | Просмотров: 6110 | Добавил: Admin | Теги: распределительная таблица, оптимальность опорного плана, потенциалы | Рейтинг: 2.0/4


Похожие материалы:

Всего комментариев: 0
avatar
  .