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

Математическое программирование – это раздел высшей математики, посвященный решению задач на нахождение экстремумов функции от нескольких переменных при наличии ограничений на переменные.

Переменными задачи называются величины х₁, х₂,...,х_п , которые полностью характеризуют экономический процесс (х=(х₁, х₂,...,х_п).

Система ограничений включает в себxя систему уравнений и неравенств, которым удовлетворяют переменные задачи.

Целевой функцией называют функцию переменных задачи, которая характеризует качество выполнения задания и экстремум которой требуется найти.

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

Найти экстремум целевой функции

Z(x) = f (x₁, x₂,…,x_n)  min (max)

при условиях, что переменные удовлетворяют системе ограничений

_I (x₁, x₂,…,x_n)  0, i= 1,…,k,

_I (x₁,x₂,…,x_n ) =0, i =k+1,…,m.

Если f и _i – линейные функции, то это задача линейного программирования. Существуют три формы записи этой задачи.

1. Общей задачей линейного программирования называют задачу:

Z (x) = c₁x₁+c₂x₂+…+c_nx_n  min(max) (1)

(2)

x_j – любого знака. (3)

Данная запись означает: найти экстремум целевой функции и соответствующие ему переменные при условии, что они удовлетворяют системе ограничений (2),(3).

2. Симметричной формой записи ЗЛП называют задачу

а) Z (x) =

(j=1,..,n)

б) Z (x) =

(j=1,…,n)

3. Канонической формой ЗЛН называют задачу

Z(x) =

4. Введем обозначения:

С = (с₁, с₂, ...,с_п) матрица строка,

Х = А = А₀ =

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

А – матрица системы уравнений,

А₀ – столбец свободных членов.

Каноническая форма может быть записана в матричной форме:

Z = CX^T  max,

AX = A₀, X  0.

Заменим столбцы матрицы

А₁ = , А₂ = ... . А_п =

Запишем в векторной форме :

Z = CX ^Tmax,

x₁A₁ + x₂A₂ + ...+ x_nA_n = A₀.

2.2. Способы преобразования форм записи злп

а ) Приведение общей ЗЛП к канонической форме

При необходимости задачу минимизации можно заменить задачей максимизации и наоборот

min f (x^*) = - max(-f (x^*) ).

Пусть ЗЛП имеет вид

Z(x) = ∑c_jx_j max,

Введем т дополнительных (балансовых) неотрицательных переменных x_n+i0 (i=1,…,m).

Для того чтобы неравенства типа «» преобразовать в равенства, нужно к их левым частям прибавить дополнительные переменные x_n+i0 (i=1,…,m₁).

Для того чтобы неравенства типа «» преобразовать в равенства из их левых частей нужно вычесть дополнительные переменные x_n+i 0, (i=m₁+1,…,m). Дополнительные переменные x_n+i в целевую функцию вводятся с нулевыми коэффициентами. После преобразований задача будет иметь вид.

Z (x) =

Эта задача записана в канонической форме. В ряде задач не на все переменные наложены условия неотрицательности. В этом случае каждую из переменных х_к любого знака заменяют разностью х_к - х_к = х_к двух неотрицательных переменных.

Пример. Привести к каноническому виду ЗЛП:

Z (x) = 3x₁ + x₂ + x₃ min,

□ 1. Переходим к задаче отыскания максимума целевой функции

- Z(x) = -3x₁- x₂ – x₃ max/

2. Преобразуем ограничения неравенства. К первому неравенству в левую часть прибавим дополнительную переменную х₄. Из левой части второго неравенства вычитаем х₅. Получим равенства

х₁ – х₂ + 2х₃ + х₄ = 1 и 2x₁ + x₂ – 2x₃ – x₅ = 5

3. Переменную х₁, на которую не наложено условие неотрицательности заменяем х₁ = х₁ - х₁ , х₁, х₁ 0.

4. Записываем каноническую форму задачи

- Z(x) = -3x₁ + 3x₁ - x₂ –x₃ + 0x₄+0x₅ max,

б) переход от канонической формы записи ЗЛП к симметричной

Пусть в общей задаче линейного программирования имеются ограничения – равенства

Каждое такое равенство эквивалентно системе неравенств

От неравенства  можно перейти к неравенству  умножением обеих частей неравенства на минус единицу и, наоборот.