их задачі;
2) складання системи обмежень;
3) вибір цільової функції.
Перемінними завдання називаються величини x1, x2, ..., хп , Які повністю характеризують економічний процес. Їх зазвичай записують у вигляді вектора Х = (х1, х2, ..., хп).
Система обмежень включає в себе систему рівнянь і нерівностей, яким задовольняють змінні завдання і які випливають з обмеженості ресурсів або інших економічних чи фізичних умов, наприклад позитивності змінних і т.п.
Цільовою функцією називають функцію змінних задачі, яка характеризує якість виконання завдання і екстремум якої потрібно знайти.
Якщо цільова функція і система обмежень лінійні, то завдання математичного програмування називається задачею лінійного програмування.
Припустимим рішенням (планом) задачі лінійного програмування (ЗЛП) називається будь n-мірний вектор Х = (х1, х2, ..., хn), задовольняє системі обмежень і умов невід'ємності.
Безліч допустимих рішень (планів) завдання утворює область допустимих рішень (ОДР).
Оптимальним рішенням (планом) ЗЛП називається таке допустиме рішення (план) завдання, при якому цільова функція досягає екстремуму.
Загальний вигляд задачі лінійного програмування:
В В В В
,
Обмеження:
1. Праві частини всіх обмежень повинні бути невід'ємними. Якщо небудь з коефіцієнтів <0, то необхідно коефіцієнти обмеження ліворуч і праворуч домножити на "-1" І змінити знак даного обмеження на протилежний;
2. Всі обмеження мають бути представлені у вигляді рівностей, тому при переході від нерівності до рівності використовують апарат додаткових змінних.
Якщо вихідні обмеження визначають витрата деякого ресурсу (знак ""), то змінні
В
слід інтерпретувати як залишок, або невикористану частину ресурсу. У цьому випадку - залишкова змінна і вводиться в рівняння з знаком "+". Якщо вихідні обмеження визначають надлишок деякого ресурсу (знак ""), то вводиться надлишкова мінлива
В
знаком "-".
Змінні:
Всі змінні повинні бути невід'ємними, тобто
.
Якщо змінна не має обмеження в знаку, то її потрібно представити як різниця двох невід'ємних змінних:
,
де. Таку підстановку варто використовувати у всіх обмеженнях, що містять цю змінну, а також у вираженні для цільової функції.
Якщо така мінлива потрапляє в оптимальне рішення, то.
Цільова функція:
Цільова функція задачі лінійного програмування є рівняння площини (або гіперплощини для числа змінних більше трьох). Максимальний або мінімальне значення цільова функція задачі лінійного програмування досягає або в вершині опуклого багатогранника, або на одній з його граней. Таким чином, рішення (рішення) задачі лінійного програмування лежить в вершинах опуклого багатогранника і для його знаходження треба обчислити значення цільової функції в вершинах опуклого...