Безліч рішень системи лінійних нерівностей
Зв'яжемо з кожною точкою (x1,x2,…xn) n-мірного простору R n n-мірний векторx =(x1,x2,…xn) з початком на початку координат і кінцем у точці (x1, x2, ... xn). Множина векторівх =(х1,х2. хn) R n , компоненти яких задовольняють m лінійним нерівностям:
a11х1+a12х2+. +a1nxn ≤ b1
називається безліччю рішень системи лінійних нерівностей.
У визначенні всі нерівності записані зі знаком ≤. Помножуючи на
(-1) будь-яка з нерівностей, можна змінити його знак на протилежний. Безліч рішень визначено для систем лінійних нерівностей як зі знаком так і ≤.
Предмет теорії моделювання
Моделювання - це заміщення одного об'єкта (оригіналу) іншим (моделлю) та фіксація та вивчення властивостей моделі. Заміщення проводиться з метою спрощення, здешевлення, прискорення вивчення властивостей оригіналу.
У випадку об'єктом-оригіналом може бути природна чи штучна, реальна чи уявна система. Вона має безліч параметрів та характеризується певними властивостями. Кількісним мірою властивостей системи служить безліч характеристик, система виявляє свої властивості під впливом зовнішніх впливів.
Моделювання доцільно, коли у моделі відсутні ознаки оригіналу, які перешкоджають його дослідженню.
Теорія моделювання - взаємопов'язана сукупність положень, визначень, методів та засобів створення моделей. Самі моделі предмет теорії моделювання.
Теорія моделювання є основною складовою загальної теорії систем - системології, де як головний принцип постулюються здійсненні моделі: система представима кінцевим безліччю моделей, кожна з яких відображаєпевну межу її сутності.
Роль та місце моделювання у дослідженні систем.
Пізнання будь-якої системи ( ) зводиться сутнісно до створення її моделі. Перед виготовленням кожного пристрою чи споруди розробляється його модель-проект. Будь-який витвір мистецтва є моделлю, що фіксує дійсність.
Досягнення математики призвели до поширення математичних моделей різних об'єктів та процесів. Позначено, що динаміка функціонування різних за фізичною природою систем однотипними залежностями, що дозволяє їх моделювати на ПК.
Класифікація моделей
Фізичні моделі. В основу класифікації покладено ступінь абстрагування моделі від оригіналу. Попередньо всі моделі можна поділити на 2 групи - фізичні та абстрактні (математичні).
Ф.М. зазвичай називають систему, еквівалентну або подібну до оригіналу, але можливо має іншу фізичну природу. Види Ф.М.:
Натуральні моделі - це реальні досліджувані системи (макети, дослідні зразки). Мають повну адекватність (відповідності) із системою оригіналу, але дороги.
Квазінатуральні моделі - сукупність натуральних та математичних моделей. Цей вид використовується тоді, коли модель частини системи не може бути математичною через складність її опису (модель людини оператора) або коли частина системи повинна бути досліджена у взаємодії з іншими частинами, але їх ще не існує або їх включення дуже дорого (обчислювальні полігони , АСУ).
Масштабна модель - це система тієї ж фізичної природи, як і оригінал, але відрізняється від нього масштабами. Методологічною основою масштабного моделювання є теорія подібності. При проектуванні ЗС масштабні моделі можутьвикористовуватись для аналізу варіантів компонувальних рішень.
Аналоговими моделями називаються системи, що мають фізичну природу, що відрізняється від оригіналу, але подібні до оригіналу процеси функціонування. Для створення аналогової моделі потрібна наявність математичного опису системи, що вивчається. В якості аналогових моделей використовуються механічні, гідравлічні, пневматичні та електричні системи. Аналогове моделювання використовують при дослідженні засобу ВТ на рівні логічних елементів та електричних ланцюгів, а також на системному рівні, коли функціонування системи описується, наприклад, диференціальними або рівняннями алгебри.
Математичні моделі. Математичні моделі є формалізоване уявлення системи за допомогою абстрактної мови, за допомогою математичних співвідношень, що відображають процес функціонування системи. Для складання математичної моделі можна використовувати будь-які математичні засоби – алгебраїчне, диференціальне, інтегральне обчислення, теорію множин, теорію алгоритмів тощо. По суті, вся математика створена для складання та дослідження моделей об'єктів та процесів.
До засобів абстрактного опису систем належать також мови хімічних формул, схем, креслень, карт, діаграм тощо. Вибір виду моделі визначається особливостями системи, що вивчається, і цілями моделювання, т.к. Вивчення моделі дозволяє отримати відповіді на певну групу питань. Для отримання іншої інформації іншої інформації може знадобитися модель іншого виду. Математичні моделі можна класифікувати на детерміновані та імовірнісні, аналітичні, чисельні та імітаційні.
Аналітичною моделлю називається такий формалізований опис системи,яке дозволяє вирішити рівняння у явному вигляді, використовуючи відомий математичний апарат.
Кількісна модель характеризується залежністю такого виду, який допускає лише приватні рішення для конкретних початкових умов та кількісних параметрів моделей.
Імітаційна модель - це сукупність опису системи та зовнішніх впливів, алгоритмів функціонування системи або правил зміни стану системи під впливом зовнішніх та внутрішніх збурень. Ці алгоритми та правила не дають можливості використання наявних математичних методів аналітичного та чисельного рішення, але дозволяють імітувати процес функціонування системи та проводити обчислення цікавих характеристик. Імітаційні моделі можуть бути створені для значно ширшого класу об'єктів та процесів, ніж аналітичні та чисельні. Оскільки для реалізації імітаційних моделей служать ЗС, засобами формалізованого опису їм служать універсальні та спеціальні алгоритмічні мови. Їм найбільше підходять для дослідження ВС на системному рівні.
Розглянемо ряд завдань, у яких необхідно знайти область розв'язання системи лінійних нерівностей.
Приклад 1 : Зобразити безліч рішень наступної системи лінійних нерівностей R².
x1 + 3х2 ≤ 6
Багато рішень, що шукають, відповідає заштрихованій області. Вершинами безлічі рішень є три точки (0,2), (0,-2) і (3,1). Вони є точками перетину прямих, що обмежують безліч рішень.
У цьому прикладі безліч рішень - багатогранна опукла множина.
Приклад 2: Зобразити безліч рішень наступної системи лінійних нерівностей R².
-x1 + 2х2 ≤ 4
Вершинами шуканої множини є дві точкиз координатами: (0,2) та (1/2, 9/4). Точка з координатою (0,3) вершиною не є, тому що не задовольняє першу нерівність. Це безліч рішень – необмежено.
РішенняПриклад 3: Зобразити безліч рішень наступної системи лінійних нерівностей у R².
х1 - х2 ³ 1
Рішенням першої та другої нерівностей є точки заштрихо-ванного нижнього сектора. Рішенням третьої нерівності є точки заштрихованої верхньої напівплощини. Оскільки загальних точок цих двох областей немає, немає рішення і в усій системи нерівностей, тобто рішенням є Æ.
Основне завдання лінійного програмування.
Загалом завдання лінійного програмування (ЗЛП) ставиться так.
Знайти векторх =(х1,х2, .xn) R n , який максимізує (або мінімізує) цільову функцію
і задовольняє m+n лінійним нерівностям:
a11х1+a12x2+. +a1nxn ≤ b1
У термінології програмування лінійна функція F(х) називається цільовою функцією завдання. Багато рішень системи лінійних нерівностей (4) називають безліччю допустимих рішень, а будь-який векторх з цієї множини називається допустимим рішенням. Оптимальним рішенням називається векторх *, при якому цільова функція набуває свого максимального (або мінімального) значення на допустимій множині рішень.
Графічний метод розв'язання задач лінійного програмування. Покажемо, як вирішується зазначена задача графічним (геометричним) методом. Для цього обмежимося розглядом системи лінійних нерівностей із двома невідомими.
Нехай задана цільова функція F=с1х1+с2х2+с0. Знайдемо серед безлічі точок (х1, х2) з області допустимих рішень спільної системи нерівностей (4) (що містить тількизмінні x1 та x2) такі, які надають лінійній функції F найменше (найбільше) значення. Для кожної i-ої точки площини функція F набуває фіксованого значення F=Fi. Безліч всіх таких точок на яких функція F приймає одне й те саме значення Fi є пряма с1х1+c2х2+c0=Fi = const, перпендикулярна до деякого вектора, який називається градієнтом F (grad F). Цей вектор виходить із початку координат і має координати grad F = (с1, с2). За властивістю вектора grad F якщо зазначену пряму пересувати паралельно самій собі в позитивному напрямку вектора grad F, значення цільової функції F=с1х1+с2х2+с0 на цій прямій буде зростати, а в протилежному напрямку - убувати.
Нехай під час руху прямий F=const у позитивному напрямку вектора grad F ця пряма вперше зустрінеться з багатокутником допустимих рішень на його вершині. Тоді в цьому положенні F1 пряма F=const називається опорною, і на цій прямій функція F набуває найменшого значення. При подальшому русі в тому ж напрямку (позитивному) пряма F=const пройде через іншу вершину багатокутника допустимих рішень і, виходячи з області рішень, також стане опорною прямою F2. На ній функція F набуває найбільшого значення серед усіх значень, що приймаються на багатокутнику допустимих рішень. Таким чином, мінімізація та максимізація цільової функції F=с1х1+с2х2+с0 на багатокутнику допустимих рішень досягається у точках перетину цього багатокутника з опорними прямими F=с1х1+с2х2+с0 = const, нормальними до вектора grad F=(с1, с2). Це перетин опорної прямої з безліччю допустимих рішень може бути або в одній точці (вершині багатокутника), або в нескінченній множині точок (якщо це безліч сторона багатокутника).
Завдання з першого, другого, третього завданнявибирається на прізвище імені по батькові студента, а за четвертим завданням вибирається на прізвище та по батькові.