Задача линейного программирования (стандартная, каноническая и общая) и ее геометрическая интерпретация
Задачи Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида[3]:
Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)
Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений с ограничениями в форме равенства[4]:
Основную задачу можно свести к канонической путём введения дополнительных переменных. Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств[5]. Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты
|
,
.
,
с обратным знаком.
