Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!
псевдостоимостями и стоимостями может быть, какое угодно.Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клетокплана xij > 0,i + j =ij= сij ,а для всех свободных клеток xij =0,i + j =ij≤ сij ,то план является оптимальным и никакими способами улучшен быть не может. Нетрудно показать, что это теорема справедлива также для вырожденного плана, и некоторые из базисных переменных равны нулю. План обладающий свойством : ij= сij (для всех базисных клеток ) (1)ij≤ сij ( для всех свободных клеток ) (2) называется потенциальным планом, а соответствующие ему платежи (i и j ) — потенциалами пунктов Ai и Bj ( i=1,...,m ; j=1,...,n ). Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так:Всякий потенциальный план является оптимальным. Итак, для решения транспортной задачи нам нужно одно - построить потенциальный план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (i и j ) удовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке : i,j= сi,j -i,j. Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода: поиски циклов с отрицательной ценой.Процедура построения потенциального (оптимального) плана состоит в следующем. В качестве первого приближения к оптимальному плануберётся любой допустимый план (например, построенный способом минимальной стоимости по строке). В этом плане m + n - 1 базисных клеток, где m - число строк, n - число столбцов транспортной таблицы. Для этого плана можно определить платежи (i и j ), так, чтобы в каждой базисной клетке выполнялось условие :i + j = сij (3) Уравнений (3) всего m + n - 1, а число неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n - 1 уравнений (3) можно найти остальные платежиi, j, а по ним вычислить псевдостоимости,i,j= i + j для каждой свободной клетки.Таблица №5
ПНПО | В1 | В2 | В3 | В4 | В5 | i |
А1 | 10= 7 | 8= 6 | 542 | 66 | 9= 6 | 1=0 |
А2 | 64 | 7= 5 | 8= 4 | 6= 5 | 526 | 2=-1 |
А3 |
Похожие работы
Тема: Решение задач транспортного типа методом потенциалов |
Предмет/Тип: Статистика (Реферат) |
Тема: Решение транспортной задачи методом потенциалов |
Предмет/Тип: Отсутствует (Курсовая работа (т)) |
Тема: Решение транспортной задачи методом потенциалов |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Курсовая работа (п)) |
Тема: Решение транспортной задачи методом потенциалов |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Курсовая работа (т)) |
Тема: Решение транспортной задачи методом потенциалов |
Предмет/Тип: Другое (Другое) |
Интересная статья: Быстрое написание курсовой работы