Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Переход от одного опорного решения к другому


 

В транспортной задаче переход от одного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок. Перевозка загружается в выбранную свободную клетку, и освобождается одна из занятых клеток, получается новое опорное решение.

Теорема(о существовании и единственности цикла). Если таблица транспортной задачи содержит опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением.

Доказательство. Опорное решение занимает N=т+п—1 клеток таблицы, которым соответствуют линейно независимые векторы-условия. Согласно теореме (о взаимосвязи линейной зависимости векторов-условий и возможности образования цикла) ни одна часть занятых клеток не образует цикл. Если же к занятым клеткам присоединить одну свободную, то соответствующие им т + п векторов линейно зависимы, и по той же теореме существует цикл, содержащий эту клетку. Предположим, что таких циклов два ( i1, j1 ), ( i1, j2 ), …, ( iк, j1 ) и

(i1, j1 ), ( i2, j1 ), …, ( i1, jl ). Тогда, объединив клетки обоих циклов без свободной клетки (i1 , j1), получим последовательность клеток (i1,j2), …, (iк,j1), (i2,j1), …, ( i1, jl ), которые образуют цикл. Это противоречит линейной независимости векторов-условий, образующих базис опорного решения. Следовательно, такой цикл единственный. Ч.т.д.

Означенный цикл

Цикл называется означенным, если его угловые клетки пронумерованы по порядку и нечетным клеткам приписан знак «+», а четным — знак «-» (рис. 6.2).

 

 


Рис. 6.2.

Сдвигом по циклу на величину θ называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на θ и уменьшение объемов пере­возок во всех четных клетках, отмеченных знаком «—», на θ.

Теорема. Если таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему одну свободную клетку, на величину θ = получится опорное решение.



6.6. Распределительный метод

 

Один из наиболее простых методов решения транспортных задач ― распределительный метод.

Пусть для транспортной задачи найдено начальное опорное решение Х1 и вычислено значение целевой функции на этом решении F(X1). По теореме (о существовании и единственности решения) для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Означив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину θ = , можно получить новое опорное решение Х2.

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции Δlk равно разности двух сумм:

Δlk = -,

где — сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком «+»;

— сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком «—».

В клетках, отмеченных знаком «+», величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком «—», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки (l, k) меньше нуля, т.е. Δlk<0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F(X) на величину θ·Δlk, т.е. опорное решение можно улучшить. Если же величины Δlk, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальностираспределительного метода является условие Δlk≥0 хlk=0.

Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку Δlk. Если оценка неотрицательная, переходят к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину θ = . В результате получится новое опорное решение.

Для каждого нового опорного решения вычисление оценок начинается с первой свободной клетки таблицы. Очередность проверяемых свободных клеток целесообразно устанавливать в порядке возрастания стоимости перевозок cij, так как решается задача на нахождение минимума.

Пример.Решить распределительным методом транспортную задачу:

bj ai
 

Решение. Строим начальное опорное решение:

.

Затем вычисляем значение целевой функции на нем: F(X1)=20·1+ +30·5+10·8 + 40·15 = 850.

bj ai
 

Находим цикл для свободной клетки (1,2) таблицы, он включает клетки (1, 2), (1, 3), (3, 3), (3, 2). Вычисляем оценку Δ12 = (3+15)-(2+8)=8. Так как Δ12=8> 0, переходим к следующей свободной клетке (2, 1). Для нее цикл таков: (2, 1), (1, 1), (1, 3), (3, 3), (3, 2), (2, 2). Оценка Δ21=(4+2+8)-(1+15+5)=14-21=-7. Так как Δ21 = -7 < 0, определяем величину груза, перераспределяемого по циклу, θ = {20, 40, 30} = 20. Приращение целевой функции ΔF= -7 · 20 = -140. Получаем новое опорное решение Х2. Значение целевой функции на нем

F(X2) = 20 · 2 + 20 · 4 + 10 · 5 + 30 · 8 + 20 · 15 = 710.

bj ai
   

Вычисляем Δ11 = (1 + 15 + 5) - (2 + 8 + 4) = 7 > 0, Δ12 = (3+15)-(2+8)=8> 0, Δ23 = (7 + 8) - (5 + 15) = -5 < 0, Δ31 = (6 + 5)—(4 + 8) = -1 < 0. Оценки можно вычислять до первой отрицательной. Так как Δ23 = -5 < 0, осуществляем сдвиг по циклу (2, 3), (3, 3), (3, 2), (2, 2) на величину θ = {10, 20} = 10. Приращение целевой функции ΔF= -5 · 10 = -50. Получаем третье опорное решение Х3. Значение целевой функции на нем



F(X3) = 20 · 2 + 20 · 4 + 10 · 7 + 40 · 8 + 10 · 15 = 660.

bj ai
   
 

Вычисляем оценки для свободных клеток: Δ11= (1 + 7) — (2 + 4) = 2 > 0, Δ12 = (3 + 15) - (2 + 8) = 8 > 0, Δ22=(5+15)-(7+8)=5>0, Δ31=(6+7)—(4+15)=-6 < 0. Так как Δ31 = -6 < 0, осуществляем сдвиг по циклу (3, 1), (2, 1), (2, 3), (3, 3) на величину θ = {20, 10} = 10. Приращение целевой функции ΔF= -6 · 10 = -60. Получаем четверки опорное решение Х4. Значение целевой функции на нем

F(X4) = 20 · 2 + 10 · 4 + 20 · 7 + 10 · 6 + 40 · 8 = 600.

bj ai
   
 
 

Вычисляем оценки для свободных клеток Δ11 = (1 + 7) — (2 + 4) =2 > 0, Δ12 = (3 + 7 + 6) - (2 + 4 + 8) = 2 > 0, Δ22 = (5 + 6)-(4 + 8)=-1<0. Так как Δ22=-1< 0, осуществляем сдвиг по циклу (2,2), (3,2), (3,1), (2,1) на величину θ={10,40}=10. Приращение целевой функции ΔF= -1 · 10 = -10. Получаем пятое опорное решение Х5.

bj ai
   
 

Значение целевой функции на нем

F(X5) = 20 · 2 + 10 · 5 + 20 · 7 + 20 · 6 + 30 · 8 = 590.

Вычисляем оценки для свободных клеток: Δ11= (1 + 7) — (2 + 4) =2 > 0, Δ12 = (3 + 7) - (2 + 5) = 3 > 0, Δ33 = (15 + 5) - (7 + 8) = 5 > 0. Все оценки для свободных клеток положительные, следовательно, реше­ние оптимально.

Ответ: min F(X) = 590 при .

<== предыдущая лекция | следующая лекция ==>
Метод минимальной стоимости | Метод потенциалов

Дата добавления: 2014-01-04; Просмотров: 744; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.005 сек.