Реферат з математики

на тему:

Метод штучного базису

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

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

,

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

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

Отже, нехай ми маємо 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 яку і можна брати як вихідний базис.

Похожие записи