Двойственность в дробно-линейном программировании и ее приложения тема диссертации по экономике, полный текст автореферата

Диссертация: содержание автор диссертационного исследования: кандидата физико-математических наук, Баялинов, Эрик Бакишевич

ВВЕДЕНИЕ

Глава I ЗАДАЧА ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

§ I. Постановка и основная экономическая интерпретация задачи дробно-линейного программирования . II

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

Глава 2 ДВОЙСТВЕННОСТЬ В ДРОБНО-ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

§ I. Построение двойственной задачи

§ 2. Основные теоремы двойственности

§ 3. Исследование влияния изменений условий задачи дробно

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

§ 4. Интерпретация двойственных переменных дробно-линейного программирования как экономических оценок ресурсов и продукции в планово-экономических задачах

Глава

РАЗРАБОТКА АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ ДРОБНО-ЛИНЕЙНОГО - ПРОГРАММИРОВАНИЯ

§ I. О втором алгоритме метода последовательного улучшения плана.

§ 2. О методе последовательного уточнения оценок

§ 3. Метод последовательного сокращения невязок

Глава

ИСПОЛЬЗОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ ПРИ ОПРЕДЕЛЕНИИ ОПТИМАЛЬНОЙ СТРУКТУРЫ ТЕРРИТОРИАЛЬНО-ПРОИЗВОДСТВЕННЫХ

- КОМПЛЕКСОВ

§ I. Моделирование формирования и развития территориальнопроизводственных комплексов . 94

§ 2. К проблеме выбора наилучшего варианта комплексного использования ресурсов Иссык-Кульской области и районов Чуйской долины Киргизской ССР

Диссертация: введение по экономике, на тему "Двойственность в дробно-линейном программировании и ее приложения"

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

Теоретические основы и методы решения задач планирования, управления и проектирования разрабатываются в сравнительно новой математической дисциплине, получившей название математического программирования. За последние 15-20 лет возник и начал формироваться новый раздел этой дисциплины - дробно-линейное программирование (ДЛП), ставшее необходимым инструментом при решении многих оптимизационных задач с удельными показателями качества.

Появление и развитие теории ДЛП обусловлено необходимостью системного подхода к анализу функционирования социалистической экономики. Так, обратимся за примером к отраслевому планированию. Отраслевое планирование - это та область, в которой в течение последнего десятилетия интенсивно развиваются теоретические исследования и оптимизационные расчеты, связанные с применением экономико-математических методов и вычислительной техники. Тем не менее, многие отрасли, в частности сезонные производства, связанные с переработкой сельскохозяйственного сырья, остаются до сих пор слабо разработанными как в теоретическом, так и в практическом отношении. Это объясняется спецификой сезонных производств. При планировании и управлении сезонного производства возникает проблема согласования и оптимизации работы сельскохозяйственной отрасли, выращивающей и поставляющей сырье, автомобильного и железнодорожного транспорта, перевозящего сырье, и пищевой промышленности, перерабатывающей его. К тол^у же,- обычно, в сезонных производствах объем производства конечной продукции нельзя фиксировать, гак как он сам является искомой величиной. Поэтому в сезонных производствах наряду с абсолютными критериями оптимальности типа "максимум прибыли", "максимум объема конечной продукции" целесообразно применять удельные критерии оптимальности типа "минимум удельной себестоимости продукции",, "минимум удельных приведенных затрат", "максимум уровня рентабельности".

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

О важности применения удельных экономических показателей в планировании промышленности говорится в "Основных направлениях экономического и социального развития СССР на 1981-1985 годы и на период до 1990 года": "Считать увеличение производства и повышение качества товаров для населения первостепенной задачей всех отраслей промышленности, всех предприятий и организаций, предметом особой заботы всех партийных, советских и хозяйственных органов.

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

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

