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

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

ГоловнаІнформатика, Компютерні науки → Теорія двоїстості та двоїсті оцінки в аналізі розв’язків лінійних оптимізаційних моделей - Реферат

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


Реферат на тему:
Теорія двоїстості та двоїсті оцінки в аналізі розв'язків лінійних оптимізаційних моделей.
План.
1. Двоїстий симплекс-метод.
2. Література
Двоїстий симплекс-метод.
Двоїстий симплекс-метод, так як і симплекс-метод, використовується при знаходженні розв'язку задачі лінійного програмування, записаної у формі основної задачі, для якої серед векторів Рі, складених з коефіцієнтів при невідомих в системі рівнянь, маючи 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). Таким чином можна знайти
Означення: Розв'язок Х=(b1; b2; … ; bm ; 0; … ; 0) системи лінійних рівнянь (2), визначене базисом Р1, Р2, … , Рm, називається псевдопланом задачі (1)-(3), якщо для будь-якого j (j=1,n).
Теорема 1: Якщо в псевдоплані Х=(b1; b2; … ;bm; 0; … ;0), визначеним базисом Р1, Р2, … , Рm, є хоча б одне від'ємне число таке, що все (j=1,n), то задача (1)-(3) зовсім не має планів.
Теорема 2: Якщо в псевдоплані Х=(b1; b2; … ; bm ; 0; … ; 0), визначеного базисом Р1, Р2, … , Рm, є від'ємні числа такі, що для будь-яких із них існують числа аij<0, то можна перейти до нового псевдоплану, при якому значення цільової функції задачі (1)-(3) не зменшиться.
Сформульовані теореми дають основу для побудови алгоритму двоїстого симплекс-методу.
Отже, продовжимо розгляд задачі (1)-(3). Нехай Х=(b1; b2; … ;bm; 0; … ;0) - псевдоплан цієї задачі. На основі вихідних даних складають симплекс-таблицю
Таблиця 1
І Ба-
зис Сб Р0 с1 с2 … се … cm cm+1 … cr … cn
P1 P2 … Pe … Pm Pm+1 … Pr … Pn
1 P1 с1 b1 1 0 … 0 … 0 a1m+1 … a1r … a1n
2 P2 с2 b2 0 1 … 0 … 0 a2m+1 … a2r … a2n
… … … … … … … … … … … … … … …
е Pe се be 0 0 … 1 … 0 aem+1 … aer … aen
… … … … … … … … … … … … … … …
і Pi сі bi 0 0 … 0 … 0 aim+1 … air … ain
… … … … … … … … … … … … … … …
m Pm сm bm 0 0 … 0 … 1 amm+1 … amr … amn
m+1 F0 0 0 … 0 … 0


в якій деякі елементи стовпця вектора Р0 є від'ємними числами. Якщо таких чисел немає, то в симплекс-таблиці записаний оптимальний план задачі (1)-(3), оскільки, припускаємо, що всі . Тому для визначення оптимального плану задачі при умові, що він існує, слід провести упорядкований перехід від однієї симплекс-таблиці до другої до тих пір, поки зстовпця вектора Р0 не будуть виключені від'ємні елементи. При цьому весь час повинні залишатися невід'ємними всі елементи (m+1)-го рядка, для любого .
Таким чином, після складання симплекс-таблиці провіряють, чи є в стовпці вектора Р0 від'ємні числа. Якщо їх немає, то знайдено оптимальний план вихідної задачі. Якщо ж вони є (як ми і припускаємо), то вибирають найбільше по абсолютній величині від'ємне число. В тому випадку, коли таких чисел декілька, то беруть яке-небуть із них: нехай це число b1. Вибір цього числа визначає вектор, виключений з базису. В даному випадку із базису виводиться вектор Р1. Для того, щоб визначити який вектор потрібно ввести в базис знаходимо , де .
Нехай це мінімальне значення береться при j = r ; тоді в базис вводять вектор Pr. Число air являється дозволяючим елементом. Перехід до нової симплекс-таблиці виконують по звичайних правилах симплексного методу. Ітераційний процес продовжують до того часу, доки в стовбці вектора P0 не буде більше від'ємних чисел. При цьому знаходять оптимальний план вихідної задачі, а пізніше і двоїстої. Якщо на якомусь кроці виявиться, що в i-тому рядку симплекс-таблиці (табл. 1) в стовбці вектора P0 стоїть від'ємне число b1, а серед інших елементів цього рядка немає від'ємних, то вихідна задача немає розв'язку.
Таким чином, знайдені розв'язки задачі (1)-(3) двоїстим симплекс-методом враховують наступні етапи:
1. Знаходять псевдоплан задачі.
2. Провіряють цей псевдоплан на оптимальність. Якщо псевдоплан оптимальний, то знайдено розв'язок задачі. В протилежному випадку або встановлюють, що задача немає розв'язків, або переходять до нового псевдоплану.
3. Вибирають дозволяючий рядок за допомогою визначення найбільшого по абсолютній величині від'ємного числа стовбця вектора P0 і дозволяючий стовпець з допомогою знаходження найменшого по абсолютній величині відношення елементів (m+1)-й рядок до відповідних від'ємних елементів дозволеного рядка.
4. Знаходять новий псевдоплан і повторяють всі дії починаючи з 2-го етапу.
Використана література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:
КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти)
"Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л.Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.36-47.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с
Loading...

 
 

Цікаве