Ответы

Ответы

---

Конечно, я помогу вам подготовить подробные ответы к экзамену по математическому моделированию. Вот первые 20 ответов, оформленные согласно вашим требованиям.

---

1. Задачи и цели исследования операций и экономико-математических методов и моделей.

Ответ

Исследование операций (ИО) — это научный подход к принятию решений, который использует математические модели, статистические методы и алгоритмы для оптимизации сложных систем. Оно направлено на поиск наилучших или оптимальных решений в условиях ограниченных ресурсов и неопределенности.

Основные задачи ИО:

1. Оптимизация: Нахождение наилучшего решения (максимизация прибыли, минимизация затрат, времени, рисков).

2. Прогнозирование: Предсказание будущих событий или тенденций на основе имеющихся данных.

3. Моделирование: Создание упрощенных представлений реальных систем для их анализа и экспериментирования.

4. Анализ рисков: Оценка и управление неопределенностью и потенциальными негативными последствиями.

5. Принятие решений: Разработка методов и инструментов для поддержки выбора оптимальных стратегий.

Цели ИО:

• Повышение эффективности и производительности систем.

• Снижение издержек и потерь.

• Улучшение качества обслуживания или продукции.

• Оптимальное распределение ресурсов.

• Повышение конкурентоспособности.

Экономико-математические методы и модели — это инструменты, которые применяют математический аппарат для анализа экономических процессов и явлений. Они позволяют формализовать экономические зависимости и находить оптимальные решения в экономике.

Задачи экономико-математических методов и моделей:

• Планирование и прогнозирование: Разработка оптимальных планов производства, распределения, инвестиций.

• Анализ эффективности: Оценка результативности различных экономических стратегий и решений.

• Управление ресурсами: Оптимальное использование труда, капитала, сырья.

• Ценообразование: Определение оптимальных цен на товары и услуги.

• Анализ рисков в экономике: Оценка влияния неопределенности на экономические результаты.

Цели экономико-математических методов и моделей:

• Научно обоснованное принятие экономических решений.

• Повышение обоснованности экономических прогнозов.

• Оптимизация экономических процессов на микро- и макроуровне.

• Выявление скрытых закономерностей и взаимосвязей в экономике.

---

2. Понятие модели. Основные принципы моделирования.

Ответ

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

Например, карта является моделью местности, а уравнение движения тела — моделью физического процесса.

Основные принципы моделирования:

1. Принцип адекватности (валидности): Модель должна соответствовать оригиналу в аспектах, существенных для цели исследования. Это означает, что поведение модели должно быть схожим с поведением реальной системы при одинаковых условиях. Неадекватная модель может привести к неверным выводам.

2. Принцип целенаправленности: Модель всегда создается для достижения определенной цели. Цель моделирования определяет, какие свойства оригинала должны быть отражены в модели, а какие можно опустить. Одна и та же система может иметь множество моделей, каждая из которых служит своей цели.

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

4. Принцип замкнутости (изоляции): Модель должна быть достаточно автономной, чтобы ее можно было изучать отдельно от оригинала. Это не означает полного отсутствия внешних связей, но границы модели должны быть четко определены.

5. Принцип верифицируемости (проверяемости): Модель должна быть проверяемой. Ее предсказания или результаты должны быть сопоставимы с реальными данными или с экспертными оценками, чтобы убедиться в ее достоверности.

6. Принцип фальсифицируемости: Модель должна быть потенциально опровергаемой. То есть, должны существовать способы, посредством которых можно было бы показать ее неточность или неверность.

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

---

3. Этапы математического моделирования: постановка задачи, определение объекта и целей исследования, задание критериев (признаков) изучения объектов и управление ими.

Ответ

Математическое моделирование — это процесс создания и анализа математических моделей для изучения реальных систем. Он включает в себя несколько ключевых этапов:

1. Постановка задачи:

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

   • Определяются границы системы, то есть что будет входить в модель, а что останется за ее пределами.

   • Устанавливаются исходные данные, которые будут доступны для построения модели, и желаемые результаты, которые модель должна предоставить.

   • Пример: “Необходимо оптимизировать маршруты доставки товаров, чтобы минимизировать затраты на топливо и время доставки.”

2. Определение объекта и целей исследования:

   • Определение объекта исследования: Четко идентифицируется реальный объект, процесс или явление, которое будет моделироваться. Это может быть производственная система, экономическая система, биологический процесс, физическое явление и так далее.

   • Определение целей исследования: Конкретизируются цели, которые преследуются при моделировании. Чего именно мы хотим добиться, изучая эту модель? Это может быть прогнозирование поведения, оптимизация параметров, анализ чувствительности и т.д.

   • Пример: “Объект исследования — система логистики компании X. Цель — найти оптимальные маршруты для автопарка, минимизирующие транспортные расходы и время в пути.”

3. Задание критериев (признаков) изучения объектов и управление ими:

   • На этом этапе определяются ключевые параметры и переменные, которые будут использоваться в модели. Это могут быть как входные данные, так и выходные показатели.

   • Критерии изучения (целевая функция): Формулируется функция, которая будет измерять “качество” решения. Эта функция может быть максимизирована (например, прибыль) или минимизирована (например, затраты).

   • Ограничения: Определяются условия, которые должны быть удовлетворены моделью. Это могут быть ограничения по ресурсам, времени, производительности, нормативным требованиям и т.д. Ограничения могут быть представлены в виде равенств или неравенств.

   • Управляемые переменные (решения): Идентифицируются переменные, значения которых могут быть изменены для достижения поставленной цели. Это то, чем мы можем “управлять” в системе.

   • Пример: “Критерий изучения — суммарные транспортные расходы (топливо, амортизация). Управляемые переменные — последовательность посещения точек доставки и выбор транспортных средств. Ограничения — грузоподъемность автомобилей, временные окна доставки, наличие водителей.”

---

4. Выбор типа математической модели.

Ответ

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

1. Цель моделирования:

   • Прогнозирование: Если цель — предсказать будущее поведение системы, могут использоваться статистические модели, временные ряды, регрессионные модели.

   • Оптимизация: Если требуется найти наилучшее решение (максимум прибыли, минимум затрат), применяются модели оптимизации: линейное программирование, нелинейное программирование, динамическое программирование.

   • Анализ “что-если”: Для изучения влияния изменения входных параметров на выходные данные используются имитационные модели.

   • Управление: Для разработки стратегий управления используются модели управления, например, модели оптимального управления.

2. Характеристики объекта исследования:

   • Детерминированность/Стохастичность:

     • Детерминированные модели: Используются, если все параметры и взаимосвязи в системе известны точно и не содержат случайных элементов. Результат таких моделей предсказуем.

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

   • Дискретность/Непрерывность:

     • Дискретные модели: Используются, если переменные принимают конечный или счетный набор значений (например, количество произведенных единиц).

     • Непрерывные модели: Применяются, если переменные могут принимать любые значения в определенном диапазоне (например, температура, время).

   • Статичность/Динамичность:

     • Статические модели: Описывают состояние системы в определенный момент времени, без учета ее эволюции во времени.

     • Динамические модели: Описывают изменение системы во времени, учитывая зависимости от прошлых состояний (например, дифференциальные уравнения, разностные уравнения).

3. Наличие данных:

   • Доступность и качество исторических данных влияют на выбор статистических и эмпирических моделей.

   • Если данных мало или они ненадежны, предпочтительнее использовать аналитические или экспертные модели.

4. Сложность системы:

   • Для простых систем можно использовать аналитические модели, решаемые алгебраически.

   • Для сложных систем с большим количеством взаимосвязей часто применяются имитационные или численные методы.

5. Доступные инструменты и компетенции:

   • Наличие программного обеспечения (например, для линейного программирования) и знаний в определенных областях математики также влияют на выбор.

Примеры типов моделей:

• Математическое программирование: Линейное, нелинейное, целочисленное, динамическое (для задач оптимизации).

• Теория массового обслуживания: Для анализа очередей и систем обслуживания.

• Имитационное моделирование: Для воспроизведения поведения системы во времени.

• Теория игр: Для анализа конфликтных ситуаций.

• Статистические модели: Регрессионный анализ, анализ временных рядов (для прогнозирования).

• Дифференциальные и интегральные уравнения: Для описания динамических систем.

---

5. Методы принятия решений.

Ответ

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

Различают несколько категорий методов принятия решений:

1. Качественные (эвристические) методы:

   • Основаны на интуиции, опыте, знаниях и мнениях экспертов. Применяются в условиях высокой неопределенности или отсутствия достаточных данных для количественного анализа.

   • Метод мозгового штурма: Генерирование большого количества идей в группе без критики, с последующим отбором.

   • Метод Дельфи: Получение консенсусного мнения экспертов путем многократного анонимного анкетирования с обратной связью.

   • Метод дерева решений: Графическое представление последовательности решений и возможных исходов с учетом вероятностей.

   • Метод сценариев: Разработка нескольких возможных будущих сценариев для оценки их влияния на решение.

2. Количественные (формализованные) методы:

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

   • Методы теории полезности: Оценка альтернатив на основе предпочтений лица, принимающего решение, с учетом риска.

   • Методы математического программирования:

     • Линейное программирование (ЛП): Для оптимизации линейной целевой функции при линейных ограничениях. Широко используется в задачах распределения ресурсов, планирования производства.

     • Нелинейное программирование (НЛП): Для задач, где целевая функция или ограничения нелинейны.

     • Целочисленное программирование: Вариант ЛП, где переменные должны быть целыми числами (например, количество единиц оборудования).

     • Динамическое программирование: Для решения многошаговых задач, где решение на каждом шаге влияет на последующие.

   • Методы статистического анализа:

     • Регрессионный анализ: Прогнозирование зависимой переменной на основе одной или нескольких независимых.

     • Дисперсионный анализ: Сравнение средних значений нескольких групп.

     • Имитационное моделирование (Монте-Карло): Проведение компьютерных экспериментов для оценки поведения системы в условиях неопределенности путем многократного моделирования случайных событий.

   • Методы теории массового обслуживания: Анализ систем с очередями (например, потоки клиентов, машин).

   • Методы теории игр: Анализ принятия решений в конфликтных ситуациях, где результат зависит от действий нескольких игроков.

   • Методы многокритериального принятия решений (МКР):

     • Метод анализа иерархий (МАИ): Разложение сложной проблемы на иерархическую структуру, попарное сравнение элементов.

     • Метод ELECTRE, PROMETHEE: Методы для сравнения альтернатив по нескольким критериям.

Процесс принятия решений обычно включает:

3. Определение проблемы.

4. Сбор и анализ информации.

5. Формулирование альтернатив.

6. Оценка альтернатив с использованием выбранных методов.

7. Выбор наилучшей альтернативы.

8. Реализация решения.

9. Мониторинг и оценка результатов.

---

6. Классификация математических моделей.

Ответ

Математические модели можно классифицировать по различным признакам, что помогает выбрать подходящий подход для их построения и анализа:

1. По характеру зависимости от времени (динамические / статические):

   • Статические модели: Описывают состояние системы в определенный момент времени, не учитывая ее эволюцию. Они не содержат переменных, зависящих от времени. Пример: модель баланса спроса и предложения на рынке.

   • Динамические модели: Описывают изменение состояния системы во времени. Включают временные производные или разности. Пример: модель роста популяции, описываемая дифференциальным уравнением.

2. По учету случайных факторов (детерминированные / стохастические):

   • Детерминированные модели: Все параметры и взаимосвязи в модели известны точно, и результаты предсказуемы. Случайные факторы не учитываются. Пример: задача линейного программирования.

   • Стохастические (вероятностные) модели: Содержат случайные переменные или процессы, что делает их результаты вероятностными. Пример: модели массового обслуживания, имитационные модели Монте-Карло, марковские цепи.

3. По характеру изменения переменных (дискретные / непрерывные):

   • Дискретные модели: Переменные принимают только целые или счетные значения. Изменения происходят в дискретные моменты времени или по шагам. Пример: модели целочисленного программирования, модели роста дискретных популяций.

   • Непрерывные модели: Переменные могут принимать любые значения в заданном диапазоне. Изменения происходят непрерывно. Пример: модели, описываемые дифференциальными уравнениями.

4. По степени формализации (аналитические / имитационные):

   • Аналитические модели: Могут быть решены с помощью аналитических методов (алгебраические уравнения, дифференциальные уравнения) для получения точного или приближенного решения. Часто имеют относительно простую структуру. Пример: модели линейного программирования, решаемые симплекс-методом.

   • Имитационные модели: Воспроизводят поведение системы во времени путем симуляции ее компонентов и их взаимодействий. Используются, когда аналитическое решение невозможно или слишком сложно. Результаты получаются путем проведения “экспериментов” с моделью. Пример: моделирование работы банка, транспортной системы.

5. По области применения (экономико-математические, физические, биологические и т.д.):

   • Экономико-математические: Модели спроса и предложения, производственные функции, модели ценообразования.

   • Физические: Модели движения тел, теплопередачи, электрических цепей.

   • Биологические: Модели роста популяций, распространения заболеваний.

6. По характеру математического аппарата:

   • Алгебраические модели: Используют алгебраические уравнения и неравенства.

   • Дифференциальные и интегральные модели: Используют дифференциальные и интегральные уравнения для описания динамики.

   • Матричные модели: Используют матрицы и векторы для представления данных и связей.

   • Графовые модели: Используют графы для представления связей между объектами (например, сетевые модели, транспортные задачи).

---

7. Обзор современного программного обеспечения, используемого для решения задач математического моделирования.

Ответ

Современное программное обеспечение для математического моделирования предлагает широкий спектр инструментов для различных типов задач — от статистического анализа до оптимизации и имитации. Выбор ПО зависит от конкретной задачи, требуемого уровня детализации и профессиональных навыков пользователя.

1. Математические пакеты общего назначения:

   • MATLAB: Мощная платформа для численных расчетов, моделирования, визуализации данных и программирования. Широко используется в инженерии, науке и финансах. Имеет обширные тулбоксы (например, Optimization Toolbox, Statistics and Machine Learning Toolbox, Simulink для имитационного моделирования).

   • Python (с библиотеками): Универсальный язык программирования с огромным количеством библиотек для научных вычислений и моделирования.

     • NumPy: Для работы с массивами и матрицами.

     • SciPy: Для научных и инженерных вычислений (оптимизация, статистика, обработка сигналов).

     • Pandas: Для анализа и манипулирования данными.

     • Matplotlib, Seaborn: Для визуализации данных.

     • Scikit-learn: Для машинного обучения и статистического моделирования.

     • Pyomo, PuLP, Gurobipy: Для математического программирования.

   • R: Язык и среда для статистических вычислений и графики. Очень популярен в статистике, эконометрике, биоинформатике. Имеет огромное количество пакетов для различных видов анализа.

   • Wolfram Mathematica: Интегрированная система для символьных и численных вычислений, визуализации, программирования. Отлично подходит для аналитических решений и сложных математических задач.

   • GNU Octave: Бесплатный аналог MATLAB с похожим синтаксисом.

2. Программное обеспечение для оптимизации (математического программирования):

   • Gurobi Optimizer: Один из самых быстрых и мощных коммерческих солверов для линейного, квадратичного, конического и смешанного целочисленного программирования.

   • CPLEX (IBM ILOG CPLEX Optimization Studio): Еще один ведущий коммерческий солвер для широкого спектра задач математического программирования.

   • OR-Tools (Google OR-Tools): Библиотека с открытым исходным кодом от Google для решения задач оптимизации (линейное программирование, маршрутизация, сетевые потоки). Поддерживает Python, C++, Java, C#.

   • Lingo/Lindo: Популярные инструменты для быстрого решения линейных, нелинейных и целочисленных задач.

   • OpenSolver (для Excel): Дополнение для Microsoft Excel, позволяющее решать более крупные и сложные задачи линейного и нелинейного программирования, чем встроенный Solver.

   • SciPy.optimize (Python): Модуль в SciPy для различных методов оптимизации.

3. Программное обеспечение для имитационного моделирования:

   • AnyLogic: Гибкая платформа для мультиметодного имитационного моделирования (дискретно-событийное, системная динамика, агентное моделирование). Используется для моделирования бизнес-процессов, логистики, производства.

   • Arena (Rockwell Automation): Популярный инструмент для дискретно-событийного моделирования производственных, логистических и обслуживающих систем.

   • Simulink (часть MATLAB): Графическая среда для моделирования и симуляции динамических систем.

   • Vensim, Stella: Инструменты для системной динамики, используемые для моделирования сложных систем с обратными связями (экономические, социальные, экологические).

4. Специализированные статистические пакеты:

   • SPSS (IBM SPSS Statistics): Широко используется для статистического анализа данных в социальных науках, маркетинге, медицине.

   • SAS: Комплексное программное обеспечение для расширенной аналитики, управления данными, бизнес-аналитики.

   • Statistica: Пакет для статистического анализа и интеллектуального анализа данных.

5. Электронные таблицы (например, Microsoft Excel):

   • Могут использоваться для простых задач математического моделирования с помощью встроенных функций и надстроек (например, “Поиск решения” (Solver) для линейного программирования).

---

8. Основные понятия и определения линейного программирования.

Ответ

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

Основные понятия и определения:

1. Целевая функция (Objective Function):

   • Линейная функция, которую необходимо максимизировать (например, прибыль, доход) или минимизировать (например, затраты, время).

   • Общий вид: Z=c_1x_1+c_2x_2+dots+c_nx_n=sum_j=1nc_jx_j, где x_j — переменные решения, а c_j — коэффициенты, представляющие вклад каждой переменной в целевую функцию.

2. Переменные решения (Decision Variables):

   • Неизвестные величины, значения которых необходимо определить для достижения оптимального значения целевой функции. Они представляют собой количество производимого продукта, объем используемых ресурсов и т.д.

   • Обычно обозначаются как x_1,x_2,dots,x_n.

3. Ограничения (Constraints):

   • Линейные равенства или неравенства, которые отражают ограничения на доступные ресурсы, производственные мощности, спрос, другие условия и требования.

   • Общий вид: a_i1x_1+a_i2x_2+dots+a_inx_nleb_i (или geb_i или =b_i), где a_ij — коэффициенты, b_i — правая часть ограничения (количество доступного ресурса).

4. Ограничения неотрицательности (Non-negativity Constraints):

   • Требование, чтобы все переменные решения были неотрицательными (x_jge0). Это логично для большинства практических задач, так как невозможно произвести отрицательное количество продукта или использовать отрицательное количество ресурса.

5. Допустимое решение (Feasible Solution):

   • Набор значений переменных решения (x_1,x_2,dots,x_n), который удовлетворяет всем ограничениям задачи (включая ограничения неотрицательности).

6. Допустимая область (Feasible Region):

   • Множество всех допустимых решений. Графически это многогранник (полиэдр) в n-мерном пространстве.

7. Оптимальное решение (Optimal Solution):

   • Допустимое решение, при котором целевая функция достигает своего максимального (для задач максимизации) или минимального (для задач минимизации) значения.

8. Оптимальное значение целевой функции (Optimal Objective Value):

   • Значение целевой функции, полученное при оптимальном решении.

9. Стандартная форма задачи ЛП:

   • Задача линейного программирования обычно приводится к стандартной форме для применения симплекс-метода.

   • Для максимизации:

     • Целевая функция — максимизация.

     • Все ограничения — неравенства типа “меньше или равно” (le).

     • Все переменные неотрицательны.

   • Для минимизации:

     • Целевая функция — минимизация.

     • Все ограничения — неравенства типа “больше или равно” (ge).

     • Все переменные неотрицательны.

10. Базисное решение (Basic Solution):

    • Решение системы линейных уравнений, полученной из ограничений путем приравнивания некоторых переменных к нулю.

11. Опорное (базисное допустимое) решение (Basic Feasible Solution):

    • Базисное решение, которое также удовлетворяет ограничениям неотрицательности. Геометрически соответствуют вершинам допустимой области. Симплекс-метод ищет оптимальное решение, переходя от одной опорной точки к другой.

---

9. Классификация задач линейного программирования.

Ответ

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

1. По цели оптимизации:

   • Задачи на максимизацию: Целевая функция должна быть максимально увеличена. Типичные примеры: максимизация прибыли, дохода, выпуска продукции.

     • Пример: “Компания хочет максимизировать прибыль от производства двух видов продукции, используя ограниченные ресурсы.”

   • Задачи на минимизацию: Целевая функция должна быть максимально уменьшена. Типичные примеры: минимизация затрат, времени, потерь, расстояний.

     • Пример: “Предприятие стремится минимизировать транспортные расходы на доставку товаров из нескольких складов в несколько пунктов назначения.”

2. По числу переменных и ограничений:

   • Задачи малого размера: Могут быть решены графически (для 2-3 переменных) или с использованием простых вычислительных инструментов.

   • Задачи среднего и большого размера: Требуют применения симплекс-метода или специализированного программного обеспечения. В реальных задачах количество переменных и ограничений может достигать тысяч и миллионов.

3. По структуре ограничений:

   • Задачи со всеми ограничениями-неравенствами: Все ограничения заданы в виде le или ge.

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

   • Задачи с ограничениями-равенствами: Все ограничения заданы в виде равенств.

4. По характеру переменных:

   • Задачи с непрерывными переменными: Переменные могут принимать любые действительные значения. Это классические задачи ЛП.

   • Задачи с целочисленными переменными (целочисленное программирование): Некоторые или все переменные должны принимать только целочисленные значения. Эти задачи сложнее, чем обычные ЛП, и требуют специальных методов (например, метод ветвей и границ, метод отсечений).

   • Задачи с бинарными переменными (булево программирование): Переменные могут принимать только значения 0 или 1 (например, “выполнять проект или нет”, “строить завод или нет”). Являются частным случаем целочисленного программирования.

5. По типичным постановкам:

   • Транспортная задача: Определение оптимальных объемов перевозок грузов от поставщиков к потребителям с минимизацией транспортных затрат.

   • Задача о назначении: Распределение заданий между исполнителями с целью минимизации общих затрат или времени.

   • Задача о смеси (диеты): Определение оптимального состава смеси (например, корма, сплава), чтобы обеспечить требуемые свойства при минимальной стоимости.

   • Задача о раскрое: Оптимальный раскрой материала для минимизации отходов.

   • Задача планирования производства: Определение объемов производства различных видов продукции для максимизации прибыли при ограниченных ресурсах.

   • Задача управления запасами: Оптимизация уровней запасов для удовлетворения спроса при минимизации затрат на хранение и дефицит.

---

10. Симплекс метод. Графическая интерпретация симплекс метода.

Ответ

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

Основная идея симплекс-метода:

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

Шаги симплекс-метода (общая идея):

1. Приведение задачи к стандартной форме: Все ограничения-неравенства преобразуются в равенства путем введения балансовых (дополнительных) переменных (для le) или избыточных и искусственных переменных (для ge и =). Целевая функция обычно переносится в левую часть равенства и максимизируется (или минимизируется).

2. Построение начального опорного плана (базисного допустимого решения): Находится исходная угловая точка допустимой области. Часто это делается с использованием искусственных переменных (метод искусственного базиса).

3. Итерационный процесс:

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

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

   • Пересчет симплекс-таблицы (или матрицы): Выполняется Жорданово исключение для преобразования таблицы так, чтобы выбранная ведущая переменная вошла в базис, а выведенная — вышла.

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

---

Графическая интерпретация симплекс-метода:

Графическая интерпретация симплекс-метода возможна для задач с двумя (или тремя) переменными решения, так как допустимая область может быть изображена на плоскости (или в пространстве).

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

6. Линии уровня целевой функции: Целевая функция (Z=c_1x_1+c_2x_2) может быть представлена в виде семейства параллельных линий (c_1x_1+c_2x_2=const). Для задач максимизации мы хотим найти линию уровня с наибольшим значением константы, которая еще пересекает допустимую область. Для минимизации — с наименьшим.

7. Переход по вершинам:

   • Симплекс-метод начинает поиск решения с одной из вершин (угловых точек) допустимой области. Каждая вершина соответствует опорному решению задачи ЛП.

   • На каждом шаге симплекс-метод “переходит” от текущей вершины к смежной вершине, которая улучшает значение целевой функции. Этот переход происходит вдоль одного из рёбер многогранника допустимых решений.

   • Процесс продолжается до тех пор, пока не будет достигнута вершина, из которой невозможно перейти к смежной вершине с лучшим значением целевой функции. Эта вершина и будет соответствовать оптимальному решению.

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

Преимущества графического метода: Нагляден, позволяет понять геометрический смысл симплекс-метода.

Недостатки: Применим только для задач с 2 (иногда 3) переменными. Для большего числа переменных требуется алгебраический подход (симплекс-метод в табличной форме).

---

11. Нахождение опорного плана и оптимального решения задач линейного программирования.

Ответ

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

1. Нахождение опорного плана

Опорный план — это допустимое решение задачи ЛП, которое соответствует вершине многогранника допустимых решений. Это начальная точка для симплекс-метода.

Методы нахождения начального опорного плана:

а) Метод базисных переменных (для простой формы):

• Если все ограничения задачи имеют вид “меньше или равно” (le) и правые части неотрицательны, а все переменные неотрицательны, то можно ввести балансовые (слабые) переменные (slack variables).

• Каждая балансовая переменная добавляется к левой части неравенства, превращая его в равенство. Например, 2x_1+3x_2le10rightarrow2x_1+3x_2+s_1=10.

• Исходный опорный план можно получить, приравняв все исходные (небазисные) переменные к нулю. Тогда значения балансовых переменных будут равны правым частям ограничений. Эти балансовые переменные формируют начальный базис.

• Пример:

  • maxZ=3x_1+2x_2

  • x_1+x_2le4

  • 2x_1+x_2le6

  • x_1,x_2ge0

• Приведение к стандартной форме:

  • maxZ=3x_1+2x_2

  • x_1+x_2+s_1=4

  • 2x_1+x_2+s_2=6

  • x_1,x_2,s_1,s_2ge0

• Начальный опорный план: x_1=0,x_2=0Rightarrows_1=4,s_2=6. Базисные переменные: s_1,s_2. Значение Z=0.

б) Метод искусственного базиса (двухфазный метод или метод М-штрафа):

• Используется, когда в задаче присутствуют ограничения типа “больше или равно” (ge) или равенства (=), или когда простой формы недостаточно.

• Для каждого ограничения типа ge вводится избыточная (surplus) переменная (вычитается) для преобразования в равенство, а также искусственная (artificial) переменная (добавляется), чтобы иметь начальный базис.

• Для ограничений типа = также вводится искусственная переменная.

• Метод М-штрафа: Искусственным переменным присваивается очень большой штраф (M) в целевой функции (−Mx_искусст для максимизации, +Mx_искусст для минимизации), чтобы вынудить их выйти из базиса.

• Двухфазный метод:

  • Фаза 1: Решается вспомогательная задача, целью которой является минимизация суммы искусственных переменных. Если минимальное значение суммы равно нулю, то найден опорный план исходной задачи (искусственные переменные выведены из базиса). Если не равно нулю, то исходная задача не имеет допустимых решений.

  • Фаза 2: Искусственные переменные удаляются, и симплекс-метод применяется к исходной целевой функции, начиная с опорного плана, найденного в Фазе 1.

2. Нахождение оптимального решения

После нахождения начального опорного плана начинается итерационный процесс симплекс-метода:

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

2. Проверка на оптимальность:

   • Для задач максимизации: Проверяются коэффициенты в строке целевой функции (или Z-строке, или оценочной строке). Если все эти коэффициенты неотрицательны (или неположительны, в зависимости от формы Z-строки), то текущее базисное допустимое решение является оптимальным.

   • Для задач минимизации: Если все коэффициенты в строке целевой функции неположительны (или неотрицательны).

3. Выбор ведущего столбца (вводимой переменной):

   • Если решение не оптимально, выбирается переменная, которая войдет в базис.

   • Для максимизации: Выбирается столбец с наибольшим положительным коэффициентом в строке целевой функции.

   • Для минимизации: Выбирается столбец с наибольшим по модулю отрицательным коэффициентом в строке целевой функции.

4. Выбор ведущей строки (выводимой переменной):

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

   • Ведущая строка — это строка с минимальным неотрицательным из этих отношений. Это гарантирует, что новое решение останется допустимым.

   • Элемент на пересечении ведущей строки и ведущего столбца называется ведущим элементом.

5. Преобразование таблицы (итерация):

   • Выполняются элементарные преобразования строк симплекс-таблицы (аналогично методу Гаусса), чтобы ведущий элемент стал 1, а все остальные элементы в ведущем столбце стали 0.

   • Это эквивалентно переходу к новой смежной вершине допустимой области.

6. Повторение: Возврат к шагу 2 до тех пор, пока не будет найдено оптимальное решение или не будет установлено, что задача не имеет конечного решения (неограниченна) или не имеет допустимых решений.

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

---

12. Вырожденное решение. Двойственные задачи линейного программирования.

Ответ

Вырожденное решение

Вырожденное решение в линейном программировании возникает, когда в опорном базисном решении (т.е. в одной из вершин допустимой области) одна или несколько базисных переменных равны нулю.

Геометрическая интерпретация:

• В n-мерном пространстве допустимая область — это многогранник. Каждая вершина многогранника определяется пересечением n граничных плоскостей (для n переменных).

• Вырождение происходит, когда более n граничных плоскостей пересекаются в одной точке, или, что то же самое, когда одна вершина многогранника лежит на более чем n гиперплоскостях, соответствующих ограничениям.

• Например, в двухмерном случае (2 переменные) вершина обычно образуется пересечением двух линий-ограничений. Если в одной точке пересекаются три или более линий-ограничений, то это вырожденная вершина.

Последствия вырождения для симплекс-метода:

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

• Основная проблема вырождения — возможность зацикливания (cycling) симплекс-метода. Это означает, что алгоритм может перейти через последовательность вырожденных базисных решений без улучшения целевой функции и вернуться к ранее посещенному базису, попав в бесконечный цикл.

• На практике зацикливание встречается редко, но существуют специальные правила для предотвращения (например, правило Блэнда, правило наименьшего индекса).

---

Двойственные задачи линейного программирования

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

Построение двойственной задачи:

Пусть прямая задача (ПЗ) имеет вид:

Прямая задача (ПЗ):

maxZ=sum_j=1nc_jx_j

при ограничениях:

sum_j=1na_ijx_jleb_i, для i=1,dots,m

x_jge0, для j=1,dots,n

Тогда соответствующая двойственная задача (ДЗ) будет:

Двойственная задача (ДЗ):

minW=sum_i=1mb_iy_i

при ограничениях:

sum_i=1ma_ijy_igec_j, для j=1,dots,n

y_ige0, для i=1,dots,m

Ключевые соотношения между прямой и двойственной задачами:

1. Симметрия: Если построить двойственную задачу для двойственной задачи, то получится исходная прямая задача.

2. Коэффициенты и правые части:

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

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

3. Матрица коэффициентов: Матрица коэффициентов A=(a_ij) прямой задачи транспонируется для двойственной задачи (AT).

4. Количество переменных и ограничений: Количество переменных двойственной задачи равно количеству ограничений прямой задачи, и наоборот.

5. Тип оптимизации: Если прямая задача на максимизацию, то двойственная на минимизацию, и наоборот.

6. Тип неравенств:

   • Ограничение “меньше или равно” (le) в прямой задаче соответствует неотрицательной переменной (y_ige0) в двойственной.

   • Ограничение “больше или равно” (ge) в прямой задаче соответствует неположительной переменной (y_ile0) в двойственной.

   • Ограничение-равенство (=) в прямой задаче соответствует свободной переменной (y_i без ограничений на знак) в двойственной.

   • Неотрицательная переменная (x_jge0) в прямой задаче соответствует ограничению “больше или равно” (ge) в двойственной.

   • Свободная переменная (x_j без ограничений на знак) в прямой задаче соответствует ограничению-равенству (=) в двойственной.

Основные теоремы двойственности:

7. Теорема слабой двойственности: Если x — допустимое решение прямой задачи, а y — допустимое решение двойственной задачи, то Z(x)leW(y) (т.е. значение целевой функции прямой задачи всегда меньше или равно значению целевой функции двойственной задачи).

8. Основная теорема двойственности (сильная двойственность): Если одна из задач (прямая или двойственная) имеет оптимальное решение, то и другая задача имеет оптимальное решение, и оптимальные значения их целевых функций равны ($Z^{\text{*}}=W^{\text{*}}$).

9. Теорема о дополняющей нежесткости (Complementary Slackness): Позволяет проверять оптимальность решения и связывает оптимальные решения прямой и двойственной задач.

Экономическая интерпретация двойственных переменных (y_i):

Двойственные переменные часто интерпретируются как теневые цены (shadow prices) или предельные оценки ресурсов. Значение y_i показывает, насколько изменится оптимальное значение целевой функции прямой задачи, если правая часть i-го ограничения (доступность i-го ресурса) увеличится на единицу. Это позволяет оценить ценность дополнительных единиц ресурсов.

---

13. Построение математической модели задачи линейного программирования.

Ответ

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

Основные шаги построения модели ЛП:

