Линейни неравенства
Нека знакът за равенство в уравнението на правата линия (4) бъде заменен със знака за неравенство ³ или £ ; съответното множество от точки M(x;y) се наричаполуравнина.
Например, линейното неравенствоy³ 2x+ 3 описва полуравнина, състояща се
от всички точкинаилинад(вляво от) линияy= 2x+ 3 . По подобен начинx³ 0 е
неравенство за полуравнина, състояща се от точкинаилинадяснона оста Oy.
Системи от линейни неравенства се използват в така нареченитезадачи на линейното програмиране. Помислете за конкретен (двуизмерен) пример.
Пример.Нека някакво множество се състои от всички точки на равнината, чиито координати удовлетворяват системата от линейни неравенства ( 10.a) - (10.e).
Всички точки от равнината, които удовлетворяват тази система от неравенства, се наричат планове. Освен това е дадена линейна функцияz= 2x+ 3y, нареченаобективна функция. Задачата се поставя по следния начин: да се намери най-голямата стойност (максимум) на целевата функция върху множеството от планове. Трябва също да посочитеоптималния планM0 (x0 ;y0), на който целевата функция взема максимума. (Задачата заминимумна целевата функция се формулира по подобен начин.)
Решение на задачата чрез графичен метод.Наборът от всички планове се състои от точки, които отговарят на всичките 5 условия едновременно: тези точки се намират(a)наилиподлиниятаy-x=2,(b)наилиподлинията3 y+x=14,(c)наилинадправата линияy- 3x=-12,(d)наиливдяснона правата линияx=0,(e)наилинадредy= =0. Това означава, че наборът от планове е изпъкнал 5-ъгълник OA1A2A3A4. Всеки от неговите върхове е в пресечната точка на двойка прави, ограничаващи 5-ъгълника. Например, в пресечната точка на правиy-x= 2,x= 0, има връх A1; в пресечната точка на правиy–x= 2 , 3y+x= 14 има връх A2. Върховете A3, A4, O се определят по подобен начин.
Наборът от точки M(x;y), в които целевата функция приема някаква постоянна стойност, се наричалиния на нивозаz. Всички линии на ниво са успоредни прави линии, дадени от уравненията 2x+3y=c.
Помислете за един от тези редове 2x+ 3y =0 (тукc=0,целева функцияz
също е равно на 0). Това е линия LO с наклонk= - 2 / 3. Други линии на ниво се получават чрез преместване на линията LO успоредно. Това изместване на права линия може да се направи с линийка. Когато линийката се премести надясно (или нагоре), стойносттаcна целевата функция се увеличава. Например правата линия L1 е равна линия, минаваща през върха A1. Линийката може да се премести надясно (или нагоре), стига да има точки от 5-ъгълника на съответната линия на ниво. В резултат на това се достига до крайна точка, която ще бъде оптималният план. Това е върхът на 5-ъгълника, характеризиращ се с това, че линията на нивото, минаваща през него, няма общи точки с вътрешността на 5-ъгълника. В този случай, както се вижда от фигурата, този връх е A3( 5; 3), чиито координатиx3 = 5,y3 = 3 се намират от системата от уравнения 3y + x= 14,y- 3x= -12. Стойността на целевата функция за този дизайн еz= 2x3+3y3=2 × 5 + 3 × 3 = 19.Отговор:zmax = 19, оптималният план е M0 ( 5; 3 ).
Правило за проверка.Има прост числен метод, който ви позволява да изберете оптималния план или да проверите правилността на избрания оптимален план. Помислете за по-обща целева функцияz=a1x+a2y, за която трябва да намерите максимума. Чрез знаците на числатаa1 ,a2 вече е възможно да се посочат онези части от границата на полигона, където трябва да се търси оптималният план.
оптимален план. Акоk12³k³k23, тогава A2 е оптимален дизайн. Акоk23 ³k, тогава A3 е оптималният план.
За първата ситуация „правилото за проверка“ може да се формулира по следния начин. Позволявам
линията на нивото минава през оптималния план (-един от върховете на горната част на границата). Нека запишем коефициентите на наклона на страните на горната част на границата и линията на нивото в реда, в който тези страни и върхът на оптималния план се пресичат при обикаляне на горната част на границата отляво надясно. Ако получените числа са подредени в низходящ ред (по-общо: в монотонно ненарастващ ред), тогава върхът на оптималния план е избран правилно.
2-ра ситуация.Нека коефициентът в целевата функцияa1 > 0, тогава оптималният план е върхът от дясната страна на границата на полигона в плана. В разглеждания пример дясната страна на границата е прекъснатата линия A1A2A3, изпъкнала надясно. Обратните наклони на страните на полилинията намаляват, когато дясната граница се заобикаля отдолу нагоре. Ако обратният наклон 1/k= -a2 /a1 е такъв, че 1/k³ 1/k34, тогава A4 е оптималният дизайн. Ако 1/k34 ³ 1/k³ 1/k23, тогава A3 е оптималният план. Ако 1 /kBC ³ 1/k, тогава A2 е оптималният дизайн.