143681 (727106), страница 3

Файл №727106 143681 (Решение задач транспортного типа методом потенциалов) 3 страница143681 (727106) страница 32016-08-01СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана 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

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 , 

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

В таблице № 5 мы получили в двух клетках čij сij , теперь можно построить цикл в любой из этих двух клеток. Выгоднее всего строить цикл в той клетке, в которой разность čij сij максимальна. В нашем случае в обоих клетках разность одинакова (равна 1), поэтому, для построения цикла выберем, например, клетку (4,2):

Таблица №6

ПН

ПО

В1

В2

В3

В4

В5

i

А1

10

8

5

42

6

6

9

0

А2

6 +

4

7

8

6

5 -

26

-1

А3

8

7 -

27

10

8

7 +

0

1

А4

7 -

14

5 +

4

6

6

8

0

j

7

6

5

6

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.

Список использованной литературы

1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976г.

2. Карманов В.Г. Математическое программирование. – М.; Наука, 1986г.

3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. – М.; Наука, 1978г.

4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. – М.; Наука, 1979г.

5. Бронштейн И.Н., Семендяев К.А. Справочник по математике. – М.; Наука, 1986г

16


Характеристики

Тип файла
Документ
Размер
184 Kb
Тип материала
Предмет
Учебное заведение
Неизвестно

Список файлов реферата

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее