РЕФЕРАТ
на тему:
Суть симплекс-методу
ПЛАН
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
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)
Нашли опечатку? Выделите и нажмите CTRL+Enter
