Руководство к лабораторной работе «Исследование задач оптимизации на графах»

Санкт-Петербургский Государственный университет

РУКОВОДСТВО

к лабораторной работе

«Исследование задач оптимизации на графах»

Санкт-Петербург

2000

введение

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

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

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

-  транспортные задачи;

-  сетевые задачи.

1. цель лабораторной работы

Целью лабораторной работы является:

-  закрепление теоретических знаний, получаемых студентами на лекционных и самостоятельных занятиях по решению транспортных задач;

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

-  ознакомление с особенностями применения современных пакетов прикладных программ для решения транспортных задач, приобретение навыков в их постановке и решении на ПЭВМ;

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

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

-  методологические и методические основы подготовки и принятия решений в сложных технико-экономических системах (ТЭС);

-  классификация задач выбора с одним отношением предпочтения;

-  содержательная постановка задачи коммивояжёра, транспортной задачи, задачи распределения ресурсов в ТЭС;

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

-  основные этапы решения транспортной задачи;

-  особенности подготовки исходных данных и решения транспортных задач с использованием пакета прикладных программ QSB и табличного процессора Excel 7.0.

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

2. теоретические основы работы

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

Важнейшая особенность современной научно-технической революции состоит в том, что по мере её развития всё большее значение приобретает учёт факторов сложности технико-экономических систем и комплексов: многоаспектность, высокая размерность, неопределённость в её разнообразных проявлениях и др. Учёные считают, что быстрое возрастание сложности – одна из наиболее характерных черт современности. Несомненно, значение проблемы преодоления сложности сохранится и в будущем. Это обусловлено быстрым возрастанием сложности технологии производства, сложности конструкций систем различного назначения, возрастанием объёмов и разнообразия информационных потоков, созданием автоматизированных систем управления глобального характера. Особенно остро вопрос о факторах сложности ставится в связи с необходимостью учёта всевозможных аспектов взаимодействия системы с окружающей средой в таких областях, как экология, экономика, военное дело и пр.