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

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

ГоловнаМатематика, Геометрія, Статистика → Суть симплекс-методу - Реферат

Суть симплекс-методу - Реферат


РЕФЕРАТ
на тему:
Суть симплекс-методу
ПЛАН
1. Поняття симлекс-методу, його місце у розв'язуванні задач
лінійного програмування
2. Поняття двоїстого симплекс-методу, його особливості
Список використаної літератури
1. Поняття симлекс-методу, його місце у розв'язуванні задач
лінійного програмування
Нехай потрібно знайти максимум функції
Z(x1, х2) = 3х1 + 2,5х2
на множині , що описується системою нерівностей. Значення функції Z(x1, х2) = 3х1 + 2,5х2 в деякій точці з координатами х1, х2 також можна сприймати як відхилення цієї точки від прямої Z(x1, х2) = 3х1 + 2,5х2 = 0. Тому чим більше точка відхиляється від прямої Z(x1, х2) = О, тим більше значення має в цій точці функція Z(x1, х2). Крім того, точки будь-якої прямої, паралельної прямій Z(x1, х2) = 0, однаково відхилені від прямої Z(x1, х2) = 0. Отже, точка, в якій функція Z(x1, х2) досягає найбільшого значення, повинна бути точкою області , яка лежатиме на прямій, що має з спільні точки і відхилена від прямої Z(x1, х2) = О найбільше. Таким чином, шукана точка може лежати лише на межі області , тобто належати деяким прямим, що обмежують область (мал. 1, 2). Відхилення такої точки від кожної з межових прямих, яким вона належить, очевидно, дорівнює нулю.
Мал. 1 Мал. 2
Допустимий розв'язок, в якому функція Z досягає найбільшого значення, називатимемо оптимальним розв'язком. Точку, що відповідає оптимальному розв'язку, називатимемо оптимальною точкою. Якщо оптимальна точка існує і єдина (на мал. 1 - точка M2), то це - деяка вершина многокутника . А якщо оптимальних точок безліч (мал. 2), то до їх множини належать і деякі вершини многокутника (на мал. 2 - точки M1* i М2*). Тому для знаходження оптимальної точки достатньо розглядати лише вершини многокутника .
Отже, з геометричного погляду нашу задачу можна сформулювати так: серед вершин многокутника знайти таку, в якій би функція Z(x1, x2) досягла найбільшого значення.
Симплекс-метод якраз і дає можливість знайти спочатку якусь вершину многокутника , а потім від неї перейти до тієї, в якій значення функції Z не менше, ніж у попередній.
Перейдемо тепер до загального випадку. Нехай потрібно знайти максимум функції
Z(x) = (p, x) = p1x1 + p2x2 + ... + рnхn (1)
(або, що те саме, мінімум функції Z1(x) = -Z(x)) на множині , що визначається системою лінійних нерівностей
i(x) = (ai, x) + bi = аi1x1 + ai2x2 + ... + аinхn + bi О (i=1, 2, ..., m). (2)
Запишемо дані нашої задачі у вигляді таблиці.
Таблиця 1
x1 x2 ... xn 1
1 a11 a12 ... a1n b1
2 a21 a22 ... a2n b2
... ... ... ... ... ...
m am1 am2 ... amn bm
Z p1 p2 ... pm 0
Не порушуючи загальності міркувань, припустимо, що ранг матриці (aij) (і = 1, m; j = 1, n) дорівнює n. Знайдемо спочатку якусь допустиму вершину множини розв'язків . Нехай через n кроків жорданових виключень матимемо таблицю:
Таблиця 2
1 2 ... n 1
x1
...
... ... ... ... ... ...
xn
n+1
...
... ... ... ... ... ...
m
...
Z
...
Z(n)
Нехай вершина 1 = 0, 2 = 0, ..., n = 0 допустима, тобто b(n)n+1 0, ..., b(n)m 0. Якщо при цьому всі коефіцієнти в Z-рядку недодатні, тобто р(n)1 0, р(n)2 0, ..., р(n)n 0, то в вершині 1 = 0, 2 = 0, ..., n = 0 досягається максимум функції Z(x).
Справді, в такому разі Z(x) = р(n)1 1(x) + р(n)2 2(x) + ... + р(n)n n(x) + Z(n) Z(n) будь-якого x, для якого 1(x) 0, 2(x) 0, ..., n(x) 0.
Нехай тепер серед чисел р1(n), р2(n), ..., рn(n) є додатні, наприклад p1(n) > 0. Тоді, збільшуючи відхилення 1(х) і залишаючи 2(x), ..., n(х) рівними нулю, тобто рухаючись по "ребру" 2(x) = 0, ..., n(х) = 0 в напрямі збільшення 1(х), збільшуватимемо і функцію Z(x). При цьому, вийшовши з вершини 1 = 0, 2 = 0, ..., n = 0, рухатимемось по згаданому ребру доти, поки вперше зіткнемось з якоюсь з "площин", що обмежують множину . У результаті цього потрапимо в нову вершину множина . Міркуючи так само, які при знаходженні допустимої вершини, ми приходимо до таких правил:
1. За основний вибираємо який-небудь із стовпчиків, що містять додатні елементи Z-рядка. (Якщо таких елементів в Z-рядку немає, точка, що належить базовим площинам, є оптимальною).
2. У -рядках знаходимо від'ємні елементи в основному стовпчику. (Якщо таких елементів немає, то множина необмежена, функція Z(x) на цій множині необмежена і оптимальної точки не існує).
3. Знаходимо найменше за абсолютною величиною від'ємне відношення вільних членів -рядків до відповідних елементів основного стовпчика. Рядок, який відповідає такому відношенню, беремо за основний.
4. З вибраним таким чином основним елементом виконуємо крок жорданового виключення. Діставши нову таблицю (нову допустиму вершину), знову повертаємось до правила 1.
Через скінченну кількість кроків знайдемо оптимальну точку або встановимо, що такої не існує. Можливе зациклювання при цьому долаємо так само, як і при розв'язуванні системи нерівностей.
Щойно описаний метод розв'язування задачі лінійного програмування (і системи лінійних нерівностей) називається симплекс-методом.
2. Поняття двоїстого симплекс-методу, його особливості
В оптимальній точці вектор р - градієнт цільової функції Z(x) = (p, x) виражається через градієнти (нормальні вектори) ai базових площин i(x) = 0 з недодатними коефіцієнтами. Якщо, наприклад, у таблиці 10 точка х*, що належить площинам 1(x) = 0, 2(x) = 0, ..., n(x) = 0, оптимальна, тобто числа р1(n), р2(n), ..., рn(n) недодатні, то
p = p1(n)a1 + p2(n)a2 + ... + pn(n)an. (3)
Така рівність є достатньою умовою того, що точка х*, яка належить площинам 1(x) = 0, 2(x) = 0, ..., n(x) = 0, оптимальна на множині точок, які задовольняють нерівності 1(x) 0, 2(x) 0, ..., n(x) 0.
Справді, для будь-якого х, що задовольняє нерівності 1(x) 0, 2(x) 0, ..., n(x) 0, якщо рi(n) 0. Тоді в -рядках у стовпчику, що містить р1(n) > 0, відшукаємо від'ємний елемент. Якщо такого немає, то двоїсто-допустимої точки не існує. При цьому відхилення 1 можна зробити як завгодно великим, і при досить великому 1 всі відхилення n+1, ..., m стануть невід'ємними (якщо всі an+11(n) > 0, an+21(n) > 0, ..., am1(n) > 0). Це означає, що область необмежена і функція Z(x) в цій області не досягає найбільшого значення (воно нескінченно велике). Оптимальної точки в такому випадку не іcнує (мал. 2).
Нехай у стовпчику, який містить р1(n) > 0, є від'ємний елемент, наприклад an+11(n) < 0. Тоді рядок, що містить цей від'ємний елемент, візьмемо основним і знайдемо всі від'ємні відношення елементів Z-рядка до відповідних елементів основного рядка (вільні члени до уваги не беруться). Найменше за модулем від'ємне відношення визначає основний стовпчик. Із знайденим таким чином основним елементом, що належить основному рядку і основному стовпчику, виконуємо один крокжорданового виключення. Якщо всі зазначені найменші від'ємні відношення відрізняються від нуля, то через скінченну кількість кроків або буде знайдено двоїсто-допустиму точку, або з'ясується, що її не існує.
Нехай тепер у таблиці 10 усі елементи Z-рядка недодатні, тобто ми маємо двоїсто-допустиму точку. Якщо при цьому всі вільні члени в -рядках невід'ємні, тобто bn+1(n) 0, bn+2(n) 0, ..., bm(n) 0, то точка також допустима, тобто оптимальна.
Припустимо, що серед вільних членів bn+1(n), bn+2(n), ..., bm(n) є від'ємні. Тоді ми повинні з даної двоїсто-допустимої точки перейти до іншої двоїсто-допустимої так, щоб, по можливості, позбутися від'ємних вільних членів у -рядках. Отже, якщо в прямому симплекс-методі переходять від однієї допустимої вершини до іншої так, що функція Z(x) при цьому збільшувалась, і рухаються по допустимих вершинах доти, поки досягнуть допустимої вершини, яка водночас буде й двоїсто-допустимою, то в двоїстому симплекс-методі рухаються по двоїсто-допустимих вершинах, наближаючись до області доти, поки не дістануть двоїсто-допустимої вершини, яка буде водночас і допустимою. При переході від однієї двоїсто-допустимої вершини до іншої значення функції Z(x) зменшується (у всякому раді не збільшується). Отже, якщо множина не порожня, то max Z(x) = min Z(x), де * (не порожня) множина всіх двоїсто-допустимих точок. Це е так званий принцип двоїстості. Щоб перейти від однієї двоїсто-допустимої вершини до іншої, у -рядку з від'ємним вільним членом відшукуємо додатні елементи. Якщо таких немає, то система нерівностей несумісна, множина порожня і оптимальної точки не існує (бо не існує допустимих точок). Нехай такі елементи є. Тоді цей -рядок беремо основним і знову відшукуємо найменше за модулем від'ємне відношення елементів Z-рядка до відповідних елементів основного рядка. Таке відношення визначає основний елемент. З визначеним таким чином основним елементом виконуємо крок жорданового виключення. Якщо всі зазначені найменші відношення не дорівнюють нулеві, то через скінченну кількість кроків або дістанемо допустиму, а отже, й оптимальну, вершину або з'ясуємо, що система несумісна.
Список використаної літератури
1. Вентцель Е.С. Исследование операций. - М.: Знание, 1978.
2. Зайченко Ю.П. Дослідження операцій. - К.: Вища школа, 1999.
3. Катренко А.В. Дослідження операцій. Підручник. - Львів, 2004.
4. Ржевський С.В. Елементи дослідження операцій. - К., 1999.
5. Справочник по математике для экономистов / Под ред. Ермолаева В.И. - М.: Высшая школа, 1997.
Loading...

 
 

Цікаве