При ЗЛП набирає вигляду
Розглянемо -мірним координатне простір з впорядкованими сукупностями (точками).
Визначення 3.1. Безліч точок простору. координати яких задовольняють рівняння. де хоча б одне з чисел (), відмінно від нуля, називають гиперплоскостью простору.
Визначення 3.2. Безліч точок простору. координати яких задовольняють нерівності. називають півпростором простору. розташованим по одну сторону від
У просторі рівняння визначає пряму, нерівність визначає полуплоскость.
Визначення 3.3. Безліч точок простору. координати яких одночасно задовольняють системі гіперплоскостей (), називають перетином гіперплоскостей.
Визначення 3.4.Випуклой лінійної комбінацією крапок. . ..., простору називають точку (.).
Опукла лінійна комбінація двох точок простору є відрізком, що з'єднує ці точки.
Визначення 3.5. Безліч точок простору називається опуклим, якщо воно разом з будь-якими двома своїми точками містить і їх довільну лінійну комбінацію (тобто містить разом з будь-якими двома точками і всі крапки відрізка).
Визначення 3.6. Точку називають граничною точкою множини, якщо в будь-який як завгодно малій околиці точки містяться як точки цієї множини, так і точки, які не належать йому.
Визначення 3.7. Безліч називають замкнутим. якщо воно містить всі свої граничні точки, в іншому випадку - відкритим.
Визначення 3.8. Точка називається кутовий точкою опуклого замкнутого безлічі, якщо вона не може бути представлена у вигляді лінійної комбінації якихось двох інших різних точок цієї множини.
Визначення 3.9. Безліч називають обмеженим. якщо існує куля радіусом кінцевої довжини з центром в будь-якій точці безлічі, який повністю містить в собі дане безліч. В іншому випадку безліч називають необмеженим.
Визначення 3.10. Безліч називають св язним. якщо будь-які дві його точки можна з'єднати ламаною (або безперервної кривої), цілком лежить в цій множині.
Визначення 3.11. Відкрите чіткий безліч називають областю.
Визначення 3.12. Якщо область містить всі свої граничні точки, то її називають замкнутою областю.
Визначення 3.13. Опуклу замкнуту область, що має кінцеве число кутових точок, називають опуклим -мірним многогранником.
Визначення 3.14. Опукле замкнутий безліч, що має кінцеве число кутових точок, називають опуклою -мірною багатогранної
Визначення 3.15.Пересеченіем множин називають безліч точок, яке є спільною частиною цих множин.
Визначення 3.16. Непорожня множина допустимих рішень ЗЛП називаютмногогранніком планів (рішень).
Визначення 3.17. Кутову точку багатогранника рішень називають вершиною.
Визначення 3.18. Вершину багатогранника планів з невід'ємними координатами називають опорною. Відповідний їй план називають опорним планом.
З визначень слід, що кожній вершині многогранника рішень відповідає опорний план ЗЛП.
Визначення 3.19. Опорний план називають невиродженим. якщо він містить рівно позитивних координат, і виродженим. якщо позитивних координат менше.
Теорема 3.1 (основна теорема лінійного програмування). Якщо ЗЛП має оптимальне рішення, то цільова функція приймає екстремальне значення в одній з вершин багатогранника планів. Якщо цільова функція приймає екстремальне значення більш ніж в одній вершині, то вона приймає його в будь-якій точці, що є їх опуклою лінійною комбінацією.
Визначення 3.20. Якщо цільова функція приймає екстремальне значення більш ніж в одній вершині багатогранника планів, то кажуть, що ЗЛП має альтернативний оптимум.
Визначення 3.21. Сукупність точок, складових область допустимих рішень, в разі двох керуючих змінних, називають багатокутником рішень (планів).
Багатокутник рішень може бути плоским багатокутником, необмеженою багатокутним безліччю, відрізком. Геометрично ЗЛП полягає в пошуку такої точки багатокутника рішень, координати якої доставляють лінійної цільової функції найбільше або найменше значення, причому допустимими рішеннями є всі точки багатокутника рішень.
Розглянемо графічний метод рішення ЗЛП.
1) Припустимо, що система нерівностей (3.1) сумісна (має хоча б одну точку, що задовольняє всім обмеженням відразу). На координатної площині побудуємо безліч допустимих рішень, що відповідає системі обмежень (3.1). Кожне нерівність системи (3.1) визначає полуплоскость () з граничною прямою ().
Нехай, наприклад, напівплощина визначається нерівністю. Для побудови півплощини () досить підставити в відповідне нерівність координати будь-якої точки (наприклад, (0, 0)) і перевірити істинність отриманого нерівності. Якщо нерівність істинне, то необхідно заштрихувати полуплоскость, що містить цю точку. У разі, якщо нерівність помилкове, то заштрихувати полуплоскость, що не містить дану точку.
Умови невід'ємності керуючих змінних. визначають півплощини з граничними прямими. (Першу координатну чверть). Так як система обмежень сумісна, то полуплоскости мають загальну область. Перетин півплощини є опуклим безліччю і являє собою сукупність точок, координати яких складають допустимі рішення.
2) Побудуємо градієнт цільової функції (в даному випадку геометричний вектор):
з початком в точці і кінцем в точці. показує напрямок найбільшого зростання цільової функції.
3) Побудуємо лінію рівня цільової функції. Ця лінія є пряма (при отримуємо лінію нульового рівня. См. Рис. 3.1), і вона перпендикулярна градієнту. Як правило, значення доцільно вибирати таким чином, щоб відповідна лінія рівня мала з безліччю допустимих рішень принаймні дві спільні точки.
4) При вирішенні завдання на максимум функції слід переміщати лінію рівня в напрямку градієнта до тих пір, поки у неї не виявиться всього одна спільна точка з безліччю допустимих рішень. Ця точка, яка визначає єдине рішення ЗЛП, буде точкою екстремуму (максимуму). При вирішенні задачі на мінімум функції слід переміщати лінію рівня в напрямку, протилежному напрямку градієнта до тих пір, поки у неї не виявиться всього одна спільна точка з безліччю допустимих рішень. Ця точка, яка визначає єдине рішення ЗЛП, буде точкою екстремуму (мінімуму).
5) Знайти координати вершини багатокутника, що є точкою екстремуму. Для цього потрібно вирішити систему рівнянь тих прямих, перетином яких є дана вершина.
6) Обчислити значення цільової функції в отриманої вершині.
Зауваження 3.1. Якщо при русі вздовж градієнта лінія рівня не залишає безліч допустимих рішень, то це безліч є необмеженим в напрямку оптимізації. В цьому випадку умовно вважають, що або.
Зауваження 3.2. ЗЛП не матиме рішень, якщо безліч допустимих рішень є порожнім безліччю. Це означає, що система обмежень має суперечливі нерівності, і на координатної площині немає жодної точки, що задовольняє всім обмеженням відразу.
Зауваження 3.3. При вирішенні ЗЛП графічним методом може зустрітися випадок, коли лінія рівня паралельна однієї зі сторін опуклого багатокутника допустимих рішень, причому ця сторона розташована в напрямку оптимізації. Тоді оптимальне значення цільової функції досягається в двох кутових точках (вершинах) області допустимих рішень, а, отже, і у всіх точках відрізка, що з'єднує ці вершини, тобто ЗЛП має безліч рішень (альтернативний оптимум).
Приклад 3.1. Фірма випускає два види морозива: вершкове і шоколадне. Для виготовлення морозива використовуються два вихідних продукту: молоко і наповнювачі, витрати яких на 1 кг морозива і добові запаси дані в таблиці:
Витрата вихідних продуктів на 1 кг морозива
Вивчення ринку збуту показало, що добовий попит на вершкове морозиво перевищує попит на шоколадне не більше, ніж на 100 кг. Крім того, встановлено, що попит на шоколадне морозиво не перевищує 350 кг на добу. Роздрібна ціна 1 кг вершкового морозива 16 руб. шоколадного - 14 руб. Яка кількість морозива кожного виду повинна виробляти
фірма, щоб дохід від реалізації продукції був максимальним? [1; 2].
Рішення. Позначимо керуючі змінні: - добовий обсяг випуску вершкового морозива, кг; - добовий обсяг випуску шоколадного морозива, кг. Складемо математичну модель задачі. Цільова функція буде мати вигляд.
Складемо нерівності для ресурсних обмежень. Обмеження по молоку має вигляд:; по наповнювачів:. Складемо нерівності для ринкових обмежень за попитом. Різниця в добовому попиті на 2 види морозива становить. Обмеження на добовий попит шоколадного морозива.
Тоді математична модель задачі буде мати вигляд
Далі вирішимо завдання графічним методом.
1) Побудуємо безліч допустимих рішень. Нерівність визначає полуплоскость, розташовану лівіше і нижче прямої. тобто прямий. Нерівність визначає полуплоскость, розташовану лівіше і нижче прямої. Обмеження визначає полуплоскость, розташовану лівіше і нижче прямої. Обмеження визначає полуплоскость, розташовану лівіше прямої. обмеження. визначають першу координатну чверть. Безліч допустимих рішень ЗЛП не порожньо. Позначимо вершини багатокутника рішень: (рис. 3.2).
2) Побудуємо градієнт цільової функції:
3) Побудуємо лінію рівня цільової функції. . Лінія рівня перпендикулярна вектору.
4) Переміщуючи пряму у напрямку паралельно самій собі, знайдемо граничну точку, в якій цільова функція покине область допустимих рішень (пунктирна лінія на рис. 3.2). Гранична точка багатокутника - точка.
5) Знайдемо координати точки як точки перетину прямих і:
6) Знайдемо значення цільової функції в точці: