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

На правах рукописи

СОЛОВЬЕВ АЛЕКСАНДР ВИТАЛЬЕВИЧ

РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МЕТОДОВ И АЛГОРИТМОВ РЕШЕНИЯ ДИНАМИЧЕСКОЙ ЗАДАЧИ ПРОИЗВОДСТВЕННОГО ПЛАНИРОВАНИЯ МЕТОДОМ ЖОРДАНОВЫХ ИСКЛЮЧЕНИЙ

Специальность 05.13.18 — Математическое моделирование, численные

методы и комплехсы программ

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Воронеж 2014 005557675

005557675

Работа выполнена в ФГБОУ ВПО «Воронежский государственный архитектурно-строительный университет».

Научный руководитель: Уксусов Сергей Николаевич, кандидат

физико-математических наук, доцент, ФГБОУ ВПО «Воронежский государственный архитектурно-строительный университет», доцент кафедры управления строительством

Официальные оппоненты: Азарнова Татьяна Васильевна, доктор

технических наук, профессор, ФГБОУ ВПО «Воронежский государственный университет», заведующая кафедрой математических методов исследования операций

Мишин Сергей Александрович, кандидат технических наук, доцент, ФГКОУ ВПО «Воронежский институт Министерства внутренних дел Российской Федерации», доцент кафедры автоматизированных информационных систем органов внутренних дел

Ведущая организация: ФГБОУ ВПО «Тамбовский государст-

венный технический университет»

Защита состоится 22 декабря 2014 года в II00 часов в конференц-зале на заседании диссертационного совета Д212.037.01 ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский проспект, 14.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет» и на сайте www.vorstu.ru

Автореферат разослан «28» октября 2014 года.

Ученый секретарь —

диссертационного со Барабанов Владимир Фёдорович

Введение

Актуальность темы. В настоящее время благодаря работам Полунина И.Ф., Баркалова С.А. и Уксусова С.Н. хорошо известна модель задачи линейного программирования с одним параметром. Однако такой модели недостаточно для решения многих практических задач, которые, как правило, содержат более одного параметра и при этом их решение не всегда зависит от параметров линейно. Кроме построения различных моделей задач линейного программирования с параметрами актуальным является также создание моделей задач дробно-линейного программирования, содержащих параметры и нахождение методов их решения. Данные модели находят свои приложения при решении задач динамического управления производством и многих других задач.

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

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

Тематика диссертационной работы соответствует одному из научных направлений ФБГОУ ВПО «Воронежский государственный архитектурно-строительный университет» - «Системы управления сложными организационно-техническими объектами».

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

Задачи исследования. Достижение цели работы потребовало решения следующих основных задач:

1. Создание модели задачи параметрического программирования со ступенчатой целевой функцией, сводящейся к многоэкстремальной задаче линейного программирования, и метода ее исследования, основанного на методе решения задач линейного программирования с несколькими целевыми функциями.

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

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

ласти, с анализом поведения решения на границах областей.

4. Разработка численных методов и алгоритмов решения задач линейного и дробно-линейного программирования с параметрами, основанных на последовательном использовании метода жордановых исключений и методов анализа параметров.

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

Тематика работы соответствует следующим пунктам паспорта специальности 05.13.18:

2. Развитие качественных и приближенных аналитических методов исследования математических моделей.

3. Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий.

4. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

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

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

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

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

дробно-линейного программирования с параметрами.

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

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

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

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

Представленные методы и их программная реализация включены в состав учебных курсов «Математическое программирование на основе жордановых исключений» и «Программная реализация метода Штифеля» в Воронежском государственном университете, используются в курсе «Математическое программирование» в Воронежском государственном архитектурно-строительном университете. Программный продукт нашел применение в планировании производственного процесса ООО НПЦ и ЗАО «Орбита».

Апробация работы. Основные результаты исследований и научных разработок докладывались и обсуждались на следующих конференциях: XII Всероссийское совещание по проблемам управления (ВСПУ XII) (Москва, 2014); II Международная НПК «Проблемы современных экономических, правовых и естественных наук в России» (Воронеж, 2014); 65-67 конференциях Воронежского ГАСУ «Инновации в сфере науки, образования и высоких технологий. Малое инновационное предпринимательство» (Воронеж 2012-2014); XI международная конференция «Сложные современные системы управления (Воронеж, 2014); 25-я Крымская осенняя математическая школа-симпозиум КРОМШ-2014 (Судак, 2014).

