Математичні моделі та методи розв’язання задач комбінаторної оптимізації в агротехнічній системі

Размещено на http://www.allbest.ru/

ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

РАДІОЕЛЕКТРОНІКИ

УДК 519.15:001.57

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Математичні моделі та методи розв'язання задач комбінаторної оптимізації в агротехнічній системі

1.05.02 - математичне моделювання та обчислювальні методи

Коваленко Світлана Миколаївна

Харків - 2008

Дисертацією є рукопис.

Робота виконана в Харківському національному технічному університеті сільського господарства ім. П. Василенка, Міністерство аграрної політики України.

Науковий керівник: доктор технічних наук, професор

Путятін Валерій Петрович, Харківський

національний технічний університет сільського

господарства ім. П. Василенка

Міністерства аграрної політики України,

завідувач кафедри кібернетики.

Офіційні опоненти: доктор фізико-математичних наук, професор

Смеляков Сергій Вячеславович,

Харківський університет повітряних сил ім. Івана Кожедуба Міністерства оборони України, професор кафедри математичного та програмного забезпечення АСУ;

доктор технічних наук, професор

Комяк Валентина Михайлівна,

Університет цивільного захисту України

Міністерства України з питань надзвичайних ситуацій та у справах захисту населення від наслідків Чорнобильської катастрофи,

професор кафедри фізико-математичних дисциплін.

Захист відбудеться «_21_»_жовтня_2008 р. о 15⁰⁰ годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському національному університеті радіоелектроніки Міністерства освіти і науки України за адресою: пр. Леніна 14, м. Харків, 61166.

З дисертацією можна ознайомитись в бібліотеці Харківського національного університету радіоелектроніки Міністерства освіти і науки України за адресою: пр. Леніна 14, м. Харків, 61166.

Автореферат розісланий «_18_» __вересня__ 2008 р.

Вчений секретар спеціалізованої вченої ради Безкоровайний В.В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Всебічному теоретичному дослідженню математичних моделей задач комбінаторної оптимізації та розробці методів їх чисельної реалізації присвячені роботи Ю.Г. Стояна, В.С. Міхалевича, І.В. Сергієнка, Н.З. Шора, С.В. Яковлева, О.А. Ємця, В.М. Комяк, С.В. Смелякова, І.В. Гребенніка. Створенню програмно-апаратних засобів та спеціалізованих обчислювальних процесорів для зменшення витрат часу і підвищення точності реалізації математичних моделей задач комбінаторної оптимізації присвячені роботи Ю.Г. Стояна, В.В. Васильєва, Ю.М. Мацевітого, В.П. Путятіна, В.М. Курейчика.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконана згідно з: Програмою «Виробництво технологічних комплексів машин і обладнання для агропромислового комплексу в 1998 - 2005 роках», розробленою відповідно до Постанови Кабінету Міністрів від 01.12.1997 р., № 1341; Комплексною програмою розвитку сільського господарства Харківської області в 2001 - 2005 роках і на період до 2010 року; НДР «Розробка і впровадження у виробництво енергозберігаючих, екологічнобезпечних технологічних систем в рослинництві», ДР № 0106U991213. При виконанні цих НДР автором розроблено та впроваджено комплекс математичних моделей та програмне забезпечення для підтримки прийняття рішень при плануванні функціонування агротехнічних систем.

Мета і задачі дослідження. Метою дослідження є розробка нових і адаптація, з урахуванням особливостей предметної області, існуючих математичних моделей задач комбінаторної оптимізації з обмеженнями на елементи комбінаторних множин у вигляді переваг, нерівностей та рівностей; підвищення ефективності (за часом та точністю) реалізації математичних моделей на програмному та програмно-апаратному рівнях.

Для цього в роботі поставлені такі основні задачі:

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

- запропонувати математичну модель ООЗ і дослідити її специфічні особливості, що зумовлені особливостями предметної області (агротехнічною системою) та впливають на вибір методу її реалізації;

- формалізувати базові прикладні задачі комбінаторної оптимізації, запропонувати їх математичні моделі й дослідити особливості;

- запропонувати ефективні (за часом і точністю) чисельні методи реалізації математичних моделей базових задач комбінаторної оптимізації;

