Ви є тут

Властивості математичних моделей задач з дробово-лінійною цільовою функцією на розміщеннях та методи їх розв'язування

Автор: 
Черненко Оксана Олексіївна
Тип роботи: 
Дис. канд. наук
Рік: 
2007
Артикул:
0407U001361
129 грн
Додати в кошик

Вміст

РОЗДІЛ 2
МОДЕЛЮВАННЯ ДЕЯКИХ ПРИКЛАДНИХ ЗАДАЧ ЯК ЗАДАЧ З ДРОБОВО-ЛІНІЙНОЮ ЦІЛЬОВОЮ ФУНКЦІЄЮ НА ЗАГАЛЬНІЙ МНОЖИНІ РОЗМІЩЕНЬ
Задачі з дробово-лінійною цільовою функцією без комбінаторних обмежень та методи їх розв'язування розглядалися у багатьох роботах (див., наприклад, [151, 152, 154, 155]). Однак досліджені моделі не завжди в повній мірі відображають властивості задач, або їх адекватний зміст. У ряді прикладів множини допустимих розв'язків задачі мають і інші властивості (зокрема, властивість бути розміщенням з деякої множини), тоді задачу можна розглядати як комбінаторну на множині розміщень. Такі задачі оптимізації на загальній множині розміщень з дробово-лінійною функцією цілі ще не розглядалися, а тому залишаються не дослідженими.
У даному розділі побудовано математичні моделі деяких прикладних задач з дробово-лінійною цільовою функцією на розміщеннях. Такі задачі мають практичне застосування і відіграють важливу роль у виробництві, а тому актуальними є їх дослідження та розв'язування.
2.1. Задачі визначення рентабельності виробництва

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

за комбінаторної умови
та додаткових лінійних обмеженнях:
на посівні площі
на використання ресурсів
на обсяг одержуваної продукції
Задача 1 розглядалася в роботі [132] з лінійною цільовою функцією, і в роботах [81, 104] з дробово-лінійною функцією цілі на загальній множині переставлень.
Задача 2 (про порядок обслуговування частини елементів замовлення для максимізації рентабельності системи обслуговування). Система обслуговування, яка складається з приладів, виконує замовлення, що включає елементів. Замовлення вважається виконаним, якщо виконано елементів замовлення . Відомо, що перший прилад виконує елементів замовлення, другий - елементів і т. д., причому . Елемент замовлення з номером виконується якимсь одним приладом за час . Відомо, що витрати системи, які не залежать від елементу замовлення, дорівнюють , витрати на використання -го приладу становлять на одиницю часу. Продуктивність використання - го приладу на одиницю часу - , - прибуток (збиток), що не залежить від елементу замовлення. Необхідно виконати замовлення, що не перевищує за часом та не менше для кожного приладу , .
Визначити, які елементи замовлення та на яких приладах повинні бути виконані, щоб рентабельність системи обслуговування була максимальною.
Побудуємо математичну модель даної задачі.
Нехай - мультимножина, кожен елемент якої є час виконання елементу замовлення. Всі можливі k-вибірки з мультимножини утворюють загальну множину розміщень , де - число різних серед елементів . Позначимо - час, який витрачається на виконання -го елементу замовлення на -ому приладі.
Тоді математична модель задачі така: знайти впорядковану пару таку, що

за комбінаторної умови
,

та додаткових лінійних обмеженнях на використання часу
.

Модель подібної задачі з лінійною цільовою функцією побудована в [22], з дробово-лінійною цільовою функцією на загальній множині переставлень у роботі [104].

2.2. Задачі мінімізації питомих витрат виробництва
Задача 3 (про вибір технологій для мінімізації питомих витрат виробництва продукції). Нехай маємо видів продукції, що споживається, та s технологічних способів для її виробництва (). Відомі:
* tij - час виготовлення i-ої продукції -им технологічним способом;
* сij - витрати за одиницю часу на виготовлення i-ої продукції -им технологічним способом;
* - витрати, що не залежать від плану виробництва;
* dij - прибуток від реалізації i-ої продукції -им технологічним способом;
* - кількість видів продукції, яка може не виговлятися ().
Потрібно визначити розподіл продукції по технологіям, щоб витрати на її виробництво віднесені до прибутку були мінімальними.
Розглянемо мультимножину G ={1,..., 1, 0, ...0}, яка має - одиниць та -нулів, де елементи G - це булеві змінні, тоді - множина розміщень елементів з мультимножини G, де sm - число елементів у розміщенні. Введемо змінну , яка визначається наступною умовою:
Вектор - розміщення елементів з мультимножини G.
Маємо модель: знайти упорядковану пару таку, що
, ,
за умови
та при лінійних обмеж