Реферат з математики
на тему:
Метод штучного базису
Останні труднощі, що залишилося перебороти ? це визначення вихідного
опорного плану і вихідної симплекса-таблиці, з яким починаються всі
ітерації.
За рахунок чого ми так легко склали вихідну симплекс-таблицю в
попередньому прикладі? Легко бачити, що це відбулося тому, що серед
,
тому що шукати координати в цьому базисі дуже просто.
На штучному введенні цих векторів і заснований метод штучного базису.
Отже, нехай ми маємо HYPERLINK “http://srg.pp.ru/isled-e/Op1.htm” \l
“37” \o “” задачу линейного программирования у HYPERLINK
“http://srg.pp.ru/isled-e/Op2t.htm” \l “27” \o ” каноническая форма –
форма задачи линейного программирования, в которой
целевая функция требует нахождения минимума, переменные
неотрицательны,
а компоненты произведения матрицы ог канонической форме
.
, тому що множенням відповідного
завжди можна перемінити знак.
Візьмемо ну дуже велике число M і будемо вирішувати наступну допоміжну
задачу:
У цій задачі відразу ясний вихідний базис ? у якості його треба взяти
У якості вихідного опорного плану треба взяти план
. Вихідна симплекс-таблиця здобуває тоді вид:
:
Помітимо, що в матричних позначеннях вихідна симплекс-таблиця виглядає
так:
,
буде багато позитивних і буде багато претендентів на введення в базис з
виведений з базису, те відповідний стовпець симплекса-таблиці можна
просто викреслити і більше до нього не повертатися.
Зрештою можливі два варіанти.
Варіант 1
Усі вектори, що відповідають уведеним додатковим перемінної, будуть
виведені з базису. У цьому випадку ми просто повернемося до вихідної
задачі, потрапивши в якусь вершину припустимої області. Усі стовпці
симплекса-таблиці, що відповідають додатковим перемінної, тоді зникнуть
і далі буде зважуватися вихідна задача.
Варіант 2
Незважаючи на те, що M дуже велико, що виходить оптимальний план буде
все-таки містити якусь з додаткових перем енних. Це означає, що
припустима область вихідної задачі порожня, тобто обмеження вихідної
задачі суперечлива і тому вихідна задача взагалі не має рішень.
Помітимо на закінчення, що величина M узагалі не конкретизується і так і
залишається у виді букви M. При рішенні навчальних задач у додатковий
рядок пишуть алгебраїчні вираження, що містять M, а при рахунку на ЕОМ
уводиться ще один додатковий рядок, куди пишуться коефіцієнти при M.
Проілюструємо це прикладом.
Приклад
Вирішити задачу лінійного програмування
, заміняючи вихідну задачу наступної:
Вихідна симплекс-таблиця прийме тоді вид:
1 10 1 2 1 1 0 0
10+
35M 2+
3M 4+
3M 4+
Подальші ітерації приводяться без особливих пояснень.
Перша ітерація
, то в симплексі-таблиці, що виходить, відповідний стовпець відразу
віддаляється.
0 1 0
-6+
3M 2/5-
-1/5M 16/5+
Друга ітерація
. Відповідно із симплекса-таблиці віддаляється стовпець, що відповідає
цьому вектору, і усі введені додаткові перемінні зникають.
Третя ітерація
Ми повернулися до вихідної задачі і продовжуємо вирішувати її за
стандартною схемою.
-15 0 0 0 -1
Таким чином, задача зважилася й оптимальний план має вид:
.
Мінімальне значення цільової функції дорівнює ? 15.
ненегативні, то, приводячи її до канонічної форми, ми відразу будемо
мати одиничну матрицю порядку m яку і можна брати як вихідний базис.
Нашли опечатку? Выделите и нажмите CTRL+Enter
