ПРАКТИКУМ
ЗГІДНО РІШЕННЯ ЛІНІЙНИХ ЗАВДАНЬ
МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ
Введення
Математичне програмування - це розділ математики, який вивчає теорію та методи пошуку кращих варіантів планування господарської діяльності людини як на одному певному підприємстві, так і в деякій галузі або в окремому регіоні, або в цілому державі.
Кращі варіанти - це ті, при яких досягається максимальна продуктивність праці, мінімум собівартості, максимальний прибуток, мінімум використання ресурсів і т.д. З точки зору математики - це клас оптимізаційних завдань. Основним інструментом при їх вирішенні є математичне моделювання. Математична модель - це формальний опис досліджуваного явища і "переклад" всіх існуючих відомостей про нього на мову математики у вигляді рівнянь, тотожностей, нерівностей. Якщо всі ці співвідношення лінійні, то вся завдання називається задачею лінійного програмування (ЗЛП). Критерієм ефективності цієї моделі є деяка функція, яку називають цільовою.
Постановка задачі лінійного програмування та форми її записи
Сформулюємо загальну задачу лінійного програмування.
Нехай дана система m лінійних рівнянь і нерівностей з n змінними (система обмежень):
(1)
і лінійна функція
. (2)
Необхідно знайти таке рішення системи (1), при якому лінійна функція
приймає максимальне (мінімальне) значення.
У загальному випадку ЗЛП може мати нескінченну безліч рішень. Часто рішення , Що задовольняє обмеженням (1), називають планом. Якщо всі компоненти
(3) для
, То
називають допустимим рішенням.
Оптимальним рішенням або оптимальним планом завдання лінійного програмування називається таке її рішення , Яке задовольняє всім обмеженням системи (1), умові (3) і при цьому дає максимум (мінімум) цільової функції (2).
Канонічна | Стандартна | Загальна |
1) Обмеження | ||
Рівняння | Нерівності | Рівняння і нерівності |
2) Умови неотрицательности | ||
Всі змінні | Всі змінні | Частина змінних |
3) Цільова функція | ||
| ||
Тут: - Змінні завдання;
- Коефіцієнти при змінних в цільовій функції;
- Коефіцієнти при змінних в основних обмеженнях задачі;
- Праві частини обмежень.
Приклад. Скласти економіко-математичну модель задачі: Для випуску виробів двох типів А і В на заводі використовують сировину чотирьох видів (I, II, III, IV). Для виготовлення виробу А необхідно: 2 од. сировини першого виду, 1 од. другого виду, 2 од. третього виду та 1 од. четвертого виду. Для виготовлення виробу В потрібно: 3 од. сировини першого виду, 1 од. другого виду, 1 од. третього виду. Запаси сировини становлять: I вигляд а - 21 од., II виду - 8 од., III виду - 12 од., IV виду - 5 од. Випуск одного виробу типу А приносить 3 УДЕ прибутку, а одного виробу типу В - 2 УДЕ. Скласти план виробництва, що забезпечує найбільший прибуток.
Рішення. Досить часто при складанні математичної моделі економічної задачі буває зручно дані умови представити у вигляді таблиці:
Сировина | Кількість сировини на од. продукції, од. | Запас сировини, од. | |
А | У | ||
I | 2 | 3 | 21 |
II | 1 | 1 | 8 |
III | 2 | 1 | 12 |
IV | 1 | - | 5 |
Прибуток від од. продукції, УДЕ | 3 | 2 | |
Нехай - Кількість виробів типу А і В відповідно, плановане до випуску (
,
).
Тоді прибуток складе: , Т. к. план виробництва повинен забезпечувати найбільший прибуток, то цільова функція задачі:
.
Складемо систему обмежень, використовуючи задану обмеженість сировини. При запланованих обсягах виробництва витрачається сировини I види: (Од.), що не повинно перевищувати запас 21 од. Т.ч. отримаємо нерівність:
. Складаючи нерівності по кожному виду сировини, отримаємо систему:
Отримуємо математичну модель задачі лінійного програмування:
Приклад. Скласти математичну модель задачі: На чотирьох верстатах (I, II, III, IV) обробляються два види деталей (А і В). Кожна деталь проходить обробку на всіх верстатах. Відомі час обробки деталей на кожному верстаті, час роботи верстатів протягом одного циклу виробництва і прибуток, отриманий від випуску однієї деталі. Дані наведені в таблиці:
Верстати | Час обробки деталі, ч. | Час роботи верстата (Цикл пр-ва), ч. | |
А | У | ||
I | 1 | 2 | 16 |
II | 2 | 3 | 26 |
III | 1 | 1 | 10 |
IV | 3 | 1 | 24 |
Прибуток від 1 деталі, УДЕ | 4 | 1 | |
Скласти план виробництва, що забезпечує найбільший прибуток за умови, що кількість деталей виду В не повинно бути менше кількості деталей види А.
Рішення. Нехай - Кількість деталей виду А і В відповідно, плановане до випуску (
,
). Завдання аналогічна попередньої, але при складанні моделі не слід випускати з поля зору фразу: кількість деталей виду В не повинно бути менше кількості деталей виду А, що математично представимо у вигляді нерівності:
.
Тоді математична модель задачі лінійного програмування має вигляд:
Будь-яка ЗЛП може бути зведена до канонічної, стандартної або загальному завданню.
Приведення завдань до канонічного вигляду
Нехай маємо задачу загального вигляду, яку потрібно привести до канонічного виду, тобто з обмежень-нерівностей зробити обмеження-рівності. Для цього в кожне обмеження вводиться додаткова неотрицательная балансова мінлива зі знаком «+», якщо знак нерівності « », І зі знаком« - », якщо знак нерівності«
». У цільову функцію ці змінні входять з нульовими коефіцієнтами, тобто значення цільової функції не змінюється.
Примітка: 1) У канонічній формі рівності прийнято записувати так, щоб праві частини обмежень були невід'ємними. Якщо будь-яка негативне, то помноживши i-е обмеження на (-1), отримаємо в правій частині позитивне число. При цьому знак нерівності потрібно змінити на протилежний.
2) Якщо обмеження містить знак «=», то додаткову змінну вводити не потрібно.
Приклад. Записати задачу лінійного програмування в канонічному вигляді.
max (min)
,
Рішення. Друге обмеження системи містить в правій частині негативне число -2. Помножимо друге обмеження на (-1), при цьому знак нерівності зміниться на протилежний
. Завдання прийме вигляд:
max (min)
,
У перше і в друге обмеження додамо по додаткової змінної і
відповідно, а з третього віднімемо додаткову зміну
. Маємо наступний канонічний вигляд завдання:
max (min)
,
Завдання для самостійної роботи.
Скласти економіко-математичні моделі наступних завдань:
Для виготовлення двох видів продукції P 1 і Р 2 використовують чотири види ресурсів S 1, S 2, S 3 і S 4. Запаси ресурсів, число одиниць ресурсів, що витрачаються на виготовлення одиниці продукції, наведені в таблиці:
Вид ресурсу | Запас ресурсу | Число од. ресурсів, витрачених на виготовлення од. продукції | |
Р1 | Р2 | ||
S1 | 18 | 1 | 3 |
S2 | 16 | 2 | 1 |
S3 | 5 | - | 1 |
S4 | 21 | 3 | - |
Прибуток, що отримується від одиниці продукції Р 1 і Р 2, - відповідно 2 грн. і 3 грн.
На придбання обладнання для нового виробничого ділянки загальною площею 375 м 2 підприємство володіє необхідною кількістю грошових коштів. Підприємство може замовити обладнання двох видів: машини першого типу вартістю 10000 грн., Що вимагають продуктивну площа 6 м 2 (з урахуванням проходів), що виробляють 4000 одиниць продукції за зміну, і машини другого типу вартістю 20000 грн., Що займають 10 м 2 площі, що виробляють 5000 одиниць продукції за зміну. Загальна продуктивність даного виробничого ділянки повинна бути не менше 221000 одиниць продукції за зміну. Побудувати модель задачі за умови, що оптимальним для підприємства варіантом придбання обладнання вважається той, який забезпечує найменші загальні витрати.
Фермер планує виробити не менше 120 тонн пшениці, 70 тонн кукурудзи і 15 тонн гречки. Для цього можна використовувати два масиви сільськогосподарських угідь в 1000 і 800 га. У таблиці наведені врожайність кожної культури на різних ділянках (верхній показник) і витрати на 1 га сільськогосподарських угідь при виробництві різних культур (нижній показник). Потрібно скласти такий план засіву, щоб валовий збір зерна задовольняв планового завдання, а вартість витрат була найменшою.
Поле | Розмір поля | Культури | ||
пшениця | кукурудза | гречка | ||
I | 1000 | 10 7 | 20 10 | 6 15 |
II | 800 | 12 8 | 24 12 | 5 20 |
План по культурах | 120 | 70 | 15 | |
Фірма має можливість рекламувати свою продукцію, використовуючи для цього телебачення, радіо і газети. Витрати на рекламу в бюджеті фірми обмежені сумою 8000 грн. в місяць. Досвід минулих років показав, що 1 грн., Витрачена на телерекламу, дає фірмі прибуток у розмірі 10 грн., А витрачена на рекламу по радіо і в газетах - відповідно 4 і 8 грн.
Фірма має намір витратити на теле-і радіорекламу не більше 70% рекламного бюджету, а витрати на газетну рекламу не повинні більше ніж удвічі перевищувати витрати на радіорекламу.
Визначити такий варіант розподілу рекламного бюджету за різними напрямами реклами, який дає фірмі найбільший прибуток від реклами своєї продукції.
Продукція фабрики випускається у вигляді паперових рулонів стандартної ширини - 2 м. За спеціальним прохання споживачів фабрика поставляє також рулони інших розмірів, розрізаючи стандартні рулони. Типові заявки на рулони нестандартних розмірів наведені в таблиці:
Заявка | Потрібна ширина рулону, м | Потрібне кол-во рулонів |
1 | 0,8 | 150 |
2 | 1,0 | 200 |
3 | 1,2 | 300 |
Визначити оптимальний варіант розкрою стандартних рулонів, при якому всі вступники спеціальні заявки будуть виконані при мінімальних витратах паперу.
Графічний метод розв'язання задач лінійного програмування
1. Область рішень лінійних нерівностей.
Нехай задано лінійне нерівність з двома змінними і
(1)
Якщо величини і
розглядати як координати точки площини, то сукупність точок площини, координати яких задовольняють нерівності (1), називається областю рішень даного нерівності. Отже, областю рішень нерівності (1) є полуплоскость з граничною прямою лінією
.
Приклад 1. Знайти полуплоскость, яка визначається нерівністю
.
Рішення. Будуємо пряму по двох точках, наприклад, по точках перетину з осями координат (0; 4) і (6; 0). Ця лінія ділить площину на дві частини, тобто на дві півплощини. Беремо будь-яку точку площини, що не лежить на побудованій прямій. Якщо координати точки задовольняють заданому нерівності, то областю рішень є та полуплоскость, в якій знаходиться ця точка. Якщо ж отримуємо невірне числове нерівність, то областю рішень є та полуплоскость, якій ця точка не належить. Зазвичай для контролю беруть точку (0; 0).
Підставимо і
в заданий нерівність. Отримаємо
. Отже, полуплоскость «до нуля» є областю рішень даного нерівності (заштрихована частина рис. 1).
Приклад 2. Знайти полуплоскость, яка визначається нерівністю
.
Рішення. Будуємо пряму , Наприклад, по точках (0; 0) і (1, 3). Оскільки пряма проходить через початок координат, точку (0; 0), то не можна брати її для контролю. Візьмемо, наприклад, точку (- 2; 0) і підставимо її координати в заданий нерівність. Отримаємо
. Це невірно. Значить, областю рішень даного нерівності буде та полуплоскость, якої не належить контрольний пункт (заштрихована частина рис. 2).
2. Область рішень системи лінійних нерівностей.
Приклад. Знайти область рішень системи нерівностей:
Рішення. Знаходимо область рішень I-го нерівності (рис. 1) і II-го нерівності (рис. 2).
Всі крапки частини площині, де штрихування наклалася, будуть задовольняти і першому і другому нерівності. Таким чином, отримана область рішень заданої системи нерівностей (рис. 3).
Якщо до заданій системі нерівностей додати умови і
, То область рішень системи нерівностей
буде знаходитися тільки в I координатної чверті (рис. 4).
Принцип знаходження рішення системи лінійних нерівностей не залежить від кількості нерівностей, що входять в систему.
Примітка: Область допустимих рішень (ОДР) якщо існує, то є замкнутий або незамкнений опуклий багатокутник.
3. Алгоритм графічного методу розв'язання ЗЛП
Якщо завдання лінійного програмування містить тільки дві змінні, то її можна вирішити графічним методом, виконуючи такі операції:
Будуємо всі півплощини, відповідні обмеженням системи.
Знаходимо область допустимих рішень (ОДР), як безліч точок, в якому перетинаються всі побудовані півплощини.
Будуємо вектор
, Що виходить з початку координат, де
і
- Це коефіцієнти при невідомих у цільовій функції
. Цей вектор вказує напрям зростання цільової функції.
Перпендикулярно вектору
проводимо так звану лінію рівня
(Тобто пряму
, Що проходить через початок координат).
Переміщаємо лінію рівня
Знаходимо координати
цієї загальної крайньої точки, вирішуючи систему рівнянь прямих, на перетині яких вона знаходиться.
Підставляємо ці координати в цільову функцію і знаходимо її max (Або min).
Приклад. Вирішити задачу лінійного програмування графічним методом
max
Рішення. Третє і четверте обмеження системи - подвійні нерівності, перетворимо їх до більш звичного для подібних завдань увазі , Це
і
, Таким чином перше з отриманих нерівностей
(Або
) Відноситься до умови неотрицательности, а друге
до системи обмежень. Аналогічно,
це
і
.
Т.ч. завдання набуде вигляду
max
,
Замінивши знаки нерівностей на знаки точних рівностей, побудуємо область допустимих рішень по рівняннях прямих:
;
;
;
.
Областю рішень нерівностей є п'ятикутник ABCDE.
Побудуємо вектор . Через початок координат перпендикулярно вектору
проведемо лінію рівня
. І потім будемо переміщати її паралельно самій собі в напрямку вектора
до точки виходу з області допустимих рішень. Це буде точка С. Знайдемо координати цієї точки, розв'язавши систему, що складається з рівнянь першої та четвертої прямих:
.
Підставимо координати точки С в цільову функцію і знайдемо її максимальне значення Приклад. Побудувати лінії рівня
і
для задачі лінійного програмування:
max (min)
Рішення. Область допустимих рішень - відкрита область (рис. 6). Лінія рівня проходить через точку В. Функція Z має мінімум в цій точці. Лінію рівня
побудувати не можна, так як немає точки виходу з області допустимих рішень, це означає, що
.
Завдання для самостійної роботи.
Знайти область рішень системи нерівностей:
а) б)
Вирішити графічно задачу лінійного програмування
min
Скласти економіко-математичну модель і вирішити графічно задачу лінійного програмування
Фірма випускає вироби двох видів А і В. Вироби кожного виду обробляють на двох верстатах (I і II). Час обробки одного виробу кожного виду на верстатах, час роботи верстатів за робочу зміну, прибуток фірми від реалізації одного виробу виду А і виду В занесені в таблицю:
Верстати | Час обробки одного виробу, хв. | Час роботи верстата за зміну, хв. | |