4.4. Основная задача линейного программирования. Развернутая и сокращенная формы записи задач линейного программирования в общих символах

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

Дана система из m линейных уравнений с n неизвестными:

a₁₁ x₁ + a₁₂ x₂ +…+a_1j x_j +…+a_1n x_n = b₁, (1)

a₂₁ x₁ + a₂₂ x₂ +…+ a_2j x_j +…+a_2n x_n = b_2,

_{…………………………………………………………………….}

a_i1 x₁ + a_i2 x₂ +…+a_ij x_j +…+a_in x_n = b₃,

…………………………………………

a_m1 x₁ + a_m2 x₂ +…+ a_mj x_j +…+ a_mn x_n =b_m,

и некоторая линейная функция:

Z=c₁ x₁ + c₂ x₂ +…+ c_j x_j +…+ c_n x_n, (2)

Требуется найти такое неотрицательное решение системы (1), (значения переменных x₁0, x₂0,…,x_n0), которое бы обращало линейную функцию (2) в максимум или минимум.

Приведенная выше запись задачи является развернутой формой в общих символах, при числе ограничений m и неизвестных n. В краткой, компактной форме это можно записать так:

max (min) Z =  c_j x_j, (3),

∑a_ij x_j = b_i (4),

X_j0, mn. (j=1,n; i=1,m) (5).

Условия (1) и (4) основной задачи называют основными ограничениями.

Для экономических систем условие неотрицательности неизвестных (5) представляется естественным, поскольку неизвестные являются реальными вещественными характеристиками.

Сформулированная задача (1), (2) или (3), (4), (5) получила свое название- основная задача линейного программирования в связи с тем, что для этой формы линейной задачи разработаны методы решения, в частности, симплексный (или метод последовательного улучшения плана).

4.5. Классификация задач линейного программирования по типу ограничений: канонического, симметричного и общего вида

В зависимости от типа ограничений, входящих в задачу, ее можно отнести к задачам линейного программирования канонического вида, когда ограничения представлены уравнениями. Задачу с однотипными ограничениями неравенствами называют симметричной: все ограничения  или все ограничения , например:

max Z =  c_j x_j, или max Z =  c_j x_j,

a_ij x_j  b_i, a_ij x_j  b_i,

x_j  0, (j=1.. n), x_j  0 (j=1.. n),

(j=1..n, i=1..m), (j=1..n, i=1..m),

m  n. m  n.

Задача называется общей задачей линейного программирования, если все функции в выражениях (1), (2) линейны, а ограничения разнотипные.

Общая задача линейного программирования легко приводится к основной, и, наоборот, с помощью дополнительных переменных х_доп., вводимых в левые части ограничений с коэффициентом +1, если неравенство  , и -1 – если  . Например, общая задача

max Z=c₁ x₁+c₂ x₂+…+c_n x_n,

a₁₁ x₁+a₁₂ x₂+ ... +a_1n x_n=b₁,

a₂₁ x₁+a₂₂ x₂+…+a_2n x_n  b₂, (6)

a₃₁ x₁+a₃₂ x₂+…+a_3n x_n  b₃,

x_j  0 (j=1, n).

приводится к основной при введении в левые части второго и третьего ограничений дополнительных переменных +x_n+1 и –x_n+2 соответственно max Z=c₁ x₁+c₂ x₂+…+c_n x_n,

a₁₁ x₁+a₁₂ x₂+…+a_1n x_n=b₁, (7)

a₂₁ x₁+a₂₂ x₂+…+a_2n x_n+x_n+1=b₂,

a₃₁ x₁+a₃₂ x₂+…+a_3n x_n-x_n+2=b₃,

x_j0, x_n+10, x_n+20,

где «+x_n+1» и «–x_n+2» -дополнительные переменные.