- здійснити апробацію запропонованих чисельних методів під час розв'язання прикладних задач комбінаторної оптимізації з обмеженнями на елементи комбінаторних множин у вигляді переваг, нерівностей та рівностей;

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

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

Предмет дослідження - математичні моделі прикладних задач комбінаторної оптимізації та методи чисельної й програмно-апаратної реалізації для підтримки прийняття раціональних проектних рішень в агротехнічній системі. прикладний задача комбінаторний оптимізація

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

Наукова новизна отриманих результатів.

1. Отримали подальший розвиток методи математичного моделювання прикладних задач комбінаторної оптимізації з обмеженнями на елементи комбінаторних множин у вигляді переваг, нерівностей та рівностей; наявністю параметрів, що характеризують природно-кліматичні умови регіону і змінні умови попиту та пропозиції продукції. Це дало можливість врахувати специфіку різноманітних задач комбінаторної оптимізації, що виникають в агротехнічній системі: пошук раціональної сівозміни з урахуванням попередників і природно-кліматичних умов, формування комплексів сільгоспмашин для виконання технологічних операцій в агротехнічній системі та ін.

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

3. Отримали подальший розвиток методи математичного моделювання базових задач комбінаторної оптимізації, що являють собою окремі випадки основної оптимізаційної задачі, після її розбиття на підзадачі. Для розв'язання базових задач досліджені межі застосовності методу повного перебору при пошуку глобального екстремуму, а також питання часових витрат залежно від характеристик ПЕОМ, що використовуються.

4. Вперше запропоновано й обґрунтовано модифікацію пошукового методу комбінаторної оптимізації, що враховує специфіку математичних моделей та базується на композиції чисельних методів, що послідовно застосовуються: випадкового пошуку; околів, що звужуються; вектора спаду. Досліджено відносні й абсолютні похибки цього методу в різні моменти часу обчислювального процесу. Отримано рекомендацію щодо того, що для задач, з кількістю елементів комбінаторних з'єднань k>13! доцільно замість методу повного перебору використовувати композицію методів комбінаторної оптимізації.

Практичне значення отриманих результатів. Запропоновані в роботі математичні моделі, методи й засоби для їх реалізації дають можливість організації системи підтримки прийняття рішень на базі розроблених математичних моделей, чисельних методів їх реалізації і програмно-апаратних засобів, що дозволяє зменшити на 15% загальні витрати часу на прийняття рішення (акт впровадження від 12.09.2007 в додатку В); створення спеціалізованих обчислювальних процесорів, які дозволяють зменшити часові витрати на формування одного варіанту системи в n разів, де n - кількість дискретних елементів системи; аналізу більшої кількості варіантів системи, що підвищує точність реалізації математичної моделі й дозволяє організувати процес автоматизації дослідження властивостей математичних моделей та методів їх реалізації (акти впровадження від 31.05.2007 та 12.09.2007 в додатках А, В); планування сівозмін сільськогосподарських культур на декілька років уперед, з урахуванням варіантів сівозмін попередніх років і варіантів технічних засобів, що застосовуються, що дозволяє на 10% зменшити часові витрати на прийняття рішення в агротехнічній системі (акт впровадження від 12.09.2007 в додатку В).

Впровадження результатів дисертаційної роботи здійснено в Науково-дослідному технологічному інституті Харківського національного технічного університету сільського господарства ім. П. Василенка (акт впровадження від 31.05.2007 в додатку А, довідка про особистий внесок в додатку Б); в Науково-виробничій і експлуатаційній фірмі «СТОЗІ» (акт впровадження від 12.09.2007 в додатку В); в навчальний процес Харківського національного технічного університету сільського господарства ім. П. Василенка (акт впровадження від 22.10.07 в додатку Д).

