| Главная » Учебно-методические материалы » ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ » Математические методы в экономике |
Тема 2. Методы линейного программирования. Решение транспортной задачи методом потенциалов
| 22.12.2011, 13:31 | |||||||||||||||||||||||||||||||||||||||||||
| Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями      . Стоимость перевозки единицы груза из Ai в Bj равна C ij; таблица стоимостей задана. Требуется найти план перевозок xij, который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок бала минимальна. Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё равно куда) какую-то сумму αi ; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму βj. Эти платежи передаются некоторому третьему лицу ("перевозчику"). Обозначим ai + bj = čij ( i=1..m; j=1..n) и будем называть величину čij "псевдостоимостью” перевозки единицы груза из Ai в Bj. Заметим, что платежи αi и βj не обязательно должны быть положительными; не исключено, что "перевозчик” сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (αi и βj) одна и та же и от плана к плану не меняется. До сих пор мы никак не связывали платежи (αi и βj) и псевдостоимости čij с истинными стоимостями перевозок Cij. Теперь мы установим между ними связь. Предположим, что план xij невырожденный (число базисных клеток в таблице перевозок ровно m + n -1). Для всех этих клеток xij>0. Определим платежи (αi и βj) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям: čij=αi+βj=сij, при xij>0. Что касается свободных клеток (где xij=0), то в них соотношение между псевдостоимостями и стоимостями может быть, какое угодно. Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана xij>0, αi+βj=čij=сij, а для всех свободных клеток xij=0, αi+βj=čij≤сij, то план является оптимальным и никакими способами улучшен быть не может. Нетрудно показать, что это теорема справедлива также для вырожденного плана, и некоторые из базисных переменных равны нулю. План обладающий свойством : čij= сij (для всех базисных клеток ) (2.36) čij ≤ сij (для всех свободных клеток ) (2.37) называется потенциальным планом, а соответствующие ему платежи (αiи βj) — потенциалами пунктов Ai и Bj(i=1,...,m; j=1,..., n). Пользуясь этой терминологией вышеупомянутую теорему можно сформулировать так: Всякий потенциальный план является оптимальным. Итак, для решения транспортной задачи нам нужно одно - построить потенциальный план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (2.36). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (αiи βj) удовлетворяющая условию (2.36), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке: γi,j=сi,j - či,j. Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода: поиски циклов с отрицательной ценой. Процедура построения потенциального (оптимального) плана состоит в следующем. В качестве первого приближения к оптимальному плану берётся любой допустимый план (например, построенный способом минимальной стоимости по строке). В этом плане m+n-1 базисных клеток, где m - число строк, n - число столбцов транспортной таблицы. Для этого плана можно определить платежи (αi и βj), так, чтобы в каждой базисной клетке выполнялось условие : αi+βj=сij (2.38) Уравнений (2.38) всего m+n-1, а число неизвестных равно m+n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m+n-1 уравнений (2.38) можно найти остальные платежи αi, βj, а по ним вычислить псевдостоимости, či,j=αi+βj для каждой свободной клетки. Таблица № 2.5
α4 = 0, => β4=6, так как α4+β4=С44=6, => α1=0, так как α1+β4=С14=6, => β3=5, так как α1+β3=С13=5, => β1= 7, так как α4+β1=С41=7, => α2=-1, так как α2+β1= С21=6, => β5=6, так как α2+β5=С25=5, => α3= 1, так как α3+β5=С35=7, => β2=6, так как α3+β2=С25=7. Если оказалось, что все эти псевдостоимости не превосходят стоимостей čij≤сij, то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости (как в нашем примере), то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла ровна разности между стоимостью и псевдостоимостью в этой свободной клетке. В таблице № 2.5 мы получили в двух клетках čij≥ сij, теперь можно построить цикл в любой из этих двух клеток. Выгоднее всего строить цикл в той клетке, в которой разность čij-сij максимальна. В нашем случае в обоих клетках разность одинакова (равна 1), поэтому, для построения цикла выберем, например, клетку (4,2): Таблица № 2.6  Теперь будем перемещать по циклу число 14, так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком - . При перемещении мы будем вычитать 14 из клеток со знаком - и прибавлять к клеткам со знаком + . После этого необходимо подсчитать потенциалы αiи βj и цикл расчетов повторяется. Итак, мы приходим к следующему алгоритму решения транспортной задачи методом потенциалов: 1. Взять любой опорный план перевозок, в котором отмечены m+n-1 базисных клеток (остальные клетки свободные). 2. Определить для этого плана платежи (αiи βj) исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например, положить равным нулю. 3. Подсчитать псевдостоимости či,j=αi+βjдля всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален. 4. Если хотя бы в одной свободной клетке псевдостоимость превышает стоимость, следует приступить к улучшению плана путём переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостоимость больше стоимости). 5. После этого заново подсчитываются платежи и псевдостоимости, и, если план ещё не оптимален, процедура улучшения продолжается до тех пор, пока не будет найден оптимальный план. Так в нашем примере после 2 циклов расчетов получим оптимальный план. При этом стоимость всей перевозки изменялась следующим образом: F0=723, F1=709, F2=Fmin=703. Следует отметить так же, что оптимальный план может иметь и другой вид, но его стоимость останется такой же Fmin = 703. | http://math.immf.ru/ | ||||||||||||||||||||||||||||||||||||||||||
