Лекція 7. Задачі лінійного програмування

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

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

Визначимо положення точок і , розв’яжемо відповідно дві системи рівнянь:

Відповідь: Отже, найменше значення цільової функції , а найбільше .

Зауваження. Значення лінійної функції трьох змінних, яка розглянута в опуклому многокутнику, містяться між найбільшим та найменшим значенням цієї функції у вершинах многокутника. А коли змінних більше трьох, то геометричне розв’язання вже неможливе, і слід звертатися до алгебраїчних методів, наприклад, скористатися симплекс-методом Л [1, ст.320].

 

 

Розглянемо на конкретних прикладах деякі типові ЗЛП.

Задача про використання ресурсів

Фабрика виготовляє стільці двох видів. На виготовлення одного стільця першого виду, який коштує 8 грошових одиниць вартості (наприклад, євро), витрачається 2 м дощок стандартного перерізу, 0,5 м2 оббивної тканини та 2 людино-години (витрати робочої сили). Аналогічно, для виготовлення стільців другого виду маємо: 12 одиниць вартості, 4 м дощок, 0,25 м2 оббивної тканини і 2,5 людино-години.

Фабрика має в наявності 440 м дощок, 65 м2 оббивної тканини, 320 людино-годин робочого часу.

Яку кількість стільців кожного виду треба виготовити, щоб вартість продукції була найбільшою?

Розв’язання.

Складемо економіко-математичну модель даної задачі.

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

 Вказану систему нерівностей називають умовами обмеження.

Крім того, за змістом задачі числа повинні бути невід’ємними (так як неможливо виготовляти «-3» стільці):

Отримали область допустимих значень змінних.

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

Це є цільова функція.

Об’єднавши умови обмеження, область допустимих значень змінних (*)

та приєднавши до них цільову функцію — отримали канонічний запис ЗЛП.

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

Побудуємо в декартовій системі координат графіки прямих (тобто ), (тобто ).

Отримали п’ятикутник , точки якого задовольняють систему нерівностей (*) (рисунок 10).

 Рис. 10

Розв’язуючи системи рівнянь дістанемо координати точок , , , — вершин п’ятикутника.

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

Отже, найбільша вартість продукції складає 1140 грошових одиниць. 

Висновок. План, який забезпечує отримання такого прибутку, передбачає виготовлення 60 стільців першого і 80 стільців другого виду. Для виконання такого плану потрібно витратити 440 м дощок, 65 м2 оббивної тканини, 320 людино-годин робочого часу.

Транспортна задача

Для забезпечення городян хлібом у місті N, що адміністративно поділено на три райони, працює два хлібозаводи №1 і №2. Перший район щоденно потребує тонн хліба, другий − тонн, а третій − тонн. Хлібозавод №1 щоденно випікає тонну хліба, а хлібозавод №2 − тонн. Вартість перевезень одиниці продукції від кожного виробника кожному району характеризується матрицею (в грошових одиницях)

Скласти такий план перевезень, при якому весь хліб буде розвезено, всі потреби будуть задоволені і вартість перевезень буде найменшою, враховуючи, що 

Зробити відповідні висновки.

Розв’язання.

Складемо економіко-математичну модель даної задачі.

Нехай 

тонн – кількість хліба, які доставляє завод №1 у 1-ий район.

тонн – кількість хліба, які доставляє завод №1 у 2-ий район.

Щоденний план перевезень характеризує таблиця

Район

Завод 123

№1

№2

Складемо цільову функцію, скориставшись матрицею вартості перевезень одиниці продукції .

Спростивши, будемо мати

 Вкажемо область допустимих значень

− кількість хліба, що завозиться у кожний район, не може бути від’ємною.

Запишемо умови обмеження, об’єднавши їх із областю допустимих значень:

Зобразимо в системі координат xОy многокутник розв’язків (див.рисунок 11).

Отримали − многокутник (п’ятикутник) розв’язків.

 Рис.11

Побудуємо в системі координат xОy вектор , координати якого є коефіцієнтами біля змінних у цільовій функції L. (див.рисунок 11).

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

Побудуємо пряму , яка перпендикулярна до вектора і проходить через початок координат. (див.рисунок 11).