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

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

(2.4)

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

(2.6)

(2.5)

где – заданные постоянные величины.

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

ЗЛП в каноническом виде:

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

Любую ЗЛП можно привести к каноническому виду посредством введения в левую часть дополнительной переменной со знаком “ – “ в случае ограничения типа “ “ и со знаком “ + ”в случае ограничения типа “ “.Если на переменную x_p не накладывается условие неотрицательности, то делают замену:

x_p= x_p¹– x_p², x_p¹ 0; x_p² 0.

Пример 2.2

max f (x₁,x₂)=x₁+2x₂, max f (x₁, x₂¹, x₃, x₄)=x₁+2x₁¹–2x₂²,

2x₁+3x₂ 10, 2x₁+3x₂¹–3x₂²+x₃=10,

2x₁+x₂=6, 2x₁+x₂¹–x₂²=6,

x₁+x₂ 2, x₁+x₂¹-x₂²-x₄=2,

x₁ 0. x₁ 0, x₂¹ 0, x₂² 0, x₃ 0, x₄ 0.

Каноническая ЗЛП в векторной форме:

A₁x₁+A₂x₂+...+A_nx_n=B

x_j 0,

где С=(с₁,с₂,…,с_n), X=(x₁,x₂,...,x_n) – вектор-строки;

CX – скалярное произведение векторов С и X;

A_j и B – вектор – столбцы:

Каноническая ЗЛП в матричной форме:

AX=B, x 0,

где C=(c₁,c₂, ..., c_n) – вектор-строка;

A = (a_ij)_m_*_n – матрица размерности m*n, столбцами которой являются вектор-столбцы A_j.

– вектор-столбцы

Стандартная форма записи ЗЛП:

AX ( ) B, x 0.

Каноническая и стандартная ЗЛП сводятся одна к другой.

Пример 2.3. Пусть собственные средства банка в сумме с депозитами составляют 100 млн. руб. Эти средства банк может разместить в кредиты по ставке r₁ и в государственные ценные бумаги по ставке r₂ . Т.к. кредиты менее ликвидны по сравнению с ценными бумагами, то обычно r₁>r₂ . Банк обязан не менее 35% от суммы в 100 млн. руб. разместить в кредитах. Ликвидное ограничение состоит в том, что ценные бумаги должны составлять не менее 30% средств, размещенных в кредитах и ценных бумагах. Определить такое размещение средств в кредиты, при котором прибыль банка будет максимальной.

Обозначим x₁,x₂ – средства (млн. руб.), размещенные в кредитах и ценных бумагах соответственно. Тогда ЗЛП в общем виде будет иметь вид:

при условиях

x₁ 0, x₂ 0.

ЗЛП в каноническом виде:

,

x₁ 0, x₂ 0, x₃ 0, x₄ 0, x₅ 0.

ЗЛП в векторной форме:

A₁x₁+A₂x₂+A₃x₃+A₄x₄+A₅x₅=B,

x_j 0, ,

где C=(r₁, r₂, 0, 0, 0), X=(x₁, x₂, x₃, x₄, x_n).

ЗЛП в матричной форме:

AX = B, X 0.

где С=(r₁, r₂, 0, 0, 0),

ЗЛП в стандартной форме совпадает с общей формой записи.