1. Понимание и анализ проблемы:

   • Тщательно изучите условия задачи, идентифицируйте, что нужно оптимизировать (максимизировать или минимизировать).

   • Определите доступные ресурсы, ограничения и взаимосвязи между различными элементами системы.

   • Пример: Компания производит два продукта (A и B) из трех видов сырья (1, 2, 3). Известны запасы сырья, расход сырья на единицу каждого продукта, прибыль от единицы каждого продукта. Цель: максимизировать общую прибыль.

2. Определение переменных решения (Decision Variables):

   • Идентифицируйте управляемые параметры, значения которых необходимо определить для решения задачи. Эти переменные должны быть количественными и представлять собой то, что мы можем контролировать.

   • Пример:

     • Пусть x_1 — количество единиц продукта A, которое будет произведено.

     • Пусть x_2 — количество единиц продукта B, которое будет произведено.

3. Формулирование целевой функции (Objective Function):

   • Выразите цель оптимизации (максимизация или минимизация) в виде линейной функции от переменных решения.

   • Коэффициенты при переменных в целевой функции должны отражать вклад каждой переменной в общую цель (например, прибыль от единицы продукта, стоимость использования единицы ресурса).

   • Пример: Если прибыль от продукта A составляет 3 у.е./ед., а от продукта B — 5 у.е./ед., то целевая функция для максимизации прибыли:

     Максимизировать Z=3x1​+5x2​

4. Формулирование ограничений (Constraints):

   • Выразите все ограничения, наложенные на систему, в виде линейных равенств или неравенств с переменными решения.

   • Каждое ограничение должно отражать лимит на ресурс, требование к производству, спросу и т.д.

   • Пример:

     • Пусть для производства 1 ед. A требуется 2 кг сырья 1, для 1 ед. B — 1 кг сырья 1. Запас сырья 1 — 10 кг.

       • 2x_1+x_2le10 (Ограничение по сырью 1)

     • Пусть для производства 1 ед. A требуется 1 кг сырья 2, для 1 ед. B — 2 кг сырья 2. Запас сырья 2 — 12 кг.

       • x_1+2x_2le12 (Ограничение по сырью 2)

     • Пусть для производства 1 ед. A требуется 1 кг сырья 3, для 1 ед. B — 1 кг сырья 3. Запас сырья 3 — 7 кг.

       • x_1+x_2le7 (Ограничение по сырью 3)

5. Задание ограничений неотрицательности (Non-negativity Constraints):

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

     x1​≥0,x2​≥0

Полная математическая модель задачи (на примере):

$\begin{array}{rlrl}& \text{Максимизировать }Z=3x\_1+5x\_2& \text{При ограничениях: }& 2x\_1+x\_2\le 10\&x\_1+2x\_2\le 12\&x\_1+x\_2\le 7\&x\_1,x\_2\ge 0\end{array}$

Важные замечания при построении:

• Линейность: Все функции (целевая и ограничения) должны быть линейными. Это означает, что переменные не могут быть возведены в степень, умножены друг на друга, находиться под корнем и т.д.

• Согласованность единиц измерения: Все величины в одном ограничении или целевой функции должны быть приведены к одной единице измерения.

• Точность данных: Качество решения напрямую зависит от точности входных данных (коэффициентов, правых частей).

• Полнота: Модель должна включать все существенные ограничения и факторы, влияющие на проблему.

---

14. Транспортная задача. Общие понятия и определения.

Ответ

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

Общие понятия и определения:

1. Поставщики (пункты отправления, источники):

   • Пункты, имеющие в наличии определенное количество продукта (запас) для отправки.

   • Обычно обозначаются A_1,A_2,dots,A_m.

   • Запас (a_i): Количество продукта, доступное у i-го поставщика.

2. Потребители (пункты назначения, стоки):

   • Пункты, испытывающие потребность в определенном количестве продукта (спрос).

   • Обычно обозначаются B_1,B_2,dots,B_n.

   • Спрос (b_j): Количество продукта, требуемое j-му потребителю.

3. Переменные решения (x_ij):

   • Количество продукта, которое перевозится от i-го поставщика к j-му потребителю.

   • Это основные неизвестные, которые необходимо определить.

   • Ограничения неотрицательности: x_ijge0.

4. Тарифы (стоимости перевозок, c_ij):

   • Стоимость перевозки единицы продукта от i-го поставщика к j-му потребителю.

   • Эти значения обычно задаются в виде матрицы тарифов.

5. Целевая функция:

   • Общая стоимость всех перевозок, которую необходимо минимизировать.

   • Формируется как сумма произведений объемов перевозок на соответствующие тарифы:

     Минимизировать Z=i=1∑m​j=1∑n​cij​xij​

6. Ограничения по запасам (предложению):

   • Суммарное количество продукта, отправляемого от каждого поставщика, не должно превышать его запас.

   • sum_j=1nx_ijlea_i, для каждого i=1,dots,m

7. Ограничения по спросу (потреблению):

   • Суммарное количество продукта, получаемого каждым потребителем, должно быть равно его спросу (в классической постановке).

   • sum_i=1mx_ij=b_j, для каждого j=1,dots,n

   • (Иногда может быть geb_j, если допустимо избыточное снабжение)

8. Типы транспортных задач:

   • Закрытая (сбалансированная) транспортная задача: Общий запас продукта у всех поставщиков равен общему спросу у всех потребителей: sum_i=1ma_i=sum_j=1nb_j. В этом случае все ограничения по запасам и спросу могут быть представлены как равенства.

   • Открытая (несбалансированная) транспортная задача: Суммарный запас не равен суммарному спросу. Для приведения к закрытой форме вводятся фиктивный поставщик (если спрос > запас) или фиктивный потребитель (если запас > спрос) с нулевыми тарифами и соответствующим недостающим/избыточным объемом.

9. Опорный план (начальное базисное решение):

   • Любой допустимый план перевозок, удовлетворяющий всем ограничениям. Не обязательно оптимальный.

   • Методы построения: Метод северо-западного угла, Метод минимальной стоимости (наименьших тарифов), Метод Фогеля.

10. Оптимальный план:

    • Опорный план, при котором общая стоимость перевозок минимальна.

    • Методы нахождения: Метод потенциалов (метод распределения), метод модифицированного распределения (MODI).

Математическая модель транспортной задачи:

$\begin{array}{rlrlr}& \text{Минимизировать }Z=\sum \_{i=1}^m\sum \_{j=1}^{n}c\_ijx\_ij& \text{При ограничениях:}& \sum \_{j=1}^{n}x\_ij\le a\_i,i=1,\dots ,m(\text{Ограничения по запасам})& \sum \_{i=1}^{m}x\_ij=b\_j,j=1,\dots ,n(\text{Ограничения по спросу})\&x\_ij\ge 0,\text{для всех }i,j(\text{Ограничения неотрицательности})\end{array}$

Примечание: Для закрытой задачи все le в ограничениях по запасам заменяются на =.

---

15. Построение опорного и оптимального плана транспортных задач.

Ответ

Решение транспортной задачи состоит из двух основных этапов: построения начального опорного плана и последующего его улучшения до оптимального плана.

1. Построение опорного плана (начального базисного решения)

Опорный план — это любое допустимое распределение перевозок, которое удовлетворяет всем ограничениям по запасам и спросу. Существуют различные методы для его построения:

а) Метод северо-западного угла (North-West Corner Method):

• Идея: Начинать заполнение матрицы перевозок с верхнего левого угла (клетки x_11) и последовательно перемещаться по строкам или столбцам.

• Шаги:

  1. Рассмотреть клетку в левом верхнем углу (x_11). Присвоить ей значение, равное минимуму из запаса первого поставщика (a_1) и спроса первого потребителя (b_1).

  2. Если $a\_1\text{<}b\_1$, то запас первого поставщика исчерпан. Переходим к следующей строке (к поставщику A_2) в том же столбце. Уменьшаем спрос b_1 на a_1.

  3. Если a_1b_1, то спрос первого потребителя удовлетворен. Переходим к следующему столбцу (к потребителю B_2) в той же строке. Уменьшаем запас a_1 на b_1.

  4. Если a_1=b_1, то и запас, и спрос удовлетворены. Переходим к следующей строке и следующему столбцу.

  5. Повторять шаги 1-4, пока все запасы не будут распределены и весь спрос не будет удовлетворен.

• Преимущества: Прост в реализации.

• Недостатки: Не учитывает тарифы, поэтому полученный план часто далек от оптимального.

б) Метод минимальной стоимости (наименьших тарифов, Least Cost Method):

• Идея: Приоритет отдается заполнению клеток с наименьшими тарифами.

• Шаги:

  1. Найти в матрице тарифов c_ij клетку с минимальной стоимостью.

  2. Присвоить этой клетке x_ij значение, равное минимуму из соответствующего запаса a_i и спроса b_j.

  3. Вычесть это значение из a_i и b_j.

  4. Если запас a_i исчерпан, вычеркнуть i-ю строку. Если спрос b_j удовлетворен, вычеркнуть j-й столбец.

  5. Повторять шаги 1-4 для оставшейся части матрицы до полного распределения запасов и удовлетворения спроса.

• Преимущества: Обычно дает опорный план ближе к оптимальному, чем метод северо-западного угла.

• Недостатки: Может быть сложнее в реализации для больших задач.

в) Метод аппроксимации Фогеля (Vogel’s Approximation Method - VAM):

• Идея: Минимизировать потенциальные “штрафы” за неиспользование самых дешевых маршрутов.

• Шаги:

  1. Для каждой строки и каждого столбца вычислить “штраф” — разность между двумя наименьшими тарифами в этой строке/столбце.

  2. Выбрать строку или столбец с наибольшим “штрафом”.

  3. В выбранной строке/столбце найти клетку с минимальным тарифом и заполнить ее максимально возможным объемом (минимум из a_i и b_j).

  4. Уменьшить a_i и b_j и вычеркнуть полностью использованную строку или столбец.

  5. Повторять шаги 1-4, пока все не будет распределено.

• Преимущества: Обычно дает опорный план, который очень близок к оптимальному, а иногда и является оптимальным.

• Недостатки: Самый трудоемкий из трех методов.

2. Построение оптимального плана (метод потенциалов / MODI)

После нахождения опорного плана его необходимо проверить на оптимальность. Если план не оптимален, его нужно улучшить. Самый распространенный метод для этого — метод потенциалов (метод распределения), часто называемый MODI (Modified Distribution Method).

Идея метода: Определить “выгодность” использования незадействованных (свободных) маршрутов. Если такой маршрут существует, то его включение в план позволит уменьшить общие затраты.

Шаги метода потенциалов (MODI):

1. Проверка на вырожденность: Количество занятых клеток (с x_ij0) должно быть равно m+n−1, где m — число поставщиков, n — число потребителей. Если занятых клеток меньше, то план вырожден, и необходимо ввести m+n−1−k фиктивных (нулевых) перевозок в свободные клетки (для которых x_ij=0) так, чтобы не образовывался замкнутый цикл.

2. Вычисление потенциалов (u_i и v_j):

   • Для каждой занятой клетки (i,j) должно выполняться условие: u_i+v_j=c_ij.

   • Присвоить одному из потенциалов (например, u_1) произвольное значение, обычно 0.

   • Используя равенства u_i+v_j=c_ij для всех занятых клеток, последовательно вычислить остальные потенциалы u_i и v_j.

3. Вычисление оценок для свободных клеток (Delta_ij):

   • Для каждой свободной (незанятой) клетки (i,j) вычислить ее оценку (или косвенный тариф): Delta_ij=u_i+v_j−c_ij.

   • Эта оценка показывает, на сколько изменится целевая функция при включении единичной перевозки по данному маршруту.

4. Проверка на оптимальность:

   • Если все Delta_ijle0 (для задачи минимизации), то текущий опорный план является оптимальным.

   • Если есть хотя бы одна Delta_ij0, то план неоптимален и может быть улучшен.

5. Построение улучшенного плана (итерация):

   • Выбрать свободную клетку с наибольшим положительным Delta_ij (это будет вводимая переменная).

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

   • Поочередно присвоить вершинам цикла знаки + и -, начиная со знака + для вводимой клетки.

   • Выбрать минимальное значение из объемов перевозок в клетках цикла со знаком -. Это значение (theta) будет перемещаться по циклу.

   • Прибавить theta к объемам в клетках со знаком + и вычесть theta из объемов в клетках со знаком -. Одна из клеток со знаком - станет нулевой и выйдет из базиса.

6. Повторение: Возврат к шагу 2 с новым опорным планом до тех пор, пока не будет достигнут оптимальный план.

---

16. Целочисленное программирование.

Ответ

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

Почему целочисленное программирование?

Во многих реальных задачах переменные по своей природе должны быть целыми. Например:

• Количество произведенных автомобилей, станков.

• Число построенных заводов или складов.

• Количество рабочих, задействованных в проекте.

• Решение “да” или “нет” (бинарные переменные 0 или 1).

Округление решения, полученного с помощью линейного программирования (где переменные непрерывны), не всегда приводит к допустимому или оптимальному целочисленному решению. Более того, округление может сделать решение неоптимальным или даже невыполнимым.

Виды целочисленного программирования:

1. Чисто целочисленное программирование (Pure Integer Programming - PIP): Все переменные решения должны быть целыми числами.

   • Пример: Задача о рюкзаке (выбор предметов для максимизации ценности, если каждый предмет либо берется целиком, либо не берется вовсе).

2. Смешанное целочисленное программирование (Mixed Integer Programming - MIP): Некоторые переменные должны быть целыми, а другие могут быть непрерывными (действительными числами).

   • Пример: Задача планирования производства, где количество произведенных единиц должно быть целым, а количество используемого сырья может быть дробным.

3. Булево (бинарное) программирование (Binary Integer Programming - BIP): Все переменные решения могут принимать только два значения: 0 или 1. Используется для моделирования решений типа “да/нет” или “выбрать/не выбрать”.

   • Пример: Задача выбора инвестиционных проектов, где каждый проект либо принимается, либо отклоняется.

Сложность решения задач ЦП:

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

Основные методы решения задач ЦП:

4. Метод отсечений (Cutting Plane Method, метод Гомори):

   • Начинается с решения “релаксированной” задачи ЛП (той же задачи, но без требования целочисленности).

   • Если полученное оптимальное решение нецелочисленное, добавляется новое линейное ограничение (отсекающая плоскость, или отсечение Гомори), которое “отсекает” текущее нецелочисленное решение, но не отсекает ни одно из допустимых целочисленных решений.

   • Процесс повторяется, пока не будет найдено целочисленное оптимальное решение.

5. Метод ветвей и границ (Branch and Bound Method):

   • Наиболее распространенный и универсальный метод.

   • “Ветвление”: Исходная задача разбивается на несколько подзадач путем добавления новых ограничений на нецелочисленные переменные. Например, если x_1=3.7, то создаются две подзадачи: одна с x_1le3 и другая с x_1ge4.

   • “Границы”: Для каждой подзадачи решается релаксированная ЛП-задача, и ее оптимальное значение используется как граница (верхняя для максимизации, нижняя для минимизации) для целочисленного решения в этой ветви.

   • Процесс продолжается до тех пор, пока не будет найдено целочисленное решение, которое лучше или равно лучшей границе среди всех неисследованных подзадач.

6. Эвристические методы:

   • Используются для нахождения “хороших”, но не обязательно оптимальных решений, особенно для очень больших и сложных задач.

   • Примеры: генетические алгоритмы, имитация отжига, таба-поиск.

Применение:

Целочисленное программирование находит широкое применение в логистике (задачи маршрутизации, планирования перевозок), производстве (планирование производства, размещение оборудования), финансах (оптимизация портфеля), телекоммуникациях, управлении проектами и многих других областях, где требуется принятие дискретных решений.

---

17. Математическая модель задач целочисленного программирования.

Ответ

Математическая модель задачи целочисленного программирования (ЦП) очень похожа на модель линейного программирования, но с одним ключевым отличием: требованием, чтобы некоторые или все переменные решения принимали только целочисленные значения.

Общий вид математической модели задачи целочисленного программирования:

$\begin{array}{rlrl}& \text{Оптимизировать }Z=\sum \_{j=1}^{n}c\_jx\_j& \text{При ограничениях: }& \sum \_{j=1}^{n}a\_ijx\_j(\le ,=,\ge )b\_i,\text{для }i=1,\dots ,m\&x\_j\ge 0,\text{для }j=1,\dots ,n\&x\_j\text{ - целые числа для некоторого подмножества (или всех) }j\in 1,\dots ,n\end{array}$

Где:

• Z — целевая функция, которую нужно максимизировать или минимизировать.

