9. Стандартна форма запису задач лп.
Завданнями лінійного програмування називаються оптимізаційні задачі, в яких обмеження, які представлені у вигляді рівності або нерівностей, і цільова функція лінійна. Розробка моделі ЛП включає наступні основні етапи: визначення змінних задачі, подання її обмежень у вигляді лінійних рівнянь або нерівностей, завдання лінійної цільової функції, що підлягає мінімізації або максимізації.
Завдання ЛП у стандартній формі з m обмеженнями і n змінними має наступний вигляд:
максимізувати
або мінімізувати
при обмеженнях:
Завдання ЛП у стандартній формі можна записати в компактних матричних позначеннях наступним чином:
максимізувати
або мінімізувати
при
обмеженнях
де A - матриця розмірності mxn, x - вектор-стовпець розмірності nxl, b - вектор-стовпець розмірності mxl, а c - вектор-рядок розмірності. 1xn.
Зазвичай A призначається матрицею коефіцієнтів, x - вектором змінних, b - вектором ресурсів, c - вектором оцінок завдання ЛП.
При рішенні задачі ЛП симплекс-методом потрібно, щоб завдання була представлена в стандартній формі. Однак не всі практичні завдання її мають, тому для задоволення вимоги алгоритму необхідно наступне.
1. За допомогою введення додаткових залишкових або надлишкових змінних перетворити нерівності в рівності.
2. Для отримання невід'ємних змінних завдання необмежені по знаку змінні замінити різницею двох невід'ємних.
При вирішенні завдань ЛП використовуються наступні основні поняття. Припустимим рішенням є невід'ємні значення змінних, для яких виконуються обмеження, а допустимої областю - сукупність допустимих рішень. Оптимальним рішенням називаються такі допустимі значення змінних, при яких ЦФ екстремально, тобто має оптимальне значення. У ряді випадків, ЦФ має одне оптимальне значення при декількох комбінацій значень змінних, отже, завдання має неєдиний оптимуму. Коли в задачі ЛП немає кінцевого оптимуму, то в цьому випадку існує необмежений оптимум.
10. Канонічна форма запису задачі лп.
Канонічною називається задача ЛП, що перебуває у встановленні екстремального значення функції
L = сjхj (3)
при виконанні умов
аijхij = bi і xj 0. (4)
Будь-яку задачу лінійного програмування можна звести до форми канонічної задачі (КЗЛП).
По-перше, не принципово, що треба шукати для цільової функції – максимум або мінімум. Випадок, коли L треба перетворити в максимум, легко зводиться до знаходження мінімуму, якщо змінити знак L на зворотний (мінімізувати не L, a L'= —L), тому що
min f(x1, x2,…,xn) =max[-f(x1, x2,…,xn)]... (8)
і навпаки.
По-друге, від умов-нерівностей можна перейти до умов-рівностей шляхом введення нових «додаткових» змінних. Причому число додаткових змінних дорівнює числу нерівностей.
Якщо m рівностей є лінійно незалежними, то систему з m лінійно незалежних рівностей з n змінними (m < n) завжди можна розв'язати відносно m змінних, називаних базисними, виразивши їх через інші k=n- m змінних, називаних вільними. Вільним змінним можна надавати будь-які значення, не порушуючи умову (4).
План КЗЛП x=(x1, x2,…, xn) називається базисним планом задачі, якщо його компоненти, що відповідають базисним стовпцям, більше нуля (xj 0), а всі інші компоненти (не базисні) – дорівнюють нулю.
Нагадаємо основні теореми лінійного програмування.
Теорема 1. Якщо цільова функція L приймає максимальне значення в деякій точці ОДР, то вона приймає це значення і в деякій кутовій точці ОДР.
Теорема 2. Кожен припустимий базисний план є кутовою точкою ОДР.
Справедливе й зворотне ствердження: якщо план x=(x1, x2,…, xn) є кутовою точкою ОДР, то він є припустимим базисним планом задачі.