Методы линейного программирования

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

при ограничениях

; ; ; ,

где i=1,2,…m₁; k=1,2,…m₂; l=1,2,…m₃. Например, a₁₁x₁+a₃x₂≤b₁₂ или x₂≥b₁₂ и т.д.

Математическая модель линейного программирования (линейной оптимизации) может быть изобра­жена в графическом виде. В этом случае каждое огра­ничение представляется граничной прямой, которая определяет область, где возможно существование решений системы неравенств. Например, на рисунке штриховка возле линий показывает, с какой стороны от линии существует решение для данного ограничения. Граничные прямые, пересекаясь, образуют многоуголь­ник ОДР (область допустимых решений), внутри которого любая точка удовлетворяет всем без исключения ограничениям. Поэтому этот многоугольник принято называть многоугольником решений:

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