Линейное программирование. Задачи оптимизации.

Цитата J0ker, 27.08.02, 14:14:53

Есть! Сеть кампутерную собирай!
Есть n компов с известными расстояниями. Предположим, что никто ничего не знает про сетевое оборудование, и компы надо друг с другом как-то связать. Есть набор способов соединения: коаксиал, витая пара, оптоволокно, голубые зубы,... (про их ограничения тоже никто ничего не слышал) и связанные с ними..., скажем, помехи. Есть функция удовлетворительности сети от стоимости и помехозащищенности, которую и надо минимизировать.

На самом деле, задача не такая и пустая получается.

Насчет способа задания, я думаю, таблица в самый раз.

Прошу прощения, я не местный... Что из себя представляет локальная сеть? Это когда все компьютеры (n-1 шт.) соединены с одним главным (администратором)? Или когда все (n шт.) компьютеров в беспорядке связаны с собой (но обязательно все и не более 1 раза)? Если первое, тогда что же здесь оптимизировать (каким именно видом соединения связать ту или иную пару PC?), если второе – то и подавно не понимаю.

Цитата Lerik, 26.08.02, 16:03:13

Что-то не соображу. Для решения задачи минимизации надо, во-первых, составить систему неравенств
Ai1 X1+Ai2 X2+...+Ain Xn<=B,
решение которой минимизирует линейную форму
C1X1+C2X2+...+Cn Xn,
во-вторых, ... да не важно, что там во вторых! С первым бы пунктом разобраться.

Ну допустим, что минимизировать я буду сумму расстояний между отверстиями... Нет, не между отверстиями, ... по крайней мере, не

между всеми... Совсем запутался!

Чего же здесь надо минимизировать?

Пусть, к примеру имеем три резистора и, соответственно, 6 отверстий - точки A1, A2, A3, A4, A5, A6. Координаты Ai(Xi,Yi).

!-------------------------------------------------------------------------
!      A1(X1,Y1)               A2(X2,Y2)                                                     !
!                  ___________                                                                  !
!      o-------|___________|-------o                                                    !
!                        A5(X5,Y5)               A6(X6,Y6)                                   !
!                                    ___________                                                !
!                        o-------|___________|-------o                                 !
!                                                                                                     !
!                                                                                                     !
!      A3(X3,Y3)               A4(X4,Y4)                                                     !
!                  ___________                                                                 !
!      o-------|___________|-------o                                                    !
!                                                                                                     !
!_______________________________________________________________!
     A0(X0,Y0) - начальное и конечное положение патрона.
     o

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

2the_moon:
именно, маршрутный алгоритм
2Lerik:
на какой кафедре ты учился?

Цитата the_moon, 27.08.02, 20:19:25

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

Люди добрые! Вручную (перебором) оптимизировать движение головки не составит труда. Мне нужно эту задачу решить одним из методов ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, а для этого ее условия надо организовать в виде системы неравенств и одной функции (см. выше)!

Цитата bin, 27.08.02, 23:21:12

2Lerik:
на какой кафедре ты учился?

Что, так всё хреново у меня? Я студент [... Удалено автором...]. Если надо (очень) могу прислать и паспортные данные.

Сообщение отредактировано: Lerik - 08.02.03, 07:07

Проблема в том, что ни одна из поставленных задач не сводится к линейному программированию. (Я не говорю о признанных неинтересными задачах).

Для линейного программирования нужны три вещи:
(1)множество допустимых значений переменных - выпуклая односвязная область.
(2)эта область с приемлимым отношением точность/сложность аппроксимируется выпуклым n-мерным многогранником.
(3)мини/макси мизируемый критерий - линейная комбинация переменных.

Все задачи пролетают по первому или третьему пункту. В задаче со сверлом - значения переменных только целые: 1 если сверло идёт по маршруту, 0 если не идёт. В задаче о расположении компонент на плате - критерий - сумма квадратов. В задаче о локальной сети подразумевается, что оптоволокно бывает, скажем, на 100Мбит и на 200Мбит, но на 132.12394534 МБит не бывает - а это уже не односвязная область.

Перед тем, как пробовать задачу, надо сверить её как минимум с этими тремя пунктами.

А вообще, попробуй задачку: надо составить расписание физкультурных упражений так, чтобы они максимизировали вес, который человек сбросит за месяц занятий. Притом надо учитывать, что всё время заниматься одним и тем же упражнением нельзя: нагрузка должна ложиться на организм равномерно, использовать все группы мышц примерно одинаково. Придётся посмотреть, какие группы мышц в каком упражнении насколько задействованы, составить линейные ограничения так, чтобы время использования каждой группы мышц лежало в допустимых пределах и т.д.

2 Lerik: Блин, подойди к руководителю и посоветуйся - он, скорее всего, видел уже много задач, может идейку подкинет.

Цитата shadeofgray, 28.08.02, 09:50:26

А вообще, попробуй задачку: надо составить расписание физкультурных упражений так, чтобы они максимизировали вес, который человек сбросит за месяц занятий. Притом надо учитывать, что всё время заниматься одним и тем же упражнением нельзя: нагрузка должна ложиться на организм равномерно, использовать все группы мышц примерно одинаково. Придётся посмотреть, какие группы мышц в каком упражнении насколько задействованы, составить линейные ограничения так, чтобы время использования каждой группы мышц лежало в допустимых пределах и т.д.

