Методи за решаване на системи от линейни неравенства

Резюме - Математика и статистика

Други резюмета по математика и статистика

ФИНАНСОВА АКАДЕМИЯ ПО ПРАВИТЕЛСТВОТО НА РФ

Катедра по математика и финансови приложения

Изпълнено от студент от група IEC 1-2

Чанкин Петър Алексеевич

Професор Александър Самуилович Солодовников

Метод с изкуствена основа8

Списък на използваната литература12

Определени свойства на системи с линейни неравенства бяха разгледани през първата половина на 19 век във връзка с някои проблеми на аналитичната механика. Систематичното изследване на системите на линейни неравенства започва в самия край на 19 век, но става възможно да се говори за теорията на линейните неравенства едва в края на двадесетте години на 20 век, когато е налице достатъчен брой свързани резултати вече се бяха натрупали.

Сега теорията на крайните системи на линейни неравенства може да се разглежда като клон на линейна алгебра, който е израснал от нея с допълнителното изискване за подреждане на полето на коефициентите.

Линейните неравенства са особено важни за икономистите, тъй като именно с помощта на линейни неравенства човек може да моделира производствените процеси и да намери най-изгодните планове за производство, транспорт, разпределение на ресурси и т.н.

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

Графичният метод се състои в конструиране на набор от възможни решения на LPP и намиране в този набор на точка, съответстваща на max/min на целевата функция.

Поради ограничените възможности за визуално графично представяне, този метод се използва само за системи с линейни неравенства с две неизвестни и системи, които могат да бъдат сведени до тази форма.

За да демонстрираме визуално графичния метод, ще решим следния проблем:

На първия етап е необходимо да се изгради област от възможни решения. За този пример е най-удобно да изберете X2 като абсциса и X1 като ордината и да запишете неравенствата, както следва:

Тъй като както графиките, така и площта на допустимите решения са през първото тримесечие.

За да намерим граничните точки, решаваме уравненията (1) = (2), (1) = (3) и (2) = (3).

Както се вижда от илюстрацията, многогранникът ABCDE образува областта на възможните решения.

Ако областта на възможните решения не е затворена, тогава или max (f) = + ∞, или min (f) = -∞.

Сега можем директно да намерим максимума на функцията f.

Като заместваме координатите на върховете на многогранника във функцията f и сравняваме стойностите, откриваме, че

f (C) = f (4; 1) = 19 максимална функция.

Този подход е доста полезен за малък брой върхове. Но тази процедура може да се забави, ако има много пикове.

В този случай е по-удобно да се разгледа линия на нивото на формата f = a. С монотонно увеличение на числото a от -∞ до + ∞, правите линии f = изместване по нормалния вектор. Ако при такова преместване на линията на нивото има някаква точка X, първата обща точка от областта на възможните решения (полиедър ABCDE) и линията на нивото, тогава f (X) е минимумът на f на множеството ABCDE . Ако X е последната точка на пресичане на линията на нивото и множеството ABCDE, тогава f (X) е максимумът от множеството възможни решения. Ако при a → -∞ линията f = a пресича множеството възможни решения, тогава min (f) = -∞. Ако това се случи като → + ∞, тогава

В нашия пример линията f = a пресича площта ABCDE в точката C (4; 1). Тъй като това е последната точка на пресичане, max (f) = f (C) = f (4; 1) = 19.

За да започнете да решавате LPP по симплекс метода, е необходимо да доведете LPP до специален формуляр и да попълните симплекс таблицата.

Системата (4) също не се побира в таблицата. Уравнения (1), (2), (3) образуват областта на възможните решения. Израз (5) целева функция. Свободните условия в системата от ограничения и областта на допустимите решения трябва да бъдат неотрицателни.

В този пример X3, X4, X5 са основни неизвестни. Те трябва да бъдат изразени чрез безплатни неизвестни и заменени в целевата функция.

Сега можете да започнете да попълвате симплекс таблицата:

В първата колона на тази таблица са посочени основните неизвестни, в последната стойностите на свободните неизвестни, в останалата част - коефициентите за неизвестни.