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

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

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

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

так, чтобы
,
и
.