Линейное программирование, Симплекс - метод - Методики решения задач линейного и нелинейного программирования

Основная задача линейного программирования:

Найти неотрицательное решение системы ограничений обеспечивающее максимум (минимум) целевой функции.

Чтобы решить задачу линейного программирования необходимо привести ее к каноническому виду.

Теоремы линейного программирования:

Теорема 1. Множество допустимых решений основной задачи линейного программирования выпукло.

Теорема 2. Линейная функция задачи линейного программирования достигает своего экстремального значения в крайней точке множества решений.

При решении системы ограничений могут возникнуть следующие случаи:

    1) Система ограничений несовместна, поэтому отыскать оптимальное решение невозможно. 2) Система ограничений имеет единственное решение. 3) Система ограничений имеет конечное число решений (имеется замкнутая область допустимых решений). Оптимальное решение отыскивается среди решений, принадлежащих данной области. 4) Система ограничений имеет бесчисленное множество решений.
Симплекс - метод

Минимум неотрицательный линейный симплекс

Решение задачи линейного программирования включает в себя 3 этапа:

    1) Отыскание базисного решения - некой точки А лежащей на функции. 2) Отыскание опорного решения - некой точки B принадлежащей области, образованной ограничениями. 3) Отыскание оптимального решения - некой точки С (рис. 2) принадлежащей той - же области, и в которой целевая функция достигает своего экстремума.

Отыскание оптимального решения с использованием симплекс - метода сводится к последовательному направленному перебору вершин многогранника, образованного ограничениями при котором монотонно увеличивается (уменьшается) значение целевой функции.

Похожие статьи




Линейное программирование, Симплекс - метод - Методики решения задач линейного и нелинейного программирования

Предыдущая | Следующая