Исследование операций

Цели и задачи дисциплины

В результате освоения данной дисциплины студент приобретает знания, умения и навыки, обеспечивающие достижение целей основной образовательной программы «Информатика и вычислительная техника». Целью изучения дисциплины обеспечить приобретение знаний, умений и навыков, обеспечивающих достижение целей основной образовательной программы «Информатика и вычислительная техника». Задачи дисциплины: 1. Получение базовых знаний и формирование основных навыков по методам исследований операций, необходимых для решения задач, возникающих в практической деятельности. 2. Создание основы для развития понятийной теоретической базы и формирование уровня практической подготовки, необходимых для понимания основных методов исследования операций и их применения в технике.

Краткое содержание дисциплины

1. Линейное программирование 1.1. Общая постановка задачи оптимизации. Целевая функция. Допустимое множество. Допустимое решение. Оптимальное решение. Оптимальное множество. 1.2. Постановка задачи математического программирования. Классификация задач математического программирования. Постановка задачи линейного программирования. 1.3. Примеры задач линейного программирования (ЛП): задача о банке, задача о диете, задача об использовании ресурсов, транспортная задача. 1.4. Общая постановка задачи ЛП и различные формы ее записи (числовая, матричная). Стандартная и каноническая формы задачи ЛП. 1.5. Геометрия задачи ЛП. Выпуклая многогранная область в n R . Проектирование выпуклого многогранника на координатные плоскости. Теорема о проекциях. Теорема о существовании оптимального решения задачи ЛП в случае ограниченности целевой функции. 1.6. Теорема о достижимости оптимального решения задачи ЛП в угловой точке (в случае ограниченности целевой функции). Строение множества оптимальных решений. 1.7. Графический метод решения задач ЛП при малом числе неизвестных. Линия уровня целевой функции. Алгоритм решения задачи ЛП графическим методом. Сведение задач линейного программирования общего вида к задачам, допускающим решение графическим методом. 1.8. Симплекс-метод решения задачи ЛП общего вида. Алгоритм решения задачи ЛП симплекс-методом. Геометрическая интерпретация симплекс-алгоритма. Теорема о конечности симплекс-алгоритма. Применение компьютерных программ для решения задач линейного программирования. 2. Теория двойственности 2.1. Постановка взаимно двойственных задач ЛП. Симметричные взаимно двойственные задачи. Экономический смысл двойственности. Основное неравенство для двойственных задач. Основная теорема двойственности и ее следствия. Критерий оптимальности. Теорема равновесия. Условия дополняющей не жёсткости. 2.2. Двойственность в экономических задачах. Двойственные цены. Применение двойственности в одно продуктивной задаче. 2.3. Транспортная задача ЛП. Открытая и закрытая модель транспортной задачи. Критерий разрешимости транспортной задачи. Методы построения начального опорного плана транспортной задачи (метод СЗ угла, метод минимального тарифа, метод Фогеля). 2.4. Потенциалы, их экономический смысл. Решение транспортной задачи методом потенциалов. Двойственность в транспортной задаче. 2.5. Транспортные задачи с нарушенным балансом запасов и потребностей. Транспортные задачи с ограничениями перевозок. Примеры решения задач нетранспортного характера, сводимые к транспортным задачам. 3. Задачи многокритериальной оптимизации. 3.1. Происхождение и постановка задачи многокритериальной оптимизации. Множество достижимых критериальных векторов. Доминирование и оптимальность по Парето. Эффективные решения и паретова граница. 3.2. Основные методы решения многокритериальных задач. Свертка критериев с весовыми коэффициентами. Метод обобщенного критерия. Метод идеальной точки. 3.3. Методы параметрического программирования и последовательных уступок решения многокритериальных задач. 4. Элементы теории игр 4.1. Понятие об игровых моделях. Платежная матрица. Верхняя и нижняя цена игры. Седловая точка. Решение игр в смешанных стратегиях. Теорема Неймана. Матричная игра как задача линейного программирования. 4.2. Принципы максимина и минимакса. Оптимальная стратегия и цена игры. Графическое решение игр вида 2 × n и m × 2. Решения игровых задач методами линейного программирования.

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

Выпускник должен обладать:

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