Метод штучного базису (реферат)

Реферат з математики на тему:

Метод штучного базису Останні труднощі, що залишилося перебороти е визначення вихідного опорного плану і вихідної симплекса-таблиці, з яким починаються всі ітерації.

За рахунок чого ми так легко склали вихідну симплекс-таблицю в попередньому прикладі? Легко бачити, що це відбулося тому, що серед.

.

тому що шукати координати в цьому базисі дуже просто.

На штучному введенні цих векторів і заснований метод штучного базису.

Отже, нехай ми маємо задачу линейного программирования у канонической форме.

.

Візьмемо ну дуже велике число M і будемо вирішувати наступну допоміжну задачу:

У цій задачі відразу ясний вихідний базис якості його треба взяти.

У якості вихідного опорного плану треба взяти план.

Коефіцієнти розкладання векторів. Вихідна симплекс-таблиця здобуває тоді вид:

Треба лише порахувати додатковий рядок, де коштують числа і :

Помітимо, що в матричних позначеннях вихідна симплекс-таблиця виглядає так:

.

А тепер почнемо перетворення симплекса-таблиці, намагаючись виводити з базису вектори, що відповідають уведеним додатковим перемінної. Тому що M дуже велике, то серед разностей буде багато позитивних і буде багато претендентів на введення в базис з.

Помітимо, що якщо якийсь вектор, що відповідає якийсь додаткової перемінний виведений з базису, те відповідний стовпець симплекса-таблиці можна просто викреслити і більше до нього не повертатися.

Зрештою можливі два варіанти.

Варіант 1.

Усі вектори, що відповідають уведеним додатковим перемінної, будуть виведені з базису. У цьому випадку ми просто повернемося до вихідної задачі, потрапивши в якусь вершину припустимої області. Усі стовпці симплекса-таблиці, що відповідають додатковим перемінної, тоді зникнуть і далі буде зважуватися вихідна задача.

Варіант 2.

Незважаючи на те, що M дуже велико, що виходить оптимальний план буде все-таки містити якусь з додаткових перем енних. Це означає, що припустима область вихідної задачі порожня, тобто обмеження вихідної задачі суперечлива і тому вихідна задача взагалі не має рішень.

Помітимо на закінчення, що величина M узагалі не конкретизується і так і залишається у виді букви M. При рішенні навчальних задач у додатковий рядок пишуть алгебраїчні вираження, що містять M, а при рахунку на ЕОМ уводиться ще один додатковий рядок, куди пишуться коефіцієнти при M.

Проілюструємо це прикладом.

Приклад Вирішити задачу лінійного програмування.

Помітимо, що в нас уже є один придатний вектор е вектор при перемінній. Тому вводимо лише дві додаткові перемінні, заміняючи вихідну задачу наступної:

Вихідна симплекс-таблиця прийме тоді вид:

Подальші ітерації приводяться без особливих пояснень.

Перша ітерація.

Тому що з базису виводиться вектор, то в симплексі-таблиці, що виходить, відповідний стовпець відразу віддаляється.

Друга ітерація.

На цій ітерації з базису виводиться вектор. Відповідно із симплекса-таблиці віддаляється стовпець, що відповідає цьому вектору, і усі введені додаткові перемінні зникають.

Третя ітерація Ми повернулися до вихідної задачі і продовжуємо вирішувати її за стандартною схемою.

Таким чином, задача зважилася й оптимальний план має вид:

.

Мінімальне значення цільової функції дорівнює .

Відзначимо на закінчення, що якщо первісна задача лінійного програмування мала обмеження виду й усі компоненти вектора ненегативні, то, приводячи її до канонічної форми, ми відразу будемо мати одиничну матрицю порядку m яку і можна брати як вихідний базис.