Види завдань лінійного програмування

Лінійне програмування - метод вирішення завдань оптимізації.

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

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

Функція мети в задачі лінійного програмування зазвичай записується так:

.

Або в скороченому вигляді з сигмою:

.

Можна зустріти позначення цільової функції і через C, і через F.

Система обмежень в задачі лінійного програмування в канонічної формі записується так:

.

Або в скороченому вигляді:

І система обмежень, і цільова функція мають лінійний характер, тобто містять змінні тільки в першого ступеня.

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

Завданням лінійного програмування в стандартній, або, як кажуть інакше, нормальної формі, називається задача, в якій потрібно знайти максимум цільової функції при обмеженнях, заданих системою нерівностей одного сенсу, тобто з однаковим знаком, і цей знак - "менше або дорівнює", причому діє також умова невід'ємності змінних. Якщо в задачі лінійного програмування, заданої в стандартній формі, потрібно знайти мінімум цільової функції, то система обмежень складається з системи нерівностей зі знаком "більше або дорівнює".

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

Якщо всі або деякі обмеження в системі задані нерівностями, то завдання можна звести до канонічної шляхом перетворення нерівностей в рівняння.

Безліч чисел (запис послідовності іксів), що задовольняють системі обмежень, називається рішенням цієї системи. Рішення системи також часто називається планом, і трохи рідше - програмою, але саме звідси і пішла назва «лінійне програмування».

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

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

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

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

Розберемо кілька типів економічних завдань і запишемо їх у вигляді математичних співвідношень. Або, інакше кажучи, побудуємо математичну модель предметної області.

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

Цільова функція. Її потрібно максимізувати або мінімізувати. Для того, щоб функцію максимізувати, змінні, які є її складовими, повинні приймати якомога більші значення відповідно до умов завдання. При мінімізації - навпаки, менші. Зазвичай цільова функція висловлює доходи або витрати.

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

Обмеження. Дуже просто. Наприклад, в кожному рівнянні (нерівності) задані обмеження перерахованих вище або інших запасів, які використовуються для виробництва певного виду продукції.

Приклад 1. Схема завдання використання сировини.

Сформулювати для вирішення як завдання лінійного програмування наступне завдання.

Для виготовлення двох видів продукції і потрібно чотири види ресурсів (сировини): , , , . Запаси сировини - відповідно , , , одиниці.

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

Рішення. Для зручності спочатку всі дані запишемо у вигляді таблиці:

Тоді на підставі таблиці запишуться нерівності (обмеження):

Справді, для виготовлення кожної одиниці продукції необхідно одиниць сировини , А для виготовлення одиниць потрібно одиниць сировини . Для виготовлення одиниць продукції потрібно одиниць сировини . Так як запаси сировини складають , То витрата не може перевищувати . В результаті отримаємо першу нерівність:

З інших рядків таблиці складемо ще 3 нерівності системи.

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

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

На сайті є Онлайн калькулятор вирішення завдань лінійного програмування симплекс-методом .

Приклад 2. Схема завдання про сумішах.

Сформулювати для вирішення як завдання лінійного програмування наступне завдання.

Потрібно знайти найбільш дешевий набір з доступних вихідних матеріалів, що забезпечують отримання суміші із заданими властивостями. Отримані суміші повинні мати в свойм складі n різних компонент в певних кількостях, а самі компоненти є складовими частинами m вихідних матеріалів. Для спрощення приймемо, що n = 3 і m = 4. Нехай вартість однієї одиниці матеріалу відповідно становить , , , . У свою чергу необхідну кількість кожної з компонент в суміші становить відповідно , , .

Рішення. Будуємо таблицю:

Коефіцієнти показують кількість j -й компоненти в одиниці i -го матеріалу. Потрібно забрати суміш із заданими властивостями при найменших витратах на придбання матеріалів.

Запишемо задачу у вигляді математичних співвідношень. Позначимо через кількість матеріалів i-го виду, що входить в суміш. Тоді задача зведеться до відшукання мінімуму функції

при обмеженнях

Одним з окремих випадків спільної справи про сумішах служить завдання про харчування. До неї зараз же і перейдемо.

На сайті є Онлайн калькулятор вирішення завдань лінійного програмування симплекс-методом .

Приклад 3. Схема завдання про харчування.

Сформулювати для вирішення як завдання лінійного програмування наступне завдання.

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

Рішення. Будуємо таблицю:

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

Запишемо задачу у вигляді математичних співвідношень. У задачі невідомо кількість кожного виду продукту. Тому позначимо кількість продукту буквою , Кількість продукту - буквою , Кількість продукту - буквою .

