Каноническая форма задачи линейного программирования

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

1) критерием оптимальности является максимум целевой функции; в случае необходимости переход к задаче на максимум достигается изменением знака целевой функции;

2) функциональное ограничение задачи имеют вид равенств с неотрицательными правыми частями. Переход к равенствам осуществляется через введение в левые части ограничений неотрицательных дополнительных переменных со знаком (+) в случае неравенства вида ≤ и со знаком (-) в случае неравенства вида ≥. Дополнительные переменные включаются в целевую функцию с нулевыми коэффициентами;

3) все переменные неотрицательны; если на некоторую переменную x_j по экономическому смыслу не наложено условие неотрицательности, то делается замена переменных.