Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Лінійне програмування




Лінійне програмування – це математичний апарат, що дозволяє вирішувати задачі оптимізації, в яких критерій оптимальності є лінійною функцією кількох змінних, а область їх зміни визначається сукупністю лінійних виразів.

Кожній задачі лінійного програмування може бути поставлена у відповідність двоїста їй задача. Центральним фактом в лінійному програмуванні є теорема подвійності, що встановлює рівність оптимальних значень цільових функцій прямої та двоїстої задач. Зазначимо, що кожній задачі лінійного програмування відповідає інша задача, яка називається двоїстою по відношенню до вихідної. Рішення двоїстої задачі може виявитися легше рішення вихідної задачі і бути корисним при вирішенні прямої задачі, а також може бути використано при розробці різних алгоритмів.

Багато задач лінійного програмування можуть бути вирішені за допомогою практично універсального алгоритму – симплексного методу, який дозволяє за скінченне число кроків знаходити оптимальне рішення. При цьому наявність у вихідній постановці різних комбінацій обмежень (рівності або нерівностей) і їх числа не позначається на можливостях застосування алгоритму, оскільки можливі еквівалентні перетворення, що дозволяють звести вихідну задачу до потрібного вигляду.

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






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных