Особенности и применение технологии DWDM

270 

Изначально  среда Delphi была  предназначена  исключительно  для  разработки  приложений 

Microsoft Windows, затем был реализован вариант для платформ Linux, однако после выпуска в 2002 

году Kylix 3, его разработка была прекращена, и вскоре было объявлено о поддержке Microsoft.NET [1]. 

Delphi - прекрасная  система  визуального  объектно-  ориентированного  проектирования, 

одинаково  радующая  и  новичков  в  программировании,  и  профессионалов.  Начинающим Delphi 

позволяет сразу, с небольшими затратами времени и сил создавать прикладные программы, которые 

внешне неотличимы от программ, созданных профессионалами. А для опытного программиста Delphi 

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

в том числе, распределённых приложений, работающих с любыми базами данных [2].  

Для удобства работы в приложении необходимо разработать «дружественный» визуальный интерфейс. 

Разработка  приложений  проходит  в  несколько  этапов.  Понимание  сути  каждого  из  этапов 

разработки  программного  обеспечения  поможет  правильно  выбрать  круг  действий,  которые 

необходимо выполнить для создания качественной программы: 

  Определение  требований.  Выявление  потенциальных  пользователей  создаваемого 

приложения и максимально точное описание предъявляемых ими требования. 

  Проектирование. Анализ задач, для решения которых разрабатывается приложение, создание 

проекта, удовлетворяющего требованиям пользователей. 

  Разработка. Написание кода, отладка и документирование программы, при условии, что она 

удовлетворяет требованиям пользователей. 

К  численному  интегрированию  обращаются,  когда  нельзя  через  элементарные  функции 

аналитически записать первообразную интеграла: 

 





b

a

dx

x

f

J

,                                                                  (1) 

или  когда  подобная  запись  имеет  сложный  вид,  где 

b

a

,

 – нижний  и  верхний  пределы 

интегрирования, 

 

x

f

 – непрерывная функция на отрезке 

 

b

a,

. 

Сущность  большинства  методов  вычисления  определенных  интегралов  состоит  в  замене 

подынтегральной  функции 

 

x

f

  аппроксимирующей  функцией 

 

x



,  для  которой  можно  легко 

записать первообразную в элементарных функциях, т.е. 

 

 

R

S

R

dx

x

dx

x

f

J

b

a

b

a

















,                                                (2) 

где 

S

– приближенное значение интеграла, 

R

– погрешность вычисления интеграла. 

Методы  численного  интегрирования,  используемые  на  практике,  можно  сгруппировать  в 

зависимости от способа аппроксимации подынтегральной функции. 

Методы  Ньютона – Котеса  основаны  на  полиномиальной  аппроксимации  подынтегральной 

функции.  Методы  этого  класса  отличаются  друг  от  друга  степенью  используемого  полинома,  от 

которой  зависит  количество  узлов,  где  необходимо  вычислить  функцию 

 

x

f

.  Алгоритмы  методов 

просты и легко поддаются программной реализации. 

Сплайновые  методы  базируются  на  аппроксимации  подынтегральной  функции  сплайнами, 

представляющими  собой  кусочный  полином.  Методы  различаются  по  типу  выбранных  сплайнов. 

Такие  методы  имеет  смысл  использовать  в  задачах,  где  алгоритмы  сплайновой  аппроксимации 

применяются для обработки данных. 

В  методах  наивысшей  алгебраической  точности  (методы  Гаусса-Кристоффеля  и  другие) 

используют не равноотстоящие узлы, расположенные по алгоритму, обеспечивающему минимальную 

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

Методы  различаются  способами  выбора  узлов  и  широко  используются  для  интегрирования.  в  том 

числе  они  применимы  и  для  несобственных  интегралов.  Хотя  из-за  необходимости  хранения 

числовых  констант  и  стандартизации  пределов  интегрирования  программы  указанных  методов 

требуют несколько большего объема памяти по сравнению с методами Ньютона – Котеса. 

В  методах  Монте-Карло  узлы  выбираются  с  помощью  датчика  случайных  чисел,  ответ  носит 

вероятностный характер. Методы оказываются эффективными при вычислении большой кратности. 

