Общая линейная экономико-математическая модель экономических процессов и явлений - так называемая общая задача линейного программирования подается в виде:
(1)
при условиях:
(2)
(3.3)
Где нужно найти значение переменных x 1, x 2, …, xn, которые удовлетворяют условиям (2) и (3), и целевая функция (1) приобретает экстремальный (максимальное или минимальное) значение.
Для общей задачи линейного программирования используются такие понятия.
Вектор Х = (х 1, х 2, …, хn), координаты которого удовлетворяют системе ограничений (2) и условия неотрицательности переменных (3), называется допустимым решением (планом) задачи линейного программирования.
Допустимый план Х = (х 1, х 2, …, хn) называется опорным планом задачи линейного программирования, если он удовлетворяет не менее, чем m линейно независимых ограничений системы (2) в виде равенств, а также ограничению (3) относительно неотрицательности переменных.
Опорный план Х = (х 1, х 2, …, хn), называется невырожденным, если он содержит точно m положительных переменных, иначе он вырожденный.
Опорный план , при котором целевая функция (1) достигает максимального (минимального ли) значение, называется оптимальным решением (планом) задачи линейного программирования.
Задачу (1)—(3) можно легко свести к канонической форме, т.е. к такому виду, когда в системе ограничений (2) все bi (i = 1, 2, …, m) неотрицательные, а все ограничения являются равенствами.
Если какое-то bi отрицательное, то, умножив i- тое ограничение на (– 1), получим в правой части соответствующее положительное значение. Когда i - тое ограничение имеет вид неравенства аi 1 х 1+ аi 2 х 2+…+ аinxn ≤ bi, то последнюю всегда можно свести к равенству, введя дополнительнуюпеременную xn +1:
ai 1 x 1+ ai 2 x 2+…+ ainxn+xn +1= bi...
Аналогично ограничение вида аk 1 x 1 + ak 2 x 2 + … + aknxn ≥ bk сводят к равенству, вычитая из левой части дополнительную переменную хn +2, т.е.:
ak 1 x 1 + ak 2 x 2 + … + aknxn – xn + 2 = bk (хn +1 ≥ 0, хn +2 ≥ 0).