незалежності системи векторів необхідно і достатньо, щоб з ненульових елементів матриці
Х , що відповідають цим векторах, неможливо було скласти замкнутий маршрут (цикл).
Так як з виділених одиницями позицій на рис. 3 не можна скласти замкнутий маршрут, то дана система лінійно незалежна і утворює базис.
Введемо тепер в систему вектор, відзначивши його знаком '+'. Щоб розкласти по векторах системи R, складемо ланцюжок з виділених елементів, яка замикається на елементі:
.
При невеликих розмірах матриці Х візуальне відшукання замкнутих ланцюжків в ній представляє значні труднощі. У такому випадку вдаються до формалізованого методу викреслювання. Метод викреслювання дозволяє виділити в довільному плані Х Т-задачі замкнутий ланцюжок, якщо вона існує.
Цей метод полягає в наступному. Виділивши в плані Х безліч ненульових елементів, що позначається через S, з'ясуємо, чи існують у безлічі елементів S цикли. Для цього переглядаємо одну за одною рядка плану Х і викреслюємо рядки, що не містять елементів S, і рядки, які містять не більше одного елемента S (ненульовий елемент). Переглянувши всі рядка плану Х , переходимо до стовпців і викреслюємо ті з них, які містять не більше одного елемента S.
При цьому елементи, що містяться у раніше викреслених рядках, в розрахунок не беруть. Далі повторюємо весь цей процес, переглядаючи спочатку рядка, а потім стовпчики залишилася після викреслювання рядків і стовпців підматриці.
Після кінцевого числа кроків цей процес закінчується одним з наступних двох фіналів: 1) всі рядки (стовпці) матриці викреслені, 2) отримана подматріца, в кожному рядку і стовпці якої міститься не менше двох елементів S.
У першому випадку з елементів множини S скласти цикл неможливо. Отже, відповідний план Х є опорним. p> У другому випадку безліч S містить цикл (цикли) і відповідний план Х не є опорним (базисним). На рис. 4 показані два плану Т-задачі: небазисной (рис. 4, а) і базисний (рис. 4, б). Номери ліній вказують порядок викреслювання. Зірочками відзначені елементи, які викреслити не можна. Вони утворюють цикл. br/>
В
1 * * 1
1 * 1 *
1 1
* 1 * 1
Рис. 4. а)
5 6 11 7 серпень
1 1
9 1 1
2 1
10 1 1 січня
3 1
4 1
Рис. 4. б)
В
Знаходження початкових опорних планів
Існує кілька методів побудови початкових опорних планів Т-завдання. З них найпоширеніший метод північно-західного кута і метод мінімального елемента.
Метод північно-західного кута. Основну ідею методу розглянемо на конкретному прикладі.
Нехай дана Т-завдання з чотирма пунктами виробництва А 1 , А 2 , А 3 , А 4 з обсягами виробництва та пунктами споживання з обсягами споживання відповідно.
Побудуємо матрицю Х розміром 4х4, причому для зручності обчислень знизу від неї залишимо рядок b j , праворуч стовпець a i . Крім того, знизу від b j утворюємо рядки, де будемо записувати незадоволені потреби, а праворуч від a i - стовпці, де будемо записувати залишки невивезеного продукту (табл. 2).
Заповнення таблиці починають з лівого верхнього елементу таблиці X - x 11 , що й зумовило назву методу. Порівнявши з і вибравши менше з них, отримаємо x 11 = 1. Записуємо це значення в матрицю Х 0 . Так як перший вибір зроблений по рядку, то інша частина першого рядка повинна бути заповнена нулями. У допоміжному стовпці записуємо залишки невивезеного продукту,, а в рядку - незадоволені потреби після одного кроку заповнення.
Переходимо до другої рядку і починаємо заповнення з елемента (новий північно-західний кут незаповненою частині таблиці 2). Порівнюючи вибираємо менше з них, і тому. Іншу частину другої рядка заповнюємо нулями. Далі заповнюємо таблицю аналогічно. Після закінчення процесу заповнення будемо мати початковий план Х 0 . Отриманий план є базисним (опорним), так як з його ненульових елементів не можна скласти цикл. Крім того, він задовольняє умовам завдання, так як
.
В
Таблиця 2
Х
В В В В В В
1
0
0
0
