Матричная форма записи

Если задача линейного программирования приведена к стандартной или канонической форме, ее удобно кратко записать в матричной форме. С этой целью вводятся следующие обозначения:

С = (с₁, с₂,..., с_j,..., с_n) – вектор-строка коэффициентов целевой функции,

B = - вектор-столбец свободных членов (правых частей ограничений),

X = - вектор-столбец переменных,

A = - матрица коэффициентов в левых частях ограничений (каждая ее строка соответствует ограничению, а каждый столбец – переменной).

Тогда задача линейного программирования в канонической форме запишется следующим образом:

Задача в стандартной форме будет иметь вид:

или .

В самом деле, по правилам перемножения векторов СХ = с₁х₁ + с₂х₂ + … + с_nх_n = . Это и есть линейное выражение в целевой функции.

Умножая матрицу А размерности (m x n) на вектор Х (n x 1), получают столбец из m выражений, т.е. матрицу (m x 1). Каждое их этих выражений получают умножением строки матрицы А на столбец Х, т.е. а_i1х₁ + а_i2х₂ + … + а_i1х_n = . Тогда АХ представляет собой столбец выражений в левых частях ограничений: АХ = . Благодаря тому, что во всех ограничениях стоит один и тот же знак, этот столбец можно сравнить со столбцом В. Тогда запись АХ = В представляет собой систему уравнений в ограничениях задачи в канонической форме (АХ ³ В или АХ £ В – соответственно системы неравенств в задачах в стандартной форме).

Отметим, что О в формулах (10) и (11) представляет собой не одно число, а нулевой вектор (столбец из n нулей), поскольку каждая из n переменных сравнивается с нулем.