Задача математичного програмування Тема 1 Питання термінології, історіографія назв
Алгоритм табличного симплекс-методу
жүктеу/скачать 3.01 Mb.
|
- Бұл бет үшін навигация:
- Нехай ми вирішуємо завдання на мінімум Крок 1
- Перевірка на оптимальність
| Алгоритм табличного симплекс-методу.
Підготовчий етап Крок 0. Складаємо симплексну таблицю, відповідну початковій задачі на мінімум
чи якщо на макс
Нехай ми вирішуємо завдання на мінімум Крок 1. Перевірка на допустимість. Перевіряємо на позитивність елементи стовпця b (вільні члени), якщо серед них немає негативних то знайдено допустиме рішення (рішення відповідне однією з вершин багатогранника умов) і ми переходимо до кроку 2. Якщо в стовпці вільних членів є негативні елементи то вибираємо серед них максимальний за модулем bk - він задає провідний рядок k - тобто ми знайшли, яку змінну будемо виводити з базису. Далі, в 0-му рядку знаходимо максимальний по модулю негативний елемент a0,i - він задає ведучий стовпець – i, і таким чином визначається провідний елемент ak,i. Змінна, відповідна провідною рядку виключається з базису, змінна відповідна ведучому стовпцю включається в базис. Перераховуємо симплекс-таблицю згідно з правилами. До речі, якщо не знайдеться негативних елементів в рядку F, це є ознака оптимального рішення на мінімум (немає змінних, за рахунок яких можна зменшити функціонал на мінімум), в нашому ж випадку (коли ми ще не перебуваємо в допустимої вершині) це означає, що система несумісна і рішення немає. Якщо після перерахунку, в стовпці вільних членів залишилися негативні елементи, то переходимо до шагу1, якщо таких немає, то до кроку 2. Крок 2. Перевірка на оптимальність. Нехай на попередньому етапі знайдено допустиме рішення. Перевіримо його на оптимальність. Якщо серед елементів симплекс таблиці, що знаходяться в рядку F (не беручи до уваги елемент b0 - поточне значення цільової функції) немає негативних, то знайдено оптимальне рішення. Якщо в рядку F є негативні елементи то рішення може бути покращено. Правила переходу до покращеної вершини сілплекса Вибираємо серед негативних елементів рядка F максимальний по модулю (виключаючи значення функції b0) a0, р = mini {a0, i} . Знайдений стовпець р - в якому знаходиться елемент a0, р буде ведучим. Для того, що б знайти провідний рядок, знаходимо відношення відповідного вільного члена і елементів з ведучого стовбця, за умови, що вони невід'ємні і знаходимо їх мінімум bk/ak,р =mini {bi/ai,р } при ai,р>0, bi>0 (***) k - Рядок, для якої це відношення мінімально – є провідним. Елемент ak, р – називають провідним (визначальним). Змінна, відповідна провідному рядку (xk) виключається з базису, змінна відповідна провідному стовпцю (xр) включається в базис. Умова (***) гарантує що ми в новій вершині залишимося в допустимої області - тобто в ній ніяка з базісних змінних не прийме від’ємне значення. Перераховуємо симплекс-таблицю за правилами. Якщо в новій таблиці після перерахунку в рядку F залишилися негативні елементи переходимо до кроку 2. Якщо неможливо знайти провідний рядок, так як немає позитивних елементів в провідному стовпці, то функція в області допустимих рішень задачі не обмежена - алгоритм завершує роботу. Якщо в рядку F і в стовпці вільних членів всі елементи позитивні, то знайдено оптимальне рішення (1) Правила перетворень симплексной таблиці. По суті це правила визначення лінійної системи обмежень відносноо нового набору базисних змінних (формули) При складанні нової симплекс-таблиці в ній відбуваються такі зміни: Замість базисної змінної xk записуємо xр; Замість небазисной змінної xр записуємо xk. Провідний елемент ak, р замінюється на зворотний величину ak, р '= 1 / ak, р Всі елементи провідного стовбця (крім ak, р) множаться на -1 / ak, р Всі елементи провідного рядка (крім ak, р) множаться на 1 / ak, р Елементи симплекс-таблиці, що залишилися перетворюються за формулою ai,j'= ai,j- ai,р*ak,j/ ak,р Схему перетворення елементів симплекс-таблиці (крім провідного рядка і провідного стовбця) називають схемою "прямокутника". Перетворений елемент ai, j і відповідні йому три сомножителі якраз і є вершинами "прямокутника". Приклад Необхідно вирішити решить ЛП задачу: Цільова функція: 2x 1+5x2+3x3+8x4 →min Обмежуючі умови: 3x1+6x2-4x3+x4≤12 4x1-13x2+10x3+5x4≥6 3x1+7x2+x3≥1 Приведемо систему обмежень до канонічного виду, для цього необхідно перейти від нерівностей до рівностей, з додаванням додаткових змінних. Так як наша задача - завдання мінімізації, то нам необхідно перетворити її до задачі на пошук максимуму. Для цього змінимо знаки коефіцієнтів цільової функції на протилежні. Елементи першого нерівності записуємо без змін, додавши в нього додаткову змінну x5 і змінивши знак "≤" на "=". Так як друга і третя нерівності мають знаки "≥" необхідно поміняти знаки їх коефіцієнтів на протилежні і внести в них додаткові змінні x6 і x7 відповідно. В результаті отримали еквівалентну задачу: 3x1+6x2-4x3+x4+x5=12 -4x1+13x2-10x3-5x4+x6=-6 -3x1-7x2-x3+x7=-1 Переходимо до формування початкової симплекс таблиці. У рядок F таблиці заносяться коефіцієнти цільової функції з протилежним знаком.
жүктеу/скачать 3.01 Mb. Достарыңызбен бөлісу:
|