28.4. Векторно-матричная форма задачи линейного программирования.

Задачу линейного программирования можно сформулировать также в векторно-матричной форме. Пусть  - векторы пространства ;  - вектор из пространства ;

 - матрица размера , составленная из коэффициентов системы ограничений (4). Линейная функция  есть скалярное произведение векторов  и .

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

Примем столбцы матрицы  за векторы из :

.

Тогда легко получаем, что

Поэтому систему ограничений можно записать в виде

Если ранг , то среди векторов  имеется  линейно независимых, которые можно принять за базис в пространстве  (см. § 16). Следовательно, любой вектор  может быть разложен по элементам этого базиса. Нам необходимо выбрать такой базис, чтобы вектор  разлагался по векторам этого базиса с неотрицательными коэффициентами .

Различных  - мерных базисов  из векторов  конечное число. Среди них могут быть базисы, по элементам которых вектор  разлагается с неотрицательными коэффициентами. Тогда минимум скалярного произведения (линейной функции) достигается на конечном множестве точек , где  - коэффициенты разложения вектора  по элементам некоторых базисов.

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

Таким образом, задача состоит в том, как найти базис

так, чтобы

,

и

.