Тепер необхідно зрозуміти, яка проста мінлива першої звернеться в нуль у міру збільшення вхідної змінної. Для цього достатньо розглянути систему:
В
При фіксованих значеннях непростих змінних система однозначно розв'язана відносно простих, тому ми можемо визначити, яка з простих змінних першої досягне нуля при збільшенні вхідної. Цю змінну назвемо виходить. Це означатиме, що ми натрапили на нову вершину. Тепер вхідну і вихідну змінну поміняємо місцями - входить В«увійдеВ» в просту, а що виходить з них В«вийдеВ» у непрості. Тепер перепишемо матрицю B і вектор c B у відповідності з новими наборами простих і непростих змінних, після чого повернемося до другого кроку. x''
Оскільки число вершин, звичайно, то алгоритм одного разу закінчиться. Знайдена вершина буде оптимальним рішенням. br/>
3. Двофазовий симплекс-метод
Причини використання
Якщо в умові завдання лінійного програмування не всі обмеження представлені нерівностями типу В«?В», то далеко не завжди нульовий вектор буде допустимим рішенням. Однак кожна ітерація симплекс-методу є переходом від однієї вершини до іншої, і якщо невідомо жодної вершини, алгоритм взагалі не може бути розпочатий. p align="justify"> Процес знаходження вихідної вершини не сильно відрізняється від однофазного симплекс-методу, однак може в підсумку виявитися складніше, ніж подальша оптимізація.
Модифікація обмежень
Всі обмеження завдання модифікуються згідно з такими правилами:
В· обмеження типу В«?В» переводяться на рівності створенням додаткової змінної з коефіцієнтом В«+1В». Ця модифікація проводиться і в однофазному симплекс-методі, додаткові змінні в подальшому використовуються як вихідний базис.
В· обмеження типу В«?В» доповнюються однієї змінної з коефіцієнтом В«? 1 В». Оскільки така мінлива через негативного коефіцієнта не може бути використана у вихідному базисі, необхідно створити ще одну, допоміжну , змінну. Допоміжні змінні завжди створюються з коефіцієнтом В«+1В».
В· обмеження типу В«=В» доповнюються однієї допоміжної змінної.
Відповідно, буде створено деяку кількість додаткових і допоміжних змінних. У вихідний базис вибираються додаткові змінні з коефіцієнтом В«+1В» і всі допоміжні. Обережно: рішення, якому відповідає цей базис, не є допустимим. p align="justify"> Відмінності між додатковими і допоміжними змінними
Незважаючи на те, що і додаткові, і допоміжні змінні...
