Метод потенциалов

Сентябрь 3, 2022

Главная
Алгебра
Метод потенциалов

Содержание

2. Метод минимального (максимального) элемента Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую
3. Задание Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:
4. Задание Найти опорный план для задачи
5. Метод потенциалов Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый
6. Метод потенциалов До сих пор мы никак не связывали платежи (αi и βj ) и псевдостоимости
7. Метод потенциалов Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным
8. Метод потенциалов Для решения транспортной задачи нам нужно одно - построить потенциальный план. Оказывается его можно
9. Процедура построения потенциального (оптимального) плана В качестве первого приближения к оптимальному плану берётся любой допустимый план.
10. Критерий оптимальности Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия
11. Метод потенциалов Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s),
12. Пример Найдём оптимальный план задачи. Фирма должна отправить некоторое количество кроватей с трёх складов в пять
13. Пример В качестве опорного плана возьмем план, полученный с помощью метода "минимального элемента" Х11=3, Х12=12, Х21=2,
14. Пример Так как у нас получились отрицательные значения, то полученный план не является оптимальным. Выберем ячейку
15. Строим следующую транспортную таблицу
16. Пример Проверим полученный план на оптимальность. Теперь ячейка 12 не заполнена.
17. Пример Построенный план не является оптимальным, следовательно, производим пересчет. Выберем ячейку 35.
18. Пример Строим следующую транспортную таблицу.
19. Пример Проверим построенный план на оптимальность. Полученный план является оптимальным. Х11=15, Х22=12, Х24=8, Х25=5, Х31=5, Х33=5,
21. Скачать презентацию

Слайд 2

Метод минимального (максимального) элемента
Суть метода заключается в том, что из

всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai и bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Слайд 3

Задание
Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:

Слайд 4

Задание
Найти опорный план для задачи

Слайд 5

Метод потенциалов
Идея метода потенциалов для решения транспортной задачи сводиться к

следующему. Представим себе что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё ровно куда) какую-то сумму αi ; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму βj . Эти платежи передаются некоторому третьему лицу (“перевозчику“). αi + βj ( i=1..m ;j=1..n) будем называть “псевдостоимостью” перевозки единицы груза из Ai в Bj . Заметим, что платежи αi и βj не обязательно должны быть положительными; не исключено, что “перевозчик” сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (αi и βj) одна и та же и от плана к плану не меняется.

Слайд 6

