Задача математичного програмування Тема 1 Питання термінології, історіографія назв
жүктеу/скачать 3.01 Mb.
|
- Бұл бет үшін навигация:
- Нагадаємо зміст термінів
- Ці ненульові змінні
- А виведена небазисна змінна стане в новій вершині базисною.
| F - b0=a0,1x1+a0,2x2+...a0,nxn → min F - b0=-a0,1x1-a0,2x2-...-a0,nxn → max
a1,1x1+a1,2x2+...a1,nxn+xn+1=b1 a1,1x1+a1,2x2+...a1,nxn+xn+1=b1 (**) a2,1x1+a2,2x2+...a2,nxn+ xn+2=b2 a2,1x1+a2,2x2+...a2,nxn+ xn+2=b2 ....................................... ....................................... am,1x1+am,2x2+...am,nxn+ xn+m =bm am,1x1+am,2x2+...am,nxn+ xn+m =bm Тут x1, x2,.. xn - початкові (називають ще сильні змінні), а xn+1, xn+2,... xn+m - додаткові (чи слабі) змінні. Після переходу в Канонічну Форму - (**), ( тобто, додавання в кількість змінних n - ще m додаткових змінних) природно, маємо кількість рівнянь кількості початкових змінних Нагадаємо зміст термінів: початкові змінні (сильні) - змінні, які фігурують у початковій формі фізичної постановці оптимізаційної задачі (напр 1 * -3 *); додаткові змінні (слабкі) - ми, додаючи їх в систему, перетворюємо нерівності в рівності і отримуємо в результаті канонічну форму базисні змінні - для системи з рівнянь з невідомими ( ) будь-які змінних називаються базисними, якщо визначник складений з коефіцієнтів при цих невідомих відмінний від нуля (інші змінні називаються вільними або небазисними). Саме щодо базисних змінних далі на кожному кроці Симплекс Методу ми будемо визначати (вирішувати) систему рівнянь для знаходження проміжних рішень. Ці рішення будуть утворювати шлях по суміжних вершинах симплекса від початкової вершини до кінцевої оптимальної. Далі - про інтерпретацію механізму перебору вершин симплекса: Зауважимо, що будь-яка вершина симплекса утворюється (рис.2, розглядаємо форму ЗЛП (*)) перетином деяких (n-m) гіперплоскостей, які отримані з відповідних нерівностей задачі (*), коли ми перевели їх в рівності канонічної постановки (**) . Відповідні змінні ЗЛП (**) (числом (n-m) - вільні змінні за версією (*)) в точці перетину задовольняють , рис1 рис 2 Решта m змінних (за версією (*)) візьмуть ненульові значення, так як відповідні гиперплоскости в цій точці (цій вершині) не перетнулися і значить в версії (**) , вони взяли ненульове значення. Ці ненульові змінні і є базисні. Таким чином, що означає перейти з однієї вершини симплекса в іншу, суміжну? Це означає замінити в поточному наборі нульових, вільних змінних одну з них на деяку змінну яка в поточному наборі була базисною. А виведена небазисна змінна стане в новій вершині базисною. Або ще інакше – щоб попасти в нову вершину, по відношенню до поточної, ми змінюємо набір базисних (ненульових) змінних на одну змінну. Вона (ця одна) береться з небазисних в поточному наборі і вводиться в базис (замість деякої базисної в поточному рішенні, що виводиться з базису). жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|