1. Загальна форма задачі лінійного програмування (лп).

Означення 1. Загальною формою задачі ЛП є задача на знаходження екстремуму (мінімуму чи максимуму) лінійної цільової функції f при лінійній системі обмежень g_i, що включає як рівності, так і нерівності з обох боків при невідомих змінних, з яких одні пов’язані умовою невід’ємності, другі – умовою недодатності, а на знак третіх ніяких умов не накладено, тобто задача має таких вигляд:

f(x)= c₁x₁ + c₂x₂ + …. + c_nx_n →extr (max/min) (1)

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ….. +a_1nx_n{ ≤ = ≥ }b₁

a₂₁x₁ + a₂₂x₂ + a₃₃x₃ + …..+ a_2nx_n{ ≤ = ≥ }b₂

a_k1x₁ + a_k2x₂ + a_k3x₃ + …….+ a_knx_n{ ≤ = ≥ }b_k (2)

a_m.1x₁ + a_m.2x₂ + a_m.3x₃ + a_m.nx_n { ≤ = ≥ } b_m

x_i≥0 i= 1,m (3)

Отже, загальна задача ЛП є формою із змішаною системою обмежень .

Означення 2. Задача ЛП має канонічний вигляд, якщо в загальній формі задачі ЛП присутні тільки обмеження (2) у вигляді рівнянь та (3).

Означення 3. Задача ЛП має стандартний вигляд, якщо в загальній формі задачі ЛП присутні тільки обмеження (2) у вигляді нерівностей ≤ та (3), коли шукається max цільвої функції f, або в загальній формі задачі ЛП присутні тільки обмеження (2) у вигляді ≥ та (3), коли шукається min цільвої функції f.

Перейти від стандартного вигляду задачі ЛП можна за допомогою додовання невід’ємних змінних.

Приклад 1. Записати в канонічній формі задачу ЛП:

Приклад 2. Записати в канонічній формі задачу ЛП:

Приклад 3. Записати в канонічній формі задачу ЛП:

В теоретичному плані всі задачі ЛП можна розглядати тільки як задачі на мінімум чи на максимум, змінивши знак цільової функції:

f(x)=c₁x₁ + c₂x₂ + c₃x₃ + …… +c_nx_n →max

z(x) = - f(x) = -( c₁x₁ + c₂x₂ + c₃x₃ + …… +c_nx_n) →min

Система обмежень (2) – (3) може бути сумісною або несумісною. Сумісна система обмежень визначає в n-вимірному векторному просторі область визначеності задачі, інакше, область існування планів задачі ЛП. Кожна крапка області означеності є планом задачі, а сама область є множиною планів задачі ЛП.

Формулювання задачі буде некоректним, якщо система обмежень задачі несумісна, суперечлива. Тоді множина планів задачі, не містить жодного плану, буде порожньою.