• x_j — переменные решения (неизвестные, которые нужно найти).

• c_j — коэффициенты целевой функции (например, прибыль или стоимость на единицу x_j).

• a_ij — коэффициенты при переменных в ограничениях (например, количество ресурса i, необходимое для производства единицы j).

• b_i — правые части ограничений (например, доступное количество ресурса i, или требование к объему).

• textОграничения(le,=,ge) — линейные равенства или неравенства, представляющие собой ограничения ресурсов, производственных мощностей, спроса и т.д.

• Ключевое требование: x_j - целые числа.

Виды целочисленного программирования по типу переменных:

1. Чисто целочисленное программирование (PIP):

   Все x_j должны быть целыми числами.

   • Пример: Задача о рюкзаке

     • Дано: n предметов, каждый со стоимостью v_j и весом w_j. Рюкзак имеет максимальную вместимость W.

     • Цель: Выбрать подмножество предметов для максимизации общей стоимости, не превышая вместимости рюкзака.

     • Модель:

       Максимизировать Z=j=1∑n​vj​xj​При ограничении: j=1∑n​wj​xj​≤Wxj​∈{0,1}, для j=1,…,n(Бинарные переменные)

       Примечание: Это также пример бинарного программирования.

2. Смешанное целочисленное программирование (MIP):

   Некоторые x_j — целые числа, другие — непрерывные (действительные).

   • Пример: Задача о размещении производственных мощностей

     • Компания планирует открыть несколько новых заводов. Известны потенциальные места, фиксированные затраты на открытие завода в каждом месте, переменные затраты на производство и доставку, а также спрос потребителей.

     • Переменные:

       • y_iin0,1: бинарная переменная, 1, если завод открыт в месте i, 0 в противном случае.

       • x_ijge0: количество продукции, отправленной с завода i потребителю j (непрерывная переменная).

     • Целевая функция (минимизация общих затрат):

       Минимизировать Z=i=1∑m​Fi​yi​+i=1∑m​j=1∑n​Cij​xij​

       (где F_i — фиксированные затраты на открытие завода i, C_ij — переменные затраты на доставку от завода i потребителю j).

     • Ограничения:

       • Удовлетворение спроса: sum_i=1mx_ij=D_j,quadtextдлякаждогоj (где D_j — спрос потребителя j).

       • Мощность завода: sum_j=1nx_ijleM_iy_i,quadtextдлякаждогоi (где M_i — максимальная мощность завода i. Если y_i=0, то завод не работает, и x_ij=0).

       • Неотрицательность: x_ijge0.

       • Целочисленность: y_iin0,1.

3. Булево (бинарное) программирование (BIP):

   Все x_jin0,1. Является частным случаем чисто целочисленного программирования.

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

---

18. Постановка задач нелинейного программирования.

Ответ

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

Постановка задачи нелинейного программирования:

Общая форма задачи нелинейного программирования выглядит следующим образом:

$\begin{array}{rlr}& \text{Оптимизировать }f(x)& \text{При ограничениях: }\&g\_i(x)\le 0,\text{для }i=1,\dots ,m\&h\_j(x)=0,\text{для }j=1,\dots ,p\&x\in X\end{array}$

Где:

• x=(x_1,x_2,dots,x_n) — вектор переменных решения.

• f(x) — целевая функция. Она может быть как линейной, так и нелинейной.

• g_i(x) — функции, определяющие ограничения-неравенства. Они могут быть линейными или нелинейными.

• h_j(x) — функции, определяющие ограничения-равенства. Они также могут быть линейными или нелинейными.

• X — множество допустимых значений переменных (например, x_kge0 или ограничения на диапазон значений). Это могут быть и нелинейные ограничения на переменные (например, x_12+x_22leR2).

Ключевые отличия от линейного программирования:

1. Нелинейность:

   • Если f(x) или любая из функций g_i(x) или h_j(x) содержит нелинейные выражения (например, x2, x_1x_2, sqrtx, sin(x), ex, логарифмы), то задача относится к нелинейному программированию.

   • Примеры нелинейных выражений: x_12+x_22, x_1cdotx_2, x3, 1/x.

2. Невыпуклость допустимой области:

   • В линейном программировании допустимая область всегда является выпуклым многогранником.

   • В нелинейном программировании, если ограничения нелинейны, допустимая область может быть невыпуклой (например, иметь “дыры” или быть несвязной).

3. Множество локальных оптимумов:

   • Для задач ЛП, если оптимальное решение существует, оно всегда глобально.

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

4. Сложность решения:

   • Для НЛП не существует универсального алгоритма, аналогичного симплекс-методу для ЛП. Методы решения зависят от свойств функций (выпуклость, дифференцируемость).

   • Методы обычно итерационные и основаны на градиентных подходах, методах второго порядка и т.д.

Примеры нелинейных задач в реальной жизни:

• Оптимизация портфеля (финансы): Минимизация риска при заданном уровне доходности, где риск часто измеряется дисперсией (квадратичная функция).

• Проектирование инженерных систем: Минимизация веса конструкции при ограничениях на прочность, где соотношения между переменными часто нелинейны.

• Задача размещения производства: Минимизация затрат, где транспортные расходы могут зависеть от квадрата расстояния.

• Экономические модели: Оптимизация производственных функций, где зависимости нелинейны (например, функция Кобба-Дугласа).

• Машинное обучение: Обучение нейронных сетей, где целевая функция (функция потерь) нелинейна.

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

---

19. Классификация задач нелинейного программирования.

Ответ

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

1. По характеру целевой функции и ограничений (выпуклость/невыпуклость):

   • Выпуклое программирование:

     • Задача: Минимизация выпуклой функции над выпуклым множеством (т.е. ограничения определяют выпуклую допустимую область).

     • Если задача на максимизацию, то целевая функция должна быть вогнутой.

     • Важность: Любой локальный оптимум в выпуклой задаче является также и глобальным оптимумом. Это значительно упрощает поиск решения.

     • Пример: Квадратичное программирование с положительно определенной матрицей для целевой функции.

   • Невыпуклое программирование:

     • Целевая функция невыпуклая (или невогнутая для максимизации) или допустимая область невыпуклая.

     • Сложность: Могут существовать множественные локальные оптимумы. Поиск глобального оптимума является вычислительно очень сложной задачей (NP-трудной).

     • Пример: Минимизация функции sin(x) или задача размещения объектов с фиксированными затратами.

2. По типу функций (квадратичные, дробно-линейные, сглаживаемые и т.д.):

   • Квадратичное программирование (QP):

     • Целевая функция — квадратичная, а все ограничения — линейные.

     • Пример: f(x)=xTQx+cTx, где Q — симметричная матрица.

     • Используется, например, в оптимизации портфеля Марковица.

   • Дробно-линейное программирование:

     • Целевая функция представляет собой отношение двух линейных функций, а ограничения — линейные.

     • Может быть сведено к задаче линейного программирования.

   • Геометрическое программирование:

     • Целевая функция и ограничения состоят из сумм степенных функций.

     • Может быть преобразовано в выпуклую задачу.

   • Сепарабельное программирование:

     • Целевая функция и ограничения могут быть представлены как суммы функций одной переменной.

     • Позволяет использовать специальные методы, например, кусочно-линейную аппроксимацию.

3. По характеру переменных (непрерывные, целочисленные):

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

   • Нелинейное целочисленное программирование (NIP): Некоторые или все переменные должны быть целыми. Это самые сложные задачи, сочетающие трудности ЦП и НЛП. Часто решаются методом ветвей и границ, где в каждом узле решается непрерывная НЛП-подзадача.

   • Нелинейное булево программирование: Переменные могут принимать только 0 или 1.

4. По наличию ограничений:

   • Безусловная оптимизация: Отсутствуют какие-либо ограничения на переменные, кроме, возможно, их области определения. Методы: градиентный спуск, метод Ньютона.

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

5. По степени дифференцируемости функций:

   • Гладко (дифференцируемо) НЛП: Функции являются непрерывно дифференцируемыми. Это позволяет использовать методы, основанные на градиентах и гессианах.

   • Негладкое НЛП: Функции не являются дифференцируемыми везде (например, содержат функции типа ∣x∣ или max(x_1,x_2)). Требуются специализированные методы (например, субградиентные методы).

Эта классификация помогает исследователям и практикам выбирать наиболее подходящие алгоритмы и программные средства для решения конкретной задачи НЛП.

---

20. Математическая модель задач нелинейного программирования.

Ответ

Математическая модель задачи нелинейного программирования (НЛП) обобщает модель линейного программирования, допуская нелинейные зависимости в целевой функции и/или ограничениях.

Общий вид математической модели задачи нелинейного программирования:

1. Целевая функция (Objective Function):

Оптимизировать f(x1​,x2​,…,xn​)

• f(x_1,x_2,dots,x_n) — это нелинейная (или линейная) функция, которую необходимо максимизировать или минимизировать.

• Примеры нелинейных целевых функций:

  • f(x_1,x_2)=x_12+x_22 (например, минимизация расстояния до начала координат)

  • f(x_1,x_2)=x_1cdotx_2 (например, максимизация площади прямоугольника при заданном периметре)

  • f(x_1,x_2)=sin(x_1)+cos(x_2)

  • f(x_1,x_2,x_3)=(x_1−5)2+(x_2−3)2+(x_3−8)2

2. Ограничения (Constraints):

а) Ограничения-неравенства:

gi​(x1​,x2​,…,xn​)≤0,для i=1,…,m

• g_i(x_1,x_2,dots,x_n) — это нелинейные (или линейные) функции, определяющие ограничения типа “меньше или равно”.

• Могут также быть ограничения типа ge0.

• Примеры нелинейных ограничений-неравенств:

  • x_12+x_22leR2 (ограничение на область внутри круга)

  • x_1cdotx_2geK (ограничение на произведение)

  • ex_1+ln(x_2)leC

б) Ограничения-равенства:

hj​(x1​,x2​,…,xn​)=0,для j=1,…,p

• h_j(x_1,x_2,dots,x_n) — это нелинейные (или линейные) функции, определяющие ограничения-равенства.

• Примеры нелинейных ограничений-равенств:

  • x_12+x_22+x_32=1 (ограничение на поверхности сферы)

  • x_1cdotx_2−x_3=0

3. Ограничения на знак переменных (обычно неотрицательность):

xk​≥0,для некоторого подмножества (или всех) k

• Хотя эти ограничения чаще всего линейны, они являются важной частью модели.

• В некоторых задачах переменные могут быть свободными по знаку.

Пример полной математической модели НЛП (Задача о производстве с нелинейными затратами/доходом):

Предприятие производит продукт, доход от которого зависит от объема производства нелинейно (например, из-за скидок при больших объемах или, наоборот, из-за перенасыщения рынка). Затраты на ресурсы также могут быть нелинейными.

Пусть x — объем производства продукта.

• Целевая функция (максимизация прибыли):

  Пусть доход R(x)=100x−2x2 (квадратичная зависимость, доход уменьшается при очень больших объемах), а затраты C(x)=10x+0.5x2 (квадратичные затраты из-за удорожания ресурсов).

  Максимизировать Z=R(x)−C(x)=(100x−2x2)−(10x+0.5x2)=90x−2.5x2

• Ограничения:

  • Ограничение на максимальную мощность производства: xle20.

  • Ограничение на качество (например, нелинейная зависимость качества от объема): x2−10x+25ge0.

  • Неотрицательность объема: xge0.

Полная модель:

$\begin{array}{rlr}& \text{Максимизировать }Z=90x-2.5x^2& \text{При ограничениях:}\&x\le 20\&x^2-10x+25\ge 0\&x\ge 0\end{array}$

Построение математической модели НЛП требует тщательного анализа зависимостей в реальной системе. Нелинейности могут быть вызваны эффектами масштаба, нелинейным спросом/предложением, физическими законами, геометрическими зависимостями и т.д.

---

21. Сетевые модели.

Ответ

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

Основные понятия сетевых моделей (теории графов):

1. Граф (Graph): Упорядоченная пара G=(V,E), где V — множество вершин (узлов), а E — множество рёбер (связей) между этими вершинами.

2. Вершина (Node/Vertex): Элемент системы, который может быть пунктом (например, город, склад, станция, человек, задача в проекте).

3. Ребро (Edge/Arc): Связь между двумя вершинами. Может быть:

   • Ориентированным (Directed Arc/Digraph): Если связь имеет направление (например, дорога с односторонним движением, поток данных). Такие рёбра называются дугами.

   • Неориентированным (Undirected Edge): Если связь не имеет направления (например, двухсторонняя дорога, связь между друзьями в социальной сети).

4. Взвешенный граф (Weighted Graph): Граф, где каждому ребру (или вершине) присвоено числовое значение (вес, длина, стоимость, пропускная способность, время).

5. Путь (Path): Последовательность вершин и рёбер, соединяющая две вершины.

6. Цикл (Cycle): Путь, который начинается и заканчивается в одной и той же вершине.

7. Сеть (Network): Обычно используется как синоним взвешенного графа, особенно ориентированного, где рёбра имеют определённые характеристики (например, пропускную способность, стоимость).

8. Исток (Source): Вершина, из которой выходит только поток.

9. Сток (Sink): Вершина, в которую входит только поток.

Типичные задачи, решаемые с помощью сетевых моделей:

• Задача о кратчайшем пути: Найти путь между двумя вершинами с минимальной суммой весов рёбер (например, кратчайший путь в дорожной сети, самый дешевый маршрут). Алгоритмы: Дейкстры, Беллмана-Форда, Флойд-Уоршелла.

• Задача о максимальном потоке: Определить максимально возможный объем потока, который можно передать от истока к стоку через сеть с ограниченными пропускными способностями рёбер (например, пропускная способность трубопровода, интернет-трафика). Алгоритм: Форда-Фалкерсона.

• Задача о минимальном остовном дереве: Найти подмножество рёбер, которое соединяет все вершины графа, не образуя циклов, и имеет минимальную общую стоимость (например, прокладка кабельной сети с минимальными затратами). Алгоритмы: Прима, Крускала.

• Задача транспортная: Распределение грузов от поставщиков к потребителям с минимизацией затрат, может быть представлена как задача о потоках.

• Задача о назначениях: Распределение задач между исполнителями.

• Сетевое планирование и управление (CPM/PERT): Определение критического пути в проекте, анализ сроков выполнения задач.

• Задача коммивояжера (Traveling Salesperson Problem - TSP): Найти кратчайший замкнутый маршрут, посещающий все вершины ровно по одному разу. Это NP-трудная задача.

Преимущества сетевых моделей:

• Наглядность: Графическое представление позволяет легко визуализировать структуру системы и взаимосвязи.

• Универсальность: Могут применяться для широкого круга задач в различных областях (логистика, производство, управление проектами, телекоммуникации, социология).

• Эффективные алгоритмы: Для многих стандартных сетевых задач существуют хорошо разработанные и эффективные алгоритмы.

Сетевые модели являются мощным инструментом для анализа и оптимизации сложных систем.

---

22. Задачи сетевого планирования.

Ответ

Задачи сетевого планирования — это особый класс сетевых моделей, применяемых для управления проектами, которые состоят из множества взаимосвязанных работ (действий) с определенной последовательностью выполнения. Цель сетевого планирования — эффективное управление временем, ресурсами и стоимостью проекта, а также выявление потенциальных проблем и узких мест.

Основные понятия сетевого планирования:

1. Работа (Activity/Task): Отдельное действие или операция в проекте, которая требует времени и/или ресурсов для выполнения. Обычно представляется дугой (стрелкой) в сетевом графике.

2. Событие (Event/Node): Момент завершения одной или нескольких работ и/или начала одной или нескольких работ. События не требуют времени или ресурсов. Представляются вершинами (кружками) в сетевом графике.

3. Сетевой график (Network Diagram): Графическое представление проекта, показывающее последовательность и взаимосвязь работ и событий. Может быть построен как “вершины-работы” (Activity-on-Node, AON) или “стрелки-работы” (Activity-on-Arrow, AOA).

4. Длительность работы (Duration): Время, необходимое для выполнения работы. Может быть детерминированным или стохастическим.

5. Путь (Path): Последовательность работ от начального до конечного события.

6. Критический путь (Critical Path): Самый длинный путь в сетевом графике. Его длительность определяет минимальное время выполнения всего проекта. Задержка любой работы на критическом пути приведет к задержке всего проекта.

7. Резерв времени (Slack/Float): Максимально допустимая задержка выполнения работы без влияния на сроки проекта или последующие работы.

   • Полный резерв: Время, на которое можно задержать работу без задержки всего проекта.

   • Свободный резерв: Время, на которое можно задержать работу без задержки начала последующих работ.