Особистий внесок здобувача. Результати, опубліковані в роботах [3, 4, 9 - 12], отримані особисто здобувачем і опубліковані без співавторів. У роботі [1] автором запропоновано апаратну реалізацію математичних моделей задач комбінаторної оптимізації, зокрема, селекцію елементів комбінаторних множин і виділення допустимих елементів відповідних множин. У роботі [2] особисто автором запропоновано математичну модель основної оптимізаційної задачі й досліджено її особливості. У роботі [5] автором розглянуто питання формування й аналізу комбінаторних множин для систем автоматизації проектних робіт в АПК. У патенті [6] на корисну модель автором запропоновано спосіб і його реалізацію для формування множини допустимих елементів комбінаторних множин за заданою системою обмежень. У патенті [7] на корисну модель запропоновано апаратну реалізацію способу селекції елементів комбінаторної множини за заданою системою обмежень. У патенті [8] на корисну модель автором запропоновано апаратну реалізацію математичної моделі задачі комбінаторної оптимізації з обмеженнями при застосуванні до оптимізації аграрної системи.

Апробація результатів дисертації. Основні результати роботи доповідалися й обговорювалися на: Міжнародному малому салоні винаходів і нових технологій, Севастополь, 29 - 31 травня 2007 р. (отримано два дипломи і дві срібні медалі за патенти № 21495 «Спосіб виділення допустимих елементів комбінаторних множин» [6] і № 21588 «Селектор елементів комбінаторних множин» [7]); 10-му ювілейному Міжнародному молодіжному форумі «Радіоелектроніка і молодь в XXI сторіччі», Харків, Харківський національний університет радіоелектроніки, 10 - 12 квітня 2006 р.; Всеукраїнській науково-практичній конференції «Комп'ютерне моделювання і інформаційні технології в економіці», Харків, Харківський національний економічний університет, 16 - 17 листопада 2006 р.; ІІ Міжнародній науково-практичній конференції «Сучасні наукові досягнення - 2007», Дніпропетровськ, 01 - 14 лютого 2007 р.; 11 Міжнародному молодіжному форумі «Радіоелектроніка і молодь в XXI сторіччі», Харків, Харківський національний університет радіоелектроніки, 10 - 12 квітня 2007 р.; Міжнародному Форумі молодих вчених «Ринкова трансформація економіки: стан, проблеми, перспективи», Харків, Харківський національний технічний університет сільського господарства ім. П. Василенка, 19 - 20 квітня 2007 р.; Всеукраїнській науково-практичній конференції «Інформатизація бізнесу очима молодих: наука, бізнес, підприємництво», Харків, Харківський національний економічний університет, 17 - 18 травня 2007 р.

Публікації. За темою дисертації опубліковано 12 робіт, у тому числі три публікації [1 - 3] у виданнях, що входять до переліків фахових видань, затверджених ВАК України, три патенти України [6 - 8] на корисні моделі. Публікації [4, 5, 9 - 12] - матеріали і тези конференцій.

Структура роботи. Дисертація складається із вступу, 5 розділів, висновків, списку використаних джерел і 4 додатків на 4 сторінках. Загальний обсяг дисертації 142 стор., у тому числі 12 рисунків (8 сторінок), 8 таблиць (2 сторінки), список із 122 використаних джерел на 13 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

Тоді, при різних значеннях кліматичних параметрів , що задаються, потрібно визначити

,(1)

.(2)

Відзначимо, що задаючи в моделі (1) - (2) різні значення вектора , а потім вирішуючи серію відповідних задач, здійснюють імітацію різних кліматичних ситуацій в екологічній підсистемі і оцінку результатів землеробства. Рішенням задачі (1) - (2) буде кортеж

, (3)

куди входять: раціональний елемент комбінаторної множини ; значення критерію ; вектор значень частинних критеріїв ; вектор значень кліматичних параметрів, раніше заданих в моделі (1) - (2).

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

Запропоновано укрупнену схему (рис. 1) основних етапів реалізації математичної моделі (1) - (2) основної оптимізаційної задачі, що покладено в основу чисельних та апаратних реалізацій математичних моделей задач комбінаторної оптимізації в застосуванні до агротехнічної системи.

Розділ 3. Математичні моделі базових задач комбінаторної оптимізації. Запропоновано підхід до розбиття основної оптимізаційної задачі на базові задачі за принципом фізичного значення шуканих параметрів. Це дозволяє перейти до розв'язання серії задач із меншою розмірністю.

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

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

Наведемо приклад однієї із семи розглянутих у роботі базових задач комбінаторної оптимізації агротехнічної системи (задача 3.1), і розглянемо її математичну модель (модель 3.1). Маємо m культур і n полів, де - площа i-го поля, і нехай при цьому . Відомо, які культури були висаджені на кожному з полів у поточному році (тобто для кожної культури відомі культури-попередники). На кожному полі може висіватися тільки одна культура. Необхідно побудувати сівозміну наступного року або на k років вперед. При побудові сівозміни необхідно дотримуватиcя рекомендацій аграрної науки щодо чергування культур у сівозміні. Крім того, необхідно передбачити можливість імітації різних природно-кліматичних і погодних умов обробітку сільськогосподарських культур. Зокрема, орієнтуватися на розгляд таких основних умов (варіантів) землеробства: середньостатистичні погодні умови; відмінні, хороші, задовільні і незадовільні погодні умови. При цьому зі всіх можливих варіантів сівозміни потрібно вибрати той, який забезпечує максимум функції мети. Функцією мети для цього класу задач є прибуток від реалізації продукції рослинництва.

Модель 3.1 задачі 3.1. Нехай є культур і полів, і при цьому . На поле з номером призначається культура з номером .

Введемо перестановку

; , (4)

де .

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

Оскільки одна культура призначається на одне поле, а кожному полю відводиться тільки одна культура, то необхідним є виконання таких обмежень:

.(5)

Крім того, облік сівозмін попередніх років потребує виключення з множини тих перестановок , які є неприпустимими з погляду аграрної науки. Ці умови можуть задаватися такими обмеженнями:

.(6)

На елементи області допустимих рішень можуть накладатися додаткові умови у вигляді переваги одних елементів комбінаторної множини над іншими. У цьому випадку

, якщо ,(7)

де - критерій переваги;

- операція переваги.

Таким чином, для випадку, що розглядається, область допустимих рішень описується системою обмежень (5 - 7).

Крім того, математична модель цього типу базових задач повинна містити параметри погодних умов, що задаються до початку розв'язання задачі. Ці параметри характеризуються вектором природно-кліматичних і погодних умов

, (8)

де - частка днів надзвичайно сприятливих для виконання технологічного процесу вирощування сільськогосподарських культур;

- частка днів сприятливих;

- частка днів несприятливих;

- частка днів украй несприятливих.

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

Тобто необхідно визначити

,(9)

,(10)

де - підмножина комбінаторної множини перестановок, елементи якої задовольняють системі обмежень (5 - 7);

елемент комбінаторної множини перестановок;

знайдений оптимальний (раціональний) елемент комбінаторної множини;

значення критерію, що оптимізується;

- прогнозовані значення природно-кліматичних і погодних параметрів, раніше заданих у моделі.

Реалізація математичної моделі (9 - 10) дозволить отримати розв'язок задачі у вигляді кортежу

(11)

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

Проведений аналіз особливостей базових задач комбінаторної оптимізації дає необхідну інформацію для обґрунтованого вибору методів і засобів реалізації відповідних математичних моделей.

Розділ 4. Чисельна реалізація математичних моделей базових задач комбінаторної оптимізації. Запропоновано й реалізовано методику обліку особливостей формування області допустимих рішень для прикладних задач комбінаторної оптимізації, що виникають в агротехнічній системі. Це дає можливість зменшити кількість значень функції мети, що обчислюються, за рахунок зменшення кількості аналізованих елементів множини комбінаторних з'єднань.

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

Запропоновано й обґрунтовано модифікацію пошукового методу комбінаторної оптимізації, заснованого на композиції та послідовному застосуванні методів: випадкового пошуку; околів, що звужуються; вектора спаду. Це дозволило об'єднати переваги кожного з методів комбінаторної оптимізації, що застосовуються.

У роботі доводиться таке твердження. Послідовне застосування декількох чисельних методів комбінаторної оптимізації (композиція методів), що сходяться, покращує або залишає незмінним рішення, отримане на попередньому етапі розв'язання задачі оптимізації одним з чисельних методів, що застосовуються.

Наведемо як приклад чисельне дослідження математичної моделі (9 - 10) методом направленого пошуку, а саме композицією методів дискретної оптимізації. При цьому візьмемо за основу значення глобального екстремуму грн., знайденого раніше методом повного перебору для елементів повної множини комбінаторних з'єднань. Відповідною перестановкою є

,(12)

де числа указують на номер поля, а нижній індекс відповідає номеру культури.

Це значення глобального екстремуму функції мети необхідне як для дослідження процесу наближення до екстремуму при чисельній реалізації композиції методів комбінаторної оптимізації, так і для оцінки похибки цього методу.

Оскільки в кожний момент часу в пам'яті ПЕОМ знаходиться поточне рекордне значення функції мети , то існує можливість побудови в часі процесу наближення функції мети до глобального екстремуму . Наводиться ілюстрація таких залежностей (рис. 2) для різних початкових точок обчислювального процесу.

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

Відносна похибка для кожного моменту часу обчислюється як .

Проводиться оцінка цього значення для кінцевого моменту часу обчислювального процесу. Рекордною перестановкою в цей момент часу є перестановка

,(13)

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

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

Таким чином, апробація комбінації методів дискретної оптимізації (випадкового пошуку, околів, що звужуються, і вектора спаду) дозволяє для математичної моделі 3.1 задачі 3.1, розглянутої як приклад, за час отримати наближення до глобального екстремуму з точністю до %. При цьому кількість елементів повної множини комбінаторних з'єднань дорівнює .

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

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

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

- відсутності етапів складання і налагодження програм;

- паралельності виконання деяких кроків алгоритму;

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

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

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

На Міжнародному малому салоні винаходів і нових технологій „Новое время” (Севастополь, 29 - 31 травня 2007 р.) із трьох поданих на конкурс патентів два патенти № 21495 [6] і № 21588 [7] відзначено двома дипломами і двома срібними медалями.

ВИСНОВКИ

Внаслідок проведеного дослідження отримано такі результати:

1. Отримали подальший розвиток методи математичного моделювання прикладних задач комбінаторної оптимізації з обмеженнями на елементи комбінаторних множин у вигляді переваг, нерівностей та рівностей; наявністю параметрів, що характеризують природно-кліматичні умови регіону та змінні умови попиту та пропозиції продукції. Це дало можливість врахувати специфіку різноманітних задач комбінаторної оптимізації, що виникають в агротехнічній системі: пошук раціональної сівозміни з урахуванням попередників і природно-кліматичних умов, формування комплексів сільгоспмашин для виконання технологічних операцій в агротехнічній системі та ін.

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

3. Отримали подальший розвиток методи математичного моделювання базових задач комбінаторної оптимізації, що являють собою окремі випадки основної оптимізаційної задачі, після її розбиття на підзадачі. Для розв'язання базових задач досліджено межі застосовності методу повного перебору при пошуку глобального екстремуму, а також питання часових витрат залежно від параметрів ПЕОМ, що застосовуються. Наприклад, для розв'язання задачі оптимізації перестановок методом повного перебору, кількість елементів комбінаторних з'єднань може дорівнювати . Часові витрати при цьому складають секч. Рекомендується вже для застосування пошукових методів комбінаторної оптимізації.

4. Вперше запропоновано й обґрунтовано модифікацію пошукового методу комбінаторної оптимізації, яка враховує специфіку математичних моделей та заснована на композиції чисельних методів, що послідовно застосовуються: випадкового пошуку; околів, що звужуються; вектору спаду. Отримано умови й рекомендації щодо доцільності застосування композиції методів комбінаторної оптимізації. Досліджено відносні й абсолютні похибки цього методу в різні моменти часу обчислювального процесу. Апробація цього методу дозволяє для розглянутої, як приклад, математичної моделі 3.1 задачі 3.1, за час секгод. отримати наближення до глобального екстремуму з відносною похибкою %. При цьому кількість елементів повної множини комбінаторних з'єднань . Підтверджено чисельними експериментами збіжність наближених рішень, що отримуються, до глобального екстремуму.

5. Для апаратної реалізації математичних моделей базових задач комбінаторної оптимізації з обмеженнями у вигляді переваг, нерівностей та рівностей запропоновано й запатентовано принципи побудови спеціалізованих обчислювальних засобів, що дозволяють зменшити часові витрати за рахунок: відсутності етапів складання і налагодження програм; паралельності виконання деяких кроків алгоритму; апаратних (крупноблокових) реалізацій підпрограм розв'язання задач комбінаторної оптимізації з обмеженнями.

6. Апробацію й впровадження результатів дисертаційної роботи здійснено: у Науково-дослідному технологічному інституті Харківського національного технічного університету сільського господарства ім. П. Василенка; у Науково-виробничій і експлуатаційній фірмі «СТОЗІ»; в навчальний процес Харківського національного технічного університету сільського господарства ім. П. Василенка. Впровадження запропонованих у роботі математичних моделей, методів і засобів для їх реалізації дають можливість: зменшити на 15% загальні витрати часу на прийняття рішення в агротехнічній системі (акт впровадження від 12.09.2007 в додатку В); застосування запропонованих у роботі і запатентованих спеціалізованих обчислювальних пристроїв дозволяє зменшити часові витрати на реалізацію математичних моделей в n разів, де n - кількість дискретних елементів системи; підвищити точність реалізації математичних моделей і здійснити автоматизацію процесу дослідження властивостей моделей і методів їх реалізації (акти впровадження від 31.05.2007, 12.09.2007 в додатках А, В); на 10% зменшити часові витрати на прийняття рішення в агротехнічній системі (акт впровадження від 12.09.2007) в додатку В).

ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Коваленко С. Н. Комбинаторные аппаратные модели для решения задач оптимизации / В. П. Путятин, С. Н. Коваленко // Вестник НТУ «ХПИ». Тематический выпуск «Системный анализ, управление и информационные технологии». - 2007. - №.18 - С. 64-71.

2. Коваленко С. Н. Модели задач комбинаторной оптимизации для принятия решений в АПК / В. П. Путятин, С. Н. Коваленко // Системи обробки інформації. - 2007. - Вип. 2 (60). - С. 71-75.

3. Коваленко С.Н. Задачи комбинаторной оптимизации агроэкосистемы севообороты - технологии - машины - экология / С. Н. Коваленко // Восточно-европейский журнал передовых технологий. - 2007. - № 4/5(28). - С. 20-24.

4. Коваленко С. Н. Многокритериальная комбинаторная оптимизация комплексов машин / С. Н. Коваленко // Управління розвитком: зб. наук. статей за матеріалами наук.-практ. конф. „Інформатизація бізнесу очима молодих: прогресивні технології, наука, підприємництво”, 17-18 трав. 2007, Х. : ХНЕУ, 2007. - № 3. - С. 123-124.

5. Коваленко С. М. Комп'ютерні комбінаторні множини в САПР АПК / С. М. Коваленко, В. І. Пастухов, В. П. Путятін // Управління розвитком: зб. наук. статей за матеріалами Всеукр. наук.-практ. конф. „Комп'ютерне моделювання та інформаційні технології в економіці”, 16-17 лис. 2006р . - Х. : ХНЕУ, 2006. - № 6. - С. 73-74.

6. Пат. 21495 Україна, МКИ G 06 F 15/08. Спосіб виділення допустимих елементів комбінаторних множин / Коваленко С. М., Путятін В. П.; замовник та власник Харків. нац. техн. ун-т сільськ. госп. ім. П. Василенка. - № 200610634; заявл. 09.10.2006; опубл. 15.03.2007. Бюл. № 3.

7. Пат. 21588 Україна, МКИ G 06 F 15/00. Селектор елементів комбінаторних множин / Коваленко С. М., Путятін В. П., Фурман І. О.; замовник та власник Харків. нац. техн. ун-т сільськ. госп. ім. П. Василенка. - № 200611118; заявл. 23.10.2006; опубл. 15.03.2007. Бюл. № 3.

8. Пат. 22314 Україна, МКИ G 06 F 15/00. Пристрій для комбінаторної оптимізації / Коваленко С. М., Путятін В. П.; замовник та власник Харків. нац. техн. ун-т сільськ. госп. ім. П. Василенка. - № 200610651; заявл. 09.10.2006; опубл. 25.04.2007. Бюл. № 5.

9. Коваленко С. Н. Комбинаторные задачи принятия решений о рациональном севообороте / С. Н. Коваленко // Радиоэлектроника и молодежь в ХХI веке: материалы 10-й юбил. Междунар молод. форума, 10 - 12 апреля 2006 г. - Х. : Харьк. нац. ун-т радиоэлектроники, 2006. - С. 418.

