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

Всього в базі: 75838
останнє поновлення: 2016-12-03
за 7 днів додано 10

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

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

 

ПОШУК:   

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

Українські рефератиРусские рефератыКниги
НазваТеорія двоїстості та двоїсті оцінки в аналізі розв’язків лінійних оптимізаційних моделей (реферат)
АвторPetya
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось1724
Скачало258
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Теорія двоїстості та двоїсті оцінки в аналізі розв’язків лінійних

оптимізаційних моделей.

 

План.

 

Двоїстий симплекс-метод.

 

Література

 

Двоїстий симплекс-метод.

 

Двоїстий симплекс-метод, так як і симплекс-метод,

використовується при знаходженні розв’язку задачі лінійного

програмування, записаної у формі основної задачі, для якої серед

векторів Рі, складених з коефіцієнтів при невідомих в системі рівнянь,

маючи m одиничних. Разом з тим двоїстий симплекс-метод можна

застосовувати при розв’язанні задачі лінійного програмування, вільні

члени системи рівнянь котрими можуть бути любі числа (при розв’язку

задачі симплексним методом ці числа припускаються невід’ємними). Таку

задачу і розглянемо тепер, попередньо припустивши, що одиничними

являються вектори P1, P2, ... , Pm. Розглянемо задачу, яка полягає у

визначенні максимального значення функції

 

при умовах

 

і серед чисел bi ( і = 1, m) є від’ємні.

 

В даному випадку Х=(b1; b2; … ;bm; 0; … ;0) є розв’язком

системи лінійних рівнянь (2). Однак цей розв’язок не є планом задачі

(1)-(3), так як серед його компонентів є від‘ємні числа.

 

Оскільки вектори Р1, Р2, … , Рm - одиничні, то кожний з

векторів Рi(j=1,n) можна представити у вигляді лінійної комбінації

даних векторів, при чому коефіцієнти розкладу векторів Рj по векторах

Р1, Р2, ... , Рm служать числа хij =аij (і=1,m; j=1,n). Таким чином

можна знайти

 

 

для будь-якого j (j=1,n).

 

(j=1,n), то задача (1)-(3) зовсім не має планів.

 

такі, що для будь-яких із них існують числа аij<0, то можна перейти

до нового псевдоплану, при якому значення цільової функції задачі

(1)-(3) не зменшиться.

 

Сформульовані теореми дають основу для побудови алгоритму

двоїстого симплекс-методу.

 

Отже, продовжимо розгляд задачі (1)-(3). Нехай Х=(b1; b2; …

;bm; 0; … ;0) – псевдоплан цієї задачі. На основі вихідних даних

складають симплекс-таблицю

 

Таблиця 1

 

І Ба-

 

 

 

 

.

 

.

 

Нехай це мінімальне значення береться при j = r ; тоді в

базис вводять вектор Pr. Число air являється дозволяючим елементом.

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

симплексного методу. Ітераційний процес продовжують до того часу, доки в

стовбці вектора P0 не буде більше від’ємних чисел. При цьому знаходять

оптимальний план вихідної задачі, а пізніше і двоїстої. Якщо на якомусь

кроці виявиться, що в i-тому рядку симплекс-таблиці (табл. 1) в

стовбці вектора P0 стоїть від’ємне число b1, а серед інших елементів

цього рядка немає від’ємних, то вихідна задача немає розв’язку.

 

 

Знаходять псевдоплан задачі.

 

Провіряють цей псевдоплан на оптимальність. Якщо псевдоплан оптимальний,

то знайдено розв’язок задачі. В протилежному випадку або встановлюють,

що задача немає розв’язків, або переходять до нового псевдоплану.

 

Вибирають дозволяючий рядок за допомогою визначення найбільшого по

абсолютній величині від’ємного числа стовбця вектора P0 і дозволяючий

стовпець з допомогою знаходження найменшого по абсолютній величині

-----> Page:

0 [1]

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