Задачей линейного программированияназывается задача исследования операций, математическая модель которой имеет вид:
n
f(X) =∑(cj∙xj)→ max(min); (7.1)
n j = 1
∑(aij∙xj) =bi, iОI, IОM= {1, 2,…,m}; (7.2)
j = 1
n
∑(aij∙xj) ≤bi,iОM; (7.3)
j = 1
xj≥ 0, jОJ, JОN= {1, 2,…,n}. (7.4)
При этом система линейный уравнений (7.2) и неравенств (7.3) и (7.4), определяющая допустимое множество решений задачи (7.1), называется системой ограничений задачи линейного программирования, а линейная функция f(X) называется целевой функцией или критерием оптимальности. В частном случае, если I = Ж, то система (7.2) и (7.3) состоит только из линейных неравенств, а если I=M, то - из линейных уравнений.
Если математическая модель задачи линейного программирования имеет вид:
n
f(X) = ∑(cj∙xj)→ min; (7.5)
j = 1
n
∑(aij∙xj) =bi, i= 1,…, m; (7.6)
j = 1
bi≥ 0; xj ≥ 0, j= 1,…, n, (7.7)
то говорят, что задача представлена в канонической форме. Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого нужно уметь:
сводить задачу максимизации к задаче минимизации;
переходить от ограничений в виде неравенств к ограничениям в виде равенств;
заменять переменные, которые не подчиняются условию неотрицательности.
Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:
если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
если в ограничениях правая часть отрицательна, то следует умножить это ограничение на «-1»;
если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
если некоторая переменная xk не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:
xk=x'k-xr, где r - свободный индекс, x'k≥ 0, x ≥ 0.
В общем случае процесс построение модели линейного программирования строится путем нахождения ответов на следующие вопросы:
для определения каких величин должна быть построена модель, то есть, как понимать переменные данной задачи?
какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?
в чем состоит цель задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?
Полученные ответы остается только связать с переменными и сформировать из переменных выражения для целевой функции и системы ограничений. Что касается моделирования, то в простейших случаях оно возможно с помощью «ручного счета» или графических решений, а в большинстве случаев - с помощью специального программного обеспечения и ЭВМ. В последнем случае программное обеспечение, как правило, требует, чтобы модель (задача) была представлена ("введена" в ЭВМ) в канонической форме.