Показано с 1 по 19 из 19
Тема: Транспортная задача
-
30.04.2009, 02:01 #1
- Регистрация
- 20.03.2009
- Сообщений
- 52
Транспортная задача
Доброго времени суток. Подскажите,пожалуйста, кому-нибудь приходилось решать задачи такого типа?
Спасибо!
-
30.04.2009, 07:09 #2
- Регистрация
- 25.11.2005
- Сообщений
- 1,731
Красивые задачи. Обе.
Типичные задачи раздела "Линейное программирование" курса прикладной математики любого вуза.
Даже указан пакет программ для решения таких задач.
В чем проблема?
-
30.04.2009, 13:51 #3
- Регистрация
- 20.03.2009
- Сообщений
- 52
Сообщение от Евгений_Кс
Спаасибо!
-
30.04.2009, 13:58 #4
- Регистрация
- 25.11.2005
- Сообщений
- 1,731
Сообщение от Эдуард Шимякин
-
30.04.2009, 14:14 #5
- Регистрация
- 20.03.2009
- Сообщений
- 52
Сообщение от Евгений_Кс
Как я понимаю поисковая система яндекса?Хотелось бы пообщаться с экспертом в этой области
-
30.04.2009, 14:49 #6
- Регистрация
- 25.11.2005
- Сообщений
- 1,731
Сообщение от Эдуард Шимякин
-
30.04.2009, 15:30 #7
- Регистрация
- 20.03.2009
- Сообщений
- 52
Сообщение от Евгений_Кс
Указываете код и все
-
30.04.2009, 15:32 #8
Предыдущие авторы уже все сказали, но хочу добавить свои пять копеек - Вентспилс находится не в Литве, а в Латвии. Это так, географическая ошибка
-
30.04.2009, 15:49 #9
- Регистрация
- 20.03.2009
- Сообщений
- 52
разбил файл на 2 части
-
01.05.2009, 19:42 #10
- Регистрация
- 09.07.2007
- Сообщений
- 724
Эдуард,
Вы молодец, сумели хоть как-то зацепить проблему.
Кстати, даже на данном форуме, кто-то раз в 2-3 года подымает эту же проблему в разных вариантах.
Тут конечно многое на самом деле сложнее, чем с виду кажется.
И конечно, одна из проблем – в задаче линейного программирования (ЛП). Она удобна для ученых, но на практике весьма слаба и мало полезна, хотя активно применяется.
1. Вы правильно заметили, что при одном суммарном объеме поставке у Вас получаются разные варианты решений и непонятно что с этим делать.
2. И Вы правильно заметили, что программа себя как-то странно ведет, если начинаете искать разные варианты решений.
Дело в том, что суммарный показатель ВЕСЬМА ПЛОХ, как оптимизируемый показатель, хотя неплох для оценки итоговых результатов, но это разные вещи.
А увлечение оптимизацией суммарного показателя связано во многом именно с ЛП.
Дело в том, что практические задачи ВСЕГДА ИНЫЕ И БОЛЕЕ СЛОЖНЫЕ, чем описано в учебной задаче.
Например, ВЫ НЕ МОЖЕТЕ ПРОСТО ТАК отправить нефть через какие-то порты и, кстати, по каким-то направлениям перевозки, А ТОЛЬКО ПО ДОГОВОРАМ НА РАЗНЫХ УСЛОВИЯХ, в т.ч. ПО ОПЛАТЕ.
В результате получается, что Вы должны (или можете) через один порт отправить столько-то, через другой столько-то и т.д.
В результате получается (И ВЕСЬМА НЕРЕДКО), что если Вы через какой-то порт не отправите (или по такому-то направлению транспортировки) столько, сколько намечено, то Вас так накажут, что Вам никакое увеличение суммарного увеличения объема не поможет.
Что же делается на практике? А пытаются решать задачу итеративно, подбирая решения, обсуждая получаемые варианты и снова вводя новые данные для нового решения.
В ряде случаев создают специальные мощные и сложные программные средства для решения итеративным способом на кооперативной основе конкретной оптимизируемой задачи для конкретного предприятия и организации.
Но далеко не все руководители даже понимают необходимость И ВОЗМОЖНОСТЬ этого и просто занимаются текущей организационной работой (пытаясь решить данную задачу), совершенно не понимая, что теряют просто масса времени, денег и возможностей выхода из положения.
Т.е. задача совсем не имеет отношения к ЛП, должна записываться по другому и максимизируемые показатели СОВСЕМ ИНЫЕ.
Но для записи задачи по-иному, у Вас в задаче не хватает исходных данных.
Что имеет автор задачи в виду, мне непонятно и что хочет добиться тоже, тут надо знать увлечения авторов или того, кто Вам эту задачу дал, какими-то методами. Дополнительно, как минимум, Вам надо знать, как меняются приоритеты и объемы поставок по конкретным портам и по отдельным направлениям в процессе решения задачи. И вот эти-то приоритеты И ЯВЛЯЮТСЯ реальными критериями нахождения необходимого решения. А суммарный итог будет лишь как итог найденного решения.
Кажется, что задача тогда резко усложнится и станет даже почти неразрешимой.
В принципе, как минимум, 50 лет назад был сформулирован нашим Нобелевским лауреатом Л.В.Канторовичем иной критерий – это во сколько раз будет перевыполнен заданный ассортимент. В исходном варианте она тоже с виду сводится тоже к задаче ЛП. В качестве ассортимента можно задать объем перевозок через конкретные порты. Но такая попытка с применением ЛП приведет для Вас скорее всего к еще более неудачному результату.
Для решения подобных задач я в 1975 г. (в 1977 г. опубликовал) вышел на новый метод решения, который назвал позже методом «надувного шарика» (МНШ). Он абсолютно иной, чем известные методы ЛП, хотя с отдельными методами имеет определенное пересечение.
Что-то по МНШ можно почитать в моих публикациях
http://sirius-2.narod.ru/tw.htm
http://sirius-2.narod.ru/stat_opt_plan.htm
http://sirius-2.narod.ru/stat_opt_raskr.htm
История его появления описана в http://sirius-2.narod.ru/n21.html
Как раз МНШ и позволяет решать подобные задачи и еще гораздо более широкий круг, что фактически уже продемонстрировал Лорьер http://sirius-2.narod.ru/n213.html
-
01.05.2009, 23:47 #11
- Регистрация
- 20.03.2009
- Сообщений
- 52
Геннадий Борисович, я Вам признателен за ваше сообщение, но есть конкретное условие и конкретная программа QSB,с помощью которой ее нужно решить.
За теорию спасибо!
-
02.05.2009, 08:48 #12
- Регистрация
- 25.11.2005
- Сообщений
- 1,731
Эдуард, лень разбираться в первой задаче.
Решение второй задачи см. во вложении.
Буду признателен тем, кто укажет на мои ошибки.
-
02.05.2009, 18:31 #13
- Регистрация
- 20.03.2009
- Сообщений
- 52
Евгений, у меня получились совершенно другие числа
-
02.05.2009, 19:17 #14
- Регистрация
- 25.11.2005
- Сообщений
- 1,731
Сообщение от Эдуард Шимякин
Кем? Вами? Мной - Не подразумевается.
Фраза "Анализ решения задачи выполнить с использованием пакета WinQSB" относится к условию не двух, а только первой задачи.- Суммарная производственная мощность шести заводов (из задачи 1) 2110 тонн.
- С учетом пропускной способности исходящих от заводов веток заводы могут впустить в транспортную систему 120+220+120+60+540+800=1860 тонн.
120+220+140+140+900+1000=2520 тоннПо данным первой задачи Пермь способна произвести только 120 тонн, так что вся пропускная способность исходящих веток не может быть использована.Аналогично Новгород производит и впускает в систему только 60 тонн.
- С учетом пропускной способности входящих в порты веток порты могут пропустить дальше 225+340+200+450+440==1655 тонн (пропускную способность Усть-Луги берем 150+75=225)
По данным первой задачи Вентспилс способен перегружать с поездов на суда только 440 тон, так что пропускная способность входящих веток в размере 400+430 тонн не может быть использована.300+300+50+40+260+100+100+250+400+430=2230- Прорисовываем движение потоков по веткам через узлы Т1-Т5 так, чтобы загрузить полностью входящие в порты ветки и видим, что это может быть сделано легко многими способами.
Ограничением транспортной системы являются:
1) недостаточная пропускная способность веток, входящих в порты СПБ и Таллинна.
2) Недостаточная пропускная способность портов Усть-Луга, Лахти, Вентспилс.
Максимальный поток – 1655 тонн.
-
02.05.2009, 20:05 #15
- Регистрация
- 24.11.2005
- Сообщений
- 570
Сообщение от Евгений_Кс
Теперь, повидимому, сдедует сделат оставшиеся 4 шага, следуя известной голдраттовской процедуре...
Хотелось бы еще и взглянуть (хотя бы теоретически), как Вам представляется "Дерево будущей реальности" для обсуждаемой транспортной задачи.
-
02.05.2009, 23:48 #16
- Регистрация
- 20.03.2009
- Сообщений
- 52
Если я еще что-то помню из математики,то имеем дело со смешанным графом G=(16,5,20)
-
03.05.2009, 08:25 #17
- Регистрация
- 25.11.2005
- Сообщений
- 1,731
Сообщение от air
На втором и третьем шаге анализируем, как можно ослабить влияние ограничения и подчиняем всю работу потребностям текущего ограничения.
Конкретно:
1. Перенаправляем пассажирский транспорт с веток, входящих в СПб и Таллинн, чем увеличиваем их пропускную способность для перевозки грузов.
2. Организуем приоритетный ремонт и обслуживание путевого хозяйства и подвижного состава веток, входящих в СПб и Таллинн.
3. Организуем приоритетный ремонт и обслуживание терминалов портов Усть-Луги, Лахти и Вентспилса.
На четвертом шаге увеличиваем пропускную способность ограничения.
Конкретно:
1. Изучаем логистику перегруженных веток и портов и улучшаем ее.
2. В ходе дополнительного анализа выясняем, к какому порту рационально строить новую ветку либо в каком порту строить новый терминал, и принимаем решение.
На пятом шаге - в новых условиях определяем новое ограничение.
Хотелось бы еще и взглянуть (хотя бы теоретически), как Вам представляется "Дерево будущей реальности" для обсуждаемой транспортной задачи.
-
03.05.2009, 11:11 #18
- Регистрация
- 24.11.2005
- Сообщений
- 570
Сообщение от Евгений_Кс
-
04.08.2009, 14:36 #19
- Регистрация
- 04.08.2009
- Сообщений
- 1
вот ссылка. В файле находится программа и пояснительная записка, где очень очень подробно всё описывается.
http://letitbit.net/download/1815.1a...river.rar.html