Главная » Справочник » Основы организации и управления транспортными системами » Общая задача линейного программирования

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

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

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

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

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

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

Если система ограничений задачи линейного программирования задана уравнениями, то к канонической форме она приводится путем введения в каждое уравнение так называемых искусственных переменных, которые и составят базис системы.

Интересно

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

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

Предыдущая статья Область применения методов сетевого планирования и управления Следующая статья Опасные свойства грузов

Статьи по теме