Контрольные, курсовые, рефераты, тесты – готовые и на заказ!
 Гарантия качества, доступные цены, индивидуальный подход
 Работы выполняют высококвалифицированные специалисты
Войти      Регистрация
 тел. 8-912-388-82-05
  std72@mail.ru
> 20 лет успешной работы
> 50000 выполненных заказов
Отзывы/вопросы

Форма входа



Главная » Учебно-методические материалы » ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ » Математические методы в экономике

Тема 2. Методы линейного программирования. Решение транспортной задачи методом потенциалов
22.12.2011, 13:31
Этот  метод  позволяет  автоматически  выделять  циклы  с  отрицательной  ценой  и определять  их  цены. 
     Пусть  имеется  транспортная  задача  с  балансовыми  условиями     
      
       
     
     .       
     Стоимость  перевозки  единицы  груза  из Ai в  Bj равна  C ij; таблица  стоимостей  задана. Требуется  найти  план  перевозок xij, который  удовлетворял  бы   балансовым  условиям  и  при  этом  стоимость  всех  перевозок  бала  минимальна. 
     Идея  метода  потенциалов  для  решения  транспортной задачи  сводиться  к  следующему. Представим  себе что  каждый  из пунктов  отправления  Ai  вносит  за  перевозку  единицы  груза (всё  равно  куда)  какую-то  сумму  αi ;  в  свою  очередь  каждый  из  пунктов  назначения  Bj   также  вносит  за  перевозку  груза  (куда  угодно)  сумму  βj. Эти платежи передаются некоторому третьему лицу ("перевозчику"). Обозначим    a+ 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) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям: 
     čijij=сij, при xij>0. 
     Что касается свободных  клеток  (где xij=0), то  в  них  соотношение  между  псевдостоимостями  и  стоимостями  может  быть, какое  угодно. 
     Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным  или  же  он  может  быть  улучшен. Существует  специальная  теорема:  Если  для  всех  базисных  клеток плана  xij>0,
     αij=čij=сij
     а  для  всех  свободных  клеток xij=0
     αij=č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,ji,j - či,j.
     Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее  трудоёмкий  элемент распределительного  метода: поиски  циклов  с  отрицательной  ценой. 
     Процедура  построения  потенциального  (оптимального)  плана  состоит  в  следующем.
     В  качестве  первого  приближения  к  оптимальному  плану    берётся  любой  допустимый  план (например,  построенный  способом  минимальной стоимости по строке). В этом плане  m+n-1 базисных клеток, где m - число  строк, n - число столбцов  транспортной  таблицы. Для  этого  плана  можно  определить  платежи  (αi и βj),  так, чтобы  в  каждой  базисной  клетке  выполнялось  условие : 
     αij=сij                                     (2.38)
     Уравнений (2.38)  всего  m+n-1, а  число  неизвестных  равно m+n.  Следовательно, одну  из  этих  неизвестных  можно  задать  произвольно  (например, равной  нулю). После  этого  из  m+n-1 уравнений  (2.38)  можно  найти  остальные  платежи   αiβj, а  по  ним  вычислить  псевдостоимости, či,jij для  каждой  свободной  клетки. 

     Таблица № 2.5

 
 
В1
 
В2
 
В3
 
В4
 
В5
 
αi
    
А1  

10

č= 7

8

č= 6

5     

42

6

6

9

č= 6

α1= 0
    
А2  

6

4

7

č= 5

8

č= 4

6

č= 5

5

26

α2= -1
    
А3  

8

č= 8

7

27

10

č= 6

8

č= 7

7

0

α3= 1
    
А4  

7

14

5

č= 6

4

č= 5

6

6

8

č= 6

α4= 0
 
βj  
   
β1= 7
   
β2= 6
   
β3= 5
   
β4= 6
   
β5= 6
 

      α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,jijдля  всех  свободных  клеток. Если  окажется, что  все они не превышают стоимостей, то план  оптимален.
     4. Если хотя бы в одной свободной клетке псевдостоимость превышает  стоимость, следует  приступить к улучшению плана путём  переброски  перевозок  по  циклу, соответствующему  любой  свободной  клетке  с  отрицательной  ценой (для  которой  псевдостоимость  больше  стоимости).
     5. После  этого  заново  подсчитываются  платежи  и  псевдостоимости, и, если  план  ещё  не  оптимален, процедура улучшения продолжается  до  тех  пор, пока  не  будет  найден  оптимальный  план.
     Так в нашем примере после 2 циклов расчетов получим оптимальный план. При этом стоимость всей перевозки изменялась следующим образом: F0=723, F1=709, F2=Fmin=703.
     Следует отметить так же, что оптимальный план может иметь и другой вид, но его стоимость останется такой же Fmin = 703.
http://math.immf.ru/




БАНКОВСКОЕ ДЕЛО
БУХГАЛТЕРСКИЙ, УПР. И ФИН. УЧЕТ
БЮДЖЕТ И БЮДЖЕТНАЯ СИСТЕМА РФ
ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ
ГУМАНИТАРНЫЕ НАУКИ
ДОКУМЕНТОВЕДЕНИЕ И ДЕЛОПРОИЗВОДСТВО
ИНВЕСТИЦИИ
ИНФОРМАЦИОННЫЕ СИСТЕМЫ В ЭКОНОМИКЕ
ИССЛЕДОВАНИЕ СИСТЕМ УПРАВЛЕНИЯ
МАРКЕТИНГ
МЕНЕДЖМЕНТ
МЕТ. РЕКОМЕНДАЦИИ, ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
МИРОВАЯ ЭКОНОМИКА И МЭО
НАЛОГИ И НАЛОГООБЛОЖЕНИЕ
ПЛАНИРОВАНИЕ И ПРОГНОЗИРОВАНИЕ
ПРАВОВЕДЕНИЕ
РАЗРАБОТКА УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ
РЫНОК ЦЕННЫХ БУМАГ
СТАТИСТИКА
УПРАВЛЕНИЕ ПЕРСОНАЛОМ
УЧЕБНИКИ, ЛЕКЦИИ, ШПАРГАЛКИ (СКАЧАТЬ)
ФИНАНСОВЫЙ МЕНЕДЖМЕНТ
ФИНАНСЫ, ДЕНЕЖНОЕ ОБРАЩЕНИЕ И КРЕДИТ
ЦЕНЫ И ЦЕНООБРАЗОВАНИЕ
ЭКОНОМИКА
ЭКОНОМИКА, ОРГ-ЦИЯ И УПР-НИЕ ПРЕДПРИЯТИЕМ
ЭКОНОМИКА И СОЦИОЛОГИЯ ТРУДА
ЭКОНОМИЧЕСКАЯ ТЕОРИЯ (МИКРО-, МАКРО)
ЭКОНОМИЧЕСКИЙ АНАЛИЗ
ЭКОНОМЕТРИКА
Оформить заказ
Ваше имя *
Ваш e-mail *
Контактный телефон
Город *
Учебное заведение *
Предмет *
Тип работы *
Тема работы/вариант *
Кол-во страниц
Срок выполнения *
Прикрепить файл
Дополнительные условия


Статистика
Онлайн всего: 32
Гостей: 32
Пользователей: 0