Программирование задач оптимизации в среде MS Excel

Содержание
ВВЕДЕНИЕ……..……………………………………………………..………….3

ГЛАВА I. ОБЩАЯ ХАРАКТЕРИСТИКА ЗАДАЧ ОПТИМИЗАЦИИ…....7
1.1. Природа и особенности задач оптимизации…………………………….7
1.2. Методология системного моделирования………………….……..…...11
1.3. Процесс постановки и решения задач оптимизации………….……....14
1.3.1. Анализ проблемной ситуации…………………………………….16
1.3.2. Построение математической модели………………………….….17
1.3.3. Анализ модели……………………………………………………...18
1.3.4. Выбор метода и средства решения………………….………...….18
1.3.5. Выполнение численных расчетов………………….…….……….20
1.3.6. Анализ результатов расчетов. …………………………………….20
1.3.7. Применение результатов расчетов……………………………….21
1.3.8. Коррекция и доработка модели…………………….……...…….22
1.4. Математическая модель задач оптимизации…………….……...…….22
1.4.1. Понятие математической модели и ее основные элементы………………………………………..……………….………..22
1.4.2. Характеристика переменных……………………………………...23
1.4.3. Характеристика ограничений……………………….…………….24
1.4.4. Характеристика целевой функции………………………….…….25

ГЛАВА II. ПРОГРАММИРОВАНИЕ ЗАДАЧ ОПТИМИЗАЦИИ В СРЕДЕ MS EXCEL……………………………………………………………..27
2.1. Алгоритмы и программы решения задач оптимизации на графах…………………………………………...…………………………….27
2.1.1. Общая характеристика задач оптимизации на графах…………..27
2.1.2. Задача о максимальном и минимальном покрывающем дереве в графе……………………………………………………………….…....…30
2.1.3. Задача о минимальном пути в графе…………………….…….….50
2.2. Внешние программы и их использование в среде MS Excel……..….58
2.2.1. Разработка внешней функции в среде Borland Delphi и ее использование в среде MS Excel………………………………..…......…58
2.2.2. Разработка функции нахождения минимального пути в среде Borland Delphi и ее использование в среде MS Excel…………………..67
2.2.3. Создание пользовательской функции для вычисления двумерной экспоненциальной функции в VBA…...........….…..………………….…73
2.2.4. Построение графика функции двух переменных……………...…76

ЗАКЛЮЧЕНИЕ………………………………………………..…………….…80
ЛИТЕРАТУРА………………………………………………………………….83
ПРИЛОЖЕНИЕ………………………………………...……………………....84
ГЛАВА I. ОБЩАЯ ХАРАКТЕРИСТИКА ЗАДАЧ ОПТИМИЗАЦИИ

1.1. Природа и особенности задач оптимизации

