Задача математичного програмування Тема 1 Питання термінології, історіографія назв
жүктеу/скачать 3.01 Mb.
|
- Бұл бет үшін навигация:
- Форми запису задач ЛП 1. Загальною
- (мінімального)
| і є її градієнтом: grad z = c.
Вектор градієнту, який вказує напрямок якнайшвидшого зростання функції в просторі векторів xэRn, ортогональний лініям (фіксованого) рівня самої функції - див рис вище Форми запису задач ЛП 1. Загальною задачою лінійного програмування називається задача, яка полягає у визначенні максимального (мінімального) значення функціоналу (*) при умовах (**) тобто в загальній формі записи ЗЛП можуть брати участь всі варіанти знаків співвідношень. Функція (*) називається цільовою функцією завдання а умови (**) - обмеженнями даного завдання. 2.Стандартною (або симетричною) ЗЛП є завдання, яке знаходить максимальне (для знаків обмежень «≤») або мінімальне (для знаків обмежень «≥») значення цільової функції (*) при виконанні умов (**) у вигляді Тобто в стандартній ЗЛП обмеження на знак хj застосовуються тільки виду «≥» а для інших обмежень або «≤» або «≥» в залежності від того вирішуємо ми ЛП завдання на максимум або на мінімум відповідно 3.Канонічною (або основною) задачею лінійного програмування називається задача, яка полягає у визначенні максимального (мінімального) значення функції (*) при виконанні умов (**), Тобто в канонічній формі на відміну від стандартної в основних обмеженнях беруть участь тільки обмеження типу рівностей "=" Зазначені вище три форми задачі лінійного програмування еквівалентні в тому сенсі, що кожна з них може бути перетворена до форми іншої. Так 1. Якщо з фізичного змісту задачі деякі змінні можуть приймати негативні значення то система приводиться до стандартного вигляду заміною відповідних змінних на нові змінні , , де вже , . 2. Якщо в системі ЗЛП є обмеження з знаком " " можемо помножити нерівності з обох сторін на (-1) і тоді змінимо знак нерівності на " " 3.Ну а рівність "=" можна формально представити як 2 нерівності " " і " " і далі див п.2 4. Обмеження у формі нерівностей наводяться до обмежень у формі рівностей за допомогою додаткових змінних наприклад , де та У стандартних программах для вирішення ЗЛП ми, як правило, окремо задаємо матрицю і вектор для обмежень типу " "чи " ", матрицю і вектор для обмежень типу "=" і вектор параметрів для цільової функції. Щоб далі не було занадто нудно - навіщо ми наводими ті чи інші відомості розглянемо, далі в спрощеному вигляді основну ідею механізму симплекс методу. жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|