математика и

Икономическата-математическо моделиране. Задачата на линейното програмиране. Графичен метод за решаване

Графичен метод за решаване на линейното програмиране проблем се прилага само в случай на две променливи. Нека разгледаме проблема с две променливи x1 и x2 и м ограничения - неравенства

Първата стъпка при използването на графичен метод е геометрична представяне на набор от всички възможни решения, т.е. в изграждането на областта на равнината, в която и двете изпълнени всички ограниченията на модела. Тази област се нарича допустима. Последното условие (43) означава, че възможните решения, представени с точки на неотрицателна първи квадрант. уравнение

Това е уравнение на права линия със самолет. неравенство

определя полуравнина, да лежи на едната страна на тази линия. За да се определи местоположението на тази полуравнина спрямо граничната линия, можете да заместите координатите на всяка точка в съответния неравенството и да го провери. Ако е вярно, че целият период на самолета, който е на мястото, е решението. Мястото на точки, отговарящи на система от неравенството (43), е пресечната точка на половин равнините, определени от линиите

Този район е изпъкнал многоъгълник или многоъгълна изпъкнало множество, ако той е неограничен. Комплектът за пресичане многоъгълник и

също неотрицателно квадрант е изпъкнало множество многоъгълник. Част от равнината, в която съответното ограничение се извършва под формата на неравенството е посочено от стрелка сочи в посока на допустим променливи. Вие областта на изпълними решения, представени по-долу.

Вторият етап на графичен метод е удобен геометрична интерпретация на обективната функция. В самолета, ние може да се направи само на нивото на линията на тази функция, което означава, че линията, на която целевата функция придобива определена постоянна стойност. Мястото на точки (х1. X2), в която целевата функция приема стойността определя от уравнението L.

който е права линия, перпендикулярна на вектор C = (С1. с2). което показва посоката на увеличаване на целевата функция. Поставяне на параметъра L възможни стойности, които получаваме семейството на паралелни прави линии, изпълва целия самолет. Преминаването от една линия на другата семейството в посоката, определена от вектора, води до увеличаване на обективната функция. Движение в обратна посока води до намаляване на стойността си. Заедно с права обективна функция е константа.

Третият етап на графичен метод е паралелно прехвърляне на кривите на ниво на обективната функция.

Крос полигон допустимите преки решения и ще се движат паралелно, за да се по посока на увеличаване на L (ако проблемът е решен до максимума на целевата функция), или в посока на намаляване на L (ако искате да се изчисли минимум от целевата функция). Преместване права проведе до такова ограничение позиция, когато условията на многоъгълника е все още по-ниски (в решаване на проблема на максимума), или в горната част (в решаване на проблеми в малко) половин равнина, генерирани от съответната граница линия. В този случай, най-малкото поне една точка на условията на полигон трябва да принадлежат на този ограничаване линия. Тази точка определя решаването на проблема. В решаването на задачи на линейното програмиране с графични методи три възможности:

• паралелно изместване ще доведе до по права линия в позиция, в която тя ще има една обща точка с възможно региона. В този случай, проблемът е с уникално решение;
• линия е успоредна на една страна на площта на възможни решения. В този случай, минимум се постига при всички точки на съответния страничен участък на възможни решения;
• в посока на увеличаване или намаляване на обективната функция възможно област е неограничена. В този случай, проблемът няма решение.

Оптималната план се постига в краищата на областта на определение на обективната функция - по върховете на многостен на възможни решения.

Ние илюстрира метода на графични решения за проблема с банката.

Изобразяват равнина възможно набор от решения на проблема, съответстваща на пресечната точка на половин равнините, определени от неравенства.

В графиката числото 1 кодира права линия, съответстваща на броя задача първото ограничение 2 кодира права линия, съответстваща на броя задача втората ограничение 3 кодира права линия, съответстваща на трета проблема ограничение. Стрелките показват съответната половина равнина отговаря на ограниченията на проблема. Пресечната точка на тези половинчати самолети е триъгълник ABC, който е набор от изпълними решения на нашия проблем. Ние изграждане на равнината на обективната функция на нивото на линията L = 0, което ще има формата

Ако се премества успоредно на себе си това ниво линия цел функция преминава през множество валидни решения в посока на вектор C = (0,15; 0,1) функции за увеличаване до тази линия ще има най-малко една обща точка с допустимото набор , определен ред в крайно положение преминава през точката на множеството от възможни решения, в които обективната функция достигне максималната си стойност. намерено максимална точка се намира в пресечната точка на линии 1 и 3. Неговите координати се получават чрез решаване на следната система от линейни уравнения:

Решението на тази система са числа Х1 = Х2 = 70 и 30, които определят оптималната портфейл от активи, където максимален размер печалба Fmax = 0,15 · 70 + 0,1 х 30 = 13.5. Полученият разтвор е, че трябва да се поставят в надписите, и $ 30 млн. За инвестиране в ценни книжа при този сценарий, банката ще направи печалба в размер на $ 13.5 милиона за $ 70 млн ..

Задача. Малкият Фирмата произвежда два вида продукти: маси и столове. За производството на един стол изисква 3фут дървен материал, както и за производството на един раздел - 7 фута. При производството на стола оставя 2 часа на работното време, както и за производство на раздела - 8 часа. Всеки стол носи печалба от $ 1, и всяка маса. - $ 3 Колко столове и маси трябва да правят тази фирма, ако тя разполага с 420 фута от дърво и 400 часа в режим на работното време и иска да получи максимална печалба.?