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


@темы: Линейное программирование

Комментарии
19.10.2009 в 12:46

не подходите слишком близко, я тигренок, а не киска...
тут книга есть, линейное программирование. Это самые азы. Посмотрите.
19.10.2009 в 12:53

Холодно. Пью.
Расскажу, как мы решали в школе. Может быть, у вас другие требования к решению.
Для начала можно изобразить на графиках множество точек, удовлетворяющих условиям x - 2 * y + 1 = 0, 3 * x + 5 * y + 14 = 0, 5 * x + y - 6 = 0. Ясно, что графики представляют собой прямые (пускай прямая задаётся условием a * x + b * y + c = 0). Каждая прямая делит плоскость на две части. На этой прямой лежат все точки, которые удовлетворяют равенству нулю выражения a * x + b * y + c. Возьмём на плоскости любую точку вне этой прямой. Для этого можно взять точку с какой-нибудь очень большой координатой, например, x = 1000000, y = 10 (Ясно, что это условный пример. Для a = 10, b = -2, c = -23 получится 10 * 1000000 - 2 * 10 - 23 ). Мы получим, что значение выражения a * x + b * y + c будет больше нуля (как в примере) или меньше нуля. Возьмём точку в другой полуплоскости, там значение выражения a * x + b * y + c будет иметь противоположный знак (почему так — предлагаю в это поверить). Далее, мы делаем следующее умозаключение: т.к. все точки, в которых выражение a * x + b * y + c равно нулю лежат на прямой, и т.к. между областями, где это выражение больше нуля, и где меньше нуля, должна быть область, где это выражение равно нулю (почему так — тоже предлагаю поверить), то во всей первой полуплоскости выражение будет больше нуля, а во всей второй — меньше нуля.
И так для всех прямых.
Нам нужна та область, которая подходит нам по каждому из условий.
Как найти угловые точки? Эта точка принадлежит двум прямым, т.е. её координаты удовлетворяют обоим равенствам, например: x - 2 * y + 1 = 0, 3 * x + 5 * y + 14 = 0. Понятно, что делать дальше?
19.10.2009 в 14:33

Всё должно быть сделано настолько простым, насколько это возможно, но не проще. А. Энштейн
Да самое нормальное - это заштриховать области неравенств. То есть выделить везде y и заштриховать. Потом выбрать общее. Это как множества
19.10.2009 в 15:37

пока не очень, буду изучать литературу
19.10.2009 в 16:05

из всего сказанного, я понял что должен построить на графике эти прямые например х-2*y+1=0 отсюда следует y=-(x+1)/2, на нём определить по какую сторону находятся точки удовлетворяющие неравенству точки? А угловые точки будут лежать на пересечении двух прямых и их будет три, а для того что бы найти их надо решать систему из двух уравнений с двумя неизвестными с помощью матриц???
19.10.2009 в 16:06

не подходите слишком близко, я тигренок, а не киска...
угу, правильно поняли!!!
Почти правильно)
Чтобы найти эти точки Вам надо решить 3 системы.
19.10.2009 в 16:09

Всё должно быть сделано настолько простым, насколько это возможно, но не проще. А. Энштейн
х-2*y+1=0 отсюда следует y=-(x+1)/2,
Отсюда не следует это. А следует у=(x+1)/2
Давайте разберём первое неравенство.

x-2y+1>=0 <=> y<=(x+1)/2 = x/2+1/2

Строите прямую y=x/2+1/2. Так как у должен быть меньше прямой, то это вся полуплоскость под нарисованной вами прямой. Это легко проверить, подставив точки под и над прямой. Увидите, где соотношение выполняется.
Заштрихуете эту область.
Начертите вторую и третью прямые аналогично, заштрихуете другим цветом и выберете, где все 3 неравенства имеют решение. Это и будет вашей областью.

Угловая точка - точка пересечения двух прямых. Соответсвтенно, вам придётся решать несколько систем уравнений из 2ух уравнений с двумя неизвестными
19.10.2009 в 16:24

ну, да, я там упустил что у меня в начальном уравнении -2y, то что три системы я тоже понял, так как находить три точки? я так понял их можно решить и не прибегая к матрицам, а просто выражая одну неизвестную через другую и подставлять во второе уравнение системы
19.10.2009 в 16:27

Всё должно быть сделано настолько простым, насколько это возможно, но не проще. А. Энштейн
Inklinometrist так как находить три точки? я так понял их можно решить и не прибегая к матрицам, а просто выражая одну неизвестную через другую и подставлять во второе уравнение системы
Совершенно верно. Как вам удобно - так и решайте
19.10.2009 в 16:46

огромное спасибо, вывели из тупика
22.10.2009 в 12:03

возвращаясь к написанному, построил я графики трёх прямы и получил такую область (извените рисовал в паинте)
тогда получается что у меня только две угловые точки???

22.10.2009 в 12:07

Холодно. Пью.
Inklinometrist, ну да, получается, что две.
22.10.2009 в 12:11

т.е третью мне просто не учитывать?
22.10.2009 в 12:18

Холодно. Пью.
Inklinometrist, а кто сказал, что их обязательно должно быть три?
22.10.2009 в 13:06

просто как область в нутри триугольника как то красивее :-)
22.10.2009 в 14:50

Холодно. Пью.
Inklinometrist, согласен, ну как уж получилось.:-)
22.10.2009 в 15:42

Я одна, но всё же я есть. Я не могу сделать всё, но всё же могу сделать что-то. И я не откажусь сделать то немногое, что могу (c)
По-моему, в книге Лунгу рассматриваются и бесконечные области