Метод потенциалов
До сих пор мы никак не связывали платежи (αi

и βj ) и псевдостоимости с истинными стоимостями перевозок Ci,j. Теперь мы установим между ними связь. Предположим, что план (xi,j) невырожденный (число базисных клеток в таблице перевозок ровно (m + n -1). Для всех этих клеток xi,j>0. Определим платежи (αi и βj ) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:
αi + βj = сi,j , при xi,j >0.
Что касается свободных клеток (где xi,j = 0), то в них соотношение между псевдостоимостями и стоимостями может быть какое угодно.

Слайд 7

Метод потенциалов
Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает,

является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана (xi,j > 0)
αi + βj = сi,j , (1)
а для всех свободных клеток ( xi,j =0)
αi + βj ≤ сi,j , (2)
то план является оптимальным и никакими способами улучшен быть не может. Нетрудно показать, что это теорема справедлива также для вырожденного плана, и некоторые из базисных переменных ровны нулю. План обладающий этим свойством называется потенциальным планом, а соответствующие ему платежи (αi и βj) — потенциалами пунктов Ai и Bj ( i=1,...,m ; j=1,...,n ).

Слайд 8

Метод потенциалов
Для решения транспортной задачи нам нужно одно - построить потенциальный

план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: Какова бы ни была система платежей (αi и βj ) удовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке.

Слайд 9

Процедура построения потенциального (оптимального) плана
В качестве первого приближения к оптимальному плану

берётся любой допустимый план. В этом плане m+n-1 базисных клеток, где m - число строк, n - число столбцов транспортной таблицы. Для этого плана можно определить платежи (αi и βj), так, чтобы в каждой базисной клетке выполнялось условие :
αi + βj = сi,j (3)
Уравнений (3) всего m+n-1, а число неизвестных равно m+n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m+n-1 уравнений (3) можно найти остальные платежи αi , βj , а по ним вычислить псевдостоимости для каждой свободной клетки.
Если оказалось, что все эти псевдостоимости не превосходят стоимостей, то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости, то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла равна разности между стоимостью и псевдостоимостью в этой свободной клетке.

Слайд 10

Критерий оптимальности
Если известны потенциалы решения Х0 транспортной задачи и для всех

незаполненных ячеек выполняются условия αi + βj ≤ сi,j, то Х0 является оптимальным планом транспортной задачи.
Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.
Цикл перерасчёта таблицы - это последовательность ячеек, удовлетворяющая условиям:
одна ячейка пустая, все остальные занятые;
любые две соседние ячейки находятся в одной строке или в одном столбце;
никакие три соседние ячейки не могут быть в одной строке или в одном столбце.
Пустой ячейке присваивают знак + , остальным - поочерёдно знаки - и + .

Слайд 11

Метод потенциалов
Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят

незаполненную ячейку (r, s), в которой αr + βs = сr,s , и строят соответствующий цикл; затем в минусовых клетках находят число X=min(Xi,j). Далее составляют новую таблицу по следующему правилу:
В плюсовых клетках добавляем Х;
Из минусовых клеток вычитаем Х;
Все остальные клетки вне цикла остаются без изменения.
Получим новую таблицу, дающую новое решение Х, такое, что F(X1)<=F(X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

Слайд 12

Пример
Найдём оптимальный план задачи.
Фирма должна отправить некоторое количество кроватей с трёх

складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице.

Слайд 13

Пример
В качестве опорного плана возьмем план, полученный с помощью метода "минимального

элемента" Х11=3, Х12=12, Х21=2, Х24=8, Х25=15, Х31=15, Х33=5. Все остальные элементы равны 0.
Составим систему уравнений для нахождения потенциалов решения, найдем сумму соответствующих потенциалов для каждой свободной ячейки и пересчитаем тарифы (стоимости) для каждой свободной ячейки.

Слайд 14

Пример
Так как у нас получились отрицательные значения, то полученный план не

является оптимальным. Выберем ячейку для пересчета 22. Получим:

Слайд 15

Строим следующую транспортную таблицу

Слайд 16

Пример
Проверим полученный план на оптимальность. Теперь ячейка 12 не заполнена.

Слайд 17

Пример
Построенный план не является оптимальным, следовательно, производим пересчет. Выберем ячейку 35.

Слайд 18

Пример
Строим следующую транспортную таблицу.

Слайд 19

Пример
Проверим построенный план на оптимальность.
Полученный план является оптимальным. Х11=15, Х22=12,

Х24=8, Х25=5, Х31=5, Х33=5, Х35=10. Все остальные Хij=0.
F=1*15+1*12+3*8+3*5+4*5+1*5+3*10=121

Метод потенциалов

Содержание

Метод минимального (максимального) элемента Суть метода заключается в том, что из

ЗаданиеСоставить первоначальный опорный план методом минимального элемента для транспортной задачи вида:

ЗаданиеНайти опорный план для задачи

Метод потенциалов Идея метода потенциалов для решения транспортной задачи сводиться к

Метод потенциалов До сих пор мы никак не связывали платежи (αi

Метод потенциаловОказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает,

Метод потенциаловДля решения транспортной задачи нам нужно одно - построить потенциальный

Процедура построения потенциального (оптимального) планаВ качестве первого приближения к оптимальному плану

Критерий оптимальностиЕсли известны потенциалы решения Х0 транспортной задачи и для всех

Метод потенциаловДля перераспределения плана перевозок с помощью цикла перерасчёта сначала находят

ПримерНайдём оптимальный план задачи.Фирма должна отправить некоторое количество кроватей с трёх

ПримерВ качестве опорного плана возьмем план, полученный с помощью метода "минимального

ПримерТак как у нас получились отрицательные значения, то полученный план не