Тема 2. Основні методи розв’язування задач лінійного програмування

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

Розв’язати ЗЛП означає знайти таке із множини допустимих розв’язків при якому цільова функція досягає максимуму або мінімуму.

Означення 2.2. Множина називається опуклою, якщо для будь-яких двох точок А,В відрізок, що їх сполучає повністю належить даній множині.

Переріз будь-якої кількості опуклих множин є опукла множина.

Означення 2.3 .Функція називається опуклою на опуклій множині, якщо для будь-яких,з цієї множини і будь-якоговиконується нерівність:

і увігнутою, якщо виконується нерівність:

Опукла функція, задана на опуклій множині досягає свого найменшого значення на границі множини, аналогічно увігнута функція досягає свого найбільшого значення на границі множини.

Функція є одночасно опуклою і увігнутою, тому досягає мінімуму та максимуму на границі опуклої множини.

Множина, що задається нерівністю є опуклою множиною.

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

2.1 Графічний метод розв’язування задач лінійного програмування

Графічний метод застосовується для розв’язання ЗЛП, записаних в стандартній формі, що містять дві змінні.

Нерівність задає на площині півплощину, обмежену прямою.

Півплощина є опуклою областю. Переріз скінченної кількості півплощин може бути: пустою множиною; точкою; відрізком, променем або прямою; обмеженим опуклим многокутником; необмеженим опуклим многокутником.

Розглянемо ЗЛП:

(2.1)

, (2.2)

(2.3)

Множина, яка є перерізом півплощин, заданих нерівностями (2.1), (2.2) називається областю допустимих розв’язків (ОДР).

1. Якщо ОДР є пуста множина, то ЗЛП не має сенсу.

2. Якщо ОДР – одна точка, то максимум і мінімум співпадають.

3. ОДР обмежений многокутник. В цьому випадку цільова функція має обидва оптимуми.

4. ОДР необмежений многокутник. В цьому випадку один із оптимумів не існує (ЗЛП не має розв’язку).

Цільова функція досягає найбільшого і найменшого значення на границі ОДР.

Алгоритм графічного методу

Крок 1.

Будуємо ОДР.

Крок 2.

Будуємо вектор цілі . В напрямку цього вектора цільова функція буде зростати.

Крок 3.

Будуємо лінію нульового рівня .

Крок 4.

Переносимо цю пряму паралельно самій собі, до тих пір доки не з’являться спільні точки з границею області. В цих точках цільова функція досягає мінімуму, якщо така точка одна – то мінімум єдиний, якщо це відрізок або промінь то мінімумів безліч.

Переносячи лінію рівня паралельно далі в напрямку вектора цілі, знаходимо положення, після якого вона вже не буде мати спільних точок з ОДР. В цьому положенні вона має спільні точки тільки з границею області, і в цих точках досягає максимуму, якщо ця точка єдина, то максимум єдиний, якщо це відрізок або промінь, то їх безліч.

Зауваження 2.1. Графічний метод можна розповсюдити на випадок трьох змінних.

Приклад 2.1. Розв’язати графічно ЗЛП

Розв’язання. Побудуємо ОДР.

Нерівність описує півплощину, обмежену прямою, що є паралельною осі. Оскільки для точки з координатами (0;0) (початок

X

Рис. 2.2. Графічне розв’язання ЗЛП (приклад 2.1)

координат) нерівність вірна, то дана півплощина лежить зліва від прямої (див. рис.2.1.1).

Півплощина - обмежена прямою . Для побудови цієї прямої знайдемо точки її перетину з осями. Поклавши отримаємо . При маємо . Отже пряма проходить через точки з координатами (0;11) та (5,5; 0). Оскільки для точки з координатами (0;0) нерівність вірна, то дана півплощина лежить нижче прямої (див. рис. 2.1.2). Аналогічно будуємо дві інші півплощини(див. рис. 2.1.3та 2.1.4).

Зауваження 2.2. Якщо при перевірці належності півплощині точки з координатами (0;0) отримаємо невірну нерівність, то шукана півплощина знаходиться по інший бік прямої, що її обмежує.

Враховуючи, що ,, розв’язки знаходяться у першій чверті. Перетином побудованих півплощин є многокутник ОАВСDЕ (див. рис. 2.1.5).

Далі будуємо вектор цілі=(6;5) та лінію нульового рівня, яка проходить через початок координат, перпендикулярно до вектора.

Ми бачимо, що мінімальне значення досягається в точці з координатами (0;0), тобто = (0;0). .

Переносячи паралельно пряму нульового рівня, досягаємо положення, після якого вона вже не буде мати з ОДР спільних точок. В цьому положенні вона має з границею ОДР одну спільну точку С, в якій досягається максимум.

В точці С перетинаються прямі та . Для знаходження координат точки С розв’яжемо систему

Домножимо перше рівняння на 2 і віднімемо від нього друге. Маємо . Звідки . Підставивши в будь-яке з рівнянь системи, знайдемо . Таким чином, .

Графічне розв’язання ЗЛП показано на рис. 2.2.

Відповідь. .

Зауваження 2.3. Даний приклад відрізняється від приклада 1.2 лише цільовою функцією. Але легко побачити, що помножившиз щойно розв’язаного приклада на 108 отримаємо цільову функцію з приклада 1.2. Таким чином, між містами А і В повинно курсувати 4 пасажирських та 3 швидких потяги, що забезпечить перевезення максимальної кількості пасажирів.

Приклад 2.2. Розв’язати графічно ЗЛП

Розв’язання. Спочатку зведемо систему виробничих обмежень до виду (2.1). Для цього перенесемо у виробничих обмеженнях вільні члени в праві частини. Маємо

Домножимо третю нерівність на -1 і отримаємо наступну ЗЛП

Побудову ОДР і розв’язання даної ЗЛП показано на рис. 2.3. ОДР є многокутник ОАВСD. Ми бачимо, що мінімуму функція z досягає в точці А(0;2) (), а максимуму на відрізку СD. Враховуючи, що в усіх точках цього відрізка цільова функція приймає одне і те саме значення, для обчислення підставляємо в неї координати точки D(1;0) ().

Відповідь. . Максимум досягається на відрізку СD. .