Методи розв’язання систем лінійних нерівностей - Математика
ФІНАНСОВА АКАДЕМІЯ ПРИ УРЯДІ РФ
Кафедра математики та фінансових додатків
«Методи вирішення систем лінійних нерівностей»
Виконав студент групи МЕК 1-2
Чанкін Петро Олексійович
Професор Олександр Самуїлович Солодовников
Графічний метод.
Метод штучного базису.
Принцип подвійності.
Список використаної литературы. 12
Окремі властивості систем лінійних нерівностей розглядалися ще першій половині 19 століття у зв'язку з деякими завданнями аналітичної механіки. Систематичне вивчення систем лінійних нерівностей почалося наприкінці 19 століття, проте про теорію лінійних нерівностей стало можливим говорити лише наприкінці двадцятих років 20 століття, коли вже накопичилася достатня кількість пов'язаних з ними результатів.
Зараз теорія кінцевих систем лінійних нерівностей може розглядатися як гілка лінійної алгебри, що виросла з неї за додаткової вимоги впорядкованості поля коефіцієнтів.
Лінійні нерівності мають особливо важливе значення для економістів, оскільки саме за допомогою лінійних нерівностей можна змоделювати виробничі процеси і знайти найбільш вигідні плани виробництва, транспортування, розміщення ресурсів і т.д.
У цій роботі будуть викладені основні методи вирішення лінійних нерівностей, стосовно конкретних завдань.
Графічний метод полягає в побудові безлічі допустимих рішень ЗЛП і знаходженні в даній множині точки, що відповідає 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 = a зміщуються по вектору нормалі [1]. Якщо за такому переміщенні лінії рівня існує певна точка X – перша загальна точка області допустимих рішень (багатогранник ABCDE) і лінії рівня, то f(X)- мінімум f на безлічі ABCDE. Якщо X- остання точка перетину лінії рівня та множини ABCDE то f(X)- максимум на множині допустимих рішень. Якщо за а→-∞ пряма f=a перетинає безліч допустимих рішень, то min(f)= -∞. Якщо це відбувається при а→+∞, то
У прикладі пряма f=a пересіює область ABCDE у точці З(4;1). Оскільки це остання точка перетину, max(f)=f(C)=f(4;1)=19.
Для того, щоб приступити до рішення ЗЛП симплекс методом, треба привести ЗЛП до спеціального вигляду та заповнити симплекс таблицю.
Система (4) – природні обмеження й у таблицю не вписуються. Рівняння (1), (2), (3) утворюють область допустимих розв'язків. Вираз (5) – цільова функція. Вільні члени в системі обмежень та області допустимих рішень мають бути невід'ємними.
У цьому прикладі X3, X4, X5 – базові невідомі. Їх треба висловити через вільні невідомі та зробити їх заміну у цільовій функції.
Тепер можна приступити до заповнення симплекс-таблиці: