Варіанти та вдосконалення симплексного методу - Mathepedia

Вибір елемента опори

опорна колонка має позитивні зниження витрат і
лінія розвороту знову веде до допустимого базового рішення.

Вибір стовпця

Виберіть перший відповідний стовпець. Це найпростіший варіант, але він часто призводить до великої кількості ітерацій і тому не використовується на практиці.
Метод, спочатку запропонований Данцигом, вибирає одну з колон з найбільшим зниженим значенням вартості. Цей варіант може зайняти багато обчислювального часу з багатьма змінними.
найвищі ціни є поєднанням виділення стовпців та рядків, які разом приносять найбільший прогрес для цільової функції. Цей варіант дуже складний у кожній ітерації, але часто призводить до невеликої кількості ітерацій.
ціна devex є наближенням, запропонованим Полою Гарріс у 1974 році найвищі ціни і одна із стандартних процедур у сучасних вирішувачах LP. Стовпці матриці та зменшені витрати масштабуються до єдиного стандарту перед вибором, щоб збільшити інформативну цінність зменшених витрат.
Біля часткове ціноутворення ділить набір змінних на блоки та застосовує один із попередніх методів до блоку. Наступний блок розглядається лише в тому випадку, якщо там не знайдено відповідної змінної.
багаторазове ціноутворення шукає набір придатних змінних, які потім переважно розглядаються як кандидати на наступних ітераціях. Тільки тоді, коли жоден із цих кандидатів не має позитивно знижених витрат, враховуються інші змінні.
часткове множинне ціноутворення - це комбінація останніх двох варіантів, яка лише коли-небудь визначає нових кандидатів із частини всіх доступних змінних. Ця стратегія належить наступній ціна devex сьогодні до стандартних стратегій.
Біля гібридне ціноутворення декілька стратегій використовуються по черзі залежно від ситуації. Деякі вирішувачі LP також використовують числові критерії при виборі стовпців, щоб обмежити проблеми, спричинені помилками округлення.

Вибір рядка

Виберіть перший відповідний рядок. Хоча цей варіант дуже швидкий за ітерацію, він часто призводить до багатьох ітерацій і чисельно нестабільний.
правило лексикографічного відбору вибирає (однозначний) лексикографічно найменший рядок з усіх можливих рядків. Це правило не особливо добре з точки зору швидкості, але воно заважає відвідувати таблиці кілька разів, а алгоритм - їздити на велосипеді. З цієї причини його можна використовувати, наприклад, для кількох ітерацій, щоб відійти від основного рішення, перш ніж повернутися до інших методів відбору.
Той, який запропонував Пола Гарріс у 1973 році Тест коефіцієнта Харріса, що є однією із стандартних процедур сьогодні, дозволяє нове рішення бути злегка неприпустимим з міркувань чисельної стабільності.

Змінні межі

Подвійний симплексний метод

В ході методів різання площини або методів розгалуження і різання дуже часто змінюється межа змінної в ЛП, яка щойно була вирішена, або додається нерівність, яка не задовольняється старим рішенням, і ЛП потім вирішується знову. Оскільки старе базове рішення вже неприпустиме, була порушена одна з основних умов таблиці первинного симплексу, тому метод первинного симплексу повинен бути запущений з самого початку, щоб вирішити новий LP. Якщо в цільовій функції нічого не було змінено, старе подвійне рішення все ще є допустимим, так що за кілька подвійних симплексних кроків від старої початкової основи, оптимальне рішення для модифікованого LP зазвичай знаходить через кілька ітерацій. У великих пластинках ця різниця часто дуже чітко відображається на загальному часу роботи.
Якщо в процесі роботи алгоритму виникають числові труднощі або дуже довго не відбувається прогрес у цільовій функції, може бути корисним тимчасово дозволити незначне порушення змінних меж, щоб переміститися з критичного кута багатогранника. Потім це можна виправити кількома подвійними симплексними кроками.
Якщо лінійна програма має певні структури, ви можете безпосередньо вказати первинно недопустимий, але подвійно допустимий пусковий базис, не потрібно його обчислювати. У такому випадку ви можете розпочати фазу II з подвійних симплексних кроків безпосередньо з цієї бази, і ви можете зберегти себе фазу I.

Переглянутий симплексний метод

Розкладання LR

Попередня обробка

Якщо рядок лінійно залежить від інших рядків, він є зайвим і може бути видалений. Однак, крім особливого випадку, коли лінія є скалярним кратним іншій лінії, це, як правило, важко розпізнати з розумними зусиллями.
Дуже часто змінні обмежуються певним діапазоном значень через умови або задані іншими змінними. Наприклад, рівняння x 1 + x 2 = 1 x_ + x_ = 1 x 1 + x 2 = 1 та умови невід'ємності обмежують обидві змінні діапазоном [0, 1] [0,1] [0, 1] . Знання цієї межі може прискорити процес вирішення проблеми. Крім того, значення x 2 x_ x 2 визначається значенням x 1 x_ x 1. Це означає, що в усіх умовах, при яких виникає x 2 x_ x 2, цю змінну можна замінити на 1 - x 1 1 - x_ 1 - x 1 і x 2 x_ x 2 можна видалити з LP.
Якщо до певного діапазону значень було зафіксовано кілька змінних, можливо, деякі нерівності завжди виконуються або вже не можуть бути виконані. У першому випадку нерівність можна усунути, у другому випадку негайно виявляється неприпустимість ЛП і можна зупинити.

тривалість роботи

історія

Бог створив цілі числа, все інше - людська робота.