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

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

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

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

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

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