система (1) постає як система п'яти рівнянь з дев'ятьма змінними:
x11 + x12 + x13 = a1
x21 + x22 + x23 = a2
x11 + x21 + x31 = b1 (4)
x12 + x22 + x32 = b2
x13 + x23 + x33 = b3
У цій системі чотири змінних (9-5 = 4) можуть брати будь-які значення в межах обмежень (2), а інші п'ять залежатимуть від них. Перші називають вільними, другі базисними змінними. p> Після того як вільні змінні взяли деякі значення, система (4) перетворюється на систему п'яти рівнянь з п'ятьма невідомими. Вона має єдине рішення. Рішення вихідної системи (4), при якому вільні змінні покладаються рівними нулю, називається базисним рішенням. Якщо при цьому базисні змінні виявилися невід'ємними, воно іменується допустимим базисним рішенням. p> Розбиття змінних на вільні і базисні до певної міри довільно. Слід враховувати лише одна умова: вільними змінними не можуть бути одночасно три змінних з однаковими першими або другими індексами. p> Далеко не всяке базисне рішення є допустимим базисним рішенням. Тим часом для нас становлять інтерес тільки ці останні. У теорії лінійного програмування доводиться, що допустимі базисні рішення є вершинами багатогранника допустимих рішень. Звідси випливає, що рішення поставленого завдання слід шукати серед допустимих базисних рішень. p> Як вибрати вільні змінні, щоб відповідне їм базисне рішення було допустимим базисним? Загальних рекомендацій на цей рахунок немає. В окремих випадках можна скористатися таким правилом:
якщо для будь-якого поєднання i, j і k виконується нерівність:
(5)
в якості комбінації вільних змінних, що забезпечує допустиме базисне рішення, може бути обрана сукупність:
(6)
Проілюструємо прикладом, який буде використаний надалі. Нехай. Тоді i = 1, j = 2, k = 3; індекси т і п можуть бути або "1", або "2", причому, якщо т = 1, то n = 2, і навпаки. p> Те ж правило залишається в силі, якщо. Тоді в сукупності (6) перші і другі індекси слід поміняти місцями. p> Якщо співвідношень типу (5) встановити не можна, як у моєму випадку, комбінація (6) як сукупності вільних змінних не годиться. Тоді таку сукупність можна скласти з трьох діагональних змінних x11, x22, x33 і однієї недіагональних, з індексами i та j, відповідними найменшим значенням величин ai і bj. p> Виходячи з цього: x11, x22, x33, x12 - вільні змінні (7)
x13, x21, x23, x31, x32 - базисні змінні
Оригінал базисне рішення
Алгоритм спрямованого перебору вершин багатогранника допустимих рішень (або, що те ж, - допустимих базисних рішень) базується на так званому симплекс-методі, головному дітище теорії лінійного програмування. Для "роботи" методу необхідно мати якесь одне (будь-яке) допустиме базисне рішення. Як знайти таке рішення, ми розібрали у попередньому розділі (етапі). Тут розглядається формалізоване подання цього рішення, зручне для використання в с...
