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

Эти методы используются для решения однокритериальных задач оптимизации, целевая функция которых отвечает условиям детерминированности и линейности, а на значения переменных накладываются линейные ограничения. Линейность предполагает наличие двух свойств: пропорциональности и аддитивности. Пропорциональность означает, что вклад каждой

переменной в целевую функцию прямо пропорционален величине этой переменной, а аддитивность заключается в представлении целевой функции в виде суммы вкладов от различных переменных.

К особенностям использования данных методов относится то, что оптимальному решению всегда соответствует одна из экстремальных точек пространства решений (это является следствием такого важного свойства задач линейного программирования, как выпуклость пространства решений).

Поэтому вычислительная схема представляет собой упорядоченный процесс перехода от исходной экстремальной точки к некоторой смежной экстремальной точке, продолжающийся до тех пор, пока существуют точки с лучшим (большим или меньшим) значением целевой функции.

Основным методом решения задач линейного программирования является симплекс-метод и его модификации, ориентированные на особенности решаемых задач (см. [6.9; 6.55; 6.57]).