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

Народ! (Уважаемые господа!) Может у кого-то была такая же проблема. Черт дернул меня взять дипломную работу  :-[ по теме "Линейное программирование"! Я порылся в теории вопроса, выяснилось, что надо рассматривать задачи минимизации или максимизации. Тут-то все понятно, даже примеры есть, как ,например, минимизировать расходы при доставке грузов со складов в магазины; при закупке пищевых продуктов по норме белков, углеводов и жиров; максимизировать производительность станков и т.д. Но хотелось бы чего-то более реального, близкого к повседневной жизни обычного человека (например, студента). Тем более, что впоследствии это надо будет красиво и наглядно оформить в виде программы (на 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 компов с известными расстояниями. Предположим, что никто ничего не знает про сетевое оборудование, и компы надо друг с другом как-то связать. Есть набор способов соединения: коаксиал, витая пара, оптоволокно, голубые зубы,... (про их ограничения тоже никто ничего не слышал) и связанные с ними..., скажем, помехи. Есть функция удовлетворительности сети от стоимости и помехозащищенности, которую и надо минимизировать.

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

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