Лінійне програмування - це наука про методи дослідження та відшукання найбільшого і найменшого значень лінійної функції, на невідоме якої накладено лінійні обмеження.
Визначення. Гіперповерхні в n-мірному просторі називається геометричне місце точок. координати яких задовольняють лінійному рівнянню (1), де - довільні дійсні числа
Нехай нам задана лінійна функція F щодо змінних.
F (x) = це цільова функція або лінійна форма.
Визначення. Гіперповерхность F (x) = c називається гіперповерхні рівних значень лінійної форми
- дані гіперповерхні паралельні.
Нехай у нас є n -точек.
Визначення: Точка А називається опуклою лінійною комбінацією крапок. якщо. де і
Визначення: Безліч точок називається опуклим. якщо воно разом з будь-якими двома точками містить їх довільну опуклу, лінійну комбінацію.
Визначення: Кутовими або крайніми точками опуклого безлічі називаються точки, які не є опуклою, лінійної комбінацією двох довільних точок цього ж множини.
Визначення: Точка безлічі називається граничної. якщо будь-яку кулю з центром в цій точці містить як точки належать множині, так і точці які не належать йому.
Визначення: Граничні точки утворюють кордон даної множини.
Визначення: Замкнутим називають безліч, що містить всі свої граничні точки.
Визначення: Безліч називається обмеженим. якщо існує куля радіуса кінцевої довжини з центром в будь-якій точці безлічі, який повністю містить в собі дане безліч. В іншому випадку безліч називається необмеженим.
Визначення: опуклий багатокутник називається опукле, замкнутий, обмежений безліч на площині, що має кінцеве число кутових точок.
Визначення: Опорною прямий опуклого багатокутника називається пряма. має з багатокутником, розташованого по одну сторону від неї, хоча б одну спільну точку.
Теорема: Замкнуте обмежений опуклий багатокутник є опуклою лінійною комбінацією своїх кутових точок.
Теорема: Перетин будь-якого числа опуклих множин є безліч опукле (якщо тільки воно непорожнє).
Геометрична інтерпретація безлічі
рішень системи лінійних нерівностей з 2 невідомими
У загальному вигляді лінійне нерівність з 2 змінними записується в такий спосіб (1) або (2).
Кожному рішенню нерівностей в (1) і (2) відповідає точка на площині. Геометричний сенс безлічі рішень нерівностей в (1) або (2) встановлюється теоремою.
Теорема: Безліч рішень лінійного нерівності (1) за допомогою однієї з двох напівплощин, на які всю площину ділить пряма включаючи і цю пряму, а інша напівплощина разом з цією ж прямий є безліччю рішень лінійного нерівності (2).
Візьмемо систему з двох нерівностей
Безліч її рішень це точки належать обом напівплощиною. По теоремі 2 їх перетину опукле безліч, що має кінцеве число кутових точок. Методом математичний індукції встановлено, що безліччю рішень системи m - лінійних неравен ств з дв умя змінними є опуклий багатокутник (якщо це перетин порожньо).