10. Коваленко С. М. Реалізація математичних моделей комбінаторних задач прийняття рішень / С. М. Коваленко // Современные научные достижения - 2007: материалы ІІ Междунар. научно-практ. конференции, 01 - 14 февр. 2007 г. - Днепропетровск, 2007. - Т.6. - С .45-47.

11. Коваленко С. Н. Аппаратурная реализация математических моделей задач принятия решений в АПК / С. Н. Коваленко // Радиоэлектроника и молодежь в ХХI веке: материалы 11-й Междунар молод. форума, 10 - 12 апреля 2007 г. - Х. : Харьк. нац. ун-т радиоэлектроники, 2007. - С. 120.

12. Коваленко С. Н. Автоматизация исследования комбинаторных задач оптимизации в АПК / С. Н. Коваленко // Рыночная трансформация экономики: состояние, проблемы, перспективы: материалы Междунар. форум молодых ученых, 19-20 апреля 2007 г. - Х. : Харьк. нац. тех. ун-т сельск. хоз-ва им. П. Василенко, 2007. - С. 184-185.

АНОТАЦІЯ

Коваленко С.М. Математичні моделі і методи розв'язання задач комбінаторної оптимізації в агротехнічній системі. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання і обчислювальні методи. - Харківський національний університет радіоелектроніки, Харків, 2008.

Запропоновано й досліджено математичну модель основної задачі комбінаторної оптимізації, що враховує комбінаторну природу базових задач, специфіку агротехнічної системи і наявність в моделі параметрів, що характеризують природно-кліматичні умови. Показано, що така задача належить до комбінаторних, багатовимірних, в загальному випадку, нелінійних і багатоекстремальних задач. Обґрунтовано модифікацію пошукового методу комбінаторної оптимізації, що враховує специфіку математичних моделей та заснована на композиції методів, що застосовуються послідовно: випадкового пошуку; околів, що звужуються; вектору спаду. Підтверджено чисельними експериментами збіжність наближених рішень, що отримуються, до глобального екстремуму. Досліджено відносні й абсолютні похибки цього методу в різні моменти часу обчислювального процесу.

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

Ключові слова: математичні моделі, комбінаторика, оптимізація, чисельні методи, апаратні моделі, прийняття рішень, агротехнічна система.

АННОТАЦИЯ

Коваленко С.Н. Математические модели и методы решения задач комбинаторной оптимизации в агротехнической системе. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Харьковский национальный университет радиоэлектроники, Харьков, 2008.

Целью исследования является: разработка новых и адаптация, с учетом особенностей предметной области, существующих математических моделей задач комбинаторной оптимизации с ограничениями; повышение эффективности (по времени и точности) реализации математических моделей на программно-аппаратном уровне, за счет дополнительного исследования и учета особенностей соответствующих математических моделей.

Получили дальнейшее развитие методы математического моделирования прикладных задач комбинаторной оптимизации с ограничениями в виде предпочтений, неравенств, равенств и наличием параметров, характеризующих природно-климатические условия региона. Это дало возможность учесть специфику разнообразных комбинаторных задач, возникающих в агротехнической системе: поиск рационального севооборота с учетом предшественников и природно-климатических условий, формирование комплексов сельхозмашин для выполнения технологических операций в агротехнической системе и др.

Предложена и исследована математическая модель основной задачи комбинаторной оптимизации, учитывающая комбинаторную природу частных задач, специфику агротехнической системы и наличие в модели параметров, характеризующих природно-климатические условия. Показано, что такая задача относится к комбинаторным, многомерным, в общем случае, нелинейным и многоэкстремальным задачам.

Предложена и реализована методика учета особенностей формирования области допустимых решений для прикладных задач комбинаторной оптимизации, возникающих в агротехнической системе. Это дает возможность сократить количество вычисляемых значений функции цели за счет уменьшения количества анализируемых элементов множества комбинаторных соединений.

Получили дальнейшее развитие методы математического моделирования базовых задач комбинаторной оптимизации, являющихся частными случаями основной оптимизационной задачи, после ее разбиения на подзадачи.