Первые статьи, посвященные рассмотрению задач дробно-линейного программирования и разработке методов их решения, появились в начале 60-х годов. В 1960 году была опубликована работа [7б], в которой ее автор - рассмотрел задачу "гиперболического программирования" и показал, что для решения этой задачи может быть использован "слегка модифицированный" симплексный метод. Работа [7б] положила начало развитию нового раздела математического программирования, получившего в середине 60-х годов название дробно-линейного программирования. Вслед за этой статьей в 1962 году появилась работа СклапевА и СоореаШЩ^ЪЪ], в которой был предложен метод решения задачи ДЛП с ограниченной областью допустимых планов. Метод обеспечивает получение решения путем решения одной задачи линейного программирования (ЛП). Эта задача формируется в результате добавления одной переменной и одного ограничения. В том же 1962 году Ъоак¡¡(/.в.в [59] доказал, что любой локальный минимум задачи ДЛИ является в то же время глобальным, и указал способ нахождения решения задачи путем решения серии соответствующих линейных задач. При использовании метода Л&иЬеЗЛ'№аитМ[м\ решение задачи ДЛП заменяется решением последовательности линейных задач с исходными ограничениями, но с разными целевыми функциями.

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

- обобщение методов линейного программирования на случай дробнолинейной целевой функции [51, [гз], [24] , [25], [2б], [30] , [76]. $ *

- сведение исходной задачи путем нелинейной замены переменных к задаче ЛП [20] ,[21] .[22],[54].

- декомпозиционные методы [б], [7], [8], [9], [10], [II], [31], [34], [Зб] , [38] , [43], [44], [45] ,[46], [50] , [51] , [53], [57], [58], [59], [61] , [71], [77], [80] , [81], [82], [83] , [85] , [86], [88], [94], [95] .

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

Первая отечественная работа [зо], в которой рассмотрена заг дача дробно-линейного программирования и предложен метод ее решения, принадлежит Шварцману А.П. Эта работа увидела свет в 1965 году.

Полученные в вышеупомянутых и других работах результаты по теории дробно-линейного программирования были позднее обобщены и во многом развиты в монографии Чернова Ю.П. и Ланге Э.Г. [2б]. В [¿в] рассмотрены методы решения непосредственно задачи ДЛП и других задач нелинейного программирования с дробной целевой функцией без сведения их к задаче линейного программирования или к другим соответствующим задачам математического программирования. Наоборот, линейное, выпуклое, вогнутое и параметрическое линейное программирование рассмотрены в [2б] как частные случаи дробно-линейного, дробно-выпуклого, дробно-вогнутого и параметрического дробно-линейного программирования соответственно.

Перечисленные и другие работы по ДЛП быстро получили широкую известность и породили многочисленные исследования в этой области. Среди многих работ, внесших весомый вклад в дело разработки эффективных методов решения как общих, так и специальных задач дробно-линейного программирования и дробного программирования вообще следует в первую очередь отметить [б] ,[ю], [II], [20], [21], [22], [31], [36] , [4-3] , [Щ , [52], [54], [57] , [58], [60 ], [бб], ¿71], [80] , [81], [82], [83], [86], [88].

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

•сом (гак же, как, в частности, и в линейном программировании) стала в дробно-линейном программировании теория двойственности, согласно которой данной экстремальной задаче ставится в соответствие тесно связанная с ней двойственная задача.

Первой работой, посвященной теории двойственности в дробном программировании, является статья 1x4] советского математика Гольштейна Е.Г. В этой статье автор описал общую схему формирования двойственных задач для функциональных аналогов задач выпуклого и дробно-выпуклого программирования и сформулировал ряд утверждений, составляющих основу теории двойственности для этих задач. Предложенная в [14] схема составления двойственной задачи имеет аналитический характер и обобщает подход, изложенный в [12], для конечномерных задач выпуклого программирования. Результаты работы [14] были впоследствии развиты в [Х5\ и [17]. Указанные работы Гольштейна Е.Г. определили одно из направлений в исследовании вопроса о двойственности в дробном программировании, которое характеризуется использованием терминов, связанных с задачей об отыскании седловой точки дробной функции Лаграшса. Реализация этого направления, как будет показано ниже, может дать весьма полезные в теоретическом и практическом отношении результаты.

Первая зарубежная работа [91] по теории двойственности в дробно-линейном программировании появилась почти одновременно с [14], а именно в 1967 году. Автор ее, индийский мвтвыаятВмаАирК, показал, что теоремы'двойственности, сформулированные и доказанные (см., напр., [65], [72] ,[95] и др.) для задач нелинейного программирования, могут быть распространены на случай, когда целевая функция экстремальной задачи имеет дробно-линейный вид и достигает своего оптимума в конечной точке допустимого множества. При построении двойственной задачи Лиуо^ассрК^ апеллировал к функции Лагранжа, имеющей обычную (не дробную) структуру. Используемая в

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

Качественно иной подход к вопросу о двойственности в дробно-линейном программировании предложен в работе [55], авторы -й&Ш/ъЗ. и Ь. - которой показали, что для частного случая задачи

ДЛП двойственная к ней может быть сформулирована также в виде задачи дробно-линейного программирования, В [48], [49]»[62],[68], [78] ,[79] ,[87] ,[91] ,[92] аналогичная (имеющая дробный вид) формулировка двойственной задачи получена для других частных случаев задачи ДЛП.

Наибольшее распространение получил другой подход, при котором исходная задача ДЛП с помощью нелинейной замены переменных преобразуется в линейную задачу [39], [40]-[45], [53], [55], [бб], [67],[74],[75],[80]-[85]. Это объясняется тем, что такой подход к рассмотрению задачи дробно-линейного программирования позволяет пользоваться хорошо разработанным аппаратом линейного программирования. Однако при этом теряется один из важнейших результатов теории двойственности - практический смысл двойственных оценок.

Настоящая работа также посвящена двойственности в дробно-линейном программировании и ее приложениям. Целью работы является:

1. реализация общей идеи [14] (использование дробной функции Ла-гранжа) для случая задачи ДЛП;

2. использование результатов пункта I при разработке теоретических основ алгоритмов решения задач ДЛП и при проведении экономических исследований.

Работа состоит из четырех глав.

Диссертация: заключение по теме "Математические и инструментальные методы экономики", Баялинов, Эрик Бакишевич

ЗАКЛЮЧЕНИЕ

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

В результате предварительных исследований свойств задачи ДЛП известная (см.,напр.,[зз]) теорема о разрешимости задачи линейного программирования обобщена на случай задачи дробно-линейного программирования. В основной части работы (гл.2) для задачи ДЛП сформулирована двойственная к ней задача, доказаны основные утверждения теории двойственности и определены условия, при которых исходная задача дробно-линейного программирования имеет по крайней мере один оптимальный план с конечными компонентами. Сформулирована задача линейного программирования, как двойственная к двойственной, по сути являющаяся линейным аналогом задачи ДЛП. Доказаны утверждения, устанавливающие связь между двумя задачами и. их планами. В качестве приложения теории двойственности к разработке вычислительных методов теоретические основы трех известных по линейному программированию методов обобщены на случай решения задачи ДЛП. Исследовано влияние изменений вектора правых частей ограничений на оптимум целевой функции и выведено соответствующее аналитическое выражение. Показано, что для задач ДЛП экономического содержания компоненты оптимального плана двойственной задачи могут быть интерпретированы как экономические оценки ресурсов и продукции, объемы потребления и производства которых ограничены условиями задачи. Предложена схема ( Я -схема) возможного использования полученных в работе теоретических результатов при решении народнохозяйственных проблем, приводящих к задачам дробно-линейного программирования.

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

В настоящее время вышеупомянутая Ц -схема применяется в Институте экономики и экономико-математических методов планирования Госплана Киргизской ССР при проведении исследований, связанных с формированием и развитием Иссыккульско-Чуйского территориально-производственного комплекса.