UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваМетод штучного базису (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2542
Скачало450
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

на тему:

 

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

 

Останні труднощі, що залишилося перебороти ? це визначення вихідного

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

ітерації.

 

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

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

 

,

 

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

 

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

 

Отже, нехай ми маємо 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+

 

     

 

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

 

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

цьому вектору, і усі введені додаткові перемінні зникають.

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