Общая постановка задачиЛинейное программирование — наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения. Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.
Определение. Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи. В общем виде математическая модель задачи линейного программирования (ЛП) записывается как
при ограничениях:
где Xi — неизвестные;a ij, bj, Ci — заданные постоянные величины.
Все или некоторые уравнения системы ограничений могут быть записаны в виде неравенств. Математическая модель в более краткой записи имеет вид
Z(x) = ∑Ci Xi max(min) при ограничениях:
Определение Допустимым решением (планом) задачи линейного программирования называется вектор X = (х1, х2,,...хn,), удовлетворяющий системе ограничений.
Множество допустимых решений образует область допустимых решений (ОДР).
Определение Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным решением задачи линейного программирования и обозначается Хопт. Базисное допустимое решение
Является опорным решением, где r — ранг системы ограничений.
|
Z(x)=C1X1+C2X2 + . .. +СJXJ + ... +СnXn _ max(min)
