уклою, якщо О» i ≥ 0, i € 1: m і
Безліч, що містить всі можливі опуклі комбінації точок деякого безлічі М, називають опуклою оболонкою даної множини. Можна показати, що опукла оболонка множини М є найменшим опуклим безліччю, що містить М.
Опукла оболонка кінцевого безлічі точок називається опуклим багатогранником, а непорожнє те кінцевого числа замкнутих півпросторів - багатогранним опуклим множиною. На відміну від опуклого багатогранника останнє може бути необмеженим.
Точка v опуклого безлічі V називається його кутовий (крайньої) точкою, якщо вона не є внутрішньою точкою ні для якого відрізка, кінці якого належать безлічі V. Кутові точки опуклого багатогранника є його вершинами, а сам він - опуклою оболонкою своїх вершин.
Безліч До називається конусом з вершиною в точці x 0 , якщо x 0 € К, і з того, що деяка точка х належить К (х € До ), Випливає, що в К міститься і промінь, що починається в х 0 і проходить через х, тобто
В
або
В
Опукла оболонка кінцевого безлічі променів, що виходять з однієї точки, називається багатогранним опуклим конусом з вершиною в даній точці.
В
1.4 Математичні основи рішення задачі лінійного програмування графічним способом
В
1.4.1 Математичний апарат
Для розуміння всього подальшого корисно знати і уявляти собі геометричну інтерпретацію завдань лінійного програмування, яку можна дати для випадків n = 2 і n = 3.
Найбільш наочна ця інтерпретація для випадку n = 2, тобто для випадку двох змінних x 1 і x 2 . Нехай нам задана задача лінійного програмування у стандартній формі
1.5)
В
Візьмемо на площині декартову систему координат і кожній парі чисел (x 1 , x 2 ) поставимо у відповідність точку на цій площині.
В
Звернемо насамперед увагу на обмеження x 1 ≥ 0 і x 2 ≥ 0. Вони з усієї площині вирізають лише її першу чверть (див. рис. 1). Розглянемо тепер, які області відповідають неравенствам виду a 1 x 1 + a 2 x 2 ≤ b. Спочатку розглянемо область, відповідну рівності a 1 x 1 + a 2 x 2 = b. Як Ви, звичайно, знаєте, це пряма лінія. Будувати її простіше всього по двох точках.
Нехай b в‰ 0. Якщо взяти x 1 = 0, то вийде x 2 = b/a 2 . Якщо взяти x 2 = 0, то вийде x 1 = b/a 1 . Таким чином, на прямий лежать дві точки (0, b/a 2 ) і (b/a 1 , 0). Далі через ці дві точки можна по лінійці провести пряму лінію (малюнок 2).
В
Якщо ж b = 0, то на прямий лежить точка (0,0). Щоб знайти іншу точку, можна взяти будь-яке відмінне від нуля значення x 1 і обчислити відповідне йому значення x
