Математическая формулировка задач линейного программирования.

Пусть задана линейная форма R=C₁X₁+C₂X₂+C_nX_n=∑C_nX_n (1) и ограничения

a₁₁x₁+a₂₂x₂+a_1nx_n-b₁≥0

a₂₁x₁+a₂₂x₂+a_2nx_n-b₂≥0 (2)-может содержать как равенства, так и неравенства

a_m1x₁+a₂₂x₂+a_mnx_n-b_m≥0

Задача формулируется вербально: требуется среди всех неотрицательных решений системы (2) найти такое, при котором линейная форма (1) принимает наименьшее значение.

Утверждение: ограничение задачи (2) можно выразить как в форме равенств, так и неравенств

1) Пусть ограничения заданы в виде неравенств, покажем, что можно перейти к задаче с ограничениями в виде уравнений. Рассмотрим любое из неравенств:

a_k1x₁+a_k2x₂+a_knx_n-b₁≥0

Для того, чтобы сделать неравенство в равенство, необходимо уменьшить левую часть неравенства

a_k1x₁+a_k2x₂+a_knx_n-x_n+k=b_k

т.к по условию задачи Х_n+k≥0 то оно вводится со знаком «-». Такие дополнительные переменные можно ввести во все неравенства системы и система (2) будет представлять собой систему уравнений, однако веденные дополнительные переменные увеличат размерность на число введенных переменных. В решении задач оптимизации эти дополнительные переменные выступают как вспомогательные.

2) Пусть ограничения заданы в виде равенств – покажем, что от равенств можно перейти к системе ограничений в виде неравенств:

a_knx₁+a_k2x₂+a_knx_n=b_k

R=C₁X₁+C₂X₂+C_nX_n при m<n, k=1, m

Рассматривается когда система (1) совместна, т.е. ранг матрицы коэффициентов системы = рангу рассматриваемой матрицы rangA=r; r-переменных можно взять в качестве базисных и выразить через остальные(n-r), которые называются свободными

(3)

В линейную (2) поставляем (3) и следующее уравнение:

R=C'₀+C'_r+1X_r+1+C'_nX_n

т.к в условии (3) все переменные положительны, то все Х_i≥0 положительные.

(5)

Система (5) с линейной формой 4 позволяет эквивалентно записать задачу (1), (2).