Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти пионерские работы была присуждена Нобелевская премия по экономике. Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.
В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решений, в том числе и в финансовой математике. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов. В развитие и совершенствование этих систем вложен труд и талант многих матеметиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики.
С формально-математической точки зрения задача линейного программирования может быть описана следующим образом: найти неизвестные величины $x_1, x_2, ..., x_n$ доставляющие
$\min \sum_{j=1}^{n} c_j x_j$
при условии выполнения системы неравенств
$\sum_{j=1}^{n} a_ij x_j \leq b_i, i=1,2,...,n$ (*)
или в векторно матричной нотации:
$\displaystyle{\min_{Ax \leq b} cx}$
Некоторая терминология:
$x=\{x_j, j=1,2,...,n \}$ - переменные задачи, которые иногда называют активностями или планом.
$c=\{ c_j, j=1,2,...,n \}$ - вектор коэффициентов целевой функции или стоимости.
$cx=\sum_{j=1}^{n} c_j x_j$ - целевая функция
$A=\vert a_{ij} , i=1,2,...,m; j=1,2,...,n \vert$ - матрица коэффициентов системы ограничений с строками и столбцами.
$b=\{ b_i, i=1,2,...,m \}$ - правая часть системы ограничений или вектор правых частей.
$Ax \leq b$- общие ограничения задачи.
Множество точек x, удовлетворяющих ограничениям (*), называется допустимым множеством. Задача с непустым допустимым множеством называется допустимой, а в противном случае - недопустимой.
Недопустимые задачи возникают обычно в результате ошибочных формулировок задач или при ошибках в подготовке данных. Поиск причин возникновения недопустимости в больших моделях линейного программирования предсталяет собой весьма сложную проблему и для его облегчения разрабатывается специальное программное обеспечение.
В практических задачах ограничения могут иметь различный характер: равенства, неравенства различных знаков и тому подобное. С теоретической точки зрения все эти постановки могут быть сведены, конечно, к неравенствам одного знака, как это записано выше. Однако для унификации теории задачу линейного программирования с помощью простых приемов сводят к специальной постановке, содержащей ограничения двух видов: равенств общего вида
$Ax = b$
и условий неотрицательности переменных
$x \geq 0$
Подробнее это сведение будет рассмотрено ниже.
