Поиск:

Ответ в темуСоздание новой темы Создание опроса
> метод "надувного шарика", метод "надувного шарика" 
:(
    Опции темы
Зинаида
Дата 24.2.2010, 10:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 9
Регистрация: 24.2.2010

Репутация: нет
Всего: нет



         Здравствуйте!
  Нужен алгоритм метода "надувного шарика" для решения целочисленной задачи линейного программирования. Подскажите, пожалуйста.
PM MAIL   Вверх
Akina
Дата 24.2.2010, 11:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



Он же "метод Бронфельда". Описан в:
Бронфельд Г.Б. Алгоритм решения задачи оптимального распределения плана производства // Труды института. Автоматизация и механизация управления производством, Горький, НИИУавтопром, 1977, вып.2, с. 75-83.
Боюсь, эти материалы тебе удастся добыть только в бумаге препринтом через МБА.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
sirius2
Дата 15.5.2017, 12:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 15.5.2017

Репутация: нет
Всего: нет



Теперь могу ответить уверенно.

1. Указанная моя статья уже 14 лет, как выложена в Интернете по адресу http://sirius-2.narod.ru/tw.htm

Для желающих могу ее выслать по эл.адресу, когда обратитесь.

2. Там описано около 95% основы алгоритма, но ее вполне достаточно для начала работы с ним.
Причины и сама история создания алгоритма описывалась не раз мною в Интернете, в т.ч. на первом моем сайте.
 Но наиболее полно это изложено в книге Бронфельд Г.Б. Прямое наложение знаний и его возможности. Анализ, методология, новая модель знаний, алгоритмы, возможности «невозможности».    -   Saarbrucken, Deutschland:  LAP LAMBERT Academic Puplishng, 2014. – 236 с.
В ряде нижегородских библиотек она есть.

Доступна к приобретению через Интернет.

3. Наиболее полно (пока) алгоритм описан в моей книге Бронфельд Г.Б. Основы искусственного интеллекта : учеб. пособие / Г.Б. Бронфельд; Нижегород. гос. техн. ун-т. им. Р.Е.Алексеева. – Н. Новгород, 2014. – 253 с.

В ряде библиотек России она есть.
Желающим могу по их запросу выслать главу из этой книги с некоторыми существенными уточнениями на текущий момент.

4. И еще наиболее важный момент. После длительных задержек по разных причинам, наконец, снова удалось запрограммировать метод, его проверить и сравнить в частности, с некоторыми методами для решения задач линейного программирования при сравнимой постановке задачи. Напоминаю, что первый раз этот метод удалось запрограммировать и реально внедрить для решения задач раскроя в 1992 г. Результаты были блестящие, и хороший программист у меня был, но тогда в России многокритериальная оптимизация никому не нужна была. А за рубежом тоже не заметили яркий прорыв в теории и практике решения оптимизационных задач и никто не обратился. 

5. Метод "надувного шарика" (МНШ) естественно показывает блестящие результаты на решении многокритериальных задач, где критерии представлены нелинейными неубывающими функциями. Тот вариант программы, который сделан сейчас, работает на размерности до 1000х1000, т.е. для 1 миллиона переменных.  Не могу сказать, что программа сильно оптимизирована, все еще впереди. И на обычном ноутбуке считает эту задачу при предельном размере - 20 часов. Сравнивали это с Matlab, он на этой размерности он не срабатывает. На меньшей размерности, например, 100х100 расчет с МНШ идет в пределах 1 сек.

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

7. Напоминаю, что это фактически продолжение постановки задачи, сделанной еще Нобелевским лауреатом Канторовичем Л.В. в его книге 1959, 1960 годов. Постепенно эта постановка задачи забылась, но постепенно оказалось содержит в себе новые мощные неиспользованные возможности.  
Поэтому, чтобы использовать МНШ, Вам надо по иному сделать математическую постановку задачи. Причем она будет в большинстве случаев намного лучше соответствовать Вашей реальной задаче, еще до математической формализации, которую требуют другие методы линейного и нелинейного программирования.

Желаю успехов.

С уважением, автор, к.т.н. Бронфельд Геннадий Борисович, [email protected] 

PS. Тут у меня есть какие-то проблемы с доступом, пока не разобрался. Поэтому если хотите получить ответ, лучше дублируйте мне прямо на эл.почту.
PM MAIL   Вверх
Akina
Дата 15.5.2017, 14:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



sirius2, думаю, что за 7 прошедших лет автору удалось решить поставленную задачу...


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
sirius2
Дата 16.5.2017, 15:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 15.5.2017

Репутация: нет
Всего: нет



И прекрасно. Раньше все равно ответ был бы недостаточно обоснован.

Но проблема для многих других, кто сталкивается с многокритериальными и оптимизационными задачами никуда не делась
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1111 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.