Начиная разговор о задачах оптимизации, обычно всегда упоминают об исключительно широком распространении этих задач, а также о том, что их история восходит к зарождению человеческой цивилизации. Действительно, трудно найти человека, который хотя бы раз не попадал в ситуацию необходимости выбора одной из нескольких возможностей. Вполне очевидно, что в подобной ситуации всегда следует выбирать наилучший вариант. Более сложный вопрос заключается в точном определении того, какой смысл следует вкладывать в понятие «наилучшее решение».
Как оптимально распорядиться семейным бюджетом или за минимальное время добраться до нужной точки в городе, как наилучшим образом спланировать деловые встречи и минимизировать риски капитальных вложений, есть ли смысл воспользоваться страховым полисом или это неоправданные финансовые затраты, как наиболее эффективно организовать работу персонала компании или определить оптимальные запасы сырья на складе – это лишь небольшая часть проблем, в которых желательно принять не просто какое-то решение, а наилучшее из всех потенциально возможных решений.
В более простых, на первый взгляд, ситуациях, когда, например, речь заходит о покупке новой вещи в быту, вряд ли у кого не возникает желание иметь вещь наилучшего качества, надежности, внешнего вида или комфорта. Однако, с одной стороны, в подобных случаях выбор может быть ограничен имеющимися в наличии доступными средствами. Тем самым на принятие решения оказывают влияние некоторые ограничивающие обстоятельства, которые из всех потенциально возможных вариантов исключают не удовлетворяющие определенным ограничениям. С другой стороны, введение в рассмотрение нескольких характеристик для оценки наилучшего варианта приводит к задачам оптимизации в многокритериальной постановке, которые с концептуальной точки зрения считаются наиболее трудными для решения.
Что касается истории систематического изучения задач оптимизации, то ее начало относится к эпохе зарождения математики как науки. Известно, что одними из первых математических задач, которые были сформулированы и решены античными математиками, были задачи нахождения геометрических фигур максимальной площади и тел максимального объема при ограничениях на периметр и площадь поверхности, соответственно.
Задачи, в которых требуется найти значения одной или нескольких переменных и при этом максимизируется или минимизируется значение некоторой непрерывной функции, занимают в математике особое место. Для их решения был разработан классический метод, связанный с нахождением нулей первой производной целевой функции и проверки их на экстремум. Этот метод, получивший название аналитического способа решения задач оптимизации, вполне подходит для решения простых задач. Его характерной особенностью является установление или нахождение решения в форме некоторой функциональной зависимости между исходными данными и решением.
Интенсивное развитие экономики и производства в XX в. Привело к появлению целого ряда новых типов задач оптимизации, которые не могли быть решены классическими методами и потребовали разработки специальной математической теории – теории решения задач оптимизации. В рамках этой теории были разработаны не только методологические основы постановки и анализа задач оптимизации, но и вычислительные методы и алгоритмы их решения. Хотя по-прежнему некоторые неклассические задачи оптимизации могут быть решены аналитически, однако акцент исследований смещается в сторону поиска вычислительного способа решения для целых классов задач оптимизации.
Таким образом, для задач оптимизации характерно наличие нескольких возможностей для выбора альтернативных решений и наличие некоторой оценочной функции для количественного выражения наилучшего выбора. В случае отсутствия альтернатив или соответствующей оценочной функции задача оптимизации теряет свой смысл. Что касается наличия некоторых дополнительных, ограничивающих выбор условий, то последние не являются обязательным атрибутом классических задач оптимизации. Однако большинство, если не все неклассические задачи оптимизации имеют дополнительные ограничения, формирующие в своей совокупности множество допустимых альтернатив.
Несколько слов о самом подходе к решению задач оптимизации. Ранее уже были упомянуты аналитический и вычислительный способы. Однако из всех методов решения задач оптимизации с конечным множеством допустимых альтернатив имеется один, который представляется универсальным средством решения задач любого класса. Речь идет о методе полного перебора и сравнения альтернативных возможностей с целью выбора наилучшего из них. Появление высокопроизводительных персональных компьютеров создает у многих пользователей ложное впечатление о потенциальной возможности решения любой задачи оптимизации простым перебором всех возможностей для выбора из них наилучшей.
Казалось бы, для этого вполне достаточно написать соответствующую компьютерную программу, которая будет последовательно рассчитывать значения оценочной функции для каждой из возможных альтернатив, сохранять текущий рекорд, а после окончания своей работы сообщит сохраненный результат пользователю. Этот способ представляется настолько многообещающим, что для значительной части современных программистов был потерян сам смысл изучения других вычислительных алгоритмов, разработанных для решения задач оптимизации.
Увы, это впечатление настолько обманчиво, что даже не требует серьезных аргументов для опровержения. Достаточно взять реальную задачу комбинаторной оптимизации, например, задачу коммивояжера с 11-12 городами, чтобы на многие часы, а может быть и сутки, ввести Pentium-IV в состояние глубочайшей задумчивости со 100%-ной загрузкой процессора. А ведь в реальных ситуациях может потребоваться решить подобную задачу с гораздо большим количеством городов для обхода. Применение метода полного перебора для непрерывных задач оптимизации вообще теряет смысл, поскольку в подобных задачах множество исходных альтернатив бесконечно по своей природе.
Другая распространенная ошибка среди пользователей и аналитиков – считать какие-нибудь новомодные методы, например, генетические или нейросетевые алгоритмы, универсальным средством решения задач оптимизации. Об этом можно прочитать в рекламных проспектах релизов тех или иных программ. Однако сознательно или нет, разработчики соответствующих программных пакетов не указывают, что эти алгоритмы, действительно обладая известной универсальностью, по своему характеру являются всего лишь приближенными методами поиска оптимальных решений. Это значит, что в общем случае нет никаких оснований считать полученное с их помощью решение действительно наилучшим из всех возможных. Полученное решение будет всего лишь близким к оптимальному, насколько же близко – это уже другой вопрос, точный ответ на который соизмерим со сложностью решения исходной задачи оптимизации.
Наконец, несколько слов следует сказать о средствах решения задач оптимизации. В простейших случаях для этого может оказаться достаточным наличие ручки и листа бумаги. А вот в более сложных… Здесь уже у аналитика появляется выбор, который зависит от наличия персонального компьютера. Действительно, существуют специальные математические программы, например, MATLAB и Mathcad, которые имеют встроенные средства решения задач оптимизации. Очевидное неудобство для пользователя может быть связано с необходимостью дополнительных затрат на их приобретение и времени на изучение их особенностей.
Оказывается, в большинстве случаев для решения типовых задач оптимизации может оказать эффективную помощь программа электронных таблиц MS Excel. Неоспоримое ее достоинство заключается в том, что она не требует дополнительных затрат на приобретение, поскольку офисный пакет от Microsoft практически всегда инсталлируется сразу после установки операционной системы MS Windows. Что касается времени на изучение программы электронных таблиц MS Excel, то оно существенно меньше за счет единообразного рабочего интерфейса офисных программ. С другой стороны, от большинства пользователей, которые пишут в своем резюме “опытный пользователь ПК”, требуется умение работать в среде MS Excel на уровне редактирования рабочих листов и манипулирования содержимым ячеек. Значит, изучение материала для таких читателей послужит приобретением дополнительных навыков практической работы с одной из самых “математических ” программ офисного пакета.
Как это не покажется парадоксальным, использование для решения задач оптимизация других технических средств – калькулятора или ставшей уже реликтом логарифмической линейки – может потребовать от аналитика более серьезных усилий и квалификации. Действительно, чтобы правильно выполнить все расчетные действия с помощью этих инструментов, необходимо хорошо знать детали того или иного вычислительного алгоритма. Учитывая высокую вероятность ошибки пользователя при выполнении промежуточных расчетов, а также невысокую точность второго инструмента, оба эти средства вряд ли могут считаться базовыми при решении задач оптимизации. В то же время нельзя их полностью исключить из рабочего арсенала аналитика, поскольку они по-прежнему используются для ручной проверки правильности вычислительных алгоритмов в простейших случаях.
Конечно, программа электронных таблиц MS Excel, содержащая встроенные средства для решения задач оптимизации, является далеко не универсальной. Современные задачи оптимизации настолько разнообразны по своему характеру, что разработка универсального метода или средства для их решения представляется практически невозможной. Однако существуют типовые классы задач оптимизации, которые могут быть успешно решены с помощью программы электронных таблиц MS Excel. Именно рассмотрению этих задач и особенностей методов их решения уделяется основное внимание на страницах диплома.
В то же время отдельные классы интересных задач оптимизации либо не могут быть вовсе решены с помощью программы MS Excel, либо их решение связано со значительным неудобством и затратами времени. В подобных случаях пользователь или аналитик оказывается в ситуации выбора. С одной стороны, обладая некоторым опытом программирования, можно воспользоваться встроенным языком VBA (Visual Basic for Applications) для написания собственных программ, реализующих те или иные алгоритмы оптимизации.
С другой стороны, электронные таблицы MS Excel позволяют вызывать пользовательские функции из внешних библиотек динамической компоновки, которые, в свою очередь, могут быть созданы с помощью специальных сред визуального программирования, таких как MS Visual C++NET и Borland Delphi 7 и их предыдущие версий.
Таким образом, для правильной постановки и решения практических задач оптимизации необходимо знать особенности отдельных классов этих задач и возможности программы электронных таблиц MS Excel.
1.2. Методология системного моделирования

