На головну

Система m лінійних рівнянь з n змінними

  1.  III. Система МВС Росії
  2.  IV. Виробництво з двома змінними факторами. Рівновага виробника.
  3.  IV. МОВА ЯК СИСТЕМА І СТРУКТУРА
  4.  UltraPulse Encore - компактна СО2-лазерна система для прецизійної абляції, вапоризації, різання і коагуляції м'яких тканин.
  5.  V. осмислення, узагальнення и сістематізація Нових знань
  6.  V. ПОЛІТИЧНА СИСТЕМА СУСПІЛЬСТВА.
  7.  V. Сістематізація и узагальнення Нових знань, умінь и навічок

Система m лінійних рівнянь з n змінними має вид:

 А11 * Х1 + А12 * Х2 + ... + а1j * Xj + ... + А1N * Xn = В1

а21 * Х1 + а22 * Х2 + ... + а2j * Xj + ... + а2n * Xn = В2

...............................

аi1 * Х1 + аi2 * Х2 + ... + аij * Xj + ... + а in * Xn = В i (6)

...............................

аm1 * Х1 + аm2 * Х2 + ... + аmn * Xn = Вm

або в короткій записи

 (I = 1, 2, ..., m)

в задачах ЛП представляють інтерес системи, в яких максимальне число незалежних рівнянь системи менше числа змінних. Будемо вважати, що в системі (6) усі m рівнянь системи незалежні, тобто m

Будь-які m змінних системи m лінійних рівнянь з n змінними (m основними (базисними), Якщо визначник матриці коефіцієнтів при них відмінний від нуля. Тоді решта n - m змінних називаються неосновними (або вільними).

Основними можуть бути різні групи з n змінних, але загальне число груп не перевищує число поєднань .

 = N! / ((N-m)! M!)

приклад:

Знайти всі можливі групи основних змінних в системі

 х1 - х2 - 2х3 + х4 = 0 (7)

2х1 + х2 + 2х3 - х4 = 2

Рішення. Загальна кількість груп основних змінних не більше ніж  = 4 * 3/2 = 6, тобто можливі групи основних змінних: х1, х2; х1, х3; х1, х4; х2, х3; х2, х4; х3, х4.

 Змінні х1, х2 можуть бути основними, тому що визначник матриці з коефіцієнтів при цих змінних  = 1 * 1 - 2 * (-1) = 3 ? 0. розмірковуючи аналогічно, можна знайти, що можуть бути основними змінні х1, х3; х1, х4, але не можуть бути основними х2, х3; х2, х4; х3, х4, тому що відповідні визначники дорівнюють 0.

 х3, х4  = (-2) * (-1) - 2 * 1 = 0.

Існує теорема. Якщо для системи з m лінійних рівнянь з n змінними ((m

Нехай, наприклад, х1, х2, ..., хm - основні змінні (якщо це не так, то нумерацію можна змінити), то визначник матриці

 ? 0.

Залишимо в лівих частинах рівнянь системи (6) члени зі змінними х1, х2, ..., хm, а члени зі змінними xm+1, xm+2, ..., Xn перенесемо в праві частини. отримаємо:

А11 * Х1 + А12 * Х2 + ... + а1m * Xm = В1 - а1m + 1 * Xm + 1 - ... - А1N * Xn

а21 * Х1 + а22 * Х2 + ... + а2m * Xm = В2 - а2m + 1 * Xm + 1 - ... - а2n * Xn

.................................................. .............................

аm1 * Х1 + аm2 * Х2 + ... + аmm * Xm = Вm - аmm + 1 * Xm + 1 - ... - аmn * Xn

Ставлячи неосновним змінним xm+1, xm+2, ..., Xn довільні значення, кожен раз будемо отримувати нову систему з новими вільними членами. Кожна з отриманих систем матиме один і той же визначник, тобто кожна з систем матиме єдине рішення. Так як одержуваних таким чином систем безліч, то і система (6) буде мати безліч рішень.

Рішення Х = (х1, х2, ..., хn) системи (6) називається допустимим, Якщо воно містить лише невід'ємні компоненти, тобто Хj> = 0 для будь-яких j = 1, 2, ..., n. В іншому випадку рішення називається неприпустимим.

Серед нескінченної кількості рішень системи виділяють базисні рішення.

базовим рішенням (БР) Системи m лінійних рівнянь з n змінними називають рішення, в якому все n - m неосновних змінних дорівнюють нулю.

У завданнях ЛП особливий інтерес представляють допустимі базисні рішення (ДБР), Або, як їх ще називають, опорні плани. Число базисних рішень є кінцевим, тому що воно дорівнює числу груп основних змінних, що не перевершує  . Базисне рішення, в якому хоча б одна з основних змінних дорівнює нулю, називається виродженим.

приклад:

У прикладі (7) існує три групи основних змінних, тобто число базисних рішень = 3.

Перше х1 і х2 - основні, х3 і х4 - неосновні (= 0), тоді

 х1 - х2 = 0

2х1 + х2 = 2

звідки х1 = 2/3; х2 = 2/3. отже першому баз рішення системи Х1 = (2/3; 2/3; 0; 0) допустимая.

Якщо взяти за основні змінні Х1 і Х3, то отримаємо другий баз рішення системи Х2 = (2/3; 0; 2/3; 0) - також допустимий. Аналогічно можна знайти третє баз рішення при основних змінних х1, х4 Х3 = (2/3; 0; 0; -2/3) - неприпустиме.

Висновок: Спільна система (6) має нескінченно багато рішень, з них базисних рішень - кінцеве число, яке не перевищує .




 лінійне програмування |  Поняття економіко-математичної моделі |  Є опуклим багатокутником (або опуклою багатокутної областю). |  Властивості задач ЛП |  Геометричний метод розв'язання задач ЛП |  симплексний метод |  Знаходження оптимуму лінійної функції |  Особливі випадки симплексного методу |  сімплексні таблиці |

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