Лінійне програмування

1 Сутність лінійного програмування

2. Загальна задача лінійного програмування

3. Методи лінійного програмування

Лінійного програмування - один із самих потужних інструментів, що застосовуються у сфері управління бізнесом.

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

Лінійне програмуванняLP, англ. Linear Programming) - метод досягнення найкращого виходу (цілі) у математичній моделі чиї вимоги представлені через лінійні відношення.

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

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

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

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

2.2 Загальна задача лінійного програмування

Задача, у якій потрібно знайти найбільше (найменше)значення цільової функції:

де c _j (j = 1, …, n), a _ij(i = 1, …, m) — задані числа.

Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіцієнтів c _j на протилежні.

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

Для вирішення задачі методом лінійного програмування необхідно, щоб описана в ній ситуація відповідала п'яти основним умовам:

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

2. Необхідно сформулювати точну ціль (максимізація прибутку чи мінімізація витрат).

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

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

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

Дата добавления: 2015-11-16