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

Пусть задана линейная форма 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).

15. Графическое представление задачи лп.

Любое неотрицательное решение системы ограничений называется допустимым. Допустимое решение, доставляющее min (max) в линейной форме, называется оптимальным. Совокупность всех допустимых решений системы ограничений называется областью решений.

Рассмотрим систему ограничений в виде равенств

Допустим, что существует решение системы (1), т.е. система линейных уравнений совместна

rangA=rangB

rangA=n-система (1) имеет единственное решение

rangA<n-бесконечно большое число решений

col(x₁ x₂…x_n)=x-единственное решение

Во втором случае каждое решение системы ограничений в пространстве с системой координат определяет некоторую гиперплоскость. Появляется возможность среди множества решений подбора таких значений как

,

которые дают экстремальное значение R.

Проиллюстрируем сказанное на примере 2-х переменных R=х₁+х₂ и задана система ограничений типа неравенств

2 х₁+ х₂≤1

х₁+2 х₂≤1 (4)

Неравенство (4) на плоскости х₁ и х₂ будут определять ограниченную область рис 15.1

X^opt=argmaxR(), 2 х₁+ х₂≤1, х₁+2 х₂≤1

Требования (свойства) к области допустимых решений:

1.Область должна быть выпуклой

Для многогранной области это будет равносильно тому, что вся область лежит по одну сторону от гиперплоскости, проходящей через грань области. Критерий оптимальности в виде линейной формы (3) определяет на плоскости некоторую прямую. R м.б. достигнуто либо в одной точке и эта точка является вершиной области, либо в бесчисленном множестве точек и это геометрическое место есть гиперплоскость, ограничивающая эту область.