Публикации. По результатам исследований опубликовано 9 научных работ, в том числе 3 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат: [1] - создание модели нахождения максимальной рентабельности производства при условии хранения готовой продукции, [3] -разработка модели задачи планирования производства с переменными ресур-

сами, [6] — разработка нового метода решения задач блочного программирования, [8] — применение метода жордановых исключений в теории игр.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 103 наименований. Основная часть изложена на 135 страницах, содержит 26 таблиц и 16 рисунков.

СОДЕРЖАНИЕ РАБОТЫ В первой главе приведен обзор состояния научных исследований по тематике работы на текущий момент. Проанализированы основные работы по использованию метода жордановых исключений в линейном, дробно-линейном и параметрическом программировании. Сформулированы цель и задачи диссертационной работы.

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

п

г, = ^СУ(О"*/ тах'

О)

X] >0, у = 1,2,...,и, /е [0, Т].

Данная модель не является достаточно общей и поэтому может не в полной мере соответствовать реальным прикладным задачам.

Отметим основные недостатки существовавшей до настоящего времени модели задачи линейного программирования:

1) в существующей модели используется только один параметр, в то время как необходимо использовать несколько параметров,

2) все коэффициенты задачи (1) являются линейными функциями, что не всегда соответствует реальной ситуации,

3) не разрабатывалась модель задачи дробно-линейного программирования с параметрами,

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

На устранение этих недостатков и направлено диссертационное исследование.

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

линейного программирования с параметром в целевой функции.

Первые две модели соответствуют следующей общей задаче линейного параметрического программирования:

(2)

•О-*. 1Л -О '

•О-*. "О

-л)-*. ...О

•л)-*» ■л)

лг,>0,> = 1,2,

(3)

в которой коэффициенты целевой функции (1), коэффициенты и правые части системы ограничений (2) являются непрерывными, необязательно линейными функциями конечного числа параметров