Отримаємо систему нерівностей (обмежень):

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

На сайті є Онлайн калькулятор вирішення завдань лінійного програмування симплекс-методом .

Приклад 4. Схема завдання про використання потужностей обладнання.

Сформулювати для вирішення як завдання лінійного програмування наступне завдання.

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

Потужність машин задана наступною таблицею:

У цій таблиці - кількість одиниць продукції, що виробляється за одиницю часу.

Ціна однієї одиниці робочого часу на виготовлення однієї одиниці продукції на кожній машині задана наступною таблицею:

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

Запишемо задачу у вигляді математичних співвідношень. Невідомим є час завантаження машин по виробництву продукції. позначимо через час завантаження машини по виготовленню продукції, через - час завантаження машини по виготовленню продукції. аналогічно - час завантаження машини по виготовленню продукції, - час завантаження машини по виготовленню продукції, - час завантаження машини по виготовленню продукції, час завантаження машини по виготовленню продукції.

Машини працюють одночасно, значить якщо позначимо час одночасної роботи всіх трьох машин буквою, то отримаємо систему нерівностей:

Машина виготовленням продукції зайнята одиниці часу на одиниці продукції. Машина виготовленням зайнята одиниці часу по одиниці продукції.

Аналогічно машина виготовленням зайнята одиниці часу, по одиниці продукції і т.д. Всього потрібно одиниць продукції і одиниці.

Тобто отримуємо ще одну систему:

Тоді загальна вартість всієї продукції запишеться у вигляді рівності:

.

Остаточно отримуємо систему обмежень, що складається з співвідношень:

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

Приклад 5. Транспортна задача (схема).

Сформулювати для вирішення як завдання лінійного програмування наступне завдання.

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

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

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

Запишемо задачу у вигляді математичних співвідношень. Кількість одиниць вантажу, що відправляються з пункту в пункт , позначимо і складемо матрицю перевезень (таблицю):

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

Тоді система обмежень запишеться у вигляді рівнянь:

Мета завдання - знайти невід'ємне рішення системи рівнянь, при якому функція мети була мінімальною.

На сайті є стаття, присвячена вирішенню транспортної задачі розподільчим методом .

У більшості завдань лінійного програмування обмеження задаються не у вигляді системи рівнянь, а в вигляді системи лінійних нерівностей, причому можливі різні форми таких систем: ліва частина менше або дорівнює (менше) правої, ліва частина більше або дорівнює (більше) правої. Крім того, система обмежень може бути змішаною: частина обмежень нерівності першого з вищезгаданих типів, частини - другого типу, а частина задана у вигляді рівнянь.

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

Приклад 6. Записати систему нерівностей

у вигляді рівнянь для приведення завдання лінійного програмування до канонічної.

Рішення. Додаючи до лівих частинах нерівностей по одній додатковій змінної, отримаємо систему рівнянь:

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

На сайті є Онлайн калькулятор вирішення завдань лінійного програмування симплекс-методом .

На нашому сайті також наведено приклади розв'язання задач лінійного програмування графічним методом без зведення задачі до канонічної і симплекс-методом з попередніми зведенням завдання до канонічної .

Щоб знайти оптимальне рішення серед безлічі допустимих рішень системи обмежень в задачі лінійного програмування будь-якого виду, знадобиться ряд теорем, до розгляду яких ми і переходимо.

Теорема 1. Безліч всіх допустимих рішень системи обмежень задачі лінійного програмування є опуклим.

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

Про те, що таке опуклі безлічі - на уроці Системи лінійних нерівностей і опуклі безлічі точок .

Теорема 2. Якщо існує, і до того ж єдине, оптимальне рішення задачі лінійного програмування, то воно збігається з однією з кутових точок безлічі допустимих рішень.

Ця теорема дозволяє зробити висновок, що пошуки оптимального рішення можна обмежити перебором кінцевого числа кутових точок. Однак для відшукання кутових точок потрібна побудова області рішень системи обмежень. Це побудова можливо тільки для двох-або тривимірного простору, а в загальному випадку задача залишається нерозв'язною. Отже, потрібно мати у своєму розпорядженні якимось аналітичним методом, що дозволяє знаходити координати кутових точок. Для цього знадобляться наступні дві теореми.

Теорема 3. Кожному допустимому базисного вирішення завдання лінійного програмування відповідає кутова точка області допустимих рішень системи обмежень.

Теорема 4 (зворотна). Кожній кутовій точці безлічі допустимих рішень системи обмежень відповідає допустимий базисний розв'язок.

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

Справедливість цього твердження випливає з теорем 2 і 4.

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

Продовження теми "Лінійне програмування"

Поділитися з друзями