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

Народ! (Уважаемые господа!) Может у кого-то была такая же проблема. Черт дернул меня взять дипломную работу  :-[ по теме "Линейное программирование"! Я порылся в теории вопроса, выяснилось, что надо рассматривать задачи минимизации или максимизации. Тут-то все понятно, даже примеры есть, как ,например, минимизировать расходы при доставке грузов со складов в магазины; при закупке пищевых продуктов по норме белков, углеводов и жиров; максимизировать производительность станков и т.д. Но хотелось бы чего-то более реального, близкого к повседневной жизни обычного человека (например, студента). Тем более, что впоследствии это надо будет красиво и наглядно оформить в виде программы (на Visual C++), а накалывать карту какого-то райнона и т.д. достаточно проблематично (точнее, влом да и не практично).

Хотел минимизировать расстояние между радиоЭлементами на электронной плате... Да что-то не пойму, как составить нужные формулы. Может я не туда гну "линию"?

С благодарностью приму любые советы, а лучше исходник проги.

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

готовой проги нет, но ты напишешь её с легкостью
берется печатная плата, на ней надо насверлить N дырок, координаты которых известны (Xi, Yi); задача - оптимизировать движения несущей головки (со сверлом) станка с ЧПУ, вход - координаты, выход - последовательность

длина шага расчитывается по теореме пифагора

минимальная сумма длин шагов соответствует верному решению, можно внести "вес", например, сделать несколько диаметров свёрел и ф-цию их смены

Вообще-то изначально идея была другой (оптимизировать именно РАСПОЛОЖЕНИЕ ЭЛЕМЕНТОВ, т.е. уменьшить длины дорожек), но мысль хорошая, надо подумать.

Абсолютно согласен с bin - программу написать очень несложно. Насколько я понимаю, проблема заключается в том, чтобы придумать себе задачу. Лично я люблю классику - возьми задачу коммивояжера (то же, что и перевозка грузов, только формулировка другая) - как-то привычнее =)

Цитата bin, 25.08.02, 14:13:18

берется печатная плата, на ней надо насверлить N дырок, координаты которых известны (Xi, Yi); задача - оптимизировать движения несущей головки (со сверлом) станка с ЧПУ, вход - координаты, выход - последовательность

длина шага расчитывается по теореме пифагора

минимальная сумма длин шагов соответствует верному решению, можно внести "вес", например, сделать несколько диаметров свёрел и ф-цию их смены

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

Сообщение отредактировано: Lerik - 26.08.02, 12:05

Цитата J0ker, 26.08.02, 10:03:32

Абсолютно согласен с bin - программу написать очень несложно. Насколько я понимаю, проблема заключается в том, чтобы придумать себе задачу. Лично я люблю классику - возьми задачу коммивояжера (то же, что и перевозка грузов, только формулировка другая) - как-то привычнее =)

Согласен, это самое простое, потому что примеров везде - завались! Но я не очень представляю себе какой интерфейс должен быть у программы? Простая подстановка чисел, как в Excel? Не смотрится! Накалывать карту или план? Проблематично и долго!

Кстати, кто такой коммивояжер и какая у него задача?

Сообщение отредактировано: Lerik - 26.08.02, 12:10

Коммивояжер - продавец вразнос. А задача у него - обойти все населенные пункты, соедненные дорогами (граф), причем требуется пройти наименьшее расстояние.

Цитата J0ker, 26.08.02, 10:03:32

Абсолютно согласен с bin - программу написать очень несложно. Насколько я понимаю, проблема заключается в том, чтобы придумать себе задачу. Лично я люблю классику - возьми задачу коммивояжера (то же, что и перевозка грузов, только формулировка другая) - как-то привычнее =)

(1) Если "перевозка грузов" это "транспортная задача", где надо с минимальными затратами на перевозку распределить грузы между потребителями, то это абсолютно не то же, что и задача коммивояжера.
(2) Транспортная задача решается симплекс-методом за линейное время, а коммивояжёр - перебором (за соответствующее время).

моя задача - это тот же самый "Коммивояжер"
а найти надо min{Summ(Li)}, где Li^2=(X1-X2)^2+(Y1-Y2)^2 любым удобным способом, можно и полным перебором

Цитата bin, 26.08.02, 20:29:32

моя задача - это тот же самый "Коммивояжер"
а найти надо min{Summ(Li)}, где Li^2=(X1-X2)^2+(Y1-Y2)^2 любым удобным способом, можно и полным перебором

Простой перебор мне не поможет, нужен именно симплекс-метод. Дипломная все же!

Цитата bin, 26.08.02, 20:29:32

моя задача - это тот же самый "Коммивояжер"
а найти надо min{Summ(Li)}, где Li^2=(X1-X2)^2+(Y1-Y2)^2 любым удобным способом, можно и полным перебором

Э, неее, строго говоря, это не тот же самый "Комивояжёр"...
Это некий частный случай задачи коммивояжёра, т.к. расстояния между точками подчиняются определённым ограничениям (к примеру, сумма двух сторон треугольника не меньше третьей стороны). Но большой разницы всё равно нет - к Коммивояжёру симплекс-метод не пригоден.

Цитата shadeofgray, 27.08.02, 11:08:20

Коммивояжёру симплекс-метод не пригоден.

Ну хорошо, с Коммивояжёром завязали... пока что. Свежие идеи есть?

Цитата shadeofgray, 26.08.02, 17:55:12

(1) Если "перевозка грузов" это "транспортная задача", где надо с минимальными затратами на перевозку распределить грузы между потребителями, то это абсолютно не то же, что и задача коммивояжера.
(2) Транспортная задача решается симплекс-методом за линейное время, а коммивояжёр - перебором (за соответствующее время).

Имелась ввиду задача без графа - просто продать товар, если даны цены в городах и спрос.

Цитата Lerik, 27.08.02, 13:36:37

Ну хорошо, с Коммивояжёром завязали... пока что. Свежие идеи есть?

Нет, с тем, которого имелл ввиду уважаемый товарищ shadeofgray отчно завязали - она симплекс-методом не решится.

Цитата Lerik, 27.08.02, 13:36:37

Ну хорошо, с Коммивояжёром завязали... пока что. Свежие идеи есть?

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

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

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

Цитата 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. Анекдот: Человек не устает смотреть на три вещи: на горящий огонь, текущую воду и работу, которую делают за него. Следовательно, идеальное зрелище - пожар!