Математика/5. Математичне моделювання

Коваленко С.М.

Харківський національний технічний університет сільського господарства ім.. Петра Василенка

Реалізація математичних моделей комбінаторних задач прийняття рішень

Розглядаються питання побудови структури та складу обчислювальних блоків для апаратурної реалізації математичних моделей задач комбінаторної оптимізації, які мають місце, наприклад, при прийнятті рішень в агропромисловому комплексі. Такі специфічні задачі виникають при формуванні комплексів сільгоспмашин, призначенні сільгосптехніки на виконання польових робіт, плануванні черговості сівозмін сільгоспкультур, вибору технології вирощування сільгоспкультур тощо [1 – 4].

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

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

Загальна структура апаратурної реалізації комбінаторних задач такого типу наведена на рис. Вона складається з наступних основних обчислювальних блоків: генератора 1 тактових імпульсів; елемента 2 затримки; інформаційного регістра 3; постійної пам’яті 4; регістра 5 зсуву; лічильника 6; блока 7 пам’яті;

блока 8 збігу; блока 9 розрахунку функції мети; блока 10 виділення екстремального значення; блока 11 реєстрації; блока 12 введення інформації.

При цьому, початкова інформація про обмеження на елементи комбінаторної множини (сполучення, розміщення або перестановки) вводиться блоком 12 вводу інформації до блоку 7 пам’яті.

Генератор 1 тактових імпульсів забезпечує подачу імпульсів до регістру 5 зсуву, через елемент 2 затримки до інформаційного регістру 3, та через лічильник 6 до блоку 7 постійної пам’яті. Крім того, лічильник 6 забезпечує подачу з блоку 7 пам’яті до блоку 8 збігу усіх елементів комбінаторної множини, заборонених наперед заданими обмеженнями.

Регістр 5 зсуву, блок 4 постійної пам’яті та інформаційний регістр 3 забезпечують генерування та подачу до блоку 8 збігу або n! перестановок з n елементів, або генерування розміщень , або генерування сполучень (залежно від задачі, що розв'язується) [1, с. 120].

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

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

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

Зауважимо, що у якості блока перебору сполучень, розміщень або перестановок можливо застосувати відповідний пристрій [4].

Література

1. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. – Москва: Радио и связь. 1990. – 120 с.

2. Патент. № 47901 А. Україна, МКИ А 01 В 49/00. Спосіб визначення раціонального складу агрегатів для польових робіт / В.І. Пастухов, В.П. Путятін (Україна). – № 2001107159; Заявл. 22.10.2001; Опубл. 15.07.2002. Бюл. № 7. – 3 с.

3. Патент. № 48638 А. Україна, МКИ G 06 F 15/00. Пристрій для моделювання графа агротехнологічного процесу / В.І. Пастухов, В.П. Путятін (Україна). – № 2001107373; Заявл. 30.10.2001; Опубл. 15.08.2002. Бюл. № 8. – 3 с.

4. Авт. св. № 643883 СССР, МКИ G 06 F 15/20. Устройство для перебора сочетаний, размещений и перестановок / Левин Г.И. (СССР) – № 2439332/18-24; Заявл. 10.01.1977; Опубл. 28.01.1979. Бюл. № 3 – 4 с.