:
а) дозволяє елемент замінюється на зворотну величину;
б) інші елементи роздільної рядка діляться на дозволяючий елемент;
в) інші елементи дозволяє стовпця діляться на дозволяючий елемент і знак змінюється на протилежний;
г) залишилися елементи таблиці розраховуються за правилом прямокутника.
Спочатку обчислюється твір, потім. Потім різниця між цими творами ділиться на дозволяючий елемент:
В
Таким чином, виходить нова симплексна таблиця.
Всі обчислення повторюються до тих пір, поки в рядку оцінок не зникнуть негативні елементи, тобто план не стане оптимальним.
Після того як знайдено оптимальний план, проглядається стовпець значень базисних змінних. Якщо в цьому стовпці немає змінних з дробовим значенням, то знайдений план є оптимальним планом задачі цілочислового програмування. Якщо ж в оптимальному плані задачі хоча б одна змінна приймає дробове значення, то для отримання цілочисельного рішення застосовується метод Гомори. p> Метод Гоморі заснований на застосуванні симплекс-методу і методу відсікань.
Алгоритм методу:
) сформована завдання вирішується симплексним методом без урахування цілочисельності;
) якщо в результаті отримано цілочисельне оптимальне рішення, то мета досягнута. В іншому випадку вибирається змінна з нецілочисельне оптимальним значенням (якщо дробових змінних декілька, то обирається та, у якої дрібна частина більше);
) для вибраної невідомої записується умова відсікання її нецілочисельне значення у вигляді лінійного нерівності. Нове обмеження додається в симплексну таблицю з оптимальним рішенням. Далі здійснюється перехід до кроку 1. p> Ознакою відсутності цілочисельного рішення є відсутність дрібних значень коефіцієнтів у рядку з дробовим значенням базисної змінної.
Приймаються за шукані значення x1, x2 - скільки деталей кожного виду слід виробляти, щоб забезпечити максимальний дохід від продажу за тиждень. Складемо цільову функцію, яка буде мати вигляд:
Q = 1,1 x1 +1,5 x2? max
При наступних обмеженнях:
В· x1 +4 В· x2? 10000 (1)
В· x3 +3 В· x4? 10000 (2)
x1 + x2? 1500 (3)
x1, x2? 0
Крок 1. Позбудемося нерівностей в обмеженнях, ввівши в обмеження 1, 2, 3 невід'ємні балансові змінні s1, s2, s3. br/>В
Крок 2. Шукаємо в системі обмежень базисні змінні. p> З останньої системи обмежень можна виділити базисні змінні s1, s2. Не всі рівняння містять базисні змінні, це означає, що вихідна задача не містить в собі допустимого базисного рішення. Для його знаходження спочатку складемо і вирішимо допоміжну завдання. Таке рішення ще називають рішенням з штучним базисом. p> Введемо в рівняння 3 штучну неотрицательную змінну r1.
Отримаємо таку систему обмежень, з базисними змінними s1, s2, r1.
В
Метою рішення допоміжної задачі є отримання допуст...