Указаны границы применимости метода полного перебора по максимальному количеству элементов множества комбинаторных соединений, которые могут быть проанализированы за приемлемое для практики проектирования (планирования) время. Для решения базовых задач исследованы границы применимости метода полного переборка при поиске глобального экстремума, а также вопросы временных затрат в зависимости от характеристик применяемых ПЭВМ. Например, для решения задач оптимизации перестановок методом полного перебора число элементов комбинаторных соединений может равняться . Временные затраты при этом составляют секч. Рекомендуется уже для применение поисковых методов комбинаторной оптимизации.

Обоснована модификация поискового метода комбинаторной оптимизации, основанного на композиции последовательно применяемых методов: случайного поиска; сужающихся окрестностей; вектора спада. Подтверждена численными экспериментами сходимость получаемых приближенных решений к глобальному экстремуму. Исследованы относительные и абсолютные погрешности этого метода в различные моменты времени вычислительного процесса. Получена рекомендация относительно того, что уже для задач с числом элементов комбинаторных соединений целесообразно вместо метода полного перебора использовать композицию методов комбинаторной оптимизации.

Резкое возрастание временных затрат от незначительного увеличения числа элементов в множествах, образующих комбинаторные соединения, требует разработки аппаратно-программных средств для повышения эффективности (по памяти, времени, точности) решения прикладных задач комбинаторной оптимизации. Важность этого вывода потребовала разработки специализированных вычислительных средств для аппаратной реализации математических моделей.

Для аппаратной реализации математических моделей базовых задач данного типа предложены и запатентованы принципы построения специализированных вычислительных средств, позволяющих сократить временные затраты за счет: отсутствия этапов составления и отладки программ; параллельности выполнения некоторых шагов алгоритма; аппаратных (крупноблочных) реализаций подпрограмм решения задач комбинаторной оптимизации с ограничениями.

Предложенные в работе математические модели, методы и средства для их реализации дают возможность: организации системы поддержки принятия решений на базе разработанных математических моделей, численных методов их реализации и программно-аппаратных средств, что позволяет сократить на 15% общие затраты времени на принятие решения; создания специализированных вычислительных процессоров, которые позволяют сократить временные затраты на формирование одного варианта системы в n раз, где n - количество дискретных элементов системы, анализа большего числа вариантов системы, что повышает точность реализации математической модели и позволяет организовать процесс автоматизации исследования свойств математических моделей и методов их реализации; планирования севооборотов сельскохозяйственных культур на несколько лет вперед, с учетом вариантов севооборотов предыдущих лет и вариантов привлекаемых технических средств, что позволяет на 10% сократить временные затраты на принятие решения в агротехнической системе.

Ключевые слова: математические модели, комбинаторика, оптимизация, численные методы, аппаратные модели, принятие решений, агротехническая система.

Abstract

Kovalenko S.N. Mathematical models and methods for solving problems of combinatorial optimization in the agricultural technical system. - Manuscript.

Thesis for a candidate's degree on the speciality 01.05.02 - mathematical modelling and computational methods. - Kharkіv National University of Radioelectronics, Kharkіv, 2008.

There has been offered and investigated a mathematical model of the main optimization problem taking into account specific character of the agricultural technical system, combinatorial character of basic problems and the presence in the mathematical model such parameters, that describe the condition of nature and climate. There has been determined that such a problem belongs to combinatorial, multivariate in the general case nonlinear and multiextremal problem. There has been substantiated a modification of the searching method of combinatorial optimization based on the composition of consecutively applied methods: the method of random search, that of converging vicinities, that of recession vector. Convergence of the received approximate solutions to the global extremum has been confirmed by means of numerical experiments. Relative and absolute errors of this method have been investigated at different instants of computational process.

For hardware support of mathematical models of the problems of this type it is offered the procedure of making specialized computational means allowing reducing time costs for realization of mathematical models.

Key words: mathematical models, combinatorial analysis, optimization, computational methods, apparatus models, problem-solving, agricultural technical system.

Відповідальний за випуск

Кривуля Г.Ф.

Підп. до друку 10.09.08.

Умов. друк. арк. 1,2.

Зам. № 2-620

Формат 60x841/16.

Ціна договірна.

Спосіб друку - ризографія.

Тираж 100 прим.

ХНУРЕ, 61166, м. Харків, просп. Леніна, 14.

Віддруковано в навчально-науковому видавничо-поліграфічному центрі ХНУРЕ.

Харків, просп. Леніна, 14

Размещено на Allbest.ru

...