Базис та базисне рішення - Студопедія
У задачі ЛП базиси та базисні рішення грають ключову роль організації пошуку оптимального рішення, якщо воно існує. З їхньою допомогою генеруються чергові вершини області допустимих рішень, і організується перехід із однієї вершини до іншої. Вдалий вибір початкового базису і базового рішення може значно прискорити процес пошуку.
Ілюструємо можливість такого вибору на прикладі завдання з обмеженнями у вигляді
Якщо уявити обмеження цього завдання якAx = b,то матрицяАнабуде формуА = [a1, a2, a3],деa1 = (4, 2) T , a2 = (1, 3) T , a3 = (5, 2) T . x = (x1,x2,x3) T . Векториa1, a2, a3,як легко переконатися в цьому, є лінійно незалежними, тому будь-яку двійку з них можна вибрати в якості початкового базису. Прикладами такого вибору є, наприклад,(2х2)– матриціВ1 = [a1, a2], B2 = [a2, a3], B3 = [a1, a3].Ці матриці дійсно є базисом для векторів матриціА.
Шляхом розкладанняА=[B, N]матричне рівнянняAx = bпредставляється як
або що еквівалентно,
Так як за визначенням матрицяBмає зворотну матрицю, рішення останнього рівняння щодо векторахB,отримаємо у вигляді
Приймаючи у цьому виразіxN = 0,отримаємо базисне рішення у вигляді
Якщо вона неотрицательно, тобто.хB≥ 0, отримаємо допустиме базисне рішення. Цьому рішенню відповідає вершина множини допустимих рішень, яку можна визначити у вигляді
х 1 = .(4.5)
У цій точці значення цільової функції дорівнюєf(x 1 ) = c T x 1 = cB T xB.
Розглянемо усі три можливості.
хB = (х1в х2в) Т = В1 -1 b= (0.6, 3.8)Т,
хB = (х2в х3в) Т = В2 -1 b= =(16/13,
38/13) Т, х 2 = (0, 16/13, 38/13) Т;
хB = (х1в х3в) Т = В3 -1 b ==(2, 1) Т,
Усі три вершини є допустимими.
1.5. Табличний симплекс-метод (симплекс-алгоритм)
Cімплекс - метод заснований на ітеративному процесі перебору (або перетворення) вершин області допустимих рішень та перевірки у цих вершинах умови оптимальності. Вершини, як зазначалося вище, генеруються з допомогою базисів. Табличний варіант алгоритму дуже зручний для машинного рахунку, оскільки пов'язаний з перетворенням таблиць - масивів даних, які містять відомості про поточний базис, базисне рішення, правило зупинки і, нарешті, про оптимальне рішення. У процесі перетворення таблиць, що є реалізацію процедуриповного виключення Гаусса,формується також інформація про двоїстих змінних розв'язуваної задачі.
Нехай завдання подано у канонічній формі
, (5.1)
дезіх –вектори розмірності (п х1),тобто. с Е п , Х Е п , А -матриця розмірності(mхп), b - (пх1)- вектор.
Припустимо, що матрицяАдопускає подання у виглядіА=[B, N], де B – (mхm) –матриця повного рангу. Для простоти припустимо, щоB -одинична матриця, тобто.B = I. Це може мати місце, наприклад, якщо обмеження вихідної задачі мають виглядAx ≤ b.У разі невід'ємного вектораb,тобтоb ≥ 0,це припущення допомагає знайти перше базисне рішення у вигляді
xB = B -! b = I -1 b = b ≥ 0. (5.2)
Тоді перша вершина дорівнюватиме
де через0п-mпозначений нульовий вектор зп-mкоординатами. Для побудови вихідної таблиціпозначимо черезIBіIN,множини індексів векторів зBіNвідповідно і обчислимо так звані симплекс -різниці для векторів, що належатьNза формулою
(СР)j = cj-. (5.4)
Симплекс – різниці містять інформацію про оптимальності поточного базисного рішення, отже, і поточної вершини. Згідно з цим правилом,якщо при вирішенні задачі на максимум на якомусь кроці (або ітерації) симплексних перетворень має місце
тоді знайдене базисне рішення є оптимальним. Інакше пошук рішення продовжується.
Легко помітити, що для всіх базисних векторів завжди є умова
т. е. вектори зВмають нульову симплекс - різницю на всіх етапах симплексних перетворень.
Нехай потрібно вирішити завдання
Зручно уявити такі дії як послідовності кроків алгоритму. Він складається з попереднього та основного етапів.
Попередній етап. Уявити завдання у канонічній формі
Крок 1.Розкладання матриці А. Записати обмеження у вигляді матричного рівнянняAx = b, x≥ 0, і подати матрицюАу вигляді
,
виділивши в ній(mxm) -матрицюBповного рангу. Зручно в даному випадку вибрати як початковий базис одиничну матрицюB = [a3, a4, a5] = I,отже,N = [a1, a2], IB , IN = .Як бачимо,B = I –одинична матриця розмірності(3х3).Якщо отримання базисуВнеможливо, то завдання немає решения.
Крок 2.Знаходження базисного рішення. Початковому базисуВвідповідає базисне рішення у вигляді
Вершина, що відповідає цьому базисному рішенню, дорівнюєх 1=(0, 0, 12, 2, 3) Т . Останні три координатих 1збігаються з відповідними координатамихB,а перші дві координати дорівнюють нулю. Значення цільової функції у цій точці дорівнює
Крок 3.Обчислення симплекс - різниць і побудова правила зупинки.Обчислимо симплекс - різниці для небазових векторів зN.
(СР)1=c1– ,
(СР)2=c2– .
Легко помітити, що через нульовий векторсВ = (0, 0, 0) Тмає місце умова
Оскільки симплекс - різниці(СР)1і(СР)2позитивні, пошук оптимального рішення продовжується.
Крок 4.Побудова та перетворення вихідної таблиці Т0.
Вихідна симплекс – таблиця, відповідна розв'язуваної задачі, наведено на рис. 2.2.
| i0 = 5 |
| J0 = 2 |
Мал. 2.2. Вихідна симплекс – таблиця.
Вона містить матрицюА,векторb,базисне рішенняxB = bі так званийіндексний рядок,у якому перший її елемент – це поточне значення цільової функціїf(x) = f(xB) = cB T xB,а решта її елементів – це так званііндекси Dj = - (CP)j, j = 1, …, n,значення яких визначається як симплекс - різниці зі зворотним знаком. Цифрова частина симплекс - таблиці називається їїголовною частиною:вона і піддається перетворенню від ітерації до ітерації.
Крок 5. Перевірка правила зупинки
ЯкщоDj ³ 0, j = 1, …, n,зупинитися; Знайдене базисне рішення є оптимальним, а значення цільової функції найбільше. У разі обидві величиниDjнегативні. Це означає, що обидві симплекс -Різниці(CP)j, j = 1, 2,позитивні, отже, пошук продовжується.
Крок 6. Вибір напрямного стовпця і напрямного рядка.Напрямний стовпець з індексомj0вибирається за найбільшим значенням(CP)j > 0.У нашому випадку це(CP)2 = 3,отже,j0 = 2.Напрямний рядок з індексомi0вибирається за правилом
.
Згідно з цим правилом, серед усіх відносин типу деxib– базисні змінні (їх чисельні значення містяться в стовпціb),-позитивні елементи стовпця, що направляє, вибирається найменше відношення з індексомi0. У нашому випадку – це рядок з індексомi0= 5. Якщо в стовпчику позитивних елементів немає, завдання не має рішення через необмеженість цільової функції.
Вибору напрямного рядка і стовпця з індексамиi0іj0відповідно відповідає виключення з базисного рішення змінної та включення замість неї змінну , причому, новій змінній у базисі присвоюється значення
l0 = .
У поточній таблиці елемент називаєтьсяпровідним елементомі відзначається кружком.
Чи не знайшли те, що шукали? Скористайтеся пошуком: