ві змінні, привести її до виду
,,, де.
Якщо ж обмеження в задачі задані у формі, то
,,.
Розглянемо завдання з обмеженнями. Цю систему обмежень можна представити у вигляді системи
.
Введемо наступні позначення:
,, ...,,, ...,,
.
Тоді задачу лінійного програмування можна записати у вигляді:
В
,.
Вектори називаються векторами умов, а сама задача лінійного програмування називається розширеною по відношенню до вихідної. Нехай і - допустимі безлічі рішень вихідної і розширеної завдань відповідно. p> Тоді будь-якій точці безлічі відповідає єдина точка множини і навпаки. У загальному випадку, допустиме безліч вихідної задачі є проекція безлічі розширеної задачі на підпростір вихідних змінних. p> Визначення 4.Набор чисел, що задовольняє обмеженням завдання лінійного програмування називається її планом.
Визначення 5. Рішенням задачі лінійного програмування називається її план, здатний мінімізувати (або максимізує) лінійну форму. p> Введемо поняття базисного рішення. З матриці розширеної задачі виберемо лінійно незалежних векторів-стовпців, які позначимо як матрицю, а через позначимо матрицю з решти стовпців. Тоді, та обмеження розширеної задачі лінійного програмування можна записати у вигляді:
. (3)
Очевидно, що стовпці матриці утворюють базис-мірного простору. Тому вектор і будь стовпець матриці можна представити у вигляді лінійної комбінації стовпців матриці. p> Помножимо (3) на ліворуч
, (4)
і знайдемо звідси:
. (5)
Надаючи різні значення, будемо отримувати різні рішення.
Якщо покласти, то
. (6)
Рішення (6) називають базисним рішенням системи з рівнянь з невідомими.
Якщо отримане рішення містить тільки позитивні компоненти, то воно називається базисним допустимим.
Особливість допустимих базисних рішень полягає в тому, що вони є крайніми точками допустимого безлічі розширеної задачі.
Якщо серед компонент немає нульових, то базисне допустиме рішення називається невиродженим.
Визначення 6. План завдання лінійного програмування будемо називати опорним, якщо вектори умов з позитивними коефіцієнтами лінійно незалежні. p> Тобто опорний план - це базисне допустиме рішення розширеної системи, кутова точка багатогранника рішень.
Теорема 1: (основна теорема лінійного програмування):
Лінійна форма досягає свого мінімуму в кутовій точці багатогранника рішень.
Якщо вона приймає мінімальне рішення більш ніж в одній кутовий точці, то вона досягає того ж самого значення в будь-якій точці, що є опуклою комбінацією цих кутових точок.
Доказ: Доказ теореми грунтується на наступній лемі.
Лемма: Якщо - замкнене, обмежене, опукле безліч, що має кінцеве число...