Основные методы сетевого планирования:

8. Метод критического пути (Critical Path Method - CPM):

   • Применение: Используется для проектов, где длительность работ известна и относительно определена.

   • Задача: Определить критический путь и рассчитать сроки выполнения проекта.

   • Этапы:

     1. Составить перечень работ, их длительности и взаимосвязи.

     2. Построить сетевой график.

     3. Рассчитать ранние сроки начала/окончания работ (Early Start - ES, Early Finish - EF) — максимально раннее время, когда работа может быть начата/завершена.

     4. Рассчитать поздние сроки начала/окончания работ (Late Start - LS, Late Finish - LF) — максимально позднее время, когда работа может быть начата/завершена без задержки проекта.

     5. Определить резервы времени для каждой работы.

     6. Идентифицировать критический путь (работы с нулевым резервом времени).

9. Метод оценки и пересмотра планов (Program Evaluation and Review Technique - PERT):

   • Применение: Используется для проектов с неопределенной длительностью работ (например, исследовательские, инновационные проекты). Длительность каждой работы оценивается тремя значениями:

     • Оптимистическая (to​)

     • Наиболее вероятная (tm​)

     • Пессимистическая (tp​)

   • Задача: Оценить ожидаемую длительность проекта и вероятность его завершения к определенному сроку.

   • Этапы:

     1. Для каждой работы рассчитать ожидаемую длительность (te​) и дисперсию (σ2) (обычно, используя бета-распределение):

        te​=6to​+4tm​+tp​​

        σ2=(6tp​−to​​)2

     2. Далее процесс аналогичен CPM: построение сетевого графика, расчет ранних/поздних сроков, определение критического пути (на основе ожидаемых длительностей).

     3. Оценить вероятность завершения проекта в заданный срок, используя центральную предельную теорему (приближая распределение длительности критического пути нормальным распределением).

Преимущества сетевого планирования:

• Визуализация: Наглядное представление сложности проекта.

• Определение приоритетов: Выявление критических работ.

• Контроль: Позволяет отслеживать прогресс и выявлять отклонения.

• Управление рисками: Помогает оценить влияние неопределенности.

• Распределение ресурсов: Помогает эффективно использовать ресурсы.

Задачи сетевого планирования являются основой проектного менеджмента и широко применяются в строительстве, разработке ПО, производстве и других областях.

---

23. Общая постановка задач динамического программирования.

Ответ

Динамическое программирование (ДП) — это математический метод решения сложных многошаговых задач оптимизации, которые могут быть разбиты на последовательность более простых, перекрывающихся подзадач. Он был разработан Ричардом Беллманом в 1950-х годах. Основная идея ДП заключается в решении каждой подзадачи лишь один раз и сохранении её решения, чтобы избежать повторных вычислений.

Общая постановка задачи динамического программирования характеризуется следующими элементами:

1. Многошаговый процесс принятия решений (Multistage Decision Process):

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

   • На каждом шаге принимается решение, которое влияет на текущее состояние системы и на возможные решения на последующих шагах.

2. Состояние системы (State):

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

   • Переход из одного состояния в другое происходит в результате принятия решения.

   • Пример: В задаче о кратчайшем пути состояние может быть текущей вершиной; в задаче о рюкзаке — текущей вместимостью и количеством рассмотренных предметов.

3. Решение (Decision/Action):

   • На каждом шаге, находясь в определенном состоянии, принимается решение из множества допустимых решений.

   • Решение переводит систему из текущего состояния в новое состояние на следующем шаге.

4. Функция перехода состояний (State Transition Function):

   • Описывает, как текущее состояние и принятое решение определяют следующее состояние.

   • Если Sk​ — состояние на шаге k, а dk​ — решение на шаге k, то Sk+1​=T(Sk​,dk​).

5. Критерий оптимальности (Целевая функция, Objective Function):

   • Функция, которую нужно оптимизировать (минимизировать или максимизировать) на протяжении всего процесса. Она суммирует “выгоды” или “издержки” на каждом шаге.

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

   • Пример: Общие затраты, суммарная прибыль, общая вероятность.

6. Принцип оптимальности Беллмана (Bellman’s Principle of Optimality):

   • Это фундаментальный принцип ДП: “Оптимальная стратегия обладает тем свойством, что, каковы бы ни были начальное состояние и начальное решение, последующие решения должны составлять оптимальную стратегию по отношению к состоянию, полученному в результате первого решения.”

   • Формально это выражается через рекуррентное соотношение Беллмана:

     fk​(Sk​)=оптdk​​{r(Sk​,dk​)+fk+1​(T(Sk​,dk​))}

     Где:

     • fk​(Sk​) — оптимальное значение целевой функции, начиная с шага k из состояния Sk​.

     • r(Sk​,dk​) — непосредственный выигрыш/затраты от принятия решения dk​ в состоянии Sk​.

     • T(Sk​,dk​) — следующее состояние, полученное из Sk​ при решении dk​.

     • “опт” — означает max или min.

7. Граничные условия (Boundary Conditions):

   • Значения оптимальной функции для конечных состояний или на последнем шаге процесса. С них начинается обратный ход вычислений.

Метод решения (прямая или обратная прокрутка):

Динамическое программирование обычно решается путем построения решения от конца к началу (обратная прокрутка) или от начала к концу (прямая прокрутка), используя рекуррентные соотношения.

Преимущества ДП:

• Позволяет решать сложные задачи, которые не поддаются другим методам.

• Гарантирует нахождение глобального оптимума для определенных классов задач.

Недостатки ДП:

• “Проклятие размерности” (Curse of Dimensionality): Число состояний может расти экспоненциально с увеличением размерности задачи, что делает ДП неприменимым для очень больших задач.

• Требует четкого определения состояний и рекуррентных соотношений.

---

24. Алгоритм решения задач динамического программирования.

Ответ

Алгоритм решения задач динамического программирования основан на принципе оптимальности Беллмана и подразумевает итеративный процесс вычисления оптимальных решений для подзадач, постепенно продвигаясь к решению всей задачи. Существует два основных подхода: прямая прокрутка (forward pass) и обратная прокрутка (backward pass). В большинстве случаев применяется обратная прокрутка.

Общий алгоритм решения с использованием обратной прокрутки:

1. Определение этапов (шагов) процесса:

   • Разбить многошаговый процесс на конечное число этапов. Эти этапы могут быть временными интервалами, порядком выполнения операций и т.д.

   • Обозначим этапы k=1,2,…,N, где N — последний этап.

2. Определение состояний на каждом этапе:

   • Для каждого этапа k определить множество возможных состояний Sk​. Состояние должно полностью описывать ситуацию на этом этапе, чтобы решения на предыдущих этапах не влияли на выбор текущего решения, кроме как через текущее состояние.

3. Определение допустимых решений (действий) в каждом состоянии на каждом этапе:

   • Для каждого состояния Sk​ определить набор допустимых решений dk​.

4. Формулирование функции перехода состояний:

   • Определить, как текущее состояние Sk​ и принятое решение dk​ влияют на следующее состояние Sk+1​.

   • Sk+1​=T(Sk​,dk​).

5. Определение критерия оптимальности (целевой функции):

   • Сформулировать функцию, которую необходимо оптимизировать (минимизировать или максимизировать), и определить непосредственный выигрыш/затраты r(Sk​,dk​) от принятия решения dk​ в состоянии Sk​.

6. Установление граничных условий (для последнего этапа):

   • Определить значение оптимальной функции для состояний на последнем этапе N. Это начальные условия для обратной прокрутки.

   • Например, fN​(SN​)=значение, связанное с конечным состоянием SN​.

7. Применение рекуррентного соотношения Беллмана (обратная прокрутка):

   • Начиная с этапа N−1 и двигаясь к этапу 1, для каждого состояния Sk​ на каждом этапе k, вычисляется оптимальное значение fk​(Sk​) и соответствующее оптимальное решение dk∗​.

   • Рекуррентное соотношение:

     fk​(Sk​)=оптdk​∈D(Sk​)​{r(Sk​,dk​)+fk+1​(T(Sk​,dk​))}

     Где D(Sk​) — множество допустимых решений из состояния Sk​.

   • В процессе вычислений сохраняются не только значения fk​(Sk​), но и оптимальные решения dk∗​ для каждого состояния и каждого этапа. Это позволяет затем восстановить оптимальный путь.

8. Определение оптимальной стратегии (прямая прокрутка для восстановления решения):

   • После того как f1​(S1​) (оптимальное значение для начального состояния на первом этапе) будет вычислено, можно восстановить оптимальную последовательность решений.

   • Начиная с начального состояния S1​, используйте сохраненные оптимальные решения d1∗​(S1​) для перехода к S2​=T(S1​,d1∗​(S1​)). Затем используйте d2∗​(S2​) для перехода к S3​ и так далее до последнего этапа.

Пример: Задача о кратчайшем пути (нахождение пути с минимальной стоимостью):

• Этапы: N−1 переходов от источника к стоку.

• Состояния: Вершины графа.

• Решение: Выбор следующей вершины для перехода.

• r(Sk​,dk​): Стоимость ребра от текущей вершины Sk​ до выбранной следующей вершины dk​.

• Граничные условия: Стоимость достижения конечной вершины (стока) равна 0.

• Рекуррентное соотношение (минимизация):

  f(i)=minj∈N(i)​{cost(i,j)+f(j)}

  Где f(i) — минимальная стоимость от вершины i до стока, N(i) — соседи вершины i, cost(i,j) — стоимость перехода от i к j.

• Вычисления: Начинают с конечной вершины и идут “назад” к начальной, вычисляя минимальные стоимости.

---

25. Классификация задач динамического программирования. Принцип Белмана.

Ответ

Классификация задач динамического программирования

Задачи динамического программирования (ДП) могут быть классифицированы по нескольким признакам:

1. По типу процесса (детерминированные / стохастические):

   • Детерминированное динамическое программирование: Переход из одного состояния в другое полностью определяется принятым решением. Результат каждого действия предсказуем.

     • Примеры: Задача о кратчайшем пути, задача о рюкзаке, задача замены оборудования.

   • Стохастическое динамическое программирование: Переход из одного состояния в другое зависит не только от принятого решения, но и от случайных факторов. Результат действия известен лишь с некоторой вероятностью.

     • Примеры: Управление запасами при случайном спросе, задачи массового обслуживания. В этом случае рекуррентное соотношение Беллмана включает математическое ожидание.

2. По характеру изменения времени/этапов (дискретные / непрерывные):

   • Дискретное динамическое программирование: Процесс разбивается на дискретные шаги (этапы). Большинство задач ДП относятся к этому типу.

     • Примеры: Планирование производства по месяцам, выбор инвестиций из списка.

   • Непрерывное динамическое программирование (или задачи оптимального управления): Процесс изменяется непрерывно во времени. Часто формулируется с использованием дифференциальных уравнений и решается с помощью вариационного исчисления или принципа максимума Понтрягина.

     • Примеры: Оптимальное управление траекторией летательного аппарата, оптимальное регулирование экономических систем.

3. По длительности горизонта планирования (конечношаговые / бесконечношаговые):

   • Конечношаговые (finite-horizon) задачи: Количество этапов конечно и известно заранее.

     • Примеры: Большинство стандартных задач ДП, где есть четкое начало и конец.

   • Бесконечношаговые (infinite-horizon) задачи: Процесс продолжается бесконечно (или очень долго). Часто используются для моделирования систем, которые функционируют на протяжении неопределенно долгого времени.

     • Примеры: Непрерывное управление запасами, обслуживание оборудования в течение всего срока службы. Решаются путем поиска стационарного решения, когда оптимальная политика не меняется со временем.

4. По характеру решаемой задачи:

   • Оптимизация траекторий/путей: Задача о кратчайшем пути, задача о коммивояжере.

   • Оптимизация распределения ресурсов: Задача о рюкзаке, задача распределения инвестиций.

   • Оптимизация управления запасами: Определение оптимального уровня запасов.

   • Оптимизация последовательности операций: Задача Джонсона для планирования на станках.

---

Принцип оптимальности Беллмана

Принцип оптимальности Беллмана (Bellman’s Principle of Optimality) — это краеугольный камень динамического программирования. Он формулируется следующим образом:

“Оптимальная стратегия обладает тем свойством, что, каковы бы ни были начальное состояние и начальное решение, последующие решения должны составлять оптимальную стратегию по отношению к состоянию, полученному в результате первого решения.”

Суть принципа:

• Если мы нашли оптимальный путь из начальной точки A в конечную точку C, и этот путь проходит через промежуточную точку B, то участок пути от B до C должен быть оптимальным путем от B до C.

• Иными словами, если некоторая последовательность решений является оптимальной для всей задачи, то любая её подпоследовательность (начиная с любого промежуточного состояния) также должна быть оптимальной для соответствующей подзадачи.

Значение для динамического программирования:

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

Математическое выражение принципа оптимальности:

Пусть fk​(Sk​) — это оптимальное значение целевой функции, начиная с этапа k из состояния Sk​. Тогда рекуррентное соотношение Беллмана для задачи минимизации выглядит так:

fk​(Sk​)=dk​∈D(Sk​)min​{r(Sk​,dk​)+fk+1​(T(Sk​,dk​))}

Где:

• dk​ — решение, принимаемое на этапе k в состоянии Sk​.

• D(Sk​) — множество допустимых решений из состояния Sk​.

• r(Sk​,dk​) — непосредственный выигрыш (или затраты) от принятия решения dk​ в состоянии Sk​.

• T(Sk​,dk​) — следующее состояние, в которое переходит система из Sk​ при принятии решения dk​.

• fk+1​(T(Sk​,dk​)) — оптимальное значение функции для оставшейся части процесса, начиная с нового состояния T(Sk​,dk​) на следующем этапе k+1.

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

---

26. Основные понятия и определения игровых моделей.

Ответ

Игровые модели (Теория игр) — это математический подход к анализу стратегических взаимодействий между рациональными участниками (игроками), каждый из которых стремится максимизировать свой выигрыш, принимая решения в условиях, когда результат зависит не только от его собственных действий, но и от действий других игроков. Теория игр применяется в экономике, политологии, биологии, социологии, военном деле и других областях.

Основные понятия и определения:

1. Игра (Game): Формализованное описание ситуации стратегического взаимодействия. Определяется множеством игроков, их стратегиями и выигрышами.

2. Игрок (Player): Участник игры, принимающий решения и стремящийся максимизировать свой выигрыш (или минимизировать проигрыш). Игроки предполагаются рациональными.

3. Стратегия (Strategy): Полный план действий игрока, который определяет, какое решение он примет в любой возможной ситуации, которая может возникнуть в ходе игры.

   • Чистая стратегия: Игрок выбирает одно конкретное действие в каждой ситуации.

   • Смешанная стратегия: Игрок выбирает действия случайным образом в соответствии с некоторым вероятностным распределением.

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

5. Платёжная матрица (Payoff Matrix): Таблица, в которой для каждого сочетания стратегий всех игроков указаны соответствующие выигрыши для каждого игрока. Для игр двух игроков с нулевой суммой обычно указывается выигрыш только первого игрока, а выигрыш второго равен проигрышу первого.

6. Равновесие (Equilibrium): Состояние игры, в котором ни один игрок не может улучшить свой выигрыш, в одностороннем порядке изменив свою стратегию, при условии, что стратегии остальных игроков остаются неизменными.

7. Равновесие Нэша (Nash Equilibrium): Набор стратегий, по одной для каждого игрока, такой, что ни один игрок не может получить больший выигрыш, отклонившись от своей стратегии, если другие игроки не меняют свои стратегии. Равновесие Нэша не обязательно оптимально для всех игроков, но стабильно, поскольку нет стимула к одностороннему изменению.

8. Доминирующая стратегия (Dominant Strategy): Стратегия, которая приносит игроку лучший выигрыш независимо от того, что делают другие игроки. Если у игрока есть доминирующая стратегия, рациональный игрок всегда выберет её.

9. Итеративное исключение строго доминируемых стратегий: Процесс, при котором игроки последовательно исключают стратегии, которые всегда хуже других стратегий, независимо от действий противника. Это может привести к сужению множества возможных исходов.

10. Оптимальная стратегия (Optimal Strategy): Стратегия, которая максимизирует гарантированный выигрыш игрока (или минимизирует гарантированный проигрыш) в условиях рационального поведения противника. В играх с нулевой суммой это стратегия, которая приводит к седловой точке.

11. Седловая точка (Saddle Point): Элемент платёжной матрицы, который является минимальным в своей строке и максимальным в своём столбце. Если в игре существует седловая точка, то соответствующая чистая стратегия для обоих игроков является оптимальной, и игра имеет цену.

Типы игр (см. также билет 28):

• Игры с нулевой суммой (Zero-Sum Games): Сумма выигрышей всех игроков равна нулю для любого исхода игры (т.е. выигрыш одного игрока равен проигрышу другого).

• Игры с ненулевой суммой (Non-Zero-Sum Games): Сумма выигрышей игроков может быть больше или меньше нуля. Эти игры допускают возможность сотрудничества или общего выигрыша.

• Кооперативные игры: Игроки могут формировать коалиции и заключать обязательные соглашения.

• Некооперативные игры: Игроки принимают решения независимо друг от друга.

• Игры в развернутой форме (Extensive Form Games): Представляются в виде дерева игры, показывают последовательность ходов.

• Игры в нормальной форме (Normal Form Games): Представляются в виде платёжной матрицы.

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

---

27. Постановка задач игровых моделей.

Ответ

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

Общая постановка задачи игровой модели (для некооперативных игр в нормальной форме):

Задача игрового моделирования заключается в анализе следующей структуры:

1. Множество игроков:

   • Определяется конечное множество N участников игры.

   • N={1,2,…,n}.

   • Пример: два конкурента на рынке, несколько стран, ведущих переговоры, два генерала в военном конфликте.

2. Множество стратегий для каждого игрока:

   • Для каждого игрока i∈N определяется набор доступных ему чистых стратегий Si​.

   • Si​={si1​,si2​,…,siki​​}, где ki​ — количество чистых стратегий игрока i.

   • Если игра разыгрывается в смешанных стратегиях, то для каждого игрока i определяется множество смешанных стратегий Σi​, которые представляют собой вероятностные распределения на Si​.

   • Пример: Игрок 1 может выбрать “Атаковать” или “Отступать”. Игрок 2 может выбрать “Обороняться” или “Контратаковать”.

3. Функция выигрыша (функция полезности) для каждого игрока:

   • Для каждого игрока i∈N определяется функция выигрыша ui​(s1​,s2​,…,sn​), которая ставит в соответствие каждому набору стратегий, выбранных всеми игроками (профиль стратегий (s1​,s2​,…,sn​)), числовое значение, представляющее выигрыш игрока i.

   • Значения выигрышей могут быть представлены в виде платёжной матрицы (для игр с небольшим числом игроков и стратегий).

   • Пример: В игре “Дилемма заключенного” выигрыши (годы тюрьмы, которые нужно минимизировать, или их отрицательные значения, которые нужно максимизировать) зависят от выбора каждого из двух заключенных: признаваться или молчать.

Цель задачи:

Основная цель постановки игровой модели — найти оптимальные стратегии для каждого игрока и предсказать исход игры (равновесие). В зависимости от типа игры и поставленной задачи, это может быть:

• Поиск доминирующих стратегий (если они существуют): Игроки выбирают стратегии, которые являются лучшими независимо от действий противника.

• Поиск равновесия Нэша (Nash Equilibrium): Нахождение такого набора стратегий, при котором ни один игрок не может улучшить свой выигрыш, односторонне изменив свою стратегию. Это наиболее распространенное решение для некооперативных игр.

• Поиск минимаксных/максиминных стратегий и цены игры (для игр с нулевой суммой): Определение стратегии, которая гарантирует игроку максимальный возможный выигрыш при наихудшем развитии событий, и соответствующей цены игры (стоимости выигрыша для первого игрока).

• Анализ устойчивости равновесий: Исследование, насколько стабилен найденный исход.

• Анализ эффективности исходов: Сравнение найденных равновесий с социально оптимальными (например, по Парето).

Пример постановки задачи (Игра “Камень, ножницы, бумага” — игра с нулевой суммой):

1. Игроки: Игрок 1, Игрок 2. (N={1,2})

2. Стратегии:

   • Для Игрока 1: S1​={Камень (К),Ножницы (Н),Бумага (Б)}

   • Для Игрока 2: S2​={Камень (К),Ножницы (Н),Бумага (Б)}

3. Функция выигрыша (для Игрока 1, выигрыш Игрока 2 равен −u1​):

   | Игрок 1 / Игрок 2 | К | Н | Б |

   | :---------------- | :-: | :-: | :-: |

   | К | 0 | 1 | -1 |

   | Н | -1 | 0 | 1 |

   | Б | 1 | -1 | 0 |

   (где 1 — выигрыш, -1 — проигрыш, 0 — ничья)

Цель: Найти оптимальные стратегии для каждого игрока. В данном случае, это смешанные стратегии, так как чистых равновесий нет.

---

28. Классификация игровых моделей.

Ответ

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

1. По количеству игроков:

   • Игры двух игроков (Two-Player Games): Включают только двух участников. Многие классические игры (например, “Дилемма заключенного”, “Камень, ножницы, бумага”) относятся к этому типу. Анализировать их проще всего.

   • Игры N игроков (N-Player Games): Включают трех и более участников. Сложность анализа значительно возрастает.

2. По сумме выигрышей игроков:

   • Игры с нулевой суммой (Zero-Sum Games): Сумма выигрышей всех игроков для любого исхода игры равна нулю. Выигрыш одного игрока в точности равен проигрышу другого. Это игры с жесткой конкуренцией, где нет места сотрудничеству.

     • Пример: Шахматы, покер (с учетом комиссии казино, конечно, не совсем но близко), “Камень, ножницы, бумага”.

   • Игры с ненулевой суммой (Non-Zero-Sum Games): Сумма выигрышей игроков для различных исходов может быть больше, меньше или равна нулю. Эти игры допускают ситуации, когда все игроки могут выиграть или проиграть одновременно, что открывает возможности для сотрудничества или конфликта интересов.

     • Пример: “Дилемма заключенного”, “Битва полов”.

3. По наличию/отсутствию кооперации:

   • Кооперативные игры (Cooperative Games): Игроки могут формировать коалиции, заключать обязательные соглашения и координировать свои действия для достижения общей выгоды. Основное внимание уделяется распределению выигрышей между членами коалиции.

     • Пример: Переговоры между компаниями о слиянии, распределение прибыли в консорциуме.

   • Некооперативные игры (Non-Cooperative Games): Игроки не могут заключать обязательные соглашения. Каждый игрок принимает решения независимо, стремясь максимизировать свой собственный выигрыш.

     • Пример: Ценовая конкуренция между фирмами, аукционы.

4. По форме представления:

   • Игры в нормальной (стратегической) форме (Normal/Strategic Form Games): Представляются в виде платёжной матрицы (для двух игроков) или многомерной таблицы (для N игроков), где указаны все возможные стратегии игроков и соответствующие им выигрыши. Не показывают последовательность ходов.

     • Пример: Большинство матричных игр.

   • Игры в развернутой (экстенсивной) форме (Extensive Form Games): Представляются в виде дерева игры, которое показывает последовательность ходов, информацию, доступную игрокам в каждом узле принятия решения, и выигрыши в конечных узлах.

     • Пример: Шахматы, переговоры, игра “Ультиматум”.

5. По наличию информации:

   • Игры с полной информацией (Perfect Information Games): На каждом шаге каждый игрок точно знает все предыдущие ходы всех игроков.

     • Пример: Шахматы, шашки.

   • Игры с неполной информацией (Imperfect Information Games): Игроки не знают всех предыдущих ходов или состояния игры.

     • Пример: Покер (неизвестны карты противников).

   • Игры с совершенной информацией (Perfect Knowledge Games): Игрокам известны не только предыдущие ходы, но и стратегии, типы и выигрыши других игроков. (Не путать с полной информацией, которая касается только истории ходов.)

   • Игры с несовершенной информацией (Imperfect Knowledge Games): Игрокам неизвестны все параметры игры (например, выигрыши противника).

6. По количеству ходов:

   • Одношаговые (Static) игры: Все игроки принимают решения одновременно (или последовательно, но не зная решений других).

   • Многошаговые (Dynamic/Repeated) игры: Игра состоит из нескольких раундов, и решения в одном раунде могут влиять на последующие.

7. По неопределенности:

   • Игры против природы (Decision Theory): Игрок принимает решение в условиях неопределенности, но “природа” не является рациональным противником, у нее нет “цели” выиграть.

   • Игры против рационального противника: Классическая теория игр.

Эта классификация помогает исследователям выбирать адекватные методы анализа и решения игровых моделей.

---

29. Методы решения игровых моделей.

Ответ

Методы решения игровых моделей зависят от типа игры (кооперативная/некооперативная, с нулевой/ненулевой суммой, с полной/неполной информацией) и её формы представления (нормальная/развернутая).

1. Методы решения некооперативных игр в нормальной форме:

а) Игры с нулевой суммой (Матричные игры):

• Поиск седловой точки:

  1. Для каждой строки платёжной матрицы найти минимальный элемент (минимум по строке — это гарантированный выигрыш первого игрока при выборе этой стратегии). Выбрать максимум из этих минимумов (максимин). Это максиминная стратегия первого игрока.

  2. Для каждого столбца найти максимальный элемент (максимум по столбцу — это гарантированный проигрыш первого игрока при выборе этой стратегии второго игрока). Выбрать минимум из этих максимумов (минимакс). Это минимаксная стратегия второго игрока.

  3. Если максимин = минимакс, то игра имеет седловую точку (равновесие в чистых стратегиях), и это значение является ценой игры.

• Решение в смешанных стратегиях (если нет седловой точки):

  • Игроки выбирают стратегии с определенными вероятностями.

  • Для игр 2×2 (два игрока, по две стратегии) можно найти оптимальные вероятности аналитически.

  • Для игр большего размера (m×n) задача сводится к задаче линейного программирования (ЛП). Каждый игрок решает свою ЛП-задачу для нахождения оптимальных вероятностей выбора стратегий, обеспечивающих максимальный гарантированный выигрыш (или минимальный проигрыш) в смешанных стратегиях.

  • Теорема фон Неймана о минимаксе гарантирует существование оптимальных смешанных стратегий и цены игры для любой конечной игры с нулевой суммой.

б) Игры с ненулевой суммой:

• Поиск равновесия Нэша (Nash Equilibrium):

  1. Для каждой клетки платёжной матрицы проверяется, является ли она равновесием Нэша.

  2. Для каждого игрока: если, при условии, что другие игроки придерживаются своих стратегий в данной клетке, этот игрок не может улучшить свой выигрыш, изменив свою стратегию в одностороннем порядке, то это равновесие Нэша.

  3. Метод “подчеркивания лучших ответов”: Для каждой стратегии Игрока 1 подчеркиваются лучшие ответы Игрока 2; затем для каждой стратегии Игрока 2 подчеркиваются лучшие ответы Игрока 1. Клетки, где оба выигрыша подчеркнуты, являются равновесиями Нэша.

  • Равновесий Нэша может быть одно, несколько или ни одного в чистых стратегиях. В смешанных стратегиях равновесие Нэша всегда существует (для конечных игр).

• Исключение строго доминируемых стратегий: Если у игрока есть стратегия, которая всегда хуже другой стратегии, независимо от действий противника, её можно исключить. Процесс повторяется до тех пор, пока не останутся только не доминируемые стратегии. Это может сократить матрицу и помочь найти равновесие Нэша.

2. Методы решения некооперативных игр в развернутой форме (Деревья игры):

• Обратная индукция (Backward Induction):

  1. Начать с конечных узлов дерева игры и определить выигрыши.

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

  3. Продолжать процесс до начального узла.

  • Этот метод позволяет найти равновесие в подиграх (Subgame Perfect Nash Equilibrium), которое является более строгим типом равновесия Нэша для динамических игр.

3. Методы решения кооперативных игр:

• Концепция ядра (Core): Множество распределений выигрышей, при которых ни одна коалиция игроков не может получить больший выигрыш, действуя самостоятельно.

• Вектор Шепли (Shapley Value): Метод для распределения общего выигрыша между игроками на основе их “вклада” в различные коалиции.

• Нуклеолус (Nucleolus): Концепция решения, которая минимизирует недовольство коалиций.

4. Вычислительные методы и симуляция:

• Для очень сложных игр (много игроков, много стратегий, неполная информация) аналитические решения могут быть невозможны. В таких случаях используются:

  • Численные алгоритмы: Для поиска равновесий в больших матричных играх.

  • Имитационное моделирование (Monte Carlo Simulation): Для оценки исходов и стратегий, особенно в играх со случайными элементами.

  • Обучение с подкреплением (Reinforcement Learning): Алгоритмы, которые позволяют агентам учиться оптимальным стратегиям путем взаимодействия с игровой средой.

Выбор метода зависит от структуры и сложности конкретной игровой модели.

---

30. Марковский случайный процесс.

Ответ

Марковский случайный процесс (цепь Маркова) — это стохастический (случайный) процесс, который обладает свойством Маркова. Свойство Маркова гласит, что будущее состояние системы зависит только от ее текущего состояния и не зависит от того, как это текущее состояние было достигнуто (т.е. от всей предыдущей истории). Это свойство значительно упрощает моделирование и анализ многих динамических систем.

Основные понятия и определения Марковских процессов:

1. Состояния (States): Множество возможных состояний, в которых может находиться система. Это множество может быть конечным, счетным или континуальным. В контексте дискретных цепей Маркова обычно рассматривают конечное или счетное множество состояний.

   • Пример: “Погода” (солнечно, облачно, дождь), “статус клиента” (активный, неактивный), “состояние оборудования” (работает, сломано).

2. Шаги (Steps/Time): Марковский процесс развивается во времени. Время может быть дискретным (цепочка Маркова) или непрерывным.

3. Вероятности перехода (Transition Probabilities):

   • Вероятность того, что система перейдет из состояния i в состояние j на следующем шаге.

   • Для дискретных цепей Маркова: Pij​=P(Xt+1​=j∣Xt​=i).

   • Свойство Маркова: P(Xt+1​=j∣Xt​=i,Xt−1​=k,…)=P(Xt+1​=j∣Xt​=i). Будущее зависит только от настоящего.

4. Матрица переходных вероятностей (Transition Matrix, P):

   • Квадратная матрица, где элемент Pij​ — это вероятность перехода из состояния i в состояние j.

   • Строки матрицы должны суммироваться к 1 (сумма вероятностей всех возможных переходов из данного состояния равна 1).

   • Пример (для 2 состояний, 1-состояние, 2-состояние):

     P=(P11​P21​​P12​P22​​)

     Где P11​+P12​=1 и P21​+P22​=1.

5. Начальное распределение вероятностей (π(0)):

   • Вектор, указывающий вероятность нахождения системы в каждом состоянии в начальный момент времени (шаг 0).

6. Распределение вероятностей состояний на k-м шаге (π(k)):

   • Вектор, показывающий вероятность нахождения системы в каждом состоянии после k шагов.

   • π(k)=π(0)Pk, где Pk — матрица переходных вероятностей, возведенная в степень k.

7. Классификация состояний:

   • Достижимые состояния: Из состояния i можно перейти в состояние j.

   • Сообщающиеся состояния: Из состояния i можно перейти в j, и из j можно перейти в i.

   • Неразложимая (эргодическая) цепь: Все состояния сообщаются друг с другом. Это важное свойство для существования стационарного распределения.

   • Поглощающее состояние (Absorbing State): Состояние, из которого невозможно выйти (Pii​=1, а Pij​=0 для j=i).

   • Периодическое состояние: Состояние, в которое система может вернуться только через фиксированное количество шагов, кратное периоду.

8. Стационарное (финальное, предельное) распределение вероятностей (π):

   • Долгосрочное распределение вероятностей состояний, к которому система сходится с течением времени, если цепь Маркова является эргодической и апериодической.

   • πP=π и ∑πi​=1. (см. билет 31)

Применение Марковских процессов:

• Моделирование погодных явлений: Переходы между солнечными, дождливыми днями.

• Моделирование движения клиентов: Переходы между состояниями (активный, неактивный, ушедший).

• Анализ надежности систем: Переходы между рабочим состоянием и состояниями отказа.

• Биологические модели: Распространение болезней, генетические модели.

• Финансы: Моделирование цен активов, кредитных рейтингов.

• Ранжирование страниц в поисковых системах (PageRank Google): Вероятность нахождения пользователя на определенной странице.

Марковские процессы предоставляют мощный аппарат для анализа систем, поведение которых характеризуется отсутствием “памяти”, то есть зависит только от текущего состояния.

---

31. Финальные вероятности состояний.

Ответ

Финальные вероятности состояний (стационарное, предельное, эргодическое распределение) — это распределение вероятностей, к которому стремится Марковский случайный процесс по мере того, как количество шагов (или время) стремится к бесконечности. Если такой предел существует, то говорят, что система достигает стационарного режима.

Концепция финальных вероятностей:

Для многих цепей Маркова, независимо от начального распределения вероятностей, система со временем “забывает” свое начальное состояние и распределение вероятностей нахождения системы в каждом состоянии сходится к некоторому фиксированному распределению π=(π1​,π2​,…,πN​).

То есть, если π(k) — вектор распределения вероятностей на k-м шаге, то link→∞​π(k)=π.

Условия существования финальных вероятностей:

Финальные вероятности существуют и единственны для неразложимых (эргодических) и апериодических цепей Маркова.

• Неразложимость (эргодичность): Из любого состояния можно попасть в любое другое состояние (прямо или косвенно). Это означает, что цепь не распадается на отдельные, несвязанные подцепи.

• Апериодичность: Система не возвращается в определенное состояние через строго фиксированное количество шагов. Иными словами, период каждого состояния равен 1. (Если состояние периодическое, то оно не сходится к одному значению, а колеблется).

Система уравнений для нахождения финальных вероятностей:

Если π=(π1​,π2​,…,πN​) — вектор финальных вероятностей, то он должен удовлетворять следующей системе линейных уравнений:

1. Условие стационарности (равновесия):

   πP=π

   Где P — матрица переходных вероятностей. В развернутом виде это означает:

   πj​=i=1∑N​πi​Pij​,для каждого состояния j=1,…,N

   Это уравнение выражает, что вероятность нахождения в состоянии j в стационарном режиме равна сумме вероятностей попадания в состояние j из любого другого состояния i, умноженных на вероятность нахождения в состоянии i.

2. Условие нормировки:

   Сумма всех финальных вероятностей должна быть равна 1 (поскольку система обязательно находится в одном из состояний):

   j=1∑N​πj​=1

Эта система из N+1 линейных уравнений с N неизвестными πj​ всегда имеет единственное решение (одно из уравнений в πP=π является линейно зависимым, поэтому его можно заменить на уравнение нормировки).

Пример:

Рассмотрим Марковскую цепь с двумя состояниями 1 и 2, и матрицей переходных вероятностей:

P=(0.80.3​0.20.7​)

Найдем финальные вероятности π=(π1​,π2​):

3. π1​=π1​P11​+π2​P21​⇒π1​=0.8π1​+0.3π2​

4. π2​=π1​P12​+π2​P22​⇒π2​=0.2π1​+0.7π2​

5. π1​+π2​=1

Из первого уравнения: 0.2π1​=0.3π2​⇒π1​=1.5π2​.

Подставим в третье уравнение: 1.5π2​+π2​=1⇒2.5π2​=1⇒π2​=1/2.5=0.4.

Тогда π1​=1.5×0.4=0.6.

Финальные вероятности: π=(0.6,0.4). Это означает, что в долгосрочной перспективе система будет находиться в состоянии 1 с вероятностью 60% и в состоянии 2 с вероятностью 40%.

Значение финальных вероятностей:

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

---

32. Системы массового обслуживания (СМО), их классы и основные характеристики.

Ответ

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

Основные элементы и характеристики СМО:

1. Входящий поток требований (Input Stream):

   • Интенсивность потока (λ): Среднее число требований, поступающих в единицу времени.

   • Закон распределения интервалов между поступлениями: Чаще всего предполагается пуассоновский поток (интервалы между поступлениями распределены экспоненциально), что означает, что приходы независимы друг от друга.

   • Тип потока: Детерминированный, регулярный, случайный (например, простейший поток).

   • Источник требований: Конечный или бесконечный.

2. Дисциплина очереди (Queue Discipline):

   • Правило, по которому требования выбираются из очереди для обслуживания.

   • FIFO (First-In, First-Out): “Первым пришел, первым обслужен” — наиболее распространенная.

   • LIFO (Last-In, First-Out): “Последним пришел, первым обслужен” (например, стопка бумаг).

   • SJF (Shortest Job First): Обслуживается требование с наименьшим временем обслуживания.

   • Приоритетная: Требования с более высоким приоритетом обслуживаются раньше.

   • Random: Случайный выбор.

3. Очередь (Queue):

   • Место, где требования ожидают обслуживания.

   • Вместимость очереди (Lq​): Максимальное количество требований, которые могут находиться в очереди. Может быть конечной или бесконечной.

   • Поведение клиентов: Терпеливые (ждут сколько угодно), нетерпеливые (уходят, если очередь слишком длинная или ожидание долгое), теряющие надежду.

4. Обслуживающий аппарат (Service Mechanism):

   • Количество каналов обслуживания (c): Число параллельных устройств или операторов, способных одновременно обслуживать требования. Может быть 1 (одноканальная СМО) или c>1 (многоканальная СМО).

   • Интенсивность обслуживания (μ): Среднее число требований, обслуживаемых одним каналом в единицу времени.

   • Закон распределения времени обслуживания: Чаще всего предполагается экспоненциальное распределение времени обслуживания.

Классы СМО (нотация Кендалла):

СМО часто обозначаются символами A/B/c/K/N, где:

• A: Тип распределения интервалов между поступлениями (M — Марковское/экспоненциальное, D — детерминированное/постоянное, G — общее).

• B: Тип распределения времени обслуживания (M — Марковское/экспоненциальное, D — детерминированное/постоянное, G — общее).

• c: Количество каналов обслуживания.

• K: Вместимость системы (общая вместимость очереди и каналов). Если не указано, считается бесконечной.

• N: Размер источника требований (генеральной совокупности). Если не указано, считается бесконечным.

Наиболее распространенные классы:

• M/M/1: Простейшая одноканальная СМО. Пуассоновский поток поступлений, экспоненциальное время обслуживания, 1 канал, бесконечная очередь, бесконечный источник.

• M/M/c: Многоканальная СМО. Аналогично M/M/1, но c каналов.

• M/M/1/K: Одноканальная СМО с ограниченной очередью (или системой).

• M/M/c/K: Многоканальная СМО с ограниченной очередью (или системой).

Основные характеристики эффективности (показатели качества функционирования) СМО:

1. Коэффициент загрузки (использования) системы (ρ):

   • ρ=c⋅μλ​. Показывает долю времени, в течение которой каналы заняты. Должен быть <1 для стабильных систем с бесконечной очередью.

2. Вероятность отказа в обслуживании (Pотказа​):

   • Доля требований, которые не были обслужены (для СМО с отказами, когда очередь ограничена).

3. Среднее число требований в системе (L):

   • L=Lq​+Ls​, где Lq​ — среднее число требований в очереди, Ls​ — среднее число требований в обслуживании.

4. Среднее число требований в очереди (Lq​):

   • Среднее количество клиентов, ожидающих своей очереди.

5. Среднее время пребывания требования в системе (W):

   • Среднее время от момента поступления требования до его завершения обслуживания.

6. Среднее время ожидания в очереди (Wq​):

   • Среднее время, которое требование проводит в очереди до начала обслуживания.

7. Вероятность того, что система свободна (P0​): Вероятность отсутствия требований в системе.

Анализ СМО позволяет оптимизировать работу систем, обеспечивая баланс между затратами на обслуживание и качеством обслуживания клиентов.

---

33. Моделирование СМО, СМО с отказами, СМО с ожиданием.

Ответ

Моделирование СМО

Моделирование систем массового обслуживания (СМО) может быть выполнено двумя основными способами:

1. Аналитическое моделирование:

   • Использует математические формулы и уравнения (например, на основе теории Марковских цепей, теории вероятностей) для расчета характеристик СМО.

   • Возможно только для относительно простых классов СМО (например, M/M/1, M/M/c) с определенными предположениями о распределениях (экспоненциальные интервалы поступлений и обслуживания).

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

   • Преимущества: Быстрота расчетов, позволяет выявить общие закономерности.

   • Недостатки: Ограничено строгими предположениями, не подходит для сложных, нелинейных систем, систем с нестандартными распределениями или дисциплинами обслуживания.

2. Имитационное моделирование (имитационная симуляция):

   • Создает компьютерную модель реальной СМО, воспроизводящую ее функционирование во времени. Генерируются случайные события (поступление требований, завершение обслуживания) в соответствии с заданными вероятностными распределениями.

   • Модель “проигрывается” множество раз, собирая статистику о поведении системы.

   • Преимущества: Позволяет моделировать очень сложные СМО с произвольными распределениями, сложными дисциплинами обслуживания, динамически изменяющимися параметрами, взаимодействием различных потоков. Не требует жестких математических предположений.

   • Недостатки: Требует больших вычислительных ресурсов, результаты являются статистическими оценками (не точными значениями), требует тщательной проверки модели (верификация и валидация).

СМО с отказами (Lost-Call Systems)

СМО с отказами — это системы, в которых входящие требования, если все каналы обслуживания заняты и/или очередь заполнена (если есть ограниченная очередь), не могут быть обслужены и покидают систему без обслуживания (теряются). Такие системы также называются системами с потерями.

• Характеристики:

  • Отсутствие или ограниченная вместимость очереди.

  • Клиенты, приходящие в занятую систему, не ждут.

• Применение: Телефонные станции (когда все линии заняты), веб-серверы (когда превышена пропускная способность), билетные кассы (когда мест нет).

• Основные показатели эффективности:

  • Вероятность отказа (Pотказа​ или Pпотерь​): Вероятность того, что поступающее требование найдет все каналы занятыми и будет потеряно. Это ключевой показатель для таких систем.

  • Абсолютная пропускная способность: Среднее число обслуженных требований в единицу времени.

  • Относительная пропускная способность: Доля обслуженных требований от общего числа поступивших (1 - Pотказа​).

• Модель Эрланга B (M/M/c/c): Классическая аналитическая модель для СМО с отказами, где c — количество каналов, а вместимость системы равна c (т.е. нет очереди). Формула Эрланга B позволяет рассчитать вероятность отказа.

СМО с ожиданием (Waiting-Line Systems)

СМО с ожиданием — это системы, в которых требования, если все каналы обслуживания заняты, встают в очередь и ждут освобождения канала. Они не покидают систему до тех пор, пока не будут обслужены (или не истечет их терпение, если это учитывается).

• Характеристики:

  • Наличие очереди (может быть бесконечной или ограниченной).

  • Клиенты готовы ждать.

• Применение: Банки, супермаркеты, поликлиники, колл-центры.

• Основные показатели эффективности:

  • Средняя длина очереди (Lq​)

  • Среднее время ожидания в очереди (Wq​)

  • Среднее число требований в системе (L)

  • Среднее время пребывания в системе (W)

  • Вероятность простоя каналов (P0​)

• Модель Эрланга C (M/M/c): Классическая аналитическая модель для СМО с ожиданием, где c — количество каналов, а очередь бесконечна. Формула Эрланга C позволяет рассчитать вероятность того, что поступающее требование застанет все каналы занятыми и будет ждать в очереди.

Выбор между СМО с отказами и СМО с ожиданием зависит от характера обслуживаемого процесса и последствий необслуженных требований.

---

34. Сущность и классификация прогнозов.

Ответ

Сущность прогнозов

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

Сущность прогнозирования заключается в следующем:

1. Обоснованность: Прогноз должен базироваться на объективных данных и научных методах, а не на интуиции или случайных предположениях.

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

3. Системность: Прогнозирование требует учета всех существенных факторов, влияющих на объект прогноза, и их взаимосвязей.

4. Динамичность: Прогнозы должны регулярно пересматриваться и корректироваться по мере поступления новой информации и изменения внешних условий.

5. Направленность на будущее: Прогноз всегда ориентирован на оценку будущих состояний, что является его главной целью.

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

Классификация прогнозов

Прогнозы можно классифицировать по различным признакам:

6. По временному горизонту (длительности):

   • Краткосрочные (Short-term): Прогнозы на период от нескольких дней до 1-2 месяцев. Используются для оперативного планирования (например, ежедневный объем продаж, прогноз погоды на завтра). Отличаются высокой точностью.

   • Среднесрочные (Medium-term): Прогнозы на период от 1-2 месяцев до 1-5 лет. Используются для тактического планирования (например, годовой объем производства, спрос на продукцию). Точность ниже, чем у краткосрочных.

   • Долгосрочные (Long-term): Прогнозы на период от 5 до 15-20 лет и более. Используются для стратегического планирования (например, демографические тенденции, развитие технологий, мировые энергетические рынки). Обладают наименьшей точностью, часто носят сценарный характер.

7. По объекту прогнозирования (сфере деятельности):

   • Экономические: Прогноз ВВП, инфляции, процентных ставок, безработицы, цен на товары.

   • Социальные: Прогноз численности населения, уровня жизни, образования, миграции.

   • Технологические: Прогноз развития новых технологий, появления инноваций.

   • Экологические: Прогноз изменения климата, загрязнения окружающей среды.

   • Демографические: Прогноз рождаемости, смертности, старения населения.

   • Производственные: Прогноз объемов производства, спроса на продукцию.

8. По функции (назначению):

   • Поисковые (Exploratory): Отвечают на вопрос “Что вероятнее всего произойдет, если текущие тенденции сохранятся?“. Изучают возможное развитие ситуации в будущем.

   • Нормативные (Normative/Target): Отвечают на вопрос “Каким должно быть будущее, чтобы достичь поставленных целей?“. Определяют пути достижения желаемого состояния.

   • Предупреждающие: Направлены на выявление потенциальных угроз или кризисов.

9. По методу получения:

   • Количественные (Quantitative): Основаны на математических моделях и статистическом анализе числовых данных.

     • Примеры: Методы экстраполяции, регрессионный анализ, эконометрические модели.

   • Качественные (Qualitative): Основаны на мнениях экспертов, интуиции, логическом анализе, когда количественные данные недостаточны или ненадежны.

     • Примеры: Метод Дельфи, мозговой штурм, сценарный анализ, экспертные оценки.

10. По форме представления результата:

    • Точечный: Одно конкретное число (например, “ВВП вырастет на 3%”).

    • Интервальный: Диапазон значений (например, “ВВП вырастет на 2.5-3.5%”).

    • Сценарный: Несколько возможных вариантов развития событий с оценкой их вероятности.

11. По типу объекта:

    • Микроуровень: Прогнозы для отдельной фирмы, продукта.

    • Макроуровень: Прогнозы для экономики страны, региона.

Правильный выбор типа прогноза и соответствующего метода критически важен для его точности и полезности.

---

35. Аналитическое моделирование в прогнозировании и планировании.

Ответ

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

Сущность аналитического моделирования:

1. Формализация: Явное представление зависимостей в виде математических выражений (функций, уравнений, неравенств).

2. Дедуктивный подход: Выведение результатов из начальных предположений и логических правил.

3. Аналитическое решение: Возможность получить явные формулы или алгоритмы для расчета искомых показателей.

4. Упрощение: Для построения аналитических моделей часто требуется делать допущения и упрощения относительно реальности, чтобы сделать модель разрешимой.

Типы аналитических моделей, используемых в прогнозировании и планировании:

5. Эконометрические модели:

   • Строятся на основе статистических данных для количественного описания экономических взаимосвязей.

   • Используют методы регрессионного анализа для определения зависимости одной переменной (например, спроса) от других (например, цены, дохода, рекламы).

   • Пример: Модель, прогнозирующая ВВП страны на основе инвестиций, потребления и экспорта.

6. Модели временных рядов:

   • Используются для прогнозирования будущих значений переменной на основе её прошлых значений, выявляя тенденции, сезонность, цикличность и случайные колебания.

   • Примеры:

     • Модели скользящего среднего (Moving Average - MA): Прогноз равен среднему арифметическому за определенный период.

     • Модели экспоненциального сглаживания (Exponential Smoothing - ES): Более сложные модели, придающие больший вес недавним наблюдениям (например, Хольта-Винтерса для учета тренда и сезонности).

     • Модели ARIMA (AutoRegressive Integrated Moving Average): Статистические модели, объединяющие авторегрессию, интегрирование и скользящее среднее для описания стохастических процессов во временных рядах.

7. Математическое программирование (Оптимизационные модели):

   • Используются для планирования и принятия оптимальных решений в условиях ограниченных ресурсов. Результатом является не только прогноз, но и оптимальный план действий.

   • Примеры:

     • Линейное программирование: Оптимизация производственного плана, распределение ресурсов, транспортные задачи.

     • Нелинейное программирование: Оптимизация инвестиционного портфеля с учетом риска (дисперсии).

     • Динамическое программирование: Планирование многошаговых процессов, таких как управление запасами, замена оборудования.

8. Имитационные модели (в некоторых контекстах):

   • Хотя имитационное моделирование относится к другому классу методов, некоторые аналитические модели могут быть использованы для получения параметров для имитационных моделей (например, аналитическое определение распределений для входных потоков).

9. Марковские цепи:

   • Используются для прогнозирования распределения состояний системы в будущем, если система обладает свойством Маркова (будущее зависит только от настоящего).

   • Пример: Прогнозирование доли рынка для компаний, основываясь на вероятностях перехода клиентов между брендами.

Преимущества аналитического моделирования:

• Точность: Для соответствующих задач могут давать точные решения.

• Понимание: Позволяют выявить причинно-следственные связи и механизмы функционирования системы.

• Скорость: Расчеты, как правило, быстрее, чем имитационное моделирование, для задач, поддающихся аналитическому решению.

• Анализ чувствительности: Легче проводить анализ чувствительности к изменениям параметров.

Недостатки аналитического моделирования:

• Ограниченность: Требует сильных упрощений и допущений, что может снизить адекватность модели реальности.

• Сложность для нелинейных и сложных систем: Многие реальные системы слишком сложны для аналитического описания.

Аналитическое моделирование является мощным инструментом, но его применимость зависит от природы и сложности прогнозируемого или планируемого объекта.

---

36. Имитационное моделирование.

Ответ

Имитационное моделирование (имитационная симуляция, Monte Carlo simulation) — это метод исследования сложных систем, процессов или явлений путем создания их компьютерной модели и проведения серии экспериментов с этой моделью. В отличие от аналитического моделирования, которое ищет явные математические решения, имитационное моделирование воспроизводит поведение системы во времени, шаг за шагом, генерируя случайные события в соответствии с заданными вероятностными распределениями.

Сущность имитационного моделирования:

1. Воспроизведение динамики: Модель имитирует реальные процессы и взаимодействия элементов системы в их временной последовательности.

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

3. Сбор статистики: В ходе “прогона” модели собираются статистические данные о поведении системы (длины очередей, время ожидания, загрузка оборудования, прибыль, потери).

4. Анализ результатов: Собранные данные анализируются для оценки характеристик системы, сравнения различных сценариев, выявления “узких мест” и принятия обоснованных решений.

Этапы имитационного моделирования:

5. Постановка задачи: Четкое определение целей моделирования, вопросов, на которые должна ответить модель, и требуемых выходных показателей.

6. Сбор и анализ данных: Изучение реальной системы, сбор исторических данных о параметрах (например, время обслуживания, интервалы между приходами), определение их вероятностных распределений.

7. Построение модели: Разработка концептуальной и затем компьютерной модели, включающей описание компонентов системы, их логики поведения, правил взаимодействия. Выбор ПО для моделирования.

8. Верификация модели: Проверка правильности реализации модели (корректность кода, отсутствие ошибок). Отвечает на вопрос: “Правильно ли построена модель?”

9. Валидация модели: Проверка соответствия модели реальной системе. Отвечает на вопрос: “Моделирует ли модель то, что мы хотим моделировать?” Сравнение результатов модели с данными реальной системы.

10. Планирование экспериментов: Определение сценариев для “прогона” модели, количества прогонов, длительности симуляции, выбор начальных условий.

11. Проведение экспериментов: Запуск модели и сбор данных.

12. Анализ результатов: Статистическая обработка и интерпретация полученных данных, формулирование выводов и рекомендаций.

Виды имитационного моделирования:

13. Дискретно-событийное моделирование (Discrete Event Simulation - DES):

    • Система изменяет свое состояние только в дискретные моменты времени, когда происходят определенные события (например, приход клиента, начало обслуживания, завершение обслуживания).

    • Широко используется для моделирования систем массового обслуживания, производственных систем, логистики, здравоохранения.

14. Системная динамика (System Dynamics - SD):

    • Моделирует системы с большим количеством взаимосвязанных элементов и обратных связей (петлями причинно-следственных связей).

    • Используется для анализа долгосрочного поведения сложных социальных, экономических, экологических систем. Обычно оперирует непрерывными переменными (или переменными, изменяющимися достаточно часто, чтобы их можно было считать непрерывными).

15. Агентное моделирование (Agent-Based Modeling - ABM):

    • Моделирует поведение отдельных автономных агентов (людей, организаций, роботов) и их взаимодействие, из которых возникает глобальное поведение системы.

    • Используется для моделирования социальных явлений, рыночного поведения, распространения инноваций.

Преимущества имитационного моделирования:

• Реализм: Позволяет моделировать очень сложные системы без упрощений, требуемых для аналитических методов.

• Гибкость: Легко изменять параметры и логику системы для анализа различных сценариев “что если”.

• Наглядность: Часто сопровождается анимацией, что улучшает понимание работы системы.

• Безопасность: Позволяет проводить эксперименты, которые были бы слишком дорогими, опасными или невозможными в реальной жизни.

Недостатки имитационного моделирования:

• Вычислительная сложность: Требует значительных вычислительных ресурсов и времени для прогонов.

• Статистический характер: Результаты являются оценками, а не точными значениями, и подвержены статистической ошибке.

• Затраты: Разработка и верификация сложных моделей могут быть трудоемкими.

Имитационное моделирование является незаменимым инструментом для анализа и оптимизации систем, которые слишком сложны для аналитического описания.

---

37. Статистические методы прогнозирования.

Ответ

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

Основные принципы статистических методов:

1. Наличие исторических данных: Для применения статистических методов необходим достаточно большой объем достоверных данных о прошлом поведении объекта прогнозирования.

2. Выявление закономерностей: Методы направлены на обнаружение трендов, сезонности, цикличности, корреляций и других статистических связей.

3. Предположение о стабильности: Часто предполагается, что выявленные в прошлом закономерности сохранятся в будущем (или их изменения можно предсказать).

4. Количественный результат: Прогноз представляется в виде числовых значений (точечный или интервальный).

Основные группы статистических методов прогнозирования:

5. Методы анализа временных рядов (Time Series Analysis):

   • Используются, когда есть только данные о значении прогнозируемого показателя в прошлом (временной ряд). Цель — выявить внутренние компоненты ряда (тренд, сезонность, цикличность, случайные отклонения) и экстраполировать их.

   • Метод скользящего среднего (Moving Average - MA): Прогноз на следующий период равен среднему арифметическому значений за несколько последних периодов.

     • Прост, сглаживает случайные колебания. Недостатки: запаздывает при наличии тренда.

   • Метод экспоненциального сглаживания (Exponential Smoothing - ES): Прогноз является взвешенным средним прошлых наблюдений, где недавним наблюдениям придается больший вес.

     • Простое экспоненциальное сглаживание: Для рядов без тренда и сезонности.

     • Метод Хольта (Holt’s Method): Для рядов с трендом.

     • Метод Хольта-Винтерса (Holt-Winters Method): Для рядов с трендом и сезонностью.

     • Более адаптивны к изменениям, чем скользящие средние.

   • Модели ARIMA (AutoRegressive Integrated Moving Average):

     • Семейство мощных и гибких моделей (AR - авторегрессия, I - интегрирование для устранения нестационарности, MA - скользящее среднее).

     • Требуют идентификации порядка модели, оценки параметров и проверки адекватности. Широко используются в эконометрике и финансовом прогнозировании.

   • Декомпозиция временных рядов: Разделение временного ряда на компоненты (тренд, сезонность, цикличность, остаток) для их отдельного анализа и прогнозирования.

6. Регрессионный анализ (Regression Analysis):

   • Используется, когда прогнозируемый показатель (зависимая переменная) зависит от одной или нескольких других переменных (независимых переменных, факторов).

   • Строится математическая модель, описывающая эту зависимость.

   • Линейная регрессия: Зависимость является линейной.

     • Y=a+b1​X1​+b2​X2​+⋯+ε

     • Пример: Прогноз продаж (Y) на основе цены (X1) и затрат на рекламу (X2).

   • Нелинейная регрессия: Зависимость нелинейная (например, полиномиальная, экспоненциальная).

   • Множественная регрессия: Используется несколько независимых переменных.

   • Этапы: Спецификация модели, оценка параметров (МНК), проверка значимости, проверка адекватности модели, прогнозирование.

7. Эконометрические модели:

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

   • Позволяют прогнозировать не только отдельные показатели, но и всю систему.

Преимущества статистических методов:

• Объективность: Основаны на данных и математических принципах.

• Измеряемая точность: Позволяют оценивать ошибки прогноза (доверительные интервалы).

• Выявление зависимостей: Помогают понять факторы, влияющие на прогнозируемый показатель.

Недостатки статистических методов:

• Требуют большого объема данных: Необходимы достаточные исторические данные.

• Предположение о стабильности: Могут быть неточными при резких структурных изменениях в системе.

• Сложность для нелинейных и качественных факторов: Плохо работают с качественными переменными или очень сложными нелинейными связями.

• Не учитывают “черных лебедей”: Не предсказывают абсолютно новые, беспрецедентные события.

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

---

38. Модели межотраслевого баланса.

Ответ

Модели межотраслевого баланса (МОБ), также известные как модели затраты-выпуск (Input-Output Models), представляют собой инструмент экономического анализа, разработанный Василием Леонтьевым (лауреатом Нобелевской премии). Эти модели описывают взаимосвязи между различными отраслями экономики, показывая, как продукция одной отрасли используется в качестве входа (ресурса) для производства продукции в других отраслях.

Сущность модели МОБ:

Модель МОБ представляет экономику как систему, состоящую из взаимосвязанных отраслей, где каждая отрасль производит продукцию и одновременно потребляет продукцию других отраслей (и, возможно, свою собственную) в качестве промежуточного продукта.

Основные элементы модели:

1. Отрасли (Sectors): Экономика разбивается на определенное количество отраслей (например, сельское хозяйство, промышленность, транспорт, услуги).

2. Валовой выпуск (Xi​): Общий объем продукции, произведенный i-й отраслью за определенный период.

3. Промежуточный продукт (xij​): Объем продукции i-й отрасли, который используется в качестве ресурса для производства продукции j-й отраслью.

4. Конечное потребление (конечный продукт, Yi​): Объем продукции i-й отрасли, который не используется в качестве промежуточного продукта в других отраслях, а идет на конечное потребление (населением, государством, на экспорт, накопление).

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

Балансовые уравнения:

Модель МОБ строится на двух видах балансовых уравнений:

а) Баланс по строкам (Межотраслевые потоки):

Объем продукции i-й отрасли (Xi​) распределяется на промежуточное потребление другими отраслями и на конечное потребление:

Xi​=j=1∑n​xij​+Yi​,для i=1,…,n

Где n — количество отраслей.

б) Баланс по столбцам (Структура затрат):

Объем валового выпуска j-й отрасли (Xj​) формируется из промежуточных затрат продукции других отраслей и добавленной стоимости:

Xj​=i=1∑n​xij​+Vj​,для j=1,…,n

Таблица межотраслевого баланса:

Данные обычно представляются в виде матрицы, где строки показывают распределение продукции отрасли, а столбцы — структуру затрат отрасли.

Производитель / Потребитель	Отрасль 1	Отрасль 2	…	Отрасль n	Конечное потребление (Y)	Валовой выпуск (X)
Отрасль 1	x11​	x12​	…	x1n​	Y1​	X1​
Отрасль 2	x21​	x22​	…	x2n​	Y2​	X2​
…	…	…	…	…	…	…
Отрасль n	xn1​	xn2​	…	xnn​	Yn​	Xn​
Добавленная стоимость (V)	V1​	V2​	…	Vn​
Валовой выпуск (X)	X1​	X2​	…	Xn​		∑Xi​=∑Xj​

Коэффициенты прямых затрат (aij​):

Ключевым понятием МОБ являются коэффициенты прямых затрат:

aij​=Xj​xij​​

aij​ показывает, сколько продукции i-й отрасли необходимо для производства единицы валового выпуска j-й отрасли. Эти коэффициенты образуют матрицу прямых затрат A. Они считаются относительно стабильными в краткосрочном и среднесрочном периодах.

Математическая модель (открытая модель Леонтьева):

Подставляя xij​=aij​Xj​ в баланс по строкам, получаем:

Xi​=j=1∑n​aij​Xj​+Yi​,или в матричной форме:

X=AX+Y

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

X−AX=Y

(I−A)X=Y

X=(I−A)−1Y

Где I — единичная матрица. Матрица L=(I−A)−1 называется матрицей полных затрат (или обратной матрицей Леонтьева). Элементы lij​ матрицы L показывают, сколько валового выпуска i-й отрасли необходимо произвести, чтобы удовлетворить единицу конечного спроса на продукцию j-й отрасли.

Применение моделей МОБ:

• Прогнозирование: Оценка валового выпуска, необходимого для удовлетворения прогнозируемого конечного спроса.

• Анализ влияния: Оценка влияния изменения конечного спроса в одной отрасли на выпуск всех остальных отраслей.

• Ценообразование: Анализ формирования цен.

• Планирование: Разработка народнохозяйственных планов, оценка потребности в ресурсах.

• Структурный анализ экономики: Выявление ключевых отраслей, взаимозависимостей.

Модели МОБ предоставляют системный взгляд на экономику и являются важным инструментом макроэкономического анализа и планирования.

---

39. Оптимизация межотраслевого баланса.

Ответ

Хотя базовая модель межотраслевого баланса (МОБ) является дескриптивной (описывает взаимосвязи), она может быть расширена до оптимизационных моделей межотраслевого баланса. Эти модели не просто показывают, как распределяется продукция, но и определяют оптимальный план производства и распределения ресурсов для достижения определенных экономических целей, обычно в условиях ограничений.

Сущность оптимизации межотраслевого баланса:

Оптимизация МОБ заключается в формулировании задачи линейного программирования (или более сложного математического программирования), где:

• Целевая функция выражает экономическую цель (например, максимизация валового национального продукта, минимизация затрат, максимизация конечного потребления, максимизация прибыли).

• Ограничения включают в себя базовые балансовые соотношения МОБ, а также дополнительные ограничения на ресурсы (труд, капитал, сырье), производственные мощности, экологические нормы, экспортно-импортные возможности и т.д.

Математическая модель оптимизации межотраслевого баланса (пример постановки):

Рассмотрим простейшую модель, направленную на максимизацию конечного продукта, при условии ограниченности первичных ресурсов.

Переменные решения:

• Xj​ — валовой выпуск j-й отрасли (j=1,…,n).

• Yj​ — конечный продукт j-й отрасли (j=1,…,n).

Параметры модели:

• aij​ — коэффициенты прямых затрат (сколько продукции i-й отрасли нужно для производства единицы продукции j-й отрасли).

• vj​ — коэффициенты добавленной стоимости (сколько добавленной стоимости приходится на единицу валового выпуска j-й отрасли).

• Lj​ — трудоемкость единицы валового выпуска j-й отрасли (сколько труда нужно для единицы Xj​).

• Rmax​ — максимальный доступный объем определенного первичного ресурса (например, общий фонд рабочего времени).

1. Целевая функция:

В зависимости от задачи, это может быть:

• Максимизация общего конечного продукта (ВНП):

  Максимизировать j=1∑n​Yj​

• Максимизация прибыли: Если заданы цены, прибыль можно выразить через валовой выпуск и затраты.

• Минимизация затрат на ресурсы: При заданном объеме конечного продукта.

2. Ограничения:

а) Балансовые соотношения (основные уравнения МОБ):

• Каждая отрасль должна произвести достаточный объем продукции для промежуточного потребления другими отраслями и для удовлетворения конечного спроса:

  Xi​=j=1∑n​aij​Xj​+Yi​,для i=1,…,n

  (или в матричной форме: X=AX+Y)

б) Ограничения по первичным ресурсам:

• Общий объем потребления каждого первичного ресурса не должен превышать его доступный запас.

• Например, ограничение по труду:

  j=1∑n​Lj​Xj​≤Rmax​

• Могут быть аналогичные ограничения по капиталу, земле, сырью.

в) Ограничения на мощность производства:

• Валовой выпуск каждой отрасли не может превышать её максимальную производственную мощность:

  Xj​≤Mj​,для j=1,…,n

г) Ограничения на неотрицательность переменных:

Xj​≥0,Yj​≥0,для всех j

Пример расширенной задачи:

Если требуется максимизировать конечное потребление, но с определенной пропорцией между отраслями (например, Y1​/Y2​=k1​, Y2​/Y3​=k2​), то можно ввести дополнительные ограничения.

Особенности и применение:

• Тип задачи: Как правило, это задачи линейного программирования, что позволяет использовать эффективные методы решения (например, симплекс-метод).

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

• Сценарный анализ: Позволяют оценить, как изменение доступности ресурсов или структуры спроса повлияет на оптимальные производственные планы.

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

• Выявление “узких мест”: Через анализ двойственных цен можно определить, какой ресурс является наиболее дефицитным и ограничивает рост.

Оптимизация МОБ позволяет переходить от простого описания экономических связей к активному управлению экономикой для достижения заданных целей.

---