Общей методологией постановки и решения задач оптимизации является системный анализ. Применительно к решению прикладных задач эта методология получила название системного моделирования.
Центральным понятием системного моделирования является собственно понятие системы, под которым понимается совокупность объектов, компонентов или элементов произвольной природы, образующих некоторую целостность в этом или ином контексте. Определяющим принципом рассмотрения некоторой совокупности объектов как системы является появление у нее новых свойств, которых не имеют составляющие элементы. Этот принцип получил специальное название – принцип эмерджентности (от англ. emergence – появление, выявление).
Системы различной физической природы окружают нас повсеместно – это конкретные предметы и объекты: солнечная система, человек, персональный компьютер, автомобиль, самолет, аэропорт. Характерным признаком системного мышления является рассмотрение абстрактных сущностей, таких как алгоритм, компьютерная программа, естественный язык, коммерческая фирма, культура, политика, наука, экономика как система.
Наиболее ортодоксальная точка зрения заключается в том, что все окружающие предметы и категории мышления являются системами. Не вдаваясь в философские аспекты данной проблемы, которая далека от своего удовлетворительного решения, в рамках системного моделирования понятие системы ограничено возможностью представления реальных объектов в форме некоторой модели. При этом концептуальная сложность проблемы смещается в область модельных представлений, базовым или главным из которых является математическая модель.
При рассмотрении той или иной системы исходным этапом при построении ее модели является определение ее границы. Речь идет о необходимости разделения всех элементов на два класса: принадлежащих и не принадлежащих системе. При этом те сущности или объекты, которые собственно принадлежат системе, и будут являться ее элементами. Например, не принадлежащие системе объекты, но оказывающие на нее то или иное влияние, образуют среду или внешнюю по отношению к системе предметную область.
Важнейшими характеристиками любой системы является ее структура и процесс функционирования. Под структурой системы понимают устойчивую во времени совокупность взаимосвязей между ее элементами или компонентами. Именно структура связывает воедино все элементы и препятствует распаду системы на отдельные компоненты. Структура системы может отражать самые различные взаимосвязи, в том числе, и вложенность элементов одной системы в другую. В этом случае принято называть более мелкую или вложенную систему подсистемой, а более крупную систему – метасистемой.
Процесс функционирования тесно связан с изменением свойств системы или отдельных ее элементов во времени. При этом важной характеристикой системы является ее состояние, под которым понимается совокупность свойств или признаков, которые в каждый момент времени отражают наиболее существенные особенности поведения системы.
Структура системы может быть описана с разных точек зрения. Наиболее общее представление о структуре дает схема устройства той или иной системы. При этом взаимодействие элементов может носить не только механический, электрический или биологический характер, но и информационный, что характерно для современных бизнес-систем. Состояние системы также можно рассматривать с различных точек зрения, наиболее общей из которых является рассмотрение особенностей функционирования или эксплуатации той или иной системы.
Процесс функционирования системы отражает поведение системы во времени и может быть представлен как последовательное изменение ее состояний. При изменении состояния системы говорят о том, что система переходит из одного состояния в другое. Совокупность признаков или условий изменения состояний системы в этом случае называется переходом. Для системы с дискретными состояниями процесс функционирования может быть представлен в виде последовательности состояний с соответствующими переходами.
Методология системного моделирования служит концептуальной основой системно-ориентированной структуризации предметной области. В этом случае исходными компонентами концептуализации являются системы и взаимосвязи между ними. Результатом системного моделирования является построение некоторой модели системы и соответствующей предметной области, которая описывает важнейшие с точки зрения решаемой проблемы аспекты системы.
В общем случае под моделью понимается некоторое представление о системе, отражающее наиболее существенные закономерности ее структуры и процесса функционирования и зафиксированное на некотором языке или в некоторой форме. Применительно к контексту задач оптимизации имеют интерес только такие аспекты построения моделей, которые связаны с информационным или логическим моделированием систем.
Примерами моделей являются не только известные физические модели (аэродинамическая модель гоночного автомобиля или проектируемого самолета), но и абстрактные или логические модели различных систем (математическая модель колебательной системы, аналитическая модель системы электроснабжения региона, информационная модель избирательной компании и другие).
Общим свойством всех моделей является их подобие некоторому реальному объекту или системе-оригиналу. Важность построения моделей заключается в возможности их использования для получения информации о свойствах структуры или поведение системы-оригинала. При этом сам процесс построения и последующего применения моделей для получения информации о системе оригинала является основным содержанием системного моделирования.
Наиболее общей информационной моделью системы является так называемая модель “черного ящика”. В этом случае система представляется в виде прямоугольника, внутреннее устройство которого скрыто от системного аналитика или вообще неизвестно. Однако система не является полностью изолированной от внешней среды, поскольку последняя оказывает на систему некоторые информационные или материальные воздействия. Такие воздействия получили название входных воздействий или входных параметров, входных переменных.
Среди входных воздействий выделяют специальный класс – так называемых управляющих воздействий (переменных). Последние предназначены для того, чтобы оказывать на систему целенаправленное воздействие, предназначенное для достижения системой некоторой цели (целей) или желаемого поведения. В свою очередь система также оказывает на среду или другие системы определенные информационные или материальные воздействия, которые получили название входных воздействий (параметров, переменных).
Ценность моделей, подобных модели “черного ящика”, весьма условна.
Основное ее назначение состоит в том, чтобы структурировать исходную информацию относительно самой системы и внешней по отношению к ней среды. Поэтому эта модель, прежде всего, фиксирует упоминавшиеся ранее границы системы. В дополнение к этому модель специфицирует воздействия, на которые реагирует система, и как проявляется эта реакция на окружающие объекты и системы. При этом, в случае количественного описания входных (выходных) воздействий, их иногда называют входными (выходными) переменными. В рамках системного моделирования разработаны определенные методологические средства, позволяющие выполнить дальнейшую структуризацию или концептуализацию этой наиболее общей модели системы.
В методологии системного моделирования выделяются сложные системы, исследование которых представляет наибольший интерес в контексте постановки и решения задач оптимизации. При этом сложность системы и, соответственно, ее модели может быть рассмотрена с различных точек зрения. Прежде всего, можно выделить сложность структуры системы, которая характеризуется большим количеством элементов и различными типами взаимосвязей между ними.....