Національна Академія наук України
Національна Академія наук України
Інститут кібернетики імені В.М.Глушкова
Фінін Георгій Семенович
УДК 518.9
СТАЦІОНАРНІ І ДИНАМІЧНІ МОДЕЛІ ТА МЕТОДИ РОЗПОДІЛУ ГІДРОРЕСУРСУ
Спеціальність 01.05.02 – математичне моделювання
та обчислювальні методи
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
доктора фізико-математичних наук
Київ - 2001
Дисертацією є рукопис
Робота виконана в Навчально-науковому комплексі “Інститут прикладного системного аналізу” Національної Академії наук України та Міністерства освіти та науки України
Науковий доктор фізико-математичних наук, професор
консультант: Остапенко Валентин Володимирович,
Навчально-науковий комплекс “Інститут прикладного системного аналізу” Національної Академії наук України та Міністерства освіти та науки України
Офіційні опоненти:
доктор фізико-математичних наук, професор, член-кореспондент Національної Академії наук України Скопецький Василь Васильович, Інститут кібернетики імені В.М.Глушкова Національної Академії наук України, завідувач відділом,
доктор фізико-математичних наук, професор, член-кореспондент Національної Академії наук України Мельник Валерій Сергійович, Навчально-науковий комплекс “Інститут прикладного системного аналізу” Національної Академії наук України та Міністерства освіти та науки України, завідувач відділом,
доктор фізико-математичних наук, професор Ляшенко Ігор Миколайович, Київський національний університет імені Тараса Шевченка, завідувач кафедрою
Провідна установа:
Інститут проблем машинобудування імені А.М.Підгорного, відділ прикладної математики та обчислювальних методів Національної Академії наук України, м.Харків
Захист відбудеться “ 23 “листопада” 2001 року об 11 годині на засіданні спеціалізованої вченої ради Д26.194.02 при Інституті кібернетики імені В.М.Глушкова Національної Академії наук України за адресою:
проспект Академіка Глушкова, 40, 03680 МСП Київ 187.
З дисертацією можна ознайомитися в науково-технічному архіві інституту.
Автореферат розісланий “ 19 “жовтня” 2001 року
Учений секретар
спеціалізованої вченої ради Синявський В.Ф.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність роботи. В дисертаційній роботі розглянуті питання розподілу ресурсів у просторі і у часі. Такі задачі виникають при дослідженні екологічних проблем, пов’язаних із збереженням грунтів у зоні зрошуваного землеробства. Так збільшення потужності зрошувальних систем призводить до порушення екологічного балансу, деградації та засоленості грунтів, збільшенню вартості будівництва. Зниження – призводить до втрат врожаю з приводу недостатнього та несвоєчасного поливу сільськогосподарських культур.
Процес управління транспортом води під час руху каналами зрошувальних систем описується течіями у сітках з узагальненим законом Кирхгофа. Задача розподілу води між користувачами в умовах обмеженої перепускної спроможності зрошувальної системи призводить до необхідності розв’язувати задачі розподілу ресурсу (у даному випадку – зрошувальної води) між споживачами однакової інтенсивності. Дана задача тісно пов’язана із задачею управління запасами вологи у грунті. Таким чином у дисертації одночасно розглядаються питання розподілу водних ресурсів та управління запасами вологи у грунті, що привело до нових формулювань задач розподілу й управління запасами. Це дозволяє уникати технологічних скидань води з магістральних каналів, що запобігає підтоплення і заболочення зони зрошення.
Розроблені математичні методи розв’язання сформульованих задач дозволяють обчислювати оптимальні режими управління зрошувальними системами та одержувати оптимальні календарні графіки поливів. При цьому вирішується задача утримання вологості активного шару грунту у заданих межах. При практичному застосуванні ці методи повинні бути доповнені дослідженнями в області фільтрації, які грунтуються на роботах І.І.Ляшка, В.В.Скопецького, В.С. Дейнеки. Це дозволить оцінити втрати зрошувальної води, пов’язані із стіканням у грунт, а також визначити об’єм води, що перетікає з верхнього б’єфа до нижнього у процесі фільтрації.
На протязі останніх сорока років прикладна область теорії графів, за допомогою якої досліджуються моделі та методи розподілу течій у сітках, набула інтенсивного розвитку.
Становлення теорії розподілу течій у сітках починається з фундаментальних робот Л.Форда і Д.Фалкерсона. Різні автори, в залежності від методів розв’язання, відносять задачі розподілу течій у сітках до задач лінійного програмування, комбінаторної оптимізації або до екстремальних задач на графах.
Роботи присвячені розподілу течій у сітках можна об’єднати у дві великі групи. У першій групі досліджуються статичні течії, у другій – динамічні.
Різновидом сіткових задач є транспортні задачі і їх узагальнення – багатопродуктивні сіткові транспортні задачі, а також динамічні задачі розподілу ресурсу. Дослідженню цих задач присвячені роботи В.С.Михалевича, Н.З.Шора, В.А.Трубіна .
Розв’язанню задачі розподілу течій у сітках з нелінійною функцією цілі інтегрального виду присвячені роботи Б.М.Пшеничного.
Подальшим розвитком теорії статичних течій у сітках є динамічні задачі. У цих задачах враховується час переміщення течії дугами. Сітка містить вершини джерела та вершини стоки з визначеною динамікою виробництва і споживання течії, а також вершини склади, у яких течія може затримуватися.
Динамічною течією у сітці називають таку течію, яка задовольняє не тільки обмеженням на пропускні спроможності дуг і вершин у кожний момент часу, а і обмеженням часу проходження суміжними вершинами. Ця обставина визначає суттєву складність розв’язання динамічних задач. Динамічні задачі можна розділити на два класи: задачі з дискретним і неперервним часом.
В багатьох роботах вивчаються динамічні транспортні задачі, для вирішення яких запропоновані методи розв’язання шляхом зведення до визначеної статичної задачі більшої вимірності.
Течії з неперервним часом можна вивчати як граничний випадок динамічних течій з дискретним часом. Але може бути застосований і зворотній перехід від неперервної задачі до дискретної, оскільки, як правило, точний розв’язок неперервної задачі неможливо одержати.
Для розв’язання задач про динамічні течії розроблено також методи, які базуються на теорії оптимального управління.
У дисертації розглянуті течії у сітках з узагальненим принципом збереження. Дана проблематика виникла при розв’язанні задач управління рухом води у каналах зрошувальних систем, що розглянуті у роботах В.В.Остапенко. Узагальнений принцип збереження описано за допомогою системи лінійних нерівностей, структура якої задається відповідним графом.
Системи лінійних нерівностей і методи їх розв’язання досить повно досліджені у роботах С.М.Чернікова та його учнів. У цих роботах, в якості одного з методів, запропоновано метод послідовного вилучення невідомих (метод Фур’є). Велику увагу приділено питанню зменшення числа нових нерівностей, які утворюються в результаті застосування метода послідовного вилучення невідомих. Для цього використовується апарат згортання системи лінійних нерівностей.
Задачі розподілу ресурсу, які досліджуються у дисертації, відносяться до задач календарного планування. Розв’язанню задач календарного планування присвячені роботи В.С.Михалевича, О.І.Кукси, В.В.Шкурби.
Задача розподілу ресурсів тісно пов’язана із задачею управління запасами, яка є однією з найважливіших задач теорії дослідження операцій. У ряді робот графік зміни запасу описується у вигляді деякої “пилки” або кусково лінійної функції, яка зазнає розриви у мить поповнення запасів. Також динаміка зміни запасу описується кусково лінійною неперервною функцією. Побудовані детерміновані і стохастичні, лінійні і нелінійні моделі управління запасами різних видів матеріальних ресурсів. Розроблені детерміновані і стохастичні методи їх розв’язання. Досліджені задачі управління запасами при наявності збурень.
Таким чином тема дисертаційної роботи належить до актуальних напрямків дослідження операцій, пов’язаних з розподілом ресурсів у просторі та часі. Проблеми, що виникають з цього приводу, вивчаються багатьма науковцями. Ці проблеми тісно пов’язані з конкретними практичними задачами, які виникають у техніці, економіці, зрошуваному землеробстві та інших областях людської діяльності.
Зв’язок роботи з науковими програмами. Результати дисертаційної роботи є складовою частиною наступних науково-дослідних робіт.
1.
“Розробка теорії і методів оптимізації для підтримки прийняття рішень в задачах моделювання та керування складними динамічними об’єктами” (бюджетна тема Президії НАН України, № держреєстрації 019U006792, 1997-2000 рр.).
Автором розроблені методи розв’язання систем лінійних нерівностей, що мають структуру графа.
2.
“Розробка інструментальних засобів і чисельних методів оптимізації та прогнозу для підтримки прийняття рішень в задачах проектування та диспетчеризації” (ДНТП 06.02/05442, договір №2/899-97, № держреєстрації 0100U006209, 1997-2000 рр.).
Автором розроблені методи розподілу ресурсу між споживачами з рівною інтенсивністю.
3.
“Побудова алгебраїчних засад алгоритміки” (наукова-дослідна тема Міністерства освіти та науки України, договір № Ф4/228-97, № держреєстрації 01.04/00264, 1997 - 2000 рр).
Автором розроблені методи розподілу ресурсу, які формалізовані для побудови обчислювальних алгоритмів засобами алгоритміки.
Мета і задачі дослідження. Метою дослідження є розробка методів розв’язання нових задач розподілу ресурсу у просторі та часі, які виникають при дослідженні актуальних прикладних проблем.
Об’єктом дослідження є течії у сітках та задачі календарного планування. Предметом дослідження є задачі розподілу ресурсу у сітках з узагальненим законом збереження та задачі розподілу ресурсу у часі між рівнопотужними споживачами.
У дисертації використані методи теорії графів та течій у сітках, методи розв’язування систем лінійних нерівностей та диференціальних рівнянь, методи математичного програмування.
Наукова новизна одержаних результатів.
1.
Побудована модель руху води каналами зрошувальних систем, що має структуру довільного графа. Ця модель описує течії у сітках, які задовольняють узагальненому закону Кирхгофа. Раніше такі моделі застосовувались для зрошувальних систем зі структурою дерева.
2.
Дано обгрунтування метода вилучення невідомої з систем лінійних нерівностей, яке є більш простим ніж відомі. Розроблено метод вилучення групи невідомих з систем лінійних нерівностей, який базується на теоремі Хеллі.
3.
Введені поняття кінцевого та проміжного підграфів неорієнтованого графа та розроблені методи вилучення групи невідомих , що відповідають ребрам цих підграфів.
4.
Введені поняття кінцевого та проміжного підграфів орієнтованого графа та розроблені методи вилучення групи невідомих течій, що течуть ребрами цих підграфів. Методи враховують час проходження течією відповідної дуги.
5.
Розроблені наближені методи розв’язання системи лінійних нерівностей, які відповідають нескінченним графам. Введені поняття локально скінченних систем нерівностей та графів.
6.
Розроблено методи, які зводять задачу відшукання динамічних течій у сітках з узагальненим законом Кирхгофа до задачі розв’язання системи лінійних нерівностей зі структурою локально скінченного графа.
7.
Задачі розподілу ресурсу між рівнопотужними споживачами описані за допомогою поняття кратності системи проміжків споживання.
8.
Отримано необхідні та достатні умови, при яких система проміжків споживання має обмежену кратність.
9.
Задача розподілу ресурсів у часі зведена до перебору ряду задач математичного програмування. Отримано умови при яких вихідна задача зводиться до однієї задачі математичного програмування.
10.
Розв’язані задачі управління обмеженими запасами у системі декількох споживачів. Розглянуто лінійні та експоненціальні моделі, які описують динаміку зміни ресурсів у споживачів.
Практичне значення одержаних результатів. Практична цінність дисертаційної роботи обумовлена можливістю використання концептуальних підходів, моделей, методів і алгоритмів науково-дослідними та проектно-конструкторськими організаціями при розробці ресурсозберігаючих технологій та екологозахисних заходів в процесі проектування систем водо- і газопостачання та при розробці керуючих систем і процесів оперативного управління зрошенням та газорозподілом.
Запропоновані моделі, методи та алгоритми використані при розробці інформаційно-обчислювальної системи “Полив”, яка впроваджена у виробництво для розрахунків режимів зрошення сільськогосподарських культур Інститутом гідротехніки і меліорації УААН.
Особистий внесок здобувача. У наведених нижче роботах особисто здобувачем одержані наступні результати [13] – доведення теорем, які подають достатні умови визначеної кратності систем проміжків споживання; [14] – способи оптимального розподілу ресурсів між рівнопотужними споживачами описані за допомогою оптимальних переставлень номерів споживачів; [15] – розроблений ігровий підхід при проектуванні зрошувальних систем з урахуванням цін на сільськогосподарську продукцію та будівництво і експлуатацію систем; [16] – на основі застосування функції розподілу сезонної потреби зрошувальної води розроблено чисельний метод визначення потужності зрошувальних систем при заданому рівні водозабезпеченості; [17] – розроблені лінійні моделі зміни вологості в активному шарі грунту, розв’язані задачі комплектування графіків поливів, як задачі лінійного та квадратичного програмування; [18] – одержані необхідні та достатні умови визначеної кратності проміжків споживання різної довжини; [19] – за допомогою систем лінійних нерівностей описані необхідні та достатні умови визначеної кратності проміжків споживання рівної довжини, придатні для розробки чисельних методів; [20] – розв’язана задача управління обмеженими запасами декількох споживачів; [21] – досліджені стаціонарні та динамічні течії у сітках з узагальненим законом Кирхгофа, обмеження описані у вигляді систем лінійних нерівностей, для яких запропоновані методи розв’язання; [22] – розроблена математична модель руху води у відкритих руслах, яка описана за допомогою узагальненого закону Кирхгофа, придатна для розв’язання задач управління; [23] – розроблено метод вилучення групи невідомих із систем лінійних нерівностей зі структурою графа для випадків кінцевого та проміжного підграфів; [24] – розроблено наближений метод апроксимації розв’язків нескінченної системи лінійних нерівностей за допомогою розв’язків скінченних систем; [25] – задача визначення динамічних течій у сітках з урахуванням часу загаювання зведена до розв’язання локально скінченних систем лінійних нерівностей; [26] – розроблено метод вилучення невідомих із систем лінійних нерівностей загального виду; [27] – розроблено спосіб розв’язування локально скінченної системи лінійних нерівностей та сформульовано критерій, коли ця система має структуру графа; [28] – розроблено чисельний метод стягування дуг при розв’язанні систем лінійних нерівностей зі структурою графа; [32] – запропоновано моделювання течій у сітках за допомогою узагальненого закону Кирхгофа;. [33] – введено поняття кратності системи проміжків споживання; [34] – задача розподілу ресурсу у часі зведена до задач математичного програмування з лінійними обмеженнями;
Апробація результатів дисертації. Результати досліджень, що включені до дисертації, оприлюднені на наступних наукових конференціях: “Современные проблемы планирования и управления водохозяйственными системами”: Новочеркасск, 1990; 3-тя Українська конференція з автоматичного керування “Автоматика – 96”: Севастополь, 1996; міжнародна конференція “Моделирование и исследование устойчивости систем”: Київ, 1997; міжнародна конференція “Питання оптимізації обчислень”: Київ, 1997; 5-та Українська конференція з автоматичного управління “Автоматика – 98”: Київ, 1998; 9-та конференція “Аналіз ризиків”: Роттердам, 1999; 6-та Українська конференція з автоматичного управління “Автоматика – 99”: Харків, 1999; міжнародна конференція “Моделювання та оптимізація складних систем”: Київ, 2001.
Зроблені доповіді на наукових семінарах в ННК “Інститут прикладного системного аналізу” НАН України та Міносвіти і науки України, Київському національному університеті імені Тараса Шевченка та Інституті кібернетики імені В.М.Глушкова НАН України.
Публікації. Результати дисертації опубліковані у 34 роботах. Із них у наукових журналах – 22, збірниках наукових праць – 4, матеріалах і тезах конференцій – 8.
При цьому особисто здобувачем написані 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 – 3.
Лінійні нерівності для графа з одним джерелом і одним стоком. Нехай – слабозв’язний орієнтований граф. Вершину назвемо джерелом, якщо вершину назвемо стоком, якщо Дуги утворюють шлях у . Величину назвемо довжиною шляху.
Припущення 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–му році. Припускаємо, що вектори змінюються відповідно у множинах .
ВИСНОВКИ
1. Розроблено математичні моделі розподілу води у відкритих каналах і мережах зрошувальних систем, що описують вихідну задачу за допомогою течій у сітках, для яких виконується узагальнений закон Кирхгофа.
2. Стаціонарні течії описано за допомогою систем лінійних нерівностей, що мають структуру графа.
3. Для розв'язання систем лінійних нерівностей загального вигляду використані методи вилучення невідомих. Розроблено метод вилучення групи невідомих, який доведено за допомогою теореми Хеллі.
4. Досліджено випадки, коли доцільно вилучати групи невідомих, що відповідають певному підграфу. Сформульовані визначення кінцевого та проміжного підграфів. Якщо вилучається група невідомих, що відповідає кінцевому підграфу, то число нерівностей у новій системі зменшується. Для проміжного підграфа розглянуті ланцюги, які пов'язують вхідну і вихідну вершини та дано визначення ваги цих ланцюгів. При вилученні невідомих течій, які відповідають проміжному підграфу, система нерівностей, структура якої задається цим підграфом, заміняється системою нерівностей, що зв'язують вхідну та вихідну течії. Число таких нерівностей визначається кількістю ланцюгів з різною вагою.
5. Введені поняття локально скінченного графа та локально скінченної системи нерівностей. Одержані критерії, які визначають коли система нерівностей має структуру графа. Розв'язки локально скінченних систем лінійних нерівностей представлені за допомогою апроксимації розв'язками скінченних систем нерівностей, які мають структуру скінченних підграфів локально скінченного графа.
6. Математичне формулювання задачі розподілу динамічних течій у сітках, для яких виконується узагальнений закон Кирхгофа, зроблено за допомогою систем лінійних включень, праві частини яких залежать від часу.
7. Досліджено властивості підграфів з однаковою довжиною шляхів від джерела до стоку. Такі підграфи розглянуті як кінцеві та проміжні. Розроблено методи вилучення групи невідомих течій, що течуть такими підграфами.
8. Запропоновано метод, який зводить задачу відшукання динамічних течій у сітках із загаювальним аргументом до задачі розв’язання систем лінійних нерівностей зі структурою скінченного або локально скінченного графів.
9. Розроблено метод прогнозу рівнів ресурсу у вершинах графа, який є деревом. Цей метод застосовано до розподілу динамічних течій з урахуванням ємностей вершин.
10. Розв’язання сформульованих задач розподілу ресурсу зводиться до визначення умов кратності систем проміжків споживання. Одержані достатні умови кратності, які мають вигляд системи лінійних обмежень. Наведено випадки, при яких ці умови мають необхідний характер. Доведені загальні умови кратності (необхідні та достатні), які виконуються при різній довжині проміжків споживання.
11. Задачі розподілу ресурсу у часі зведені до ряду задач математичного програмування, у яких умови кратності описані лінійними обмеженнями. Розв’язання вихідних задач вимагає повного перебору переставлень номерів споживачів. Отримано умови, при виконанні яких можна у явному вигляді описати оптимальні переставлення.
12. Сформульовано задачі динамічного управління запасами, які зведено до задач розподілу ресурсу між споживачами з однаковою потужністю. Досліджені випадки одного та декількох проміжків споживання, а також випадок змінних у часі обмежень. У задачах управління запасами застосовані лінійні та експоненціальні моделі динаміки зміни ресурсу.
13. Досліджено ряд задач, які виникають при розподілі гідроресурсу для потреб зрошуваного землеробства. Розроблена спрощена модель, яка грунтується на рівнянні дифузії і більш точно описує динаміку зміни вологості грунту, ніж балансові рівняння. Досліджені мінімаксні моделі, які дозволяють визначати економічно доцільні значення параметрів зрошувальних систем.
Основні положення дисертації опубліковані в таких працях:
1.
Финин Г.С. Определение потребности оросительной воды при заданном уровне водообеспеченности // Мелиорация и водное хозяйство. - 1992.- вып. 77.- С.24-28.
2.
Фінін Г.С. Комплектування графіків поливу на сукупності ланів сівозміни // Мелиорация и водное хозяйство. - 1993.- вып. 78.- С.12-16.
3.
Фінін Г.С. Мінімаксні моделі визначення параметрів зрошувальних систем // Гідротехніка і меліорація в Україні : збірка наукових праць.- Київ, 1993.- вип. 2. - С. 58-63.
4.
Финин Г.С. Модели влагопереноса для управления влажностью почвы // Проблемы управления и автоматики. - 1999. - № 2. - С. 84-90.
5.
Финин Г.С. Решение систем линейных неравенств методами исключения неизвестных // Вестник Международного Соломонового университета. - 1999.- №1.- С. 116-122.
6.
Финин Г.С. Метод исключения группы неизвестных потоков в сетях с обобщенным законом Кирхгофа // Кибернетика и системный анализ. - 1999.- № 6.- С. 154-159.
7.
Фінін Г.С. Опукла модель розподілу гідроресурсу між споживачами // Математические машины и системы. - 1999.-№2.- С. 78-82.
8.
Финин Г.С. Методы исключения неизвестных в задачах управления потоками в сетях // Вісник Харківського державного політехнічного університету. Збірка наукових праць. Випуск 72.- Харків: ХДПУ, 1999.- С. 16-22.
9.
Финин Г.С. Решение задач распределения ресурса на графах // Доповіді НАН України,- 2000,- № 3.- С. 101-103.
10.
Финин Г.С. Распределение динамических потоков в сетях // Доповіді НАН України,- 2000,- № 4.- С. 97-100.
11.
Финин Г.С. Динамічні течії у сітках із загаювальним аргументом // Доповіді НАН України,- 2000,- № 5.- С. 101-104.
12.
Финин Г.С. Решение локально конечной системы линейных неравенств со структурой ориентированного мультиграфа // Кибернетика и системный анализ. - 2000.- № 6. - С. 173-177.
13.
Остапенко В.В., Поливода О.В., Финин Г.С. Задача распределения ресурсов между равноинтенсивными потребителями // Оптимизация и ее приложения : Сб.науч.тр./ НАН Украины, Ин-т кибернетики им. В.М.Глушкова.- К, 1997. - С. 3-8.
14.
Остапенко В.В., Поливода О.В., Финин Г.С. Оптимальное распределение ресурсов для потребителей с равным расходом // Доповіді НАН України,- 1998,- № 6.- С. 106-109.
15.
Остапенко В.В., Финин Г.С. Минимаксный подход к проектированию оросительных систем // Автоматика. - 1990 - №6.- С. 45-51.
16.
Остапенко В.В., Фінін Г.С. Про чисельний метод визначення потужності зрошувальних систем // ДАН УРСР.- 1991.- №9.- С. 54-58.
17.
Остапенко В.В., Финин Г.С. Математическое моделирование в задачах комплектования графиков поливов // Автоматика. - 1992 - №5.- С. 77-82.
18.
Остапенко В.В., Финин Г.С. Оптимизация системы интервалов потребления в задаче распределения ресурса // Проблемы управления и информатики. - 1998. - № 1. - С. 120-127.
19.
Остапенко В.В., Финин Г.С. Кратность системы интервалов в задаче распределения ресурсов // Кибернетика и системный анализ. - 1998. № 1. - С. 175-181.
20.
Остапенко В.В., Финин Г.С. Динамическая задача удержания запасов в заданных пределах // Кибернетика и вычислительная техника. - 1998.- вып.117.- С. 7 - 14 .
21.
Остапенко В.В., Финин Г.С. Потоки в сетях с обобщенным принципом сохранения // Журнал обчислювальної і прикладної математики. – 1999.- № 1 (84).- С. 82-86.
22.
Остапенко В.В., Финин Г.С. Моделирование движения воды обобщенным законом Кирхгофа // Проблемы управления и автоматики. - 1999. - № 4. - С. 86-90.
23.
Остапенко В.В., Финин Г.С. Метод исключения неизвестных для систем линейных неравенств со структурой графа // Кибернетика и системный анализ. - 1999. № 5. - С. 66-74.
24.
Остапенко В.В., Финин Г.С. Системы линейных неравенств со структурой бесконечного графа// Проблемы управления и автоматики. - 2000. - № 3. - С.86-90.
25.
Остапенко В.В., Фінін Г.С Методи управління течіями у сітках з узагальненим принципом збереження // Математичні машини і системи. - 2000. -№ 2, 3. - С. 59-63.
26.
Остапенко В.В., Финин Г.С. Методы исключения неизвестных из систем линейных неравенств и их приложения // Український математичний журнал. – 2001. № 4. – С. 568-571.
27.
Остапенко В.В., Фінін Г.С Розв’язок локально скінченної системи нерівностей зі структурою графа // Український математичний журнал. – 2001. № 1. – С. 50-56.
28.
Остапенко В.В., Финин Г.С., Ганношина И.Н. Стягивание дуг при решении систем линейных неравенств со структурой графа // Кибернетика и системный анализ. - 2000. №2. - С. 167-170.
29.
Финин Г.С. Определение параметров оросительных систем игровыми способами // Современные проблемы планирования и управления водохозяйственными системами : Тез. докл. - Новочеркасск, 1990.
30.
Фінін Г.С. Кратність систем підмножин в задачі управління ресурсами // Праці П'ятої конференції з автоматичного управління “Автоматика-98”: Київ, 13-16 травня 1998р. -ч.1-Київ: видавництво НТУУ “КПІ”, 1998.- С.129-135.
31.
Finin G.S. Control of irrigation conditions to minimize the risk jf grope fields losses // 9 th Annual Conference Risk Analysis: Facing the New Millennium, Rotterdam, October 10-13, 1999. P. 791.
32.
Остапенко В.В., Павлыгин А.И., Финин Г.С. Обобщенный принцип сохранения потоков в сетях // Праці 3 - ї конференції з автоматичного керування “Автоматика-96”: Севастополь , 1996. -Севастополь: СевГТУ, 1996.-Т.2 С. 137.
33.
Остапенко В.В., Поливода О.В., Финин Г.С. Моделирование процесса распределения ресурсов с помощью понятия кратности систем интервалов потребления // Моделирование и исследование устойчивости систем : Тез. междунар. конф. - Киев, 1997.- С. 96.
34.
Остапенко В.В., Поливода О.В., Фінін Г.С. Зведення однієї задачі розподілу ресурсів до задачі математичного програмування // Питання оптимізації обчислень :Праці міжнар.конф. / НАН України, Ін-т кибернетики ім. В.М.Глушкова.- К, 1997.- С. 244-248.
Фінін Г.С. Стаціонарні і динамічні моделі та методи розподілу гідроресурсу.– Рукопис.
Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. – Інститут кібернетики імені В.М.Глушкова НАН України, Київ, 2001.
Розроблено математичні моделі розподілу води у відкритих каналах і мережах зрошувальних систем, що описують вихідну задачу за допомогою течій у сітках, для яких виконується узагальнений закон Кирхгофа.
Стаціонарні течії описано за допомогою систем лінійних нерівностей, що мають структуру графа. Для розв'язання систем лінійних нерівностей загального вигляду розроблено метод вилучення групи невідомих.
Досліджено випадки, коли доцільно вилучати групи невідомих, що відповідають кінцевому та проміжному підграфам. Якщо вилучається група невідомих, що відповідає кінцевому підграфу, то число нерівностей у новій системі зменшується. При вилученні невідомих течій, які відповідають проміжному підграфу, система нерівностей, структура якої задається цим підграфом, заміняється системою нерівностей, що зв'язують вхідну та вихідну течії. Число таких нерівностей визначається кількістю ланцюгів з різною вагою.
Введені поняття локально скінченного графа та локально скінченної системи нерівностей. Одержані критерії, які визначають коли система нерівностей має структуру графа. Розв'язки локально скінченних систем лінійних нерівностей представлені за допомогою апроксимації розв'язками скінченних систем нерівностей, які мають структуру скінченних підграфів локально скінченного графа.
Математичне формулювання задачі розподілу динамічних течій у сітках, для яких виконується узагальнений закон Кирхгофа, зроблено за допомогою систем лінійних включень, праві частини яких залежать від часу.
Досліджено властивості підграфів з однаковою довжиною шляхів від джерела до стоку. Такі підграфи розглянуті як кінцеві та проміжні. Розроблено методи вилучення групи невідомих течій, що течуть такими підграфами.
Запропоновано метод, який зводить задачу відшукання динамічних течій у сітках із загаювальним аргументом до задачі розв’язання систем лінійних нерівностей зі структурою скінченного або локально скінченного графів.
Розв’язання задач розподілу ресурсу у часі зведено до визначення умов кратності систем проміжків споживання. Одержані достатні умови кратності, які мають вигляд системи лінійних обмежень. Наведено випадки, при
