Общая постановка задачи линейного программирования

Линейное программирование

Задачей линейного программированияназывается задача исследования операций, математическая модель которой имеет вид:

_n

f(X) =∑(c_j∙x_j)→ max(min); (7.1)

_n ^{j = 1}

∑(a_ij∙x_j) =b_i, iОI, IОM= {1, 2,…,m}; (7.2)

^{j = 1}

_n

∑(a_ij∙x_j) ≤b_i,iОM; (7.3)

^{j = 1}

x_j≥ 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) = ∑(c_j∙x_j)→ min; (7.5)

^{j = 1}

_n

∑(a_ij∙x_j) =b_i, i= 1,…, m; (7.6)

^{j = 1}

b_i≥ 0; x_j ≥ 0, j= 1,…, n, (7.7)

то говорят, что задача представлена в канонической форме. Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого нужно уметь:

сводить задачу максимизации к задаче минимизации;

переходить от ограничений в виде неравенств к ограничениям в виде равенств;

заменять переменные, которые не подчиняются условию неотрицательности.

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

если в ограничениях правая часть отрицательна, то следует умножить это ограничение на «-1»;

если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

если некоторая переменная x_k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:

x_k=x^'_k-x_r, где r - свободный индекс, x^'_k≥ 0, x ≥ 0.

В общем случае процесс построение модели линейного программирования строится путем нахождения ответов на следующие вопросы:

для определения каких величин должна быть построена модель, то есть, как понимать переменные данной задачи?

какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?

в чем состоит цель задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?

Полученные ответы остается только связать с переменными и сформировать из переменных выражения для целевой функции и системы ограничений. Что касается моделирования, то в простейших случаях оно возможно с помощью «ручного счета» или графических решений, а в большинстве случаев - с помощью специального программного обеспечения и ЭВМ. В последнем случае программное обеспечение, как правило, требует, чтобы модель (задача) была представлена ("введена" в ЭВМ) в канонической форме.