Головна

Базисні та опорні рішення системи лінійних рівнянь

  1. CAD-системи
  2. D.3. Системи економетричних рівнянь
  3. Grid-системи
  4. I'a-чштіе школи і становлення шкільної системи
  5. I. Визначення рівнянь лінійної регресії
  6. I.I. Способи вирішення проблеми неясності богослужбових текстів, запропоновані на Помісному Соборі 1917 - 1918 рр.
  7. I.II. Споспоб вирішення проблеми, пропонований нами.

Введемо поняття базисного рішення системи лінійних рівнянь. Розглянемо  - Мірні вектори, координати яких дорівнюють коефіцієнтам при невідомих і вільних членів рівнянь системи (7):

 ; ...; ; .

За допомогою цих векторів систему (7) можна записати у вигляді

.

На підставі отриманого співвідношення можна зробити висновок, що рішення системи рівнянь (7) зводиться до знаходження коефіцієнтів розкладання  вектора  по векторах  . В результаті Жорданових винятків розширена матриця системи лінійних рівнянь (7)

прийме наступний вигляд:

,

тобто вектори  перетворилися в поодинокі. З цього випливає, що вектори  лінійно незалежні і складають базис системи векторів  . систему  рівнянь, в якій стовпці коефіцієнтів при  невідомих є поодинокими векторами, будемо називати наведеної до одиничного базису. Іноді систему в такому записі називають наведеної до дозволеного виду.

змінні  , Відповідні векторах базису  називають базисними, а весь набір базисних змінних - базисом системи змінних  . змінні  , Відповідні векторах  , називають вільними (Їм можна надавати в загальному рішенні (1.8) довільні числові значення).

Якщо в загальному рішенні (8) системи (7) вільним змінним надати нульові значення, то отримане приватне рішення  , Або у векторній запису  , називається базисним.

Так в прикладі 1 базисним буде рішення: (3;  3; 0; 0).

Взагалі кажучи, з даної системи  векторів  можна вибрати максимально  різних базисів, де

.

Кожному такому базису відповідатимуть базис системи змінних  і відповідне базисне рішення. Зі сказаного випливає, що максимально можливе число базисних рішень  . Проте насправді їх може виявитися менше, тому що деякі групи по  векторів можуть бути лінійно залежні і, отже, не будуть утворювати базису. Чи не будуть утворювати базису і відповідні цим векторах змінні.

Щоб знайти базисні рішення системи рівнянь, потрібно перетворювати систему, послідовно переходячи від одного одиничного базису до іншого. Ми будемо це робити за допомогою Жорданових винятків.

В економічних задачах негативні змінні, як правило, не мають реального сенсу. Тому розглянемо спосіб відшукання невід'ємних розв'язків системи лінійних рівнянь. Невід'ємні базисні рішення займають особливе місце в математичному програмуванні та називаються опорнимірешеніямі (Планами).

Розглянемо спосіб відшукання опорних рішень. Припустимо, що в таблиці 4 всі елементи стовпця вільних членів невід'ємні. З'ясуємо, як зберегти неотрицательность вільних членів в процесі Жорданових винятків.

Нехай перший крок жорданова виключення проводиться з дозволяє елементом  (Таблиця 9). Після зробленого кроку вільний член в роздільною рядку

 (9)

буде невід'ємним, якщо  , Тобто якщо дозволяє елемент позитивний (  за припущенням). Це перша вимога до яке дозволяє елементу.

Таблиця 9

  1  ...  ...
 ...  ...  ...  ...  ...
 ...  ...
 ...  ...  ...  ...  ...
 ...    ...
 ...  ...  ...  ...  ...

Нехай відношення (9) виконується. Тоді після кроку жорданова виключення вільний член довільної (  -й) рядки, рівний

буде невід'ємним, якщо

 . (10)

Так як , ,  , Нерівність (10) справедливо при будь-якого від'ємного .

нехай тепер  , Тоді нерівність (10) можна переписати у вигляді

.

Цим нерівністю виражається друга вимога до яке дозволяє елементу: ставлення вільного члена роздільною рядки до яке дозволяє елементу має задовольняти умові мінімальності, тобто воно повинно бути найменшим з усіх відносин вільних членів до відповідних елементів дозволяє стовпця. Якщо такій вимозі задовольняє відразу кілька відносин, то дозволяє елемент можна взяти в будь-якому рядку, що відповідає одному з цих відносин.

Отже, для відшукання опорного рішення системи лінійних рівнянь її потрібно представити у вигляді жорданової таблиці так, щоб всі її вільні члени були невід'ємні, а потім зробити можливе число кроків Жорданових винятків, вибираючи дозволяють елементи серед позитивних чисел основної частини таблиці за найменшим відношенню вільних членів до відповідних позитивним елементам стовпця, обраного що дозволяє. Шукане опорне рішення знайдеться прирівнянням верхніх (вільних) змінних нулю, а базисних (бічних) - вільним членам. Якщо в ході Жорданових винятків зустрінеться  -строка, в якій всі елементи непозитивні, а вільний член неотрицателен, то дана система не має невід'ємних (зокрема, опорних) рішень, хоча і є спільною.

Приклад 2. Знайти опорне рішення системи

Рішення: Запишемо систему у вигляді таблиці 10, попередньо помноживши третє рівняння на  1. Як дозволяючого можна взяти будь-який стовпець, що містить хоча б один позитивний елемент. Візьмемо, наприклад, третій стовпець. Роздільну рядок виберемо за найменшим сімплексному відношенню: min (3/1; 1/1) = 1/1. Менше з цих відносин відповідає третьому рядку. Вона і буде роздільної. На перетині третього рядка і третього стовпця знаходиться дозволяє елемент 1, з яким і виконується крок жорданову виключення.

табл.10 табл.11

 
 0 = 2  1 + 1 1
 0 = 2  1 0 1
 0 =  3 0 11
 
 0 = 5 1 2
 0 = 2  1 + 1
=  3 0 1

В результаті ще двох кроків Жорданових винятків отримаємо таблиці 12 і13.

 
=  2/3  
=  2/3  
=  7/3  

табл.12 табл.13

 
=  2/5  1/5  2/5
 0 =  6/5  3/5 9/5
=  11/5  3/5  1/5

З таб.13 при  = 0 знаходимо опорне рішення системи:

 (2/3; 0; 7/3; 2/3).



Рішення систем лінійних рівнянь | Основна ідея і алгоритм симплексного методу

Денної та заочної форм навчання | Звичайні і модифіковані жорданову виключення | Й випадок. Система обмежень має кращий вигляд. | й випадок. ЗЛП представлена ??в симетричної формі запису. |

© um.co.ua - учбові матеріали та реферати