9.5. Геометрична інтерпретація алгебраїчних властивостей в вершині симплекса. Алгебра переходу від вершини до вершини в СМ
У процесі вирішення ЗЛП ми здійснюємо спрямований перебір вершин сімлекса (так як знаємо, що саме серед них знаходиться оптимальне рішення);
Геометрична інтерпретація алгебраїчних властивостей в вершині симплекса:
Очевидно, щоб утворити вершину, певна кількість (n-m) гіперплоскостей обмежень повинні перетнутися.
Точніше: щоб утворити вершину, певна кількість (n-m) гіперплоскостей обмежень відповідного набору вільних змінних (відповідного етапу вирішення ЛП задачі, коли ми перейшли в цю вершині) повинні перетнутися, причому кожна з цих в перетині повинна = "0" (множина значень х на кожній з цих гіперплоскостей, повинні задовольняти а в точці перетину, вони всі повинні бути = 0).
Алгебра: В алгебраїчній системі (**) це відповідає рішенню вважати змінні xm+1, xm+2,..,xn рівними значенню = 0. Ці (n-m) змінних називають небазисними.
Значення ж інших m змінних, відповідающих гіперплоскостям, що залишилися лежати поза точкою перетину (поточної вершини симплексу), в цій точці, природно не рівні "0", а рівні деяким ненульовим значенняь, які і утворюють поточне рішення ЛП завдання.
Ці змінні, на цьому кроці, називають базисними, а відповідне рішення (отримане в даній вершині) - базисним рішенням (БР).
Таким чином на першому кроці симплекс методу базисне решення може бути отримано з канонічного виду ЛП завдання, представленого для зручності у вигляді (**) чи (***)
(***)
Після підстановки для сильних змінних xm+1=0, xm+2=0,..,xn=0 (оскільки вони тут і зараз є вільними) значення слабких змінних є х1=b1,...,xm=bm Це і буде базисним рішенням на першому кроці методу.
Ми тут розглянули такий механізм визначення БР, що він автоматом виводить нас в якусь вершину симплекса. У яку саме, зараз не важливо яку - головне що в вершину. Не у внутрішню точку, не на ребро, а в вершину - це важливо, так як існує твердження, що оптимум ЛП завдання знаходиться саме в одній з вершин симплекса.
Достарыңызбен бөлісу: |
