Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Національна Академія наук України
Інститут кібернетики імені В.М.Глушкова
УДК 518.9
СТАЦІОНАРНІ І ДИНАМІЧНІ МОДЕЛІ ТА МЕТОДИ РОЗПОДІЛУ ГІДРОРЕСУРСУ
Спеціальність 01.05.02 –математичне моделювання
та обчислювальні методи
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
доктора фізико-математичних наук
Київ - 2001
Дисертацією є рукопис
Робота виконана в Навчально-науковому комплексі “Інститут прикладного системного аналізу” Національної Академії наук України та Міністерства освіти та науки України
Науковий доктор фізико-математичних наук, професор
консультант: Остапенко Валентин Володимирович,
Навчально-науковий комплекс “Інститут прикладного системного аналізу” Національної Академії наук України та Міністерства освіти та науки України
Офіційні опоненти:
доктор фізико-математичних наук, професор, член-кореспондент Національної Академії наук України Скопецький Василь Васильович, Інститут кібернетики імені В.М.Глушкова Національної Академії наук України, завідувач відділом,
доктор фізико-математичних наук, професор, член-кореспондент Національної Академії наук України Мельник Валерій Сергійович, Навчально-науковий комплекс “Інститут прикладного системного аналізу” Національної Академії наук України та Міністерства освіти та науки України, завідувач відділом,
доктор фізико-математичних наук, професор Ляшенко Ігор Миколайович, Київський національний університет імені Тараса Шевченка, завідувач кафедрою
Провідна установа:
Інститут проблем машинобудування імені А.М.Підгорного, відділ прикладної математики та обчислювальних методів Національної Академії наук України, м.Харків
Захист відбудеться “ 23 “листопада” 2001 року об 11 годині на засіданні спеціалізованої вченої ради Д26.194.02 при Інституті кібернетики імені В.М.Глушкова Національної Академії наук України за адресою:
проспект Академіка Глушкова, 40, 03680 МСП Київ 187.
З дисертацією можна ознайомитися в науково-технічному архіві інституту.
Автореферат розісланий “ 19 “жовтня” 2001 року
Учений секретар
спеціалізованої вченої ради Синявський В.Ф.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність роботи. В дисертаційній роботі розглянуті питання розподілу ресурсів у просторі і у часі. Такі задачі виникають при дослідженні екологічних проблем, пов’язаних із збереженням грунтів у зоні зрошуваного землеробства. Так збільшення потужності зрошувальних систем призводить до порушення екологічного балансу, деградації та засоленості грунтів, збільшенню вартості будівництва. Зниження –призводить до втрат врожаю з приводу недостатнього та несвоєчасного поливу сільськогосподарських культур.
Процес управління транспортом води під час руху каналами зрошувальних систем описується течіями у сітках з узагальненим законом Кирхгофа. Задача розподілу води між користувачами в умовах обмеженої перепускної спроможності зрошувальної системи призводить до необхідності розв’язувати задачі розподілу ресурсу (у даному випадку –зрошувальної води) між споживачами однакової інтенсивності. Дана задача тісно пов’язана із задачею управління запасами вологи у грунті. Таким чином у дисертації одночасно розглядаються питання розподілу водних ресурсів та управління запасами вологи у грунті, що привело до нових формулювань задач розподілу й управління запасами. Це дозволяє уникати технологічних скидань води з магістральних каналів, що запобігає підтоплення і заболочення зони зрошення.
Розроблені математичні методи розв’язання сформульованих задач дозволяють обчислювати оптимальні режими управління зрошувальними системами та одержувати оптимальні календарні графіки поливів. При цьому вирішується задача утримання вологості активного шару грунту у заданих межах. При практичному застосуванні ці методи повинні бути доповнені дослідженнями в області фільтрації, які грунтуються на роботах І.І.Ляшка, В.В.Скопецького, В.С. Дейнеки. Це дозволить оцінити втрати зрошувальної води, пов’язані із стіканням у грунт, а також визначити об’єм води, що перетікає з верхнього б’єфа до нижнього у процесі фільтрації.
На протязі останніх сорока років прикладна область теорії графів, за допомогою якої досліджуються моделі та методи розподілу течій у сітках, набула інтенсивного розвитку.
Становлення теорії розподілу течій у сітках починається з фундаментальних робот Л.Форда і Д.Фалкерсона. Різні автори, в залежності від методів розв’язання, відносять задачі розподілу течій у сітках до задач лінійного програмування, комбінаторної оптимізації або до екстремальних задач на графах.
Роботи присвячені розподілу течій у сітках можна об’єднати у дві великі групи. У першій групі досліджуються статичні течії, у другій –динамічні.
Різновидом сіткових задач є транспортні задачі і їх узагальнення –багатопродуктивні сіткові транспортні задачі, а також динамічні задачі розподілу ресурсу. Дослідженню цих задач присвячені роботи В.С.Михалевича, Н.З.Шора, В.А.Трубіна .
Розв’язанню задачі розподілу течій у сітках з нелінійною функцією цілі інтегрального виду присвячені роботи Б.М.Пшеничного.
Подальшим розвитком теорії статичних течій у сітках є динамічні задачі. У цих задачах враховується час переміщення течії дугами. Сітка містить вершини джерела та вершини стоки з визначеною динамікою виробництва і споживання течії, а також вершини склади, у яких течія може затримуватися.
Динамічною течією у сітці називають таку течію, яка задовольняє не тільки обмеженням на пропускні спроможності дуг і вершин у кожний момент часу, а і обмеженням часу проходження суміжними вершинами. Ця обставина визначає суттєву складність розв’язання динамічних задач. Динамічні задачі можна розділити на два класи: задачі з дискретним і неперервним часом.
В багатьох роботах вивчаються динамічні транспортні задачі, для вирішення яких запропоновані методи розв’язання шляхом зведення до визначеної статичної задачі більшої вимірності.
Течії з неперервним часом можна вивчати як граничний випадок динамічних течій з дискретним часом. Але може бути застосований і зворотній перехід від неперервної задачі до дискретної, оскільки, як правило, точний розв’язок неперервної задачі неможливо одержати.
Для розв’язання задач про динамічні течії розроблено також методи, які базуються на теорії оптимального управління.
У дисертації розглянуті течії у сітках з узагальненим принципом збереження. Дана проблематика виникла при розв’язанні задач управління рухом води у каналах зрошувальних систем, що розглянуті у роботах В.В.Остапенко. Узагальнений принцип збереження описано за допомогою системи лінійних нерівностей, структура якої задається відповідним графом.
Системи лінійних нерівностей і методи їх розв’язання досить повно досліджені у роботах С.М.Чернікова та його учнів. У цих роботах, в якості одного з методів, запропоновано метод послідовного вилучення невідомих (метод Фур’є). Велику увагу приділено питанню зменшення числа нових нерівностей, які утворюються в результаті застосування метода послідовного вилучення невідомих. Для цього використовується апарат згортання системи лінійних нерівностей.
Задачі розподілу ресурсу, які досліджуються у дисертації, відносяться до задач календарного планування. Розв’язанню задач календарного планування присвячені роботи В.С.Михалевича, О.І.Кукси, В.В.Шкурби.
Задача розподілу ресурсів тісно пов’язана із задачею управління запасами, яка є однією з найважливіших задач теорії дослідження операцій. У ряді робот графік зміни запасу описується у вигляді деякої “пилки” або кусково лінійної функції, яка зазнає розриви у мить поповнення запасів. Також динаміка зміни запасу описується кусково лінійною неперервною функцією. Побудовані детерміновані і стохастичні, лінійні і нелінійні моделі управління запасами різних видів матеріальних ресурсів. Розроблені детерміновані і стохастичні методи їх розв’язання. Досліджені задачі управління запасами при наявності збурень.
Таким чином тема дисертаційної роботи належить до актуальних напрямків дослідження операцій, пов’язаних з розподілом ресурсів у просторі та часі. Проблеми, що виникають з цього приводу, вивчаються багатьма науковцями. Ці проблеми тісно пов’язані з конкретними практичними задачами, які виникають у техніці, економіці, зрошуваному землеробстві та інших областях людської діяльності.
Зв’язок роботи з науковими програмами. Результати дисертаційної роботи є складовою частиною наступних науково-дослідних робіт.
Автором розроблені методи розв’язання систем лінійних нерівностей, що мають структуру графа.
Автором розроблені методи розподілу ресурсу між споживачами з рівною інтенсивністю.
Автором розроблені методи розподілу ресурсу, які формалізовані для побудови обчислювальних алгоритмів засобами алгоритміки.
Мета і задачі дослідження. Метою дослідження є розробка методів розв’язання нових задач розподілу ресурсу у просторі та часі, які виникають при дослідженні актуальних прикладних проблем.
Об’єктом дослідження є течії у сітках та задачі календарного планування. Предметом дослідження є задачі розподілу ресурсу у сітках з узагальненим законом збереження та задачі розподілу ресурсу у часі між рівнопотужними споживачами.
У дисертації використані методи теорії графів та течій у сітках, методи розв’язування систем лінійних нерівностей та диференціальних рівнянь, методи математичного програмування.
Наукова новизна одержаних результатів.
Запропоновані моделі, методи та алгоритми використані при розробці інформаційно-обчислювальної системи “Полив”, яка впроваджена у виробництво для розрахунків режимів зрошення сільськогосподарських культур Інститутом гідротехніки і меліорації УААН.
Особистий внесок здобувача. У наведених нижче роботах особисто здобувачем одержані наступні результати [13] –доведення теорем, які подають достатні умови визначеної кратності систем проміжків споживання; [14] –способи оптимального розподілу ресурсів між рівнопотужними споживачами описані за допомогою оптимальних переставлень номерів споживачів; [15] –розроблений ігровий підхід при проектуванні зрошувальних систем з урахуванням цін на сільськогосподарську продукцію та будівництво і експлуатацію систем; [16] –на основі застосування функції розподілу сезонної потреби зрошувальної води розроблено чисельний метод визначення потужності зрошувальних систем при заданому рівні водозабезпеченості; [17] –розроблені лінійні моделі зміни вологості в активному шарі грунту, розв’язані задачі комплектування графіків поливів, як задачі лінійного та квадратичного програмування; [18] –одержані необхідні та достатні умови визначеної кратності проміжків споживання різної довжини; [19] –за допомогою систем лінійних нерівностей описані необхідні та достатні умови визначеної кратності проміжків споживання рівної довжини, придатні для розробки чисельних методів; [20] –розв’язана задача управління обмеженими запасами декількох споживачів; [21] –досліджені стаціонарні та динамічні течії у сітках з узагальненим законом Кирхгофа, обмеження описані у вигляді систем лінійних нерівностей, для яких запропоновані методи розв’язання; [22] –розроблена математична модель руху води у відкритих руслах, яка описана за допомогою узагальненого закону Кирхгофа, придатна для розв’язання задач управління; [23] –розроблено метод вилучення групи невідомих із систем лінійних нерівностей зі структурою графа для випадків кінцевого та проміжного підграфів; [24] –розроблено наближений метод апроксимації розв’язків нескінченної системи лінійних нерівностей за допомогою розв’язків скінченних систем; [25] –задача визначення динамічних течій у сітках з урахуванням часу загаювання зведена до розв’язання локально скінченних систем лінійних нерівностей; [26] –розроблено метод вилучення невідомих із систем лінійних нерівностей загального виду; [27] –розроблено спосіб розв’язування локально скінченної системи лінійних нерівностей та сформульовано критерій, коли ця система має структуру графа; [28] –розроблено чисельний метод стягування дуг при розв’язанні систем лінійних нерівностей зі структурою графа; [32] –запропоновано моделювання течій у сітках за допомогою узагальненого закону Кирхгофа;. [33] –введено поняття кратності системи проміжків споживання; [34] –задача розподілу ресурсу у часі зведена до задач математичного програмування з лінійними обмеженнями;
Апробація результатів дисертації. Результати досліджень, що включені до дисертації, оприлюднені на наступних наукових конференціях: “Современные проблемы планирования и управления водохозяйственными системами”: Новочеркасск, 1990; 3-тя Українська конференція з автоматичного керування “Автоматика –”: Севастополь, 1996; міжнародна конференція “Моделирование и исследование устойчивости систем”: Київ, 1997; міжнародна конференція “Питання оптимізації обчислень”: Київ, 1997; 5-та Українська конференція з автоматичного управління “Автоматика –”: Київ, 1998; 9-та конференція “Аналіз ризиків”: Роттердам, 1999; 6-та Українська конференція з автоматичного управління “Автоматика –”: Харків, 1999; міжнародна конференція “Моделювання та оптимізація складних систем”: Київ, 2001.
Зроблені доповіді на наукових семінарах в ННК “Інститут прикладного системного аналізу” НАН України та Міносвіти і науки України, Київському національному університеті імені Тараса Шевченка та Інституті кібернетики імені В.М.Глушкова НАН України.
Публікації. Результати дисертації опубліковані у 34 роботах. Із них у наукових журналах –, збірниках наукових праць –, матеріалах і тезах конференцій –.
При цьому особисто здобувачем написані 15 наукових робіт, а інші –у співавторстві.
Структура та обсяг роботи. Дисертація складається з вступу, п’яти розділів, висновків та списку літературних джерел. Загальний об’єм дисертації складає 285 сторінок, у який входить 258 сторінок основного машинописного тексту, 14 сторінок займають 4 малюнки і 10 таблиць, список використаних літературних джерел із 157 найменувань на 13 сторінках.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У розділі 1 “Аналіз методів розподілу гідроресурсів” зроблено огляд літератури, присвячений цій проблемі. Аналіз огляду літератури дав змогу виявити основні напрямки досліджень, що розроблені у дисертації.
У Розділі 2 “Розв’язання лінійних систем алгебраїчних нерівностей зі структурою графа” розроблені методи вилучення невідомих з систем лінійних нерівностей, які виникають при моделюванні руху води за допомогою узагальненого закону Кирхгофа.
Запропонована модель зміни рівнів води у відкритому руслі має вигляд
(1)
=const. (2)
Тут позначено : –поточний, –початковий рівні води перед i-ою перетинаючою спорудою, –витрати споживача, який розташований перед i-ю спорудою, дугами (j, і) течуть течії , - коефіцієнт згасання хвилі при проходженні дуги (j, і), –час проходження дуги (j,і). Множина описує усі вершини виходу дуг, які входять у вершину v; множина описує усі вершини входження дуг, які виходять із вершини v. Кожній вершині iV приписані коефіцієнти та , які описують зв’язок між витратами води та рівнями.
Задача утримання рівнів води у заданих межах
, , (3)
сформульована наступним чином. На заданому проміжку часу [0, T] обрати управління , які задовольнятимуть обмеження (2), так, щоб на цьому проміжку виконувались нерівності (3).З урахуванням (1) обмеження (3) зводяться до системи лінійних алгебраїчних нерівностей
(4)
яка подає узагальнений закон Кирхгофа.
Вилучення групи невідомих із систем лінійних нерівностей зі структурою графа.
Теорема 1 та метод вилучення групи невідомих застосовуються для вилучення невідомих з системи (15), (16). Відомо, що якщо ребро (i, j), яке відповідає невідомій, що вилучається, є або кінцевим або проміжним, то нова система нерівностей має структуру, яка задається деяким графом. Цей граф відрізняється від вихідного тим, що у ньому стягнуте ребро (i, j) і вершини i та j ототожнені. У цьому випадку одержана система нерівностей має на дві двосторонні нерівності менше, ніж вихідна.
У дисертації розглянуті кінцевий і проміжний підграфи. Вилучення невідомих, що відповідають кінцевому підграфу, призводить до нової системи лінійних нерівностей. Структура такої системи подається новим графом, отриманим із вихідного шляхом стягування кінцевого підграфа у вершину. При цьому число нерівностей зменшується. При вилученні невідомих, що відповідають проміжному підграфу, утворюється система нерівностей, якій відповідає граф із стягнутим в одну вершину проміжним підграфом. У цій вершині кількість нерівностей визначається різними простими ланцюгами проміжного підграфа.
Локально скінченні системи лінійних нерівностей зі структурою нескінченного графа.
Наведені вище дослідження, поширюються на випадок нескінченного графа. Така задача виникає при управлінні динамічними течіями у сітках, які описані системою нерівностей (5), (6) при наявності часу загаювання .
Розглянемо критерій, що визначає чи буде система нерівностей мати структуру графа.
Нехай G={V,E} - зв’язний неорієнтований граф, V - множина його вершин, Е - множина ребер. Розглянемо скінченні або локально скінченні графи.
У розділі 3 “Розподіл динамічних течій у сітках” розглядаються динамічні течії у сітках за умови виконання закону Кирхгофа з деякою похибкою. При цьому відсутні обмеження на ємності вершин. Така задача виникає при розрахунку оптимального управління рухом води в каналах зрошувальних систем.
Нехай G=V, E cкінченний орієнтований граф, де V - множина вершин, Е - множина дуг. Поставимо задачу: знайти функції , що задовольняють умовам (5), (6).
Припустимо, що проміжки і відомі при t[-, 0], де . Один з підходів до розв’язання поставленої задачі полягає у спрощенні системи (5), (6) за допомогою вилучення невідомих течій, що течуть кінцевими або проміжними дугами. Теж саме спрощення здійснюється при вилученні групи невідомих течій, що течуть кінцевими або проміжними підграфами, які задовольняють сформульованим нижче припущенням 1 –.
Лінійні нерівності для графа з одним джерелом і одним стоком. Нехай –слабозв’язний орієнтований граф. Вершину назвемо джерелом, якщо вершину назвемо стоком, якщо Дуги утворюють шлях у . Величину назвемо довжиною шляху.
Припущення 1. Граф має одне джерело а й один стік b.
Припущення 2. Граф не має контурів.
Припущення 3. Будь-який шлях з а в b має однакову довжину .
Лема 1. Будь-яка вершина досяжна з вершини а і вершина b досяжна з будь-якої вершини .
Лема 2. Нехай . Тоді будь-який шлях з а в с має однакову довжину і будь-який шлях із с в b має однакову довжину.
У розділі 4 “Кратність систем підмножин у задачі управління ресурсами” викладено комплекс підходів, що дозволяють сформулювати задачі оптимізації графіків споживання у вигляді задач математичного програмування з лінійними обмеженнями. Основна ідея регулювання, при умові дефіциту ресурсу, полягає у зсуві строків споживання для забезпечення кращого розподілу у часі наявних ресурсів.
Розглянемо сітку, яка складається з одного джерела і n споживачів. Позначимо , t0, витрати які споживає i–й споживач в момент t. Припустимо, що величина витрат ресурсу, що витікає з джерела, не перевершує заданого числа k0. Функції будемо називати функціями споживання.
Формулювання задачі оптимізації. Розглянемо задачу першого типу. Позначимо x=(,...,), y=(,...,) —вектори початків і довжин проміжків споживання, (x, y)= (,...,,,...,) - їх спільний вектор. Задамо спочатку обмеження на параметри і
(32)
де –задані невід’ємні числа.
Розглянемо тепер задачу другого типу. Для її розв’язання треба знайти мінімальне ціле k, при якому наведена вище система проміжків споживання має кратність не більше ніж k і при цьому вектори x та y задовольняють обмеженням (32), (33).
Споживання різної інтенсивності. Перейдемо тепер до деяких узагальнень випадку, у якому функції мають вид (31). Нехай
(35)
Будемо вважати , що –цілі додатні числа.
Очевидно, що у даному випадку k –споживання неможна безпосередньо описати за допомогою поняття кратності. Для того щоб це зробити введемо до розгляду фіктивних користувачів. Вважаємо, що i–й користувач, інтенсивність споживання якого дорівнює , складається з фіктивних користувачів, кожний з яких має інтенсивність, яка дорівнює одиниці на проміжку споживання . Розглянемо задачу виду (32) –(34) для вихідних користувачів. Додатково будемо вимагати, щоб виконувалась умова k –споживання. Поставлена задача є задачею першого типу при умові, що функція споживання має вид (35).
Лінійні обмеження у задачах математичного програмування.
Оптимальні розв’язки. Розглянемо задачу виду (32) –(34) при умові, що має місце k –споживання. За теоремою 12 k –споживання має місце у тому випадку, якщо для деякого переставлення виконується нерівність (49).У задачі виду (32) –(34) та (49) обмеження (32) та (49) лінійні. Тому, якщо множина М описується у вигляді системи лінійних нерівностей, то маємо задачу математичного програмування з лінійними обмеженнями. Додаткові обмеження, які формували множини та , відповідно формули (37) та (41), є лінійними. Таким чином, якщо немає інших нелінійних сумісних обмежень на початки та тривалості проміжків споживання, то у розгляді залишаються тільки лінійні обмеження.
Для кожного переставлення =(,...,) система обмежень (32), (33), (49) є або сумісною, або ні. Якщо вона сумісна, то назвемо таке переставлення припустимим. Для кожного припустимого переставлення задача (32) –(34), (49) має розв’язок x(), y(), який будемо називати оптимальним для даного переставлення . Переберемо усі припустимі переставлення та знайдемо те з них, для якого функція f приймає найменше значення на оптимальному розв’язку відносно цього переставлення. Дане переставлення будемо називати f - оптимальним. Такий перебор не може повністю описати ту умову, що має місце k–споживання. Тому назвемо x*=x(), y*=y() квазіоптимальним розв’язком.
У випадку коли y для усіх номерів i з теореми 13 виходить, що перебрав усі припустимі переставлення, одержимо в результаті умову k –споживання. Таким чином, у цьому випадку x* та y* є оптимальним розв’язком вихідної задачі.
Аналогічно можна розглянути задачу мінімізації числа k. Для кожного переставлення знаходимо мінімальне k (будемо позначати його k()), при якому система обмежень (32), (33), (49) сумісна. Покладемо Тут мінімум береться по усім припустимим переставленням. Переставлення на якому досягається цей мінімум назвемо k - оптимальним. У загальному випадку є квазіоптимальним розв’язком, а у випадку коли y для усіх значень i є оптимальним розв’язком поставленої задачі.
Оптимальні переставлення. Розглянемо випадок рівних довжин проміжків y. Тоді функція f залежить тільки від n+1 змінних ,...,, y, а множина М знаходиться у просторі . Позначимо (x, y) = (,...,, y) і сформулюємо оптимізаційну задачу (32) –(34) та
(52)
способи управління запасами. На основі викладених вище підходів, у дисертації зроблена математична формалізація та обгрунтування евристичних методів, які наведені у роботах [2, 17]. Досліджується задача розподілу обмеженого ресурсу між декількома користувачами з урахуванням зміни запасів у користувачів.
Припустимо, що є один ресурс, який використовують n споживачів. Позначимо - об’єм ресурсу, яким володіє i-й споживач. Динаміка зміни описується диференціальним рівнянням
= . (53)
Коефіцієнт 0 описує процес використання ресурсу і - м користувачем; функція описує витрати ресурсу, який надходить до i - го користувача і компенсує падіння .
Об’єм ресурсу повинен знаходитись у визначених границях
. (54)
Експоненціальнімоделі динаміки зміни вологості грунту. Запишемо модель зміни вологості в активному шарі грунту у виді
, (84)
(0,t)= =const . (85)
Тут —вологість грунту в точці х у момент часу t , –коефіцієнт теплообміну, –вологість грунту при рівноваговому стані, , де Q(t) —витрати зрошувальної води , P(t) —інтенсивність опадів, >0,(t) = W(t), де .
Наведена модель суттєво більш точно описує динаміку зміни вологості грунту, ніж балансові рівняння, оскільки відображає процес зменшення випаровування при зменшенні вологості грунту.
Мінімаксний підхід до проектування зрошувальних систем. На етапі проектування зрошувальних систем необхідно визначити потужність системи, екологічну безпечність, ступінь керованості, наявність засобів оперативного контролю, надійність функціонування, ремонтно–придатність, термін роботи до реконструкції та інші характеристики, які суттєво впливають на кошторисну вартість системи. З іншого боку, заощадження витрат при будівництві зрошувальної системи призводить до недостатньої технічної оснащеності системи, що не дозволить робити своєчасні поливи, призводить до підтоплення та засолення грунту. Таким чином, при проектуванні зрошувальних систем слід зважувати два основні критерії якості: перший пов'язаний з витратами на будівництво й експлуатацію, другий —із зниженням урожаю за рахунок порушення режимів зрошення. Ці два критерії взаємно протилежні, оскільки зменшення збитків від зниження врожайності потребує збільшення витрат на будівництво й експлуатацію. Тому дані критерії не можна вивчати окремо, а слід розглядати у деякому комплексі. Крім того, при проектуванні зрошувальних систем слід враховувати, що у період багаторічного функціонування виникають коливання цін на сільськогосподарську продукцію та експлуатацію системи. Це призводить до того, що додавання критеріїв якості або яка–небудь інша їхня комбінація може не дозволити одержати вірні значення характеристик зрошувальних систем.
Для розв'язання сформульованої задачі пропонується мінімаксний підхід, суть якого визначається наступним. Задаються проміжки часу, у яких у майбутньому припускається стабільність цін і граничні зміни цін. Потім обирається один із запропонованих у цьому підрозділі критеріїв якості і за допомогою чисельних методів математичного програмування обчислюються оптимальні значення характеристик зрошувальних систем. Основну увагу приділено визначенню характеристики потужності зрошувальної системи —гідромодулю, який визначає максимально можливі витрати водопостачання.
Основні функціонали. Введемо наступні позначення: —вартісні втрати за рік від зниження врожайності; —вектор змінних ; q—гідромодуль; —максимальні зрошувальні норми, ступінь керованості системи та інші параметри, які визначають оптимальний розв'язок; —вектор цін на сільськогосподарську продукцію у t–му році; —витрати на будівництво зрошувальних систем при відповідному векторі цін ; —витрати кожного року на експлуатацію зрошувальної системи; —вектор змінних; —ремонтопридатність, надійність функціонування та інші параметри, по яких проводиться оптимізація; —вектор цін на експлуатацію у t–му році. Припускаємо, що вектори змінюються відповідно у множинах .
ВИСНОВКИ
. Розроблено математичні моделі розподілу води у відкритих каналах і мережах зрошувальних систем, що описують вихідну задачу за допомогою течій у сітках, для яких виконується узагальнений закон Кирхгофа.
. Стаціонарні течії описано за допомогою систем лінійних нерівностей, що мають структуру графа.
. Для розв'язання систем лінійних нерівностей загального вигляду використані методи вилучення невідомих. Розроблено метод вилучення групи невідомих, який доведено за допомогою теореми Хеллі.
4. Досліджено випадки, коли доцільно вилучати групи невідомих, що відповідають певному підграфу. Сформульовані визначення кінцевого та проміжного підграфів. Якщо вилучається група невідомих, що відповідає кінцевому підграфу, то число нерівностей у новій системі зменшується. Для проміжного підграфа розглянуті ланцюги, які пов'язують вхідну і вихідну вершини та дано визначення ваги цих ланцюгів. При вилученні невідомих течій, які відповідають проміжному підграфу, система нерівностей, структура якої задається цим підграфом, заміняється системою нерівностей, що зв'язують вхідну та вихідну течії. Число таких нерівностей визначається кількістю ланцюгів з різною вагою.
. Введені поняття локально скінченного графа та локально скінченної системи нерівностей. Одержані критерії, які визначають коли система нерівностей має структуру графа. Розв'язки локально скінченних систем лінійних нерівностей представлені за допомогою апроксимації розв'язками скінченних систем нерівностей, які мають структуру скінченних підграфів локально скінченного графа.
. Математичне формулювання задачі розподілу динамічних течій у сітках, для яких виконується узагальнений закон Кирхгофа, зроблено за допомогою систем лінійних включень, праві частини яких залежать від часу.
. Досліджено властивості підграфів з однаковою довжиною шляхів від джерела до стоку. Такі підграфи розглянуті як кінцеві та проміжні. Розроблено методи вилучення групи невідомих течій, що течуть такими підграфами.
. Запропоновано метод, який зводить задачу відшукання динамічних течій у сітках із загаювальним аргументом до задачі розв’язання систем лінійних нерівностей зі структурою скінченного або локально скінченного графів.
. Розроблено метод прогнозу рівнів ресурсу у вершинах графа, який є деревом. Цей метод застосовано до розподілу динамічних течій з урахуванням ємностей вершин.
. Розв’язання сформульованих задач розподілу ресурсу зводиться до визначення умов кратності систем проміжків споживання. Одержані достатні умови кратності, які мають вигляд системи лінійних обмежень. Наведено випадки, при яких ці умови мають необхідний характер. Доведені загальні умови кратності (необхідні та достатні), які виконуються при різній довжині проміжків споживання.
. Задачі розподілу ресурсу у часі зведені до ряду задач математичного програмування, у яких умови кратності описані лінійними обмеженнями. Розв’язання вихідних задач вимагає повного перебору переставлень номерів споживачів. Отримано умови, при виконанні яких можна у явному вигляді описати оптимальні переставлення.
12. Сформульовано задачі динамічного управління запасами, які зведено до задач розподілу ресурсу між споживачами з однаковою потужністю. Досліджені випадки одного та декількох проміжків споживання, а також випадок змінних у часі обмежень. У задачах управління запасами застосовані лінійні та експоненціальні моделі динаміки зміни ресурсу.
13. Досліджено ряд задач, які виникають при розподілі гідроресурсу для потреб зрошуваного землеробства. Розроблена спрощена модель, яка грунтується на рівнянні дифузії і більш точно описує динаміку зміни вологості грунту, ніж балансові рівняння. Досліджені мінімаксні моделі, які дозволяють визначати економічно доцільні значення параметрів зрошувальних систем.
Основні положення дисертації опубліковані в таких працях:
Фінін Г.С. Стаціонарні і динамічні моделі та методи розподілу гідроресурсу.–Рукопис.
Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.05.02 –математичне моделювання та обчислювальні методи. –Інститут кібернетики імені В.М.Глушкова НАН України, Київ, 2001.
Розроблено математичні моделі розподілу води у відкритих каналах і мережах зрошувальних систем, що описують вихідну задачу за допомогою течій у сітках, для яких виконується узагальнений закон Кирхгофа.
Стаціонарні течії описано за допомогою систем лінійних нерівностей, що мають структуру графа. Для розв'язання систем лінійних нерівностей загального вигляду розроблено метод вилучення групи невідомих.
Досліджено випадки, коли доцільно вилучати групи невідомих, що відповідають кінцевому та проміжному підграфам. Якщо вилучається група невідомих, що відповідає кінцевому підграфу, то число нерівностей у новій системі зменшується. При вилученні невідомих течій, які відповідають проміжному підграфу, система нерівностей, структура якої задається цим підграфом, заміняється системою нерівностей, що зв'язують вхідну та вихідну течії. Число таких нерівностей визначається кількістю ланцюгів з різною вагою.
Введені поняття локально скінченного графа та локально скінченної системи нерівностей. Одержані критерії, які визначають коли система нерівностей має структуру графа. Розв'язки локально скінченних систем лінійних нерівностей представлені за допомогою апроксимації розв'язками скінченних систем нерівностей, які мають структуру скінченних підграфів локально скінченного графа.
Математичне формулювання задачі розподілу динамічних течій у сітках, для яких виконується узагальнений закон Кирхгофа, зроблено за допомогою систем лінійних включень, праві частини яких залежать від часу.
Досліджено властивості підграфів з однаковою довжиною шляхів від джерела до стоку. Такі підграфи розглянуті як кінцеві та проміжні. Розроблено методи вилучення групи невідомих течій, що течуть такими підграфами.
Запропоновано метод, який зводить задачу відшукання динамічних течій у сітках із загаювальним аргументом до задачі розв’язання систем лінійних нерівностей зі структурою скінченного або локально скінченного графів.
Розв’язання задач розподілу ресурсу у часі зведено до визначення умов кратності систем проміжків споживання. Одержані достатні умови кратності, які мають вигляд системи лінійних обмежень. Наведено випадки, при яких ці умови мають необхідний характер. Доведені загальні умови кратності (необхідні та достатні), які виконуються при різній довжині проміжків споживання.
Сформульовано задачі динамічного управління запасами, які зведено до задач розподілу ресурсу між споживачами з однаковою потужністю. Досліджені випадки одного та декількох проміжків споживання, а також випадок змінних у часі обмежень. У задачах управління запасами застосовані лінійні та експоненціальні моделі динаміки зміни ресурсу.
Досліджено ряд задач, які виникають при розподілі гідроресурсу для потреб зрошуваного землеробства. Розроблена спрощена модель, яка грунтується на рівнянні дифузії і більш точно описує динаміку зміни вологості грунту, ніж балансові рівняння. Досліджені мінімаксні моделі, які дозволяють визначати економічно доцільні значення параметрів зрошувальних систем.
Ключові слова: розподіл ресурсу, математична модель, системи лінійних нерівностей, вилучення групи невідомих, графи, течії у сітках, кратність проміжків споживання, управління запасами.
Finin G.S. Stationary and dynamical models and methods of distribution hydroresource.- Manuscript.
Thesis doctor of physics and mathematics on speciality 01.05.02 - mathematical modelling and computing methods. - Glushov Institute of cybernetics of National Academy of Sciences of Ukraine, Kiev, 2001.
There are developed the mathematical models of distribution of water in open channels and nets of irrigation systems describing an initial problem with the help of flows in nets for which the generalized law of the Kirchhoff is fulfilled.
The stationary flows are described with the help of systems of linear inequalities have a structure of the graph. For a solving of linear inequalities systems of a general view the methods of an elimination of unknowns are used.
Cases are investigated, when it is expedient to eliminate groups of unknowns appropriate to a defined subgraph. The definitions of final and intermediate subgraphs are formulated. If the group of unknowns appropriate to a final subgraph is eliminated the number of inequalities in a new system decreases. For an intermediate subgraph the chains connecting entering and output tops are considered and the definition of weight of these chains is given. For want of elimination of unknown flows appropriate to an intermediate subgraph, the system of inequalities, which structure is set by this subgraph, is substituted system of inequalities connecting entering and output flows. The number of such inequalities is determined by number of chains with different weight.
The concepts locally finite graph and locally of finite system of inequalities are entered. The criterions defining, when the system of inequalities has a structure the graph, are obtained. The solutions locally of finite systems of linear inequalities, are represented with the help of approximation by solutions of finite systems of inequalities have a structure of finite subgraphs of the locally finite graph.
The mathematical statement of a problem of distribution of dynamic flows in nets, for which the generalized law of the Kirchhoff is fulfilled, is made with the help of systems of linear inclusions, which right members depend on time.
The properties of subgraphs with identical length of paths from a source up to a drain are investigated. Such subgraphs are considered as final and intermediate. The methods of an elimination of group of unknown flows flowing on such subgraphs are developed.
The method reducing a problem of the definition of dynamic flows in nets with lagging argument to a problem of a solution of systems of linear inequalities with a structure of finite or locally finite graphs is offered.
The solution of the problems of resource distribution in time is reduced to the definition of conditions of a multiplicity of systems of consumption intervals. The sufficient conditions of multiplicity that are looking like a system of linear restrictions are obtained. Cases are reduced, when these conditions have a necessary character. The general conditions of a multiplicity (necessary and sufficient), fulfilled for different length of consumption intervals are proved.
The problems of resource distribution in time are reduced to a series of problems of mathematical programming, in which condition of a multiplicity are described by linear restrictions. The solution of initial problems requires full selection of permutations of numbers of customers. The conditions are obtained, for want of which realization it is possible in an obvious aspect to describe optimum permutations.
The formulated problems of dynamic storekeeping are reduced to problems of resource distribution between customers with an identical power. Cases one and several intervals of consumption, and also case of restrictions, varying in time are investigated. In problems of storekeeping the linear and exponential models of dynamics of resource change are applied.
The series of problems originating of distribution of hydroresource for needs of irrigation agriculture is investigated. The simplified model which bases on a diffusion equation, and more precisely describes dynamics of change of soil moisture, than balance equations, is developed. The minimax models permitting to determine economically expedient values of parameters of irrigation systems are investigated.
Key words: resource distribution, mathematical model, systems of linear inequalities, elimination of group of unknowns, graph, flows in nets, multiplicity of intervals of consumption, storekeeping.
Финин Г.С. Стационарные и динамические модели и методы распределения гидроресурса.–Рукопись.
Диссертация на соискание ученой степени доктора физико-математичесих наук по специальности 01.05.02 –математическое моделирование и вычислительные методы. –Институт кибернетики имени В.М.Глушкова НАН Украины, Киев, 2001.
В диссертационной работе рассмотрены вопросы распределения ресурсов в пространстве и во времени. Одновременно рассматриваются вопросы распределения водных ресурсов и управления запасами влажности почвы, что привело к новым формулировкам задач распределения и управления запасами.
Разработаны математические модели распределения воды в открытых каналах и сетях оросительных систем, описывающие исходную задачу с помощью потоков в сетях, для которых выполняется обобщенный закон Кирхгофа.
Стационарные потоки описаны с помощью систем линейных неравенств, имеющих структуру графа.
Для решения систем линейных неравенств общего вида использованы методы исключения неизвестных. Разработан метод исключения группы неизвестных, доказанный с помощью теоремы Хелли.
Исследованы случаи, когда целесообразно исключать группы неизвестных, соответствующие определенному подграфу. Сформулированы определения концевого и промежуточного подграфа. Если исключается группа неизвестных, соответствующих концевому подграфу, то число неравенств в новой системе уменьшается. Для промежуточного подграфа рассмотрены цепи, связывающие входную и выходную вершины, и дано определение веса этих цепей. При исключении неизвестных потоков, соответствующих промежуточному подграфу, система неравенств, структура которой задается этим подграфом, заменяется системой неравенств, связывающей входной и выходной потоки. Число таких неравенств определяется числом цепей с разным весом.
Введены понятия локально конечного графа и локально конечной системы неравенств. Получены критерии определяющие, когда система неравенств имеет структуру графа. Решения локально конечных систем линейных неравенств представлены с помощью аппроксимации решениями конечных систем неравенств, имеющих структуру конечных подграфов локально конечного графа.
Математическая формулировка задачи распределения динамических потоков в сетях, для которых выполняется обобщенный закон Кирхгофа, сделана с помощью систем линейных включений, правые части которых зависят от времени.
Исследованы свойства подграфов с одинаковой длиной путей от источника до стока. Такие подграфы рассмотрены как концевые и промежуточные. Разработаны методы исключения группы неизвестных потоков, текущих по таким подграфам.
Предложен метод, сводящий задачу определения динамических потоков в сетях с запаздывающим аргументом к задаче решения систем линейных неравенств со структурой конечного или локально конечного графов. Задача отыскания динамических потоков в мультиграфах сведена к задаче решения систем линейных неравенств со структурой конечного или локально конечного мультиграфов.
Разработан метод прогноза уровней ресурса в вершинах графа, являющегося деревом. Этот метод применен для распределения динамических потоков с учетом емкостей вершин.
При распределении ресурсов во времени между потребителями, имеющими одинаковую мощность, сформулированы задачи двух типов. В задачах первого типа осуществляется распределение ограниченного ресурса между потребителями. В задачах второго типа минимизируется распределяемый ресурс. Задачи обобщаются в случае потребления разной интенсивности и для нескольких интервалов потребления.
Решение сформулированных задач распределения ресурса сводится к определению условий кратности систем интервалов потребления. Получены достаточные условия кратности, имеющие вид системы линейных ограничений. Приведены случаи, когда эти условия имеют необходимый характер. Доказаны общие условия кратности (необходимые и достаточные), выполняющиеся при разной длине интервалов потребления.
Задачи распределения ресурса во времени сведены к ряду задач математического программирования, в которых условия кратности описаны линейными ограничениями. Решение исходных задач требует полного перебора перестановок номеров потребителей. Получены условия, при выполнении которых можно в явном виде описать оптимальные перестановки.
Сформулированные задачи динамического управления запасами сведены к задачам распределения ресурса между потребителями с одинаковой мощностью. Исследованы случаи одного и нескольких интервалов потребления, а также случай изменяющихся во времени ограничений. В задачах управления запасами применены линейные и экспоненциальные модели динамики изменения ресурса.
Исследовано ряд задач, возникающих при распределении гидроресурса для нужд оросительного земледелия. Разработана упрощенная модель, базирующаяся на уравнении диффузии, и более точно описывающая динамику изменения влажности почвы, чем балансовые уравнения. Исследованы минимаксные модели, позволяющие определять экономически целесообразные значения параметров оросительных систем.
Ключевые слова: распределение ресурсов, математическая модель, системы линейных неравенств, исключение группы неизвестных, графы, потоки в сетях, кратность интервалов потребления, управление запасами.