20.07.2017, 21:35 [+3 UTC]
в нашей команде: 2 065 чел. | участники онлайн: 4 (рекорд: 21)

:: РЕГИСТРАЦИЯ

:: консультации

:: задать вопрос

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.41 (25.02.2017)

Общие новости:
23.02.2017, 09:51

Форум:
20.07.2017, 21:20

Последний вопрос:
20.07.2017, 15:47

Последний ответ:
20.07.2017, 16:56

Последняя рассылка:
20.07.2017, 15:45

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
21.02.2010, 22:59 »
Бабич Илья Александрович
Спасибо большое,понял где ошибся когда сам делал [вопрос № 176834, ответ № 259644]
13.01.2012, 16:07 »
Даровко Антон Владимирович
Гордиенко Андрей Владимирович, я оценил Ваше решение на отлично. [вопрос № 185158, ответ № 269564]
18.01.2010, 11:57 »
markiza
Спасибо Вам огромное!!!!Очень рада!!!А можно я потом ещё задам вопросы по теме искусство-живопись???Вы мне поможете ещё??? [вопрос № 176107, ответ № 258712]

РАЗДЕЛ • Исследование операций

Консультации и решение задач по исследованию операций, линейному, динамическому программированию, теории игр и сетевому планированию.

[администратор рассылки: Коцюрбенко Алексей aka Жерар (Мастер-Эксперт)]

Лучшие эксперты в этом разделе

Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 313
Коцюрбенко Алексей aka Жерар
Статус: Мастер-Эксперт
Рейтинг: 128
CradleA
Статус: Профессионал
Рейтинг: 48

Перейти к консультации №:
 

Консультация онлайн # 191120
Автор вопроса: zwety21 (Посетитель)
Отправлена: 09.06.2017, 22:20
Поступило ответов: 1

Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Используя метод потенциалов, решить транспортную задачу.
Выполнить проверку, используя табличный редактор Microsoft Excel

-----
 Прикрепленный файл (кликните по картинке для увеличения):

Состояние: Консультация закрыта

Здравствуйте, zwety21!

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

В данном случае исходная таблица имеет вид:

ЗаводКомбинат 1Комбинат 2Комбинат 3Производство
110152555
22053030
312102025
Потребность502535110

Наименьшая стоимость перевозки в таблице равна 5. Выберем клетку 2:2 с данной стоимостью. Потребность равна 25, производство равно 30, поэтому перевозка будет равна min(25,30)=25. Потребность комбината 2 стала равна 0 (25-25), производство завода 2 стало равно 5 (30-25), поэтому исключаем из дальнейшего рассмотрения второй столбец (соответствующий комбинату 2):
ЗаводКомбинат 1Комбинат 2Комбинат 3Производство
110152555
2205*25305
312102025
Потребность5003585

В оставшейся части таблицы наименьшая стоимость перевозки равна 10. Выберем клетку 1:1 с данной стоимостью. Потребность равна 50, производство равно 55, поэтому перевозка будет равна min(50,55)=50. Потребность комбината 1 стала равна 0 (50-50), производство завода 1 стало равно 5 (55-50), поэтому исключаем из дальнейшего рассмотрения первый столбец (соответствующий комбинату 1):
ЗаводКомбинат 1Комбинат 2Комбинат 3Производство
110*5015255
2205*25305
312102025
Потребность003535

Наименьшая стоимость 20, клетка 3:3, перевозка min(35,25)=25, исключаем строку 3:
ЗаводКомбинат 1Комбинат 2Комбинат 3Производство
110*5015255
2205*25305
3121020*250
Потребность001010

Наименьшая стоимость 25, клетка 1:3, перевозка min(10,5)=5, исключаем строку 1:
ЗаводКомбинат 1Комбинат 2Комбинат 3Производство
110*501525*50
2205*25305
3121020*250
Потребность0055

Осталась клетка 2:3, перевозка 5, исключаем строку 2 и столбец 3:
ЗаводКомбинат 1Комбинат 2Комбинат 3Производство
110*501525*50
2205*2530*50
3121020*250
Потребность0000

Все строки и столбцы исключены (то есть оставшиеся потребности и производства равны нулю), следовательно, опорное решение построено верно. Вычислим общую стоимость поставок:
10·50 + 5·25 + 25·5 + 30·5 + 20·25 = 1400.

Теперь используем метод потенциалов для оптимизации опорного решения. Этот метод работает следующим образом:
всем производителям i и потребителям j ставим в соответствие некоторые значения ui и vj, называемые потенциалами. Один из потенциалов задаём (например, ui=0), остальные определяем исходя из того, что для стоимости cij поставки, входящей в опорное решение, должно выполняться равенство cij=ui+vj;
находим для всех перевозок оценки по формуле Δij=cij-(ui+vj). Для перевозок, входящих в опорное решение, они будут нулевые, для остальных могут отличаться от нуля;
если нет отрицательных оценок, то текущее решение является оптимальным, и оптимизация заканчивается;
в противном случае выбираем клетку с наименьшей оценкой (то есть с максимальной по абсолютной величине отрицательной оценкой;
начиная с выбранной клетки, строим в таблице замкнутый цикл, содержащий клетки опорного решения;
обходим клетки цикла в произвольном порядке, помечая их по очереди как "положительные" и "отрицательные" (выбранная клетка с наименьшей оценкой помечается как "положительная");
находим минимальное значение величины перевозки для всех "отрицательных" клеток;
уменьшаем на эту величину объёмы перевозок для всех "отрицательных" клеток цикла и увеличиваем - для всех "положительных";
получаем новое опорное решение, для которого повторяем всё сначала.

Используем метод потенциалов для оптимизации опорного решения, полученного методом минимальной стоимости:
ЗаводКомбинат 1Комбинат 2Комбинат 3Производство
110*501525*555
2205*2530*530
3121020*2525
Потребность502535110

Вычислим потенциалы:
u1=0;
c11=u1+v2=10v1=10-0=10;
c13=u1+v3=25v3=25-0=25;
c23=u2+v3=30u2=30-25=5;
c22=u2+v2=5v2=5-5=0;
c33=u3+v3=20u3=20-25=-5;
и добавим их в таблицу:
ЗаводКомбинат 1Комбинат 2Комбинат 3ПроизводствоU
110*501525*5550
2205*2530*5305
3121020*2525-5
Потребность502535110
V10025

Найдём оценки перевозок:
Δ11=0;
Δ12=c12-(u1+v2)=15-(0+0)=15;
Δ13=0;
Δ21=c13-(u2+v1)=20-(10+5)=5;
Δ2223=0;
Δ31=c31-(u3+v1)=12-(10-5)=7;
Δ32=c31-(u3+v2)=10-(0-5)=15.
Поскольку отрицательных оценок нет, опорное решение является оптимальным.


Консультировал: Коцюрбенко Алексей aka Жерар (Мастер-Эксперт)
Дата отправки: 19.06.2017, 19:59

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 191120
Коцюрбенко Алексей aka Жерар
Мастер-Эксперт

ID: 312929

# 1

= общий = | 19.06.2017, 20:37 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
zwety21:

И решение, полученное в Excel: 191120.xls (14.5 кб)

 

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

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.13790 сек.

© 2001-2017, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.41 от 25.02.2017
Бесплатные консультации онлайн