WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Метод штучного базису - Реферат

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


Реферат з математики
на тему:
Метод штучного базису
Останні труднощі, що залишилося перебороти це визначення вихідного опорного плану і вихідної симплекса-таблиці, з яким починаються всі ітерації.
За рахунок чого ми так легко склали вихідну симплекс-таблицю в попередньому прикладі? Легко бачити, що це відбулося тому, що серед
векторів
були вектори виду
,
тому що шукати координати в цьому базисі дуже просто.
На штучному введенні цих векторів і заснований метод штучного базису.
Отже, нехай ми маємо задачу линейного программирования у канонической форме
.
Можна вважати, що всі , тому що множенням відповідного
обмеження на -1 у
завжди можна перемінити знак.
Візьмемо ну дуже велике число M і будемо вирішувати наступну допоміжну задачу:
У цій задачі відразу ясний вихідний базис у якості його треба взяти
вектори, що коштують при ,
адже вони мають вид
У якості вихідного опорного плану треба взяти план
Коефіцієнти розкладання векторів . Вихідна симплекс-таблиця здобуває тоді вид:
Треба лише порахувати додатковий рядок, де коштують числа і :
Помітимо, що в матричних позначеннях вихідна симплекс-таблиця виглядає так:
,
де одинична матриця розмірності
, а .
А тепер почнемо перетворення симплекса-таблиці, намагаючись виводити з базису вектори, що відповідають уведеним додатковим перемінної. Тому що M дуже велике, то серед разностей буде багато позитивних і буде багато претендентів на введення в базис з
векторів .
Помітимо, що якщо якийсь вектор, що відповідає якийсь додаткової перемінний виведений з базису, те відповідний стовпець симплекса-таблиці можна просто викреслити і більше до нього не повертатися.
Зрештою можливі два варіанти.
Варіант 1
Усі вектори, що відповідають уведеним додатковим перемінної, будуть виведені з базису. У цьому випадку ми просто повернемося до вихідної задачі, потрапивши в якусь вершину припустимої області. Усі стовпці симплекса-таблиці, що відповідають додатковим перемінної, тоді зникнуть і далі буде зважуватися вихідна задача.
Варіант 2
Незважаючи на те, що M дуже велико, що виходить оптимальний план буде все-таки містити якусь з додаткових перем енних. Це означає, що припустима область вихідної задачі порожня, тобто обмеження вихідноїзадачі суперечлива і тому вихідна задача взагалі не має рішень.
Помітимо на закінчення, що величина M узагалі не конкретизується і так і залишається у виді букви M. При рішенні навчальних задач у додатковий рядок пишуть алгебраїчні вираження, що містять M, а при рахунку на ЕОМ уводиться ще один додатковий рядок, куди пишуться коефіцієнти при M.
Проілюструємо це прикладом.
Приклад
Вирішити задачу лінійного програмування
Помітимо, що в нас уже є один придатний вектор це вектор при перемінній . Тому вводимо лише дві додаткові перемінні , заміняючи вихідну задачу наступної:
Вихідна симплекс-таблиця прийме тоді вид:
Ба- с План -1 -2 -3 1 М М
зис
M 15 1 2 3 0 1 0
M 20 2 1 5 0 0 1
1 10 1 2 1 1 0 0
10+
35M 2+
3M 4+
3M 4+
8M 0 0 0
Подальші ітерації приводяться без особливих пояснень.
Перша ітерація
Тому що з базису виводиться вектор , то в симплексі-таблиці, що виходить, відповідний стовпець відразу віддаляється.
Ба- с План -1 -2 -3 1 М
зис
M 3
0 0 1
-3 4
1 0 0
1 6
0 1 0
-6+
3M 2/5-
-1/5M 16/5+
+1/5M 0 0 0
Друга ітерація
На цій ітерації з базису виводиться вектор . Відповідно із симплекса-таблиці віддаляється стовпець, що відповідає цьому вектору, і усі введені додаткові перемінні зникають.
Ба- с План -1 -2 -3 1
зис
-2
1 0 0
-3
0 1 0
1
0 0 1
0 0 0
Третя ітерація
Ми повернулися до вихідної задачі і продовжуємо вирішувати її за стандартною схемою.
Ба- с План -1 -2 -3 1
зис
-2
0 1 0
-3
0 0 1
-1
0 1 0
-15 0 0 0 -1
Таким чином, задача зважилася й оптимальний план має вид:
.
Мінімальне значення цільової функції дорівнює 15.
Відзначимо на закінчення, що якщо первісна задача лінійного програмування мала обмеження виду й усі компоненти вектора ненегативні, то, приводячи її до канонічної форми, ми відразу будемо мати одиничну матрицю порядку m яку і можна брати як вихідний базис.
Loading...

 
 

Цікаве