Задача дробово-лінійного програмування. Математична модель задачі дробово-лінійного програмування
У деяких практичних завданнях критерій прийняття рішень описується відношенням двох економічних або технічних параметрів. У таких ситуаціях необхідно приймати рішення з метою максимізації або мінімізації відношення цих двох параметрів. Якщо кожен з них математично описується лінійною функцією, то в таких випадках необхідно знайти екстремум (максимум чи мінімум) відношення цих двох лінійних функцій. Відношення двох лінійних функцій називають дробово-лінійною цільовою функцією. Задача оптимізації дробово-лінійної функції при лінійних обмеженнях називається задачею дробово-лінійного програмування. Як правило, при максимізації відношення двох економічних показників, показник чисельника прагне досягти максимальне можливе значення, а показник знаменника — мінімальне. При мінімізації — навпаки.
Задача нелінійного програмування. Математична модель задачі нелінійного програмування
Досить детально розглянута в розділах, присв'ячених лінійному програмуваню, задача пошуку оптимальних обсягів виробництва грунтується на припущеннях про лінійність зв'язку між витратами ресурсів і обсягами виготовленої продукції; між ціною, рекламою та попитом тощо. Якщо такі зв'язки є нелінійними, то більш адекватні математичні моделі доцільно формулювати в термінах нелінійного програмування.
Нехай для деякої виробничої системи необхідно визначити план випуску продукції, за умови найкращого способу використання ресурсів системи. Відомі загальні запаси кожного ресурсу, норми витрат кожного ресурсу на одиницю продукції та ціна реалізації одиниці виготовленої продукції. Критерії оптимальності можуть бути різноманітними, наприклад максимізація виручки від реалізації продукції. Така умова подається лінійною залежністю загальної виручки від обсягів проданого товару та ціни одиниці продукції.
Однак, загально відомим є факт, що за умов ринкової конкуренції питання реалізації продукції є досить складним. Обсяг збуту кінцевої продукції визначається перш за все її ціною, отже в якості цільової функції доцільно розглядати максимізацію не всієї виготовленої, а лише реалізованої продукції. Тоді необхідно визначити також і оптимальне значення ціни одиниці продукції, при якій обсяг збуту буде максимальним. Для цього, її потрібно ввести в задачу як невідому величину, при цьому обмеження задачі мають враховувати зв'язки між ціною, рекламою та обсягами збутої продукції. Цільова функція міститиме добуток двох невідомих величин (оптимальна ціна одиниці продукції та оптимальна кількість відповідного виду продукції), а отже є нелінійною. Таким чином приходимо до задачі нелінійного програмування.
Розв'язок задачі цілочисельного програмування графічним методом
Графічний метод для розв'язку задачі цілочисельного програмування доцільно використовувати в тому випадку, коли число невідомих в задачі такого типу дорівнює двом. Перший крок при використанні графічного методу полягає в побудові багатокутника розв'язків без урахування умови цілочисельності. Далі, виходячи з того, що умову цілочисельності змінних задовольняють не всі координати точок області допустимих рішень, замінимо область допустимих рішень ослабленої задачі (без умови цілочисельності) на опуклий багатокутник, що містить тільки допустимі точки з цілочисельними координатами. Після цього, для того, щоб знайти максимум або мінімум цільової функції на опуклій області, як і у випадку задачі лінійного програмування, будують вектор градієнт 
. Далі, пересуваючи пряму 
в напрямку вектора 
, знаходимо точку, в якій цільова функція приймає оптимальне значення. Потім визначаємо координати точки екстремуму функції і обчислюємо значення цільової функції в цій точці.
Метод Гоморі. Приклад розв'язку задачі цілочисельного програмування методом Гоморі
Розглянемо приклад знаходження розв'язку задачі цілочисельного програмування використовуючи метод Гоморі. Отже, для виготовлення товару A і В підприємство використовує два види сировини. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A та B, а також загальна кількість сировини наведені в наступній таблиці:
Таблиця даних задачі цілочисельного програмування
Необхідно скласти такий план випуску даної продукції, щоб прибуток від її реалізації був максимальним.
Лінійне програмування. Постановка задачі лінійного програмування
Лінійне програмування має вигляд лінійної математичної моделі, яка складається з трьох частин:
- Функції мети для якої знаходимо оптимальне значення
де
— апибуток від реалізації однієї i-ї продукції, а 
— кількість даної продукції. Якщо в (1) змінити знаки коефіццієнтів 
на протилежні, то функція 
змінюється на 
і навпаки. - Обмеження по запасу ресурсів:
де
— нориа витрат i-го ресурсу; 
— кількість продукції j-го виду, випуск одиниці якої потребує витрат, також слід зазначити, що виличина не повинна бути від'ємною; 
— запаси i-го ресурсу; i=1,...,m — порядковий номер ресурсу; j=1,...,n — порядковий номер продукції.
Метод Гоморі (метод відсікаючих площин)
Метод відсікаючих площин існує у двох варіантах: перший варіант призначений для розв'язку повністю цілочисельних задач (перший алгоритм Гоморі) і другий варіант — призначений для розв'язку частково цілочисельних задач (другий алгоритм Гоморі). Основна відмінність між ними полягає у способі формування відсікання.
Алгоритм знаходження розв'язку методом Гоморі для цілком цілочисельних задач нпступний:
- Лінійна задача розв'язується класичним симплекс-методом, без врахування цілочисельності змінних
. В результаті отримують деякий оптимальний опорний план, який має наступний вигляд:
- Якщо (1) містить рівняння для яких базисниі змінні
мають дробові значення, то серед них обирають таке рівняння, яке має найбільшу дробову частину. Дане рівняння перетворюють у додаткову нерівність:
де
.
Для обрання чисел 
та 
існують наступні правила:
Загрузка ...