(7? </, <7;', 1<;<и).

Решить задачу (2) — (3) - значит найти такое разбиение области изме-

я

нения параметров (прямоугольника /7 = ]~~[[7]"; 7]']) на конечное число об-

¡=1

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

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

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

О-*/-»"13"-

аЧх1 + а\2Х2 а|Л — а1

ап,\хх+атгхг+-+ат„х„^а*

х/ ^ 0,у = 1,2,..., л

в которой коэффициенты целевой функции являются ступенчатыми функциями параметра I е [0; Г].

(4)

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

В диссертационной работе задача (4) сведена к многоэкстремальной задаче линейного программирования, в которой поочередно максимизируются несколько функций:

п

м

2, = Vс2. ■ х, —> шах,

(5)

2к 'Х1

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

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

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

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

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

Скорость сравнивалась по количеству шагов симплекс-метода, затраченных на поиск оптимального решения задачи (4) (или доказательства отсутствия такового при некоторых значениях параметра). В качестве показа-

теля скорости была взята безразмерная величина V =

А

лг,

где /V,—количест-

во шагов симплекс-метода, необходимых для. решения по предлагаемому алгоритму, а Л/,— количество шагов симплекс-метода, необходимых для поэтапного решения задачи. Результаты расчетов для количества ступенек от 2 до 20 представлены на рис. 1.

0,9 0.8 0.7 : 0,6 | 0,5 0,4 0,3 0,2 0,1 0

0 5 10 15 20 25 30

Количество ступенек

N

Рис. !. Эмпирическая зависимость относительной скорости V = —-

»г

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

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

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

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

г, = Х (су + У х;~> тах>

ху>0, у = 1,2,...,и, /,е[а,/?], 1ге[Г,5].

в которой числа а1у, <1 г и известны и постоянны, а величины и ?2 являются переменными парамеграми.

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

Сложившееся сочетание параметров (/,, /2) рассматривается как точка

прямоугольника П = {(/,, а — У — Ч — на плоскости.

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

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

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

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

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

>=1

в11Х1 +а12х2 +--+аЫХп —а\ ]

а»Л + + -+ в„Л á ат | ' Xj >0,7=1,2,..., и

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

На основе метода жордановых исключений разработан алгоритм, позволяющий находить решение задачи (7) без ее сведения к задаче линейного параметрического программирования, В соответствии с данным алгоритмом интервал [0; Т\ разбивается на промежутки, на каждом из которых находится оптимальный план с фиксированными координатами, не зависящими от параметра t, и определяется максимум (минимум) целевой функции, зависящий от параметра t.

Задачи дробно-линейного программирования с параметрами до настоящего времени не рассматривались. Решить задачу (7) можно было только путем сведения ее к задаче линейного параметрического программирования, основанного на методе, предложенном американскими математиками A.Chames и W.W.Cooper. При этом существующий подход предполагает увеличение количества неизвестных.

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

Скорость сравнивалась пс количеству шагов симплекс-метода, затраченных на поиск оптимального решения задачи (7) (или доказательства отсутствия такового при некоторых значениях параметра). В качестве показала

теля скорости была взята безразмерная величина V = —-, где N. - количест-

N2

во шагов симплекс-метода, необходимых для решения по предлагаемому алгоритму, jV2- количество шагов симплекс-метода, необходимых для решения по старому алгоритму Результаты расчетов для размерности задачи /ихл от 5 до 200 представлены на рис. 2.

О 50 100 150 200 250

Размерность задачи

Рис. 2. Эмпирическая .зависимость относительной скорости V = —-нахождения оптимального решения задачи от размерности задачи

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

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

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

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

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

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

ftic. 3. Структурная схема алгоритма решения задачи параметрического программирования со ступенчатой целевой функцией

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

Put. 4. Структурная схема алгоритма решения задачи параметрического программирования с двумя независимыми параметрами

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

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

В качестве среды для реализации алгоритма использован Delphi 7. Структура комплекса представлена на рис. 6. Главное управляющее окно программного комплекса показано на рис. 7. Решение соответствующей задачи показано на рис. 8.

(^Начало)

определение размэрности задачи

I исходных данных/

ш

Нахо оденме огетимального опорного плана при начальном значении параметра

Исследование целевой функции на гра«*цах получетых интервалов. Поиск глобального максимума

^=1- Г

<Г Зызод и сохранен*« результатов;

- -

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

задача со ступенчатой целевой функцией

Выбор алгоритма решения

задача с двумя независимыми параметрами

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

метод жордановых исключений

Модуль анализа эффективности

Блок адаптации под тип задачи

Выходные данные

Входные данные

Рис. 6. Функциональная структура программного комплекса

У1 У2

220 390

44000 108000 85000 8Б40 6000

2X1 >-0 £Х2>=0

0X3 >-0

Количество строк

Р 1

(1 Десятичные гцюби

Кол^вспю столЛюв Ойьжж»вт«ыбшойи

]*> Поикс-свы-а реяим V* Поклздаъ резрашжхцмй элемент

Рис. 7. Окно ввода исходных данных в программный комплекс

Рис. 8. Окно вывода результатов

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

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

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

N

безразмерная величина V =—где ¿V,- количество шагов симплекс-

метода, необходимых для решения по методу жордановых исключений, а Ы2- количество шагов симплекс-метода, необходимых для решения по старому алгоритму. Результаты расчетов для размерности задачи ихл от 20 до 200 представлены на рис. 9.

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

0,9 0,8

1 0,7

О

| 0,6

0

5 0,5

X

л

5 0,4

1 0,3

I

° 0,2 0,1 о

о 20 40 60 80 100 120 140 160 180 200

Размерность задачи

N

Рис. 9. Эмпирическая зависимость относительной скорости V = —-- нахождения оптимального решения задачи от размерности задачи

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

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

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

Коэффициенты соответствующих задач линейного и дробно-линейного программирования взяты из таблицы:

Таблиц»

Керамзитобетон Шлакобетон Опилкобетон

Цемент 220 200 260

Песок 390 540 1100

Керамзит 330 0 0

Шлак котельный 0 720 0

Опилки 0 0 150

Вода 92,3 92,3 92,3

Запасы сырья ограничены следующими величинами: цемент — 120000кг, песок - 580000 кг, керамзит - 45000 кг, шлак котельный - 51000 кг, опилки - 36000 кг, вода — не ограничена.

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

(1775-200/)*, + (1420-360/)х2 + (1600-400/)х3,

где (х,; х2; х3) - план производства, t - время реализации готовой продукции (мес.) / е [0; 2].

Себестоимость произведенной продукции выражается формулой С = 1016х, + 61 Ох, + 872л:,.

Задача определения максимальной рентабельности производства сводится к следующей задаче дробно-линейного программирования:

, (1775 - 2000л:, + (1420 - 360/)х, + (1600 - 400/) х,

z(X) --i—*-i—i. _> max

1016x, + 610x2 +872x3 220x, + 200x2 + 260x3 < 120000, 390x, + 540x2 +1100x, < 580000, 330x, <45000,

720x2 <51000, (8)

150x3 <36000, x, >20,

x,,x2,x3 >0.

После двух шагов методом жордановых исключений мы получаем оптимальный опорный план X, =(20; 70,83; 0) при /е[0; 0,984]. Рентабельность затрат на данном промежутке вычисляется по формуле 124083-/ + 21500 ,е[0;0984] v ' 63528

На промежутке /е (0,984; 2] оптимальным планом является план Х'г = (0; 70,83; 240). При этом рентабельность вычисляется по формуле „,ч 508083-/ + 117500 . „„ ,

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В процессе выполнения диссертационного исследования были получены следующие основные результаты:

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

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

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

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

5. Разработан комплекс программ, позволяющий решать задачи линейного и дробно-линейного программирования с параметрами.

Основные результаты диссертации опубликованы в следующих

работах:

Публикации в изданиях, рекомендованных ВАК РФ:

1. Соловьев, А. В. Задача определения рентабельности затрат на производство при условии хранения готовой продукции/ А. В. Соловьев, С. Н. Уксусов // Экономика и менеджмент систем управления, №1.3(11). — 2014. — С. 407-416.

2. Соловьев, А. В. Задача планирования производства в условиях поэтапной реализации готовой продукции / А. В. Соловьев // Системы управления и информационные технологии, №3.1(57). - 2014. - С. 178-182.

3. Соловьев, А. В. Модель задачи параметрического программирования с двумя параметрами / А. В. Соловьев // Экономика и менеджмент систем управления, №1.5(11). - 2014. - С. 281-291.

Статьи в других изданиях

4. Соловьев, А. В. Математические методы и модели задач управления производством/ А. В. Соловьев, С. Н. Уксусов // Материалы 25-й Крымской математической школы-симпозиума КРСШШ-2014. - Судак, 2014. - С. 23

5. Соловьев, А. В. Математическая модель рентабельности затрат на производство продукции при условии её хранения / А. В. Соловьев, С. Н. Уксусов// Научный вестник Воронежского государственного архитектурно-строительного университета. Сер. Управление строительством. — Воронеж, 2014.-№ 1(6).-С. 128-133.

6. Соловьев, А. В. Оптимизация грузопотоков по критерию времени доставки грузов/ А. В. Соловьев, П. П. Чураков // Научный вестник Воронежского государственного архитектурно-строительного университета. Сер. Управление строительством. - Воронеж, 2013. —№ 2(5). - С. 108-113.

7. Соловьев, А. В. Применение метода жсрдановых исключений в случае конфликтных ситуаций в строительстве/ А. В. Соловьев, С. Н. Уксусов // Научный вестник Воронежского государственного архитектурно-строительного университета. Сер. Управление строительством. - Воронеж, 2013.-№2(5).-С. 89-94.

8. Соловьев, А. В. Решение задачи плакирования отраслевого производства методом жордановых исключений/ А. В. Соловьев, Р. Д. Зильберов, С. Н. Уксусов // Научный вестних Воронежского государственного архитек-1урно-строительного университета. Сер. Управление строительством. - Воронеж, 2013. - № 2(5). - С. 86-89.

9. Соловьев, А. В. Решение задачи динамического управления производством методом жордановых исключений/ А. В. Соловьев, С. Н. Уксусов // Труды XI международной конференции «Сложные современные системы управления» - Воронеж, 2014. - С. 273-278.

СОЛОВЬЕВ АЛЕКСАНДР ВИТАЛЬЕВИЧ

РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МЕТОДОВ И АЛГОРИТМОВ РЕШЕНИЯ ДИНАМИЧЕСКОЙ ЗАДАЧИ ПРОИЗВОДСТВЕННОГО ПЛАНИРОВАНИЯ МЕТОДОМ ЖОРДАНОВЫХ ИСКЛЮЧЕНИЙ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 21.10.2014. Формат 60><84 1/16. Бумага писчая. Усл. печ. л. 1,2. Тираж 100 экз. Заказ № 414

Отпечатано: отдел оперативной полиграфии Издательства учебной литературы и учебно-методических пособий Воронежского государственного архитектурно-строительного университета 394006 г. Воронеж, ул. 20-летия Октября, 84