Краткие методические указания по самостоятельному изучению курса

1. Введение в ТПР [4, гл.1]. Познакомьтесь с постановкой задачи принятия решений (ЗПР) и процессом принятия решений. Уясните типовые ЗПР (с точки зрения конечного результата). Обратите особое внимание на различие ЗПР по признаку их структуризованности (по Саймону).

2.Основные понятия системного анализа и исследования операций [2 или 3, разд.1.1-1.4]. Уясните такие понятия как система, структура, связи, операция и ее составляющие, критерий, оптимальное решение, ЛПР. Рассмотрите этапы системного анализа и исследования операций. Отметьте основные особенности исследования операций (ИО), отличие от СА.. Обратите внимание на требования к критерию в ИО. Разберите варианты математических моделей в ИО.

3. Классы задач исследования операций [2 или 3, разд.1.5]. Рассмотрите постановки типовых задач ИО: управления запасами, распределения, массового обслуживания, упорядочения, сетевого планирования, выбора маршрута, замены оборудования, поиска. Подробнее рассмотрите состязательные задачи и решение игровых задач с нулевой суммой. Уясните смысл принципа гарантированного результата.

4. Методы классического анализа [2 или 3, гл.2 и 3]. Здесь следует освежить знания по теории экстремумов: понятия и виды экстремумов, теорема существования решения (Вейерштрасса), экстремальные точки, свойства функций, необходимые и достаточные условия экстремума. Рассмотрите порядок исследования на экстремум функций многих переменных и достаточные условия максимума (минимума), проблему отыскания условного оптимума. Изучите метод множителей Лагранжа и уяснить область его применения.

5. Динамическое программирование (ДП) в исследовании операций [1, гл.10],[2, гл.4 или 3, гл.9].

Уясните концепцию ДП, принцип оптимальности Р.Беллмана и условия применимости метода. Особо обратите внимание на понимание понятия «состояние». Изучите следующие вопросы: Функциональное уравнение ДП в общем случае. Процедура динамического программирования. Задача распределения одного вида ресурса, вычислительные аспекты ДП. Достоинства метода ДП. Примене­ние ДП к задачам с мультипликативным критерием. Декомпозиция в ДП. Многомерные задачи ДП (здесь важно понять, откуда берется многомерность). Проблема размерности. Снижение раз­мерности с помощью множителей Лагранжа. Область применения динамического программирования.

Обязательно разберите численные примеры.

6. Линейное программирование (ЛП) [1, гл.2-5 и 7], [3, гл. 4 и 5], [13].

Рассмотрите общую постановку задачи ЛП, примеры задач, описываемых моде­лями ЛП (задачи составления рациона или смеси, использования ресурсов, транспорт­ная задача, общая распределительная задача, задача загрузки оборудова­ния, игра 2-x лиц с нулевой суммой). Выясните, для чего нужны каноническая и стандартная формы задач ЛП, как исходную модель преобразовать к одной из них. Попробуйте сами предложить реальную ситуацию, описываемую линейной моделью.

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

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

Изучите двойственность задач ЛП. Обратите внимание на экономическую ин­терпретацию двойственной задачи. Рассматривая основные теоремы двойственности, убедитесь в тесной связи решений прямой и двойственной задач.

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

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

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

7. Целочисленное программирование [1, гл.9], [3, гл.7]. Обратите внимание на особенности дискретных задач, источники дискретности, пробле­мы получения целочисленного решения. Рассмотрите концепцию метода отсечения и его практическую применимость. Подробнее разберите метод ветвей и границ. Получите представление о других методах целочисленного программирования.

8. Нелинейное программирование (НП) [1, гл.20,21], [3, гл.8].

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

9. Многокритериальные задачи принятия решений [3, гл.10].

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

10. Неструктуризованные задачи принятия решений [4, гл.4,5 и 8]. Выясните отличие этих ЗПР от задач исследования операций. Рассмотрите методы решения слабоструктуризованных и неструктуризованных ЗПР: многокритериальная теория полезности, вербальный анализ, метод анализа иерархий. Проработайте примеры решения ЗПР данными методами. Определите особенности и условия применимости каждого из методов