3.Спеціальні задачі лінійного програмування та їх застосування в менеджменті (цілочислове програмування, параметричне програмування).
Цілочислові задачі лінійного програмування — задачі математичного програмування, в яких крім умови цілочисловості всі обмеження та цільова функція є лінійними.
Існує доволі широке коло задач математичного програмування, в економіко-математичних моделях яких одна або кілька змінних мають набувати цілих значень. Наприклад, коли йдеться про кількість верстатів у цеху, тварин у сільськогосподарських підприємствах тощо.
Зустрічаються також задачі, які з першого погляду не мають нічого спільного з цілочисловими моделями, проте формулюються як задачі цілочислового програмування. Вимоги дискретності змінних в явній чи неявній формах притаманні таким практичним задачам, як вибір послідовності виробничих процесів; календарне планування роботи підприємства; планування та забезпечення матеріально-технічного постачання, розміщення підприємств, розподіл капіталовкладень, планування використання обладнання тощо.
Параметричне програмування — це метод визначення залежності змін розв’язку задачі від зміни вектора коефіцієнтів цільової функції чи вектора обмежень.
4.Особливі задачі лінійного програмування в маркетингу. Задача прикріплення споживачів до постачальників.
Основною математичною моделлю оптимального прикріплення споживачів до постачальників є так звана транспортна задача лінійного програмування, яка в загальному виді формулюється в такий спосіб:
У т пунктах відправлення (А1, А2 ... Ат), які надалі будемо називати постачальниками, зосереджена певна кількість одиниць некоторогооднородного продукту, яке позначимо ai (i = 1, 2 ... m).
Даний продукт споживається в n пунктах (В1, B2 ... Вn), які будемо називати споживачами; об'єм споживання позначимо через bj (j = 1, 2 ... n).
Відомі витрати на перевезення одиниці продукту з пункту Аi у пункт Вj, які рівні cij і наведені в матриці транспортних витрат З = (сij).
Потрібно скласти такий план прикріплення споживачів до постачальників ( інакше кажучи, план перевезень), при якому весь продукт вивозиться з пунктів Ai у пункти Bj відповідно до потреби й загальна величина транспортних витрат мінімальна.
Позначимо
кількість продукту, перевезеного з
пункту Ai
у
пункт Bj,
через
Хij.
Сукупність
усіх змінних хij
для
стислості позначимо символом
,
тоді
цільова функція задачі придбає вид:
А обмеження виглядають у такий спосіб:
Умови (25.31) означають повне задоволення попиту у всіх пунктах споживання; умови (25.30) визначають більший вивіз продукції від усіх постачальників.
Необхідною й достатньою умовою можливості розв'язання задачі (25.29) – (25.31) є умова балансу:
.
5.Методи планування та управління мережами. Задача комівояжера.
Тут потрібно відшукати найкращий маршрут, для того щоб об'їхати всі доручені комівояжерові пункти й повернутися назад або в найкоротший строк, або з найменшими витратами на проїзд. У загальному виді цю задачу можна сформулювати в такий спосіб.
Є
п
міст,
занумерованих числами від 1 до п.
Комівояжер,
виїжджаючи з міста 1, повинен побувати
в кожному місті рівно один раз і
повернутися у вихідний пункт. Відомі
відстані між містами: сij
(i,
j
=
;
i ≠
j). Потрібно
знайти самий короткий маршрут.
Уведемо змінні:
Вимоги однократного в'їзду й виїзду з кожного міста запишуться у вигляді:
Однак ці обмеження повністю не описують припустимі маршрути, тому що не виключають можливості розриву шляхи, тобто появи декількох не зв'язаних між собою подмаршрутов для частини міст. Тому вводяться додатково змінних Ui, які ухвалюють тільки цілі ненегативні значення. Тоді можна записати ще (n – 1)2 – (n – 1) обмежень:
Неважко показати, що обмеження (25.48) не виключають припустимий маршрут, але виключають можливість існування подмаршрутов.
Таким чином, задача про комівояжера полягає в мінімізації:
Це дійсно при умовах (25.47), (25.48), де змінні xij, Ui ухвалюють тільки ненегативні цілі значення.