Задача линейного программирования
В общем случае задача линейного программирования записывается так, что ограничениями являются как уравнения, так и неравенства, а переменные могут быть как неотрицательными, так и произвольно изменяющимися. В случае, когда все ограничения являются уравнениями и все переменные удовлетворяют условию неотрицательности, задачу линейного программирования называют канонической. Каноническая задача линейного программирования в координатной форме записи имеет вид:
Используя знак суммирования эту задачу можно записать следующим образом:
Каноническая задача линейного программирования в векторной форме имеет вид:
В данном случае введены векторы
,
, ,
Здесь – скалярное произведение векторов и .
Каноническая задача линейного программирования в матричной форме записи имеет вид
где
, .
Здесь – матрица коэффициентов системы уравнений,
– матрица-столбец переменных задачи; – матрица-столбец правых частей системы ограничений.
|
|
Нередко используются задачи линейного программирования, называемые симметричными, которые в матричной форме записи имеют вид:
или
В большинстве методов решения задач линейного программирования предполагается, что система ограничений состоит из уравнений и естественных условий неотрицательности переменных. Однако, при составлении математических моделей экономических задач ограничения в основном формулируются системы неравенств, поэтому возникает необходимость перехода от системы неравенств к системе уравнений. Это может быть сделано следующим образом. К левой части линейного неравенства
прибавляется величина , такая, что переводит неравенство в равенство ,
где
.
Неотрицательная переменная называется дополнительнойпеременной.
Основания для возможности такого преобразования дает следующая теорема.