Made on
Tilda
Задача: Проанализировать задачи о рюкзаке и TSP как модели
Цель: Понять, как абстрактные задачи становятся математическими моделями реальных ситуаций
Инструкция: 1) Вспомните условия задач. 2) Определите элементы, связи и параметры. 3) Обсудите, какие реальные ситуации они описывают
Элементы: рюкзак (контейнер), предметы для упаковки
Связи: предметы конкурируют за место в рюкзаке; выбор одного предмета влияет на доступную ёмкость для других
Параметры: вместимость рюкзака, вес/объём каждого предмета, ценность каждого предмета
Ограничения: суммарный вес выбранных предметов не должен превышать вместимость рюкзака; максимизировать суммарную ценность
Реальные ситуации: загрузка контейнера, формирование инвестиционного портфеля, планирование раскроя материалов
Пример разбора "Задачи коммивояжера (TSP)":Элементы: города (точки), которые нужно посетить
Связи: дороги между городами, образующие полный граф; последовательность посещения
Параметры: расстояния/стоимости между городами, количество городов
Ограничения: посетить каждый город ровно один раз; вернуться в исходный город; минимизировать общую длину маршрута
Реальные ситуации: планирование маршрутов доставки, сверление отверстий в платах, составление расписаний
Цель задания: Научиться находить и анализировать модели в повседневной жизни, понимать их структуру и классификацию
Модель всегда проще оригинала, она содержит только те свойства, которые важны для решения конкретной задачи. Например, глобус — модель Земли, но на нём нет всех городов, дорог, людей.
Нет, более того — она не может быть точной копией. Суть моделирования как раз в упрощении. Иногда намеренное искажение (идеализация) помогает лучше понять суть явления.
Выбор зависит от цели: если нужно испытать прочность — материальная модель; если рассчитать траекторию — математическая; если объяснить принцип работы — графическая.
Процесс моделирования представляет собой структурированную последовательность этапов, направленную на преобразование неформализованной проблемы в рабочую модель, пригодную для анализа и получения обоснованных выводов.
Содержательная постановка: Купить все необходимые продукты, потратив как можно меньше времени.
Итог: Задача сведена к классической задаче коммивояжера (TSP) на множестве отделов S с добавленной точкой E. Мы ищем самый короткий замкнутый маршрут, проходящий через все нужные отделы и возвращающийся к выходу.
Исследование точных решений демонстрирует фундаментальную проблему вычислительной сложности. Количество возможных гамильтоновых циклов растет факториально (n-1)!/2, что делает полный перебор неосуществимым для практически значимого числа вершин n.
Вопрос для анализа: Рассмотрим формализацию задачи «Оптимизировать поход в магазин». Какие типовые проблемы моделирования могут быть выявлены при критическом рассмотрении предложенной формализации?
1. Проблема исходных данных
Каков источник и точность данных для параметров модели, в частности, расстояний d(Mₐ, M₆)? Какие факторы (разная проходимость проходов, этажность) могут сделать понятие «расстояние» недостаточным для оценки временных затрат?
Модель оперирует идеализированными данными. На практике расстояния носят оценочный характер, а ключевым параметром является время перемещения, которое зависит от непредсказуемых факторов (очереди, пробки в проходах). Это приводит к погрешности в работе модели.
2. Проблема адекватности критерия
Является ли минимизация геометрического пути эквивалентной минимизации времени, затрачиваемого на поход? Какие дополнительные факторы (плотность потока покупателей, время ожидания в очереди) не отражены в текущей целевой функции?
Исходная цель «потратить меньше времени» была неполно формализована через минимизацию пути. Для повышения адекватности требуется либо усложнение модели (введение весовых коэффициентов, отражающих пропускную способность отделов), либо замена критерия (прямая минимизация расчетного времени с учетом дополнительных факторов).
3. Проблема полноты модели
Какие содержательные ограничения реальной задачи были опущены в предложенной формализации? Например, необходимость сохранять температурный режим для отдельных товаров или логистику распределения веса покупок.
Модель игнорирует семантику товаров (скоропортящиеся, хрупкие, тяжелые) и связанные с этим практические ограничения на порядок их приобретения. Это классическая ошибка, когда формальная строгость достигается за счет потери существенных содержательных деталей.
4. Проблема применимости точных методов
Для магазина среднего размера (|S| ≈ 20-30) точное решение TSP может оставаться вычислительно затратным. Какой компромисс между оптимальностью маршрута и скоростью его расчета является приемлемым в данном контексте?
Для решения бытовой задачи нет необходимости в абсолютно оптимальном маршруте. Достаточным является нахождение субоптимального, но логичного решения. Следовательно, применение точных алгоритмов для TSP избыточно; эффективнее использовать эвристические методы (правило ближайшего соседа) или аппроксимационные алгоритмы, дающие приемлемое решение за полиномиальное время.
Разбор примера показывает, что даже простая на первый взгляд задача при формализации затрагивает ключевые проблемы моделирования: корректность исходных данных, адекватность выбора и формулировки критерия, баланс между простотой и полнотой модели, учет вычислительной осуществимости методов исследования.
Цель задания: Научиться применять этапы моделирования к реальным процессам, выявлять проблемы формализации.
Текст в формате PDF или DOCX".
Постановка задачи — это содержательное описание "что нужно сделать", а формализация — перевод этого описания на строгий математический или логический язык с определением объектов, параметров и критериев.
Потому что она определяет возможность практического решения задачи. Экспоненциальный рост сложности (как в TSP) делает невозможным точное решение для больших размеров задачи, требуя применения приближённых методов.
Это формальное выражение (функция), которую нужно максимизировать или минимизировать. Критерий количественно определяет, что считать "хорошим" решением (например, минимальное время, максимальная прибыль).
Дата проведения: Следующее занятие (03.02)
Темы: 2.1-2.6 (Этапы моделирования, Формализация, Типы моделей и их свойства)
Формат: 10-15 минут, n вопросов разных типов
Что повторить:
Интерполяция — нахождение промежуточных значений внутри известного диапазона данных.
Пример: Стоимость доставки 10 кг — 500 руб., 20 кг — 900 руб. Найти стоимость 15 кг.
Экстраполяция — прогнозирование значений за пределами известного диапазона данных.
Пример: Средние продажи с января по ноябрь — 100 ед./мес. Спрогнозировать продажи в декабре.
Ключевое: Экстраполяция рискованна! За границами данных могут действовать новые факторы.
| Свойство | Линейная зависимость | Нелинейная зависимость |
|---|---|---|
| Суть | Изменение одной величины прямо пропорционально изменению другой | Изменения непропорциональны |
| График | Прямая линия | Кривая (парабола, экспонента и др.) |
| Формула | y = k × x + b(k и b — константы) | y = x², y = 2ˣ,y = √x, y = 1/x |
| Пример 1 | Стоимость связи: Тариф: 300 руб./мес + 5 руб./минута. Удвоение минут → удвоение доплаты | Тормозной путь: При удвоении скорости путь до остановки увеличивается примерно в 4 раза |
| Пример 2 (TSP) | Расстояние маршрута: Если ВСЕ расстояния на карте увеличить вдвое, то и любой маршрут станет вдвое длиннее | Время маршрута: Из-за пробок время растет быстрее расстояния: 10 км → 1 час, 20 км → не 2, а 5 часов |
Дискретная величина — принимает отдельные, «счетные» значения (часто целые числа).
Интуитивный пример: Лестница — вы на 1-м, 2-м, 3-м этаже, но не «на 2,75 этаже».
В моделях: Количество городов в TSP, количество предметов в рюкзаке.
Непрерывная величина — может принимать любое значение в интервале.
Интуитивный пример: Пандус — вы можете подняться на 1.5 м, 1.501 м, 1.5001 м.
В моделях: Расстояние между городами (15.73 км), вес предмета (2.457 кг).
Детерминированная модель — «Мир без сюрпризов». При одних входных данных результат всегда одинаков.
Пример: Рецепт торта — если четко следовать инструкции, результат предсказуем.
В моделях: Расчет длины маршрута по идеальной карте.
Стохастическая (вероятностная) модель — учитывает случайность, неопределенность.
Пример: Бросок игральных костей — знаем вероятности, но не конкретный результат.
В моделях: Прогноз времени доставки с учетом пробок, погоды, поломок.
Задача: "Прогноз времени доставки пиццы"
Дано:
Обсудите: Почему прогноз может оказаться неверным?
Скорость доставки меняется! Зависимость нелинейная — каждый следующий километр "дороже".
Дискретно:
Непрерывно:
"Время зарядки телефона имеет нелинейную зависимость от уровня заряда: первые 50% заряжаются быстрее, чем последние. Сам уровень заряда — непрерывная величина (может быть 47.3%). Количество полных циклов зарядки — дискретная величина (500 циклов). Время полной зарядки — детерминированная величина при одинаковых условиях."
Устная подготовка + краткие письменные заметки (для себя). Основная задача — быть готовым к тесту 03.02.
При экстраполяции мы выходим за границы известных данных. За этими границами могут начать действовать новые факторы, которые не учитывались в модели (например, сезонность, физические ограничения, изменение тренда).
Расстояния на карте складываются линейно: 10 км + 10 км = 20 км. Но время зависит от скорости, которая может меняться из-за пробок, рельефа, типа дороги. Поэтому время часто имеет нелинейную зависимость от расстояния.
Зависит от контекста! Например, "количество денег" — дискретно в копейках (нельзя заплатить 0.5 копейки), но непрерывно при безналичном расчете (можно списать 100.57 рубля). В модели важно определиться с нужной точностью.
Задача: Проанализировать задачи о рюкзаке и TSP как модели
Цель: Понять, как абстрактные задачи становятся математическими моделями реальных ситуаций
Инструкция: 1) Вспомните условия задач. 2) Определите элементы, связи и параметры. 3) Обсудите, какие реальные ситуации они описывают
Элементы: рюкзак (контейнер), предметы для упаковки
Связи: предметы конкурируют за место в рюкзаке; выбор одного предмета влияет на доступную ёмкость для других
Параметры: вместимость рюкзака, вес/объём каждого предмета, ценность каждого предмета
Ограничения: суммарный вес выбранных предметов не должен превышать вместимость рюкзака; максимизировать суммарную ценность
Реальные ситуации: загрузка контейнера, формирование инвестиционного портфеля, планирование раскроя материалов
Пример разбора "Задачи коммивояжера (TSP)":Элементы: города (точки), которые нужно посетить
Связи: дороги между городами, образующие полный граф; последовательность посещения
Параметры: расстояния/стоимости между городами, количество городов
Ограничения: посетить каждый город ровно один раз; вернуться в исходный город; минимизировать общую длину маршрута
Реальные ситуации: планирование маршрутов доставки, сверление отверстий в платах, составление расписаний
Цель задания: Научиться находить и анализировать модели в повседневной жизни, понимать их структуру и классификацию
Модель всегда проще оригинала, она содержит только те свойства, которые важны для решения конкретной задачи. Например, глобус — модель Земли, но на нём нет всех городов, дорог, людей.
Нет, более того — она не может быть точной копией. Суть моделирования как раз в упрощении. Иногда намеренное искажение (идеализация) помогает лучше понять суть явления.
Выбор зависит от цели: если нужно испытать прочность — материальная модель; если рассчитать траекторию — математическая; если объяснить принцип работы — графическая.