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

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

Линейное программирование рассматривает задачи с линейной математической моделью. Это задачи, в которых требуется найти такие значения переменных x₁, x₂,..., x_n, при которых некоторая линейная функция от этих переменных принимает максимальное или минимальное значение:

F = c₁·x₁ + c₂·x₂ +... + c_n·x_n → max / min (1)

при выполнении ограничений на переменные x₁, x₂,..., x_n, заданных линейными уравнениями или неравенствами:

a11·x1	+	a12·x2	+...+	a1n·xn	≤ b1
a21·x1	+	a22·x2	+...+	a2n·xn	≤ b2
………………	…
ap1·x1	+	ap2·x2	+...+	apn·xn	≤ bp (2)
a(p+1)1·x1	+	a(p+1)2·x2	+...+	a(p+1)n·xn	= bp+1
a(p+2)1·x1	+	a(p+2)2·x2	+...+	a(p+2)n·xn	= bp+2
...					(3)
am1·x1	+	am2·x2	+…+	amn·xn	= bm
,			….		(4)

Здесь p – количество ограничений, имеющих вид “не больше”, m-p – количество ограничений “равно”, m – общее количество ограничений.

Функция (1) называется целевой функцией или критерием оптимальности, а ограничения (2) – системой ограничений задачи.

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

(4) – ограничения на неизвестные

Если ЗЛП включает в себя ограничения только вида «=» (3), то такая задача называется канонической, если ЗЛП включает в себя ограничения только вида «< =», то такая задача называется симметричной. Любое ограничение ЗЛП вида «< =» преобразуется в равенство добавлением к его левой части дополнительной неотрицательной переменной, а неравенства вида «> =» - вычитанием из его левой части дополнительной неотрицательной переменной.

Например, неравенства

,

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

, ,

а неравенства

,

после вычитания дополнительных неизвестных преобразуются в равенства вида

, .

Неравенство вида «> =» преобразуется в неравенство вида «< =» домножением левой и правой частей данного неравенства на (-1).

Если по условию задачи требуется найти такие значения переменных x₁, x₂,..., x_n, при которых целевая функция (1.1) будет иметь максимальное значение, то говорят, что целевая функция подлежит максимизации (или направлена на максимум). Если требуется, чтобы целевая функция принимала минимальное значение, то говорят, что она подлежит минимизации (направлена на минимум).

В большинстве задач (но не всегда) требуется, чтобы переменные x₁, x₂,..., x_n принимали неотрицательные значения (ограничение на неотрицательность): x_j≥ 0, j=1,..., n. В некоторых задачах требуется, чтобы переменные принимали целочисленные значения (ограничение на целочисленность).

Линейная математическая модель может быть построена для многих задач, решаемых на практике.

Любые значения переменных x₁, x₂,..., x_n, удовлетворяющие ограничениям задачи (1.2), называются допустимыми решениями (независимо от того, какое значение при этом принимает целевая функция). Большинство задач имеет бесконечно много допустимых решений. Все множество допустимых решений представляет собой область допустимых решений (ОДР).

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