Да, задачка, кажись, тянет на линейную оптимизацию. Если что не так - поправь.
Пусть имеем четыре упражнения: 1, 2, 3, 4.
Пять групп мышц: V, W, X, Y, Z.
Aij - действие i-го упражнения на мышцу j в одну минуту.
Сумма Ti (i=1,2,...,n) должна быть равна 5400 мин  (3 часа каждый день в течение одного месяца).
Необходимо определить время Ti, которое надо затратить на каждое i-ое упражнение, чтобы ... (не уверен) максимизировать нагрузку на весь организм, т.е.:
(A1v+A1w+A1x+A1y+A1z)*T1+...+(A5v+A5w+A5x+A5y+A5z)*T5 - max.
Система неравенств выглядит следующим образом:

/
| Sum(Aiv*Ti)<=(норма нагрузки для мышцы V), i=1,2,...,n.
/      ........................
\      ........................
|  Sum(Aiz*Ti)<=(норма нагрузки для мышцы Z), i=1,2,...,n.
\

Причем, чтобы нагрузка на все мышцы была равномерной, т.е. никакая мышца не "сачковала", их можно загрузить на полную, т.е. неравенства в системе заменить на равенства.
Чтобы не заниматься все время одним и тем же упражнением необходимо, наверное, дополнить получившуюся систему уравнений следующими строками:
Tj - Tk <= 3 (мин), j,k=1,2...,n; j<>k.

После решения задачи, т.е. нахождения Ti их надо будет разложить "пилообразно" на 30 дней.

Вроде так?

Согласен, задачка неплохая! Но пятью пять - снова двадцать пять! Какай интерфейс сделать у программы? Запустил прогу на выполнение, занес упражнения, точнее - название и нагрузку на каждую группу мышц для каждого упражнения (кстати как? Множество полей для ввода цифр?) нажал "Просчитать" и увидел результат? Вроде бы нормально, только хотелось бы не вводить все числовые данные с клавиатуры (как в языке С при редактировании шаблона окна), а просто "хлопать мышью" (как в VC++). Ну, конечно, я веду речь не о списках цифр, из которого можно выбрать мышью нужную! Составить базу данных для ВСЕХ упражнений в мире нереально: их слишком много... Хотя можно сделать определенную базу упражнений (ну, скажем, сотню) и возможность подключать к ней новые, а потом просто выбирать из прелдоженного списка необходимые упражнения... Наверное это хорошая мысль!?

Цитата J0ker, 28.08.02, 11:15:38

Блин, подойди к руководителю и посоветуйся - он, скорее всего, видел уже много задач, может идейку подкинет.

Ага, он уже подкинул! Я просто в восторге! :-((((( Зацени:

Минимизировать расходы дорожно-ремонтной бригады при выравнивании местности. Т.е. какое место равнять грейдером, какое бульдозром, а куда скреперу наведасться, чтобы сжечь поменьше соляры.
Хотя после всех наших с вами мучений, мне эта задачка уже кажется не такой уж и бредовой. Вот только карту местности (3D) наностить хреново будет каждый раз. Зато красиво! Панарама природы на экране.

Не, не, не! Ну это к черту! Прочь эти мысли!

Цитата Lerik, 28.08.02, 20:22:26

Запустил прогу на выполнение, занес упражнения, точнее - название и нагрузку на каждую группу мышц для каждого упражнения (кстати как? Множество полей для ввода цифр?) нажал "Просчитать" и увидел результат?

Кстати, а как узнать, какое упражнение на какие мышцы действует и, главное, с каким коэффициентом? ???

Цитата Lerik, 29.08.02, 07:21:43

Кстати, а как узнать, какое упражнение на какие мышцы действует и, главное, с каким коэффициентом? ???

Да-а-а, с этим будут серьезные проблемы! (У меня нет медико-физкультурного образования).

Может кто предложит что-то еще?

Тихо, сам с собой я веду беседу. Ау!

Lerik, создалось впечатление, что ты ждешь здесь сырцов - в худшем случае, свёрстанную работу - в лучшем. Тебе накидали идей "что делать" и "как делать", а делать, собственно, тебе прийдется самому. А после твоего 3-го подряд неинформационного сообщения интерес к этой теме просто угас. Если у тебя есть конкретные вопросы по реализации, то спрашивай. А про

Цитата

Кстати, а как узнать, какое упражнение на какие мышцы действует и, главное, с каким коэффициентом?

тебе врядли кто-то ЗДЕСЬ поможет возьми любые упражнения и любые коэффициенты действия на любые виды мышц, сделай файл настройки (веб-форму настройки/SQL базу с настройками/храни настройки в registry/в неиспользуемых кластерах тома) - какая, нафиг, разница что и как действует с какими коэффициентами - это диплом по линейному программированию, а не по физкультуре

Работать самому - это классно! А вот от готовой проги я не отказался бы. Чесслово!
А что касается линейности... Возьму стандартную задачу:накормить всех и сытно,и подешевле!

P.S. Анекдот: Человек не устает смотреть на три вещи: на горящий огонь, текущую воду и работу, которую делают за него. Следовательно, идеальное зрелище - пожар!