В  класс  специальных  группируются  методы,  алгоритмы  которых  разрабатываются  на  основе 

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

время и уменьшить погрешность вычисления интегралов. 

271 

Нами  разработано  приложение  для  автоматизации  численного  интегрирования  определенных 

интегралов в среде Delphi. Были выбраны простейшие методы из класса методов Ньютона – Котеса, 

когда подынтегральную функцию 

 

x

f

 на интервале интегрирования заменены полиномом нулевой 

степени, т.е. константой.  

В приложении запрограммированы алгоритмы вычисления определенных интегралов методами 

прямоугольников, трапеции и Симпсона. 

Известно,  что  определенный  интеграл  функции  представляет  собой  площадь  криволинейной 

трапеции, ограниченной кривыми 

0



x

, 

a

y



, 

b

y



 и 

 

x

f

y



 (рис. 1):  

 

 

 

Рисунок 1. График функции 

 

Численное интегрирование по этим методам осуществляется следующим образом. 

В  методе  прямоугольников  подынтегральная  функция 

 

x

f

  заменяется  кусочно-постоянной 

функцией,  т.е.  функцией,  постоянной  на  каждом  отрезке 

]

,

[

1

i

i

x

x



.  Значение  этой  постоянной  на 

каждом отрезке будет разным, равным 





2

/

1

i

i

h

x

f





. 

        

  

 

(а)  

 

 

 

 

     (б) 

 

Рисунок 2. Геометрический смысл замены 

 

x

f

 на одном элементарном отрезке 

]

,

[

1

i

i

x

x



 и  

на всем отрезке 

 

b

a,

 а) кусочно-постоянной функцией в методе прямоугольников, (б)  

кусочно-линейной функцией в методе трапеции. 

 

Видно, что искомая площадь заменяется суммой площадей соответствующих прямоугольников 

(рис. 2, а) и трапеций (рис. 2, б).  

Квадратурная  формула  вычисления  сумм  площадей,  т.е.  приближенного  значения  интеграла 

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

 

b

a,

: 

 





R

h

x

f

h

dx

x

f

S

i

i

n

i

i

b

a



















2

/

1

1

,                                           (3) 

Метод трапеций использует для описания функции 

 

x

f

 линейную интерполяцию, заменяя ее 

кусочно-линейной  функцией  на  отрезке 

 

b

a,

,  т.е.  ломаной,  соединяющей  точки 

i

x

,  

 

i

i

x

f

y



. 

Квадратурная  формула  вычисления  площади  трапеции,  т.е.  приближенного  значения  интеграла 

методом трапеции на всем отрезке 

 

b

a,

: 

 





R

h

y

y

dx

x

f

S

n

i

i

i

i

b

a



















1

1

2

1

,                                              (4) 

272 

Погрешность на всем интервале 

 

b

a,

 равна:           



  



f

a

b

h

R









12

2

,   

 





b

a,





,             (5) 

Во  многих  случаях  требуется  вычислять  интегралы  для  таблично  заданных  функций,  когда 

точки  разбиения  отрезка 

 

b

a,

  на  элементарные  отрезки  заданы,  и  повысить  точность  численного 

интегрирования  путем  уменьшения  шага  не  удается.  В  этом  случае  желательно  использовать 

квадратурные формулы, которые при том же разбиении отрезка дают более высокую точность, чем 

методы  прямоугольников  и  трапеций.  Одним  из  таких  методов  является  метод  Симпсона. 

Повышение точности в нем достигается за счет повышения точности интерполяции – функция 

 

x

f

 

заменяется интерполяционным многочленом Лагранжа второй степени (квадратичная интерполяция).  

Квадратурная  формула  вычисления  приближенного  значения  интеграла  методом  Симпсона  на 

всем отрезке 

 

b

a,

: 

 



 















n

n

n

n

n

n

b

a

y

y

y

y

y

y

y

y

h

y

y

y

y

y

y

y

y

y

h

dx

x

f

S





















































1

2

4

3

2

1

0

1

2

4

3

2

2

1

0

4

2

...

2

4

2

4

3

4

...

4

4

3

,               (6) 

Переходим  к  проектированию  визуального  интерфейса  используя  такие  компоненты,  как Main 

Menu, Save Dialog, Label, Edit, Combo Box, List Box, Button, Page Control. 

 

 

 

Рисунок 3. Визуальный интерфейс приложения 

 

В приложении использовались модальные формы (рис. 4, 5): 

 

 

 

Рисунок 4. Форма, вызывающая справку о программе. 

273 

 

 

Рисунок 5. Форма для условных обозначений. 

 

Визуализация  метода.  В  главном  окне  выберем  метод  решения,  далее  выбираем  функцию  для 

решения и нажимаем на кнопку «Solve».  

После нажатия кнопки выводится окно, где необходимо ввести данные: 

 

 

 

Рисунок 6. Главное окно формы с окном Input Box 

 

Для  ввода  пределов  интегрирования  использовалась  функция  вызова  диалогового  окна  ввода 

Input Box (рис. 6), для вывода шага вычисления использовалась процедура вызова диалогового окна 

Show Message (рис.7): 

 

 

Рисунок 7. Окно Show Message 

 

В  результате  выполнения  программы  результаты  расчетов  записываются  в List Box и 

сохраняются в формате txt в отдельном файле.  

274 

 

 

Рисунок 8. Главное окно приложения с результатами расчетов 

 

В приложении имеется 3 вкладки компонента Page Control для трех методов интегрирования – 

прямоугольников, трапеции и Симпсона.  

На рисунке 8 показано также, что на вкладке метода прямоугольников использовался еще один 

компонент Page Control для  выбора  одного  из  трех  методов  численного  интегрирования  методом 

прямоугольников:  метод  левых  прямоугольников,  метод  средних  прямоугольников  и  метод  правых 

прямоугольников. 

Независимо  от  выбранного  метода  в  процессе  численного  интегрирования  необходимо 

вычислить  приближенное  значение 

S

  интеграла (1) и  оценить  погрешность 

R

 (2). Погрешность 

будет  уменьшаться  при  увеличении  количества  разбиений 

N

  интервала  интегрирования 

 

b

a,

  за 

счет  более  точной  аппроксимации  подынтегральной  функции,  однако  при  этом  будет  возрастать 

погрешность за счет суммирования частичных интегралов. 

Это обстоятельство должно предостеречь от выбора чрезмерно большого числа 

N

 и привести к 

необходимости разработки способа оценки погрешности 

R

 выбранного метода интегрирования. 

Разработанный  проект  наглядно  показывает,  что Delphi - прекрасная  система  визуального 

объектно - ориентированного проектирования. 

Delphi  упрощает  создание  программ,  переводя  его  на  визуальный  уровень.  Это  позволяет 

программисту  сразу  сосредоточиться  на  сути  решаемой  задачи.  В  этом  контексте  система Delphi 

представляется  средой,  близкой  к  идеальной.  Комфортное  место  разработчика  сочетается  с 

множеством  технологий,  интегрированных  в  среду,  причём  для  перехода,  допустим,  к  новой 

технологии  доступа  к  данным  не  требуется  изучать  никаких  новых  методик.  Требуется  понимание 

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

 

ЛИТЕРАТУРА: 

1. https://ru.wikipedia.org. Свободная энциклопедия. 

2. Хомоненко А.Д.. Delphi 7. -СПб.: "БХВ-Петербург", 2008. 

 

REFERENCES: 

1. https://ru.wikipedia.org. The free encyclopedia. 

2. Khomonenko A.D. Delphi 7. -SPb .: "BHV-Petersburg", 2008. 

 

Масимова Г.Г., Заманова С.Қ. 

Delphi ортасында анықталған интегралдарды сандық интегралдау үшін қосымша құру 

Түйіндеме.  Жұмыста Delphi ортасында  анықталған  интегралдарды  есептеу  үшін  қосымша  құру 

қарастырылған. Визуалдық жобалаудың ерекшеліктері келтірілген.  

Түйін сөздер: анықталған интеграл, Delphi бағдарламалау ортасы, сандық интегралдау. 

 

Massimova G.G., Zamanova S.K. 

Developing an application for the numerical integration of definite integrals in the environment delphi 

Summary. The paper deals with the development of applications in Delphi programming environment for 

computing definite integrals. Given the features of visual design.  

Key words: definite integrals, programming environment Delphi, numerical integration. 

275 

УДК 519.17  

 

Медетбекова У. бакалавр, Наурызбаева А.И., Тулегенова Б.А.

 

Казахский национальный технический университет имени К.И. Сатпаева 

г. Алматы, Республика Казахстан 

ganar_1@mail.ru 

 

РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА «ПОИСК МАКСИМАЛЬНОГО  

ПОТОКА МЕТОДОМ ФОРДА-ФАЛКЕРСОНА» 

 

Аннотация. Программное решение одной из задач оптимизации – задачи о максимальном потоке в сети. 

Задача  занимает  центральное  место  в  теории  сетей  применительно  к  организации  работы  транспорта, 

компьютерных  сетей,  систем  нефтепроводов.  В  данной  статье  рассматривается  нахождение  максимального 

потока с помощью алгоритма Форда-Фалкерсона, разработан программный комплекс. 

Ключевые слова. Алгоритм Форда-Фалкерсона, максимальный поток, сеть. 

 

Преимущества цепей поставок в логистических системах определяются потенциалом возможности 

приращения ценности реализуемого продукта для конечного потребителя. В этой связи стратегические 

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

пропорциональный  метод  распределения  товара  в  сети,  зачастую,  не  имеет  возможности  привести  в 

соответствие располагаемые мощности поставщика, транспортной организации, центра распределения 

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

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

современные особенности процесса управления логистическими системами [1].  

Алгоритм Форда – Фалкерсона нахождения максимального потока в сети 

Теорема Форда-Фалкерсона 1 (о максимальном потоке и минимальном разрезе). 

В  любой  сети  существует  максимальный  поток.  Величина  максимального  потока  равна 

пропускной способности минимального разреза [2]. 

Теорема Форда-Фалкерсона 2. 

Поток, вычисленный с помощью алгоритма Форда-Фалкерсона имеет максимальную величину, а 

разрез (X,X), где X-множество  вершин,  помеченных  при  последнем  помечивании,  имеет 

минимальную пропускную способность. 

Описание алгоритма 

Пусть изначально в сети имеется поток f (допустим с нулевыми значениями на всех дугах). 

Алгоритм  Форда-Фалкерсона  для  нахождения  максимального  потока  в  сети  состоит  из  двух 

процедур: 

1) Процедура помечивания вершин 

2) Процедура изменения потока 

1) Процедура помечивания вершин. 

Обработка i-й  вершины  с  пометкой (x,e) заключается  в  том,  что  из  вершины i помечаются 

смежные непомеченные вершины по следующему правилу: 

- если дуга направлена из i в j и поток по этой дуге (f

ij

) меньше пропускной способности дуги 

(c

ij

), то вершине j присваивается метка (i

+

,min(e,c

ij

-f

ij

)) 

- если дуга направлена из j в i и поток по этой дуге (f

ji

) больше нуля, то вершине j присваивается 

метка (i

-

,min(e,f

ji

)) 

Эта  процедура  всегда  начинается  с  помечивания  и  обработки  истока.  Он  помечается  особой 

меткой (-, ). Затем обрабатываются другие помеченные вершины (после обработки истока пометятся 

вершины, смежные с ним) и т.д. 

Процесс помечивания заканчивается в двух случаях: 

1) Ни одну вершину больше нельзя пометить, но сток не помечен. Это  значит, что найденный 

поток - максимальный и алгоритм останавливается. 

2) Помечается сток. В этом случае производится изменение потока. 

2) Процедура изменения потока. 

Если сток получил метку (k

+

,d), то потоки будут изменяться на величину d следующим образом: 

- если мы находимся в вершине j с меткой (i

+

,x), то прибавляем d к f

ij

 и переходим в вершину i. 

- если мы находимся в вершине j с меткой (i

-

,x), то вычитаем d из f

ij

 и переходим в вершину i. 

Изменение потока начинается от стока и продолжается до достижения истока. После этого все 

метки стираются и заново выполняется процедура помечивания вершин. 

276 

Этот  процесс  продолжается  до  тех  пор,  пока  не  будет  найден  максимальный  поток  (ни  одну 

вершину больше нельзя пометить, но сток не помечен) [3]. 

Разработанный  программный  комплекс  на  основе  алгоритма  Форда – Фалкерсона  нахождения 

максимального потока в сети состоит из разделов «Визуальный редактор», «Решение», «Граф». При 

запуске программы открывается окно «Поиск максимального потока методом Форда - Фалкерсона» 

(рисунок 1). 

 

 

 

Рисунок 1. Вид главного окна «Поиск максимального потока методом Форда-Фалкерсона»  

 

В  верхней  части  окна  созданы  меню  «Файл»  и  «Справка».  Меню  «Файл»  состоит  из  разделов 

«Новый  граф», «Открыть», «Сохранить»  и  «Выход»,  они  используются  для  создания  нового  графа, 

открытия уже существующего графа, сохранения построенного графа и выхода из программы.  

Раздел  «Визуальный  редактор»  включает  кнопки  «Разместить  вершину», «Добавить  ребро», 

«Удалить вершину». С помощью этих кнопок можно осуществить следующие действия: разместить 

вершину, добавить ребро, удалить вершину. 

Вид раздела «Визуальный редактор» показан на рисунке 2.  

 

 

 

Рисунок 2. Вид раздела «Визуальный редактор» 

 

В  разделе  «Решение»  существует  кнопка  «Найти  максимальный  поток».  Эта  кнопка  позволяет 

вычислить максимальный поток. Перед нажатием кнопку «Найти максимальный поток» нужно задать 

число  вершин  и  заполнить  матрицу  смежности  вершин.  А  также  в  этом  разделе  можно  задать 

значения течение потока, то есть из какой точки в какую точку течет поток (рисунок 3). 

 

277 

 

 

Рисунок 3. Общий вид раздела «Решение» 

 

В левой стороне раздела «Решение» находится кнопка, которая позволяет задать чило вершин. 

Внизу этой кнопки есть кнопки «Загрузить граф из файла» и «Сохранить граф в файл» (рисунок 4). 

 

 

 

Рисунок 4. Вид окна, которая позволяет задать число вершин 

 

В  середине  находится  окно,  в  которое  строится  графы.  Здесь  можно  построить,  удалить 

вершины и ребра графа (рисунок 5).  

 

 

 

Рисунок 5.  Вид окна, в которое строится графы 

 

Раздел «Граф» состоит из вкладок «Матрица смежности вершин», «Дополнительно». В вкладка 

«Дополнительно»  есть  кнопки  «Удалить  все  ребра», «Обновить  изображение», «Распределить 

равномерно»,  «Распределить без наложений» (рисунок 6).  

 

   

 

 

Рисунок 6. Вид раздела «Граф» 

 

 

278 

ЛИТЕРАТУРА 

1. Тулембаева А.Н.Логистика. Учебное пособие. Издатмаркет 6 2004 Логистика: Учебник / Под ред. Б. А. 

Аникина. 2-е изд., перераб. и доп. - М.: Инфра • М, 2000.  

2. Неруш Ю. М. Логистика: Учебник для вузов. 2-е изд., перераб. и доп.- М.: ЮНИТИ: ДАНА, 1998. 

3. Логистика: Учебное пособие/Под ред. Б.А. Аникина. — М.: ИНФРА-М, 1997.  

 

REFERENCES 

1. Тulembayeva А.N. Logistic. Train aid. 2004 Logistic: Textbook / Under red. B. А. Аnikina. 2th publ., - М.: 

Infra is M, 2000.  

2. Nerush U. М. Logistic: Textbook for institutions of higher learning. 2th publ., - М.: Uniti: Dana, 1998. 

3. Logistic: train/aid Under red. B.А. Anikina. - М.: Infra-m, 1997.  

 

Ұ. Медетбекова, А.І. Наурызбаева, Б.А. Төлегенова 

жүктеу/скачать 19,96 Mb.

Достарыңызбен бөлісу: