Целью линейного программирования является отыскание оптимума (максимума или минимума) заданной линейной функции при наличии ограничений в виде линейных уравнений или линейных неравенств.
Землеустроительные задачи, решаемые методами линейного программирования должны удовлетворять следующим требованиям:
1. быть многовариантными, то есть их решение не должно быть однозначным;
2. иметь определённую целевую установку, связанную с поиском экстремального значения математической функции, выражающей цель задачи:
3. содержать определённые ограничения, которые должны лимитировать условие задачи.
Математическая формулировка задачи линейного программирования заключается в следующем. Устанавливается перечень искомых величин х1, х2….хп. которые могут принимать различные численные значения. На эти неизвестные налагаются определённые условия, образующие так называемую систему ограничений. Ограничениями служат уравнения или неравенства, построенные в соответствии с логическим содержанием задачи. Они могут иметь только линейный вид:
(4.1)
также могут содержать и нелинейные выражения, а также быть смешенными.
Затем составляется некоторая функция тех же искомых величин выражающая фактор, принимаемый в качестве критерия (доход, издержки, себестоимость). Такая функция называется целевой, а её вид и параметры зависят от конкретных условий и в общем виде будет выглядеть:
Решение X = (x1, х2,...,хп), при котором функция F обращается в оптимум (минимум или максимум), называется оптимальным решением.
В задачах линейного программирования коэффициенты заданные постоянные величины, а число уравнений меньше числа переменных, т.е. т<п.
Без ограничения общности можно считать, что все правые части системы (4.1) неотрицательны, т. е. . Если в некоторых уравнениях системы (4.1) это условие нарушено, то можно умножить обе части таких уравнений на - 1.
Задача линейного программирования, система ограничений которой задана в виде системы уравнений (4.1), носит название канонической.