Основные формы записи задачи линейного программирования

Общей задачей линейного программирования (ОЗЛП) называют задачу

(9.2.10)

при ограничениях:

, (9.2.11)

, (9.2.12)

, (9.2.13)

, (9.2.14)

x_j — произвольные , (9.2.15)

где c_j, A_ij, b_i — заданные действительные числа;

(9.2.10) — целевая функция;

(9.2.11) — (9.2.15) — ограничения;

x = (x ₁,..., x_n) — план задачи.

Задачу линейного программирования можно представить в 3-х различных видах: развернутом, матричном и векторном.

Приведенная выше ОЗЛП записана в развернутой или индексной форме.

В этой же форме задачу можно представить и несколько иначе:

(9.2.16)

при линейных ограничениях:

(9.2.17)

, (9.2.18)

x_j — произвольные ,

здесь c_j , A_ij , b_i — заданные действительные числа;

(9.2.16) ¾ целевая функция;

(9.2.17) — ограничения;

(9.2.18) — условие неотрицательности части переменных;

x = (x ₁,..., x_n) — план задачи.

Рассмотрим теперь матричную форму записи ЗЛП.

Введем следующие обозначения:

где

C — матрица-строка;

A — матрица системы уравнений;

X — матрица-столбец переменных;

A ₀ — матрица-столбец свободных членов.

Тогда наша задача примет вид:

; (9.2.19)

, X ³ 0 (9.2.20)

или

mаx(min) Z = CX, AX {£,=,³} A ₀, X ³ 0. (9.2.21)

Полезной является также векторная форма ЗЛП.

Для столбцов матрицы A введ е м обозначения:

, ,..., ,..., .

Тогда задача (9.2.10)—(9.2.15) в векторной форме записи примет вид:

mаx (min) Z = CX; (9.2.22)

A ₁ x ₁ +... + A _jx_j + A _nx_n = A ₀, X ³ 0, (9.2.23)

где CX ¾ скалярное произведение векторов C =(c ₁;...; c_n) и X =(x ₁,..., x_n).

Не умоляя общности, можно считать, что в системе (9.2.10)-(9.2.15) первые k ограничений являются неравенствами, а последующие – m - уравнениями.

Относительно направления знака неравенства будем предполагать, что левая часть ³ правой, что всегда можно добиться умножая обе части на –1.

Тип экстремума (max / min) – носит относительный характер (аналогично).

Задача ЛП (9.2.10)–(9.2.15) - общая задача линейного программирования (ОЗЛП).

Если все ограничения – уравнения, а все Xi – неотрицательны то

- это каноническая задача линейного программирования(КЗЛП).