LAB #2. Решение задачи о рюкзаке. С ограничениями
Задача о рюкзаке — это классическая проблема комбинаторной оптимизации, где требуется выбрать набор предметов с максимальной ценностью при ограничении по весу.
Основные характеристики задачи:
Основные характеристики задачи:
- Каждый предмет имеет вес и стоимость
- Предметы нельзя делить на части
- Можно брать каждый предмет только один раз
- Цель — максимизировать общую стоимость при соблюдении весового ограничения
МОДЕЛЬ
Система ограничений:
- Временные ограничения: tijk ≤ Tmax
- Ограничения по загрузке: Qmin ≤ qijk ≤ Qmax
- Балансовые ограничения: Σj,k xijk = Di
Основная целевая функция:
Z = Σi=19 Σj=13 Σk=12 (cijkxijk - λRijkxijk) → min
Z = Σi=19 Σj=13 Σk=12 (cijkxijk - λRijkxijk) → min
При следующих условиях:
- Di — спрос на перевозку
- Qmin, Qmax — минимальная и максимальная загрузка
- xijk ≥ 0 — неотрицательность переменных
Алгоритм реализации
Этапы внедрения:
- Сбор исходных данных
- Расчёт коэффициентов надёжности
- Определение весового коэффициента λ
- Решение оптимизационной задачи
- Проверка условий оптимальности
- Корректировка решения при необходимости
Детальное описание этапов:
- На этапе 1 собирается информация о:
- Стоимости перевозок cijk
- Временных параметрах tijk
- Нагрузках qijk
- На этапе 2 рассчитывается:
Rijk = 1 / (1 + Eijk/Sijk)
- На этапе 3 определяется значение λ в зависимости от:
- Требуемого уровня надёжности
- Бюджетных ограничений
Основные определения
Экспертная оценка — субъективное мнение специалистов
Статистическая оценка — анализ объективных данных
Источники данных для оценки загруженности дорог
Открытые источники для сбора статистики:
- Яндекс.Пробки — текущая загруженность дорог
- Google Maps — статистика времени в пути
- 2ГИС — информация о дорожной ситуации
- Официальные сайты городских служб
- Социальные сети — группы местных водителей
Методы получения экспертного мнения
Способы сбора экспертных оценок:
- Анкетирование водителей/пешеходов
- Опросы в социальных сетях
- Анализ отзывов на картах
- Изучение форумов местных жителей
Практический пример сбора данных
Статистические данные:
- Замер времени прохождения маршрута
- Сбор данных о пробках
- Анализ интернет-отзывов
Экспертные оценки:
- Анализ отзывов водителей
- Изучение обсуждений
- Сбор мнений из форумов
Пример расчета
Сбор данных:
- Измерение времени в пути
- Сбор отзывов
- Анализ пробок
Обработка данных:
Среднее время в пути:
- Утро: 20 минут
- День: 15 минут
- Вечер: 25 минут
Шкала оценки загруженности:
- 1 балл — свободное движение
- 2 балла — небольшие пробки
- 3 балла — средние пробки
- 4 балла — серьезные пробки
- 5 баллов — парализация движения
Расчет показателей:
Средняя загруженность: (20 + 15 + 25) / 3 = 20 минут
Оценка по шкале: 3 балла (средние пробки)
Оценка по шкале: 3 балла (средние пробки)
Формирование итоговой оценки
R = α ⋅ E + (1 − α) ⋅ S
Где:
- E — экспертная оценка (из отзывов)
- S — статистическая оценка (время в пути)
- α — вес экспертного мнения (например, 0.4)
Пример расчета:
| Параметр | Значение |
|---|---|
| Экспертная оценка (E) | 3 (из анализа отзывов) |
| Статистическая оценка (S) | 3 (из замеров времени) |
| Вес экспертного мнения (α) | 0.4 |
| Итоговая оценка (R) | 0.4 ⋅ 3 + 0.6 ⋅ 3 = 3 |
Выводы
Полученная итоговая оценка R = 3 указывает на наличие средних пробок на исследуемом маршруте.
Влияние количества экспертов на вес экспертной оценки
Основные положения:
- Количество экспертов напрямую влияет на вес экспертной оценки в итоговой формуле
- Чем больше экспертов, тем выше может быть вес их мнения
- Существует оптимальный баланс между количеством экспертов и весом их оценки
Формула итоговой оценки
R = α ⋅ E + (1 − α) ⋅ S
Где:
- α — вес экспертного мнения
- E — экспертная оценка
- S — статистическая оценка
Как меняется вес α в зависимости от количества экспертов
Рекомендации по выбору веса:
- При 3-4 экспертах: α = 0,3 − 0,4
- При 5-6 экспертах: α = 0,4 − 0,5
- При 7-8 экспертах: α = 0,5 − 0,6
- При 9+ экспертах: α = 0,6 − 0,7
Примеры расчета с разным количеством экспертов
Ситуация 1: 3 эксперта, α = 0,4
Оценки экспертов: 4, 5, 3
E = (4 + 5 + 3) / 3 = 4
S = 3 (статистическая оценка)
R = 0,4 ⋅ 4 + 0,6 ⋅ 3 = 3,4
Ситуация 2: 6 экспертов, α = 0,5
Оценки экспертов: 4, 5, 3, 4, 4, 4
E = (4 + 5 + 3 + 4 + 4 + 4) / 6 = 3,83
S = 3
R = 0,5 ⋅ 3,83 + 0,5 ⋅ 3 = 3,42
Ситуация 3: 9 экспертов, α = 0,6
Оценки экспертов: 4, 5, 3, 4, 4, 4, 3, 4, 4
E = (4 + 5 + 3 + 4 + 4 + 4 + 3 + 4 + 4) / 9 = 3,78
S = 3
R = 0,6 ⋅ 3,78 + 0,4 ⋅ 3 = 3,47
Факторы, влияющие на выбор веса α
Критерии определения веса:
- Квалификация экспертов — чем выше квалификация, тем больше может быть вес
- Однородность мнений — при согласованности оценок можно увеличить вес
- Актуальность темы — для быстроменяющихся ситуаций вес может быть ниже
- Доступность статистических данных — при качественной статистике вес экспертного мнения может быть снижен
Пример практического исследования маршрутов доставки
Исходные данные
Склады:
- Склад А: г. Москва, ул. Ленина, 1
- Склад Б: г. Москва, ул. Гагарина, 5
Район доставки (4 адреса):
- Адрес 1: ул. Центральная, 10
- Адрес 2: ул. Советская, 15
- Адрес 3: ул. Первомайская, 20
- Адрес 4: ул. Молодежная, 25
Типы транспорта:
- Легковой автомобиль
- Грузовой фургон
Статистические данные
Время в пути (мин) для грузового авто:
Утро:
- Склад А → Адреса: 25-30 мин
- Склад Б → Адреса: 30-35 мин
День:
- Склад А → Адреса: 20-25 мин
- Склад Б → Адреса: 23-28 мин
Вечер:
- Склад А → Адреса: 35-40 мин
- Склад Б → Адреса: 40-45 мин
Экспертные оценки
Критерии оценки маршрутов:
- 1 балл — отлично
- 2 балла — хорошо
- 3 балла — удовлетворительно
- 4 балла — плохо
- 5 баллов — очень плохо
Экспертные оценки (среднее из 5 экспертов):
Склад А:
- Легкий транспорт: 1.8 балла
- Грузовой транспорт: 2.1 балла
Склад Б:
- Легкий транспорт: 2.2 балла
- Грузовой транспорт: 2.5 балла
Расчет коэффициентов надежности
K = \frac{1}{1 + \frac{E}{S}}
где:
- E — экспертная оценка
- S — среднее статистическое время
Результаты расчета
Склад А:
Легкий транспорт:
- Утро: K = 0.85
- День: K = 0.92
- Вечер: K = 0.78
Грузовой транспорт:
- Утро: K = 0.82
- День: K = 0.88
- Вечер: K = 0.75
Склад Б:
Легкий транспорт:
- Утро: K = 0.80
- День: K = 0.85
- Вечер: K = 0.72
Грузовой транспорт:
- Утро: K = 0.78
- День: K = 0.82
- Вечер: K = 0.70
Время в пути (мин) для легкового авто:
Утро (8:00-9:00):
- Склад А → Адреса: 20-25 мин
- Склад Б → Адреса: 25-30 мин
День (12:00-13:00):
- Склад А → Адреса: 15-20 мин
- Склад Б → Адреса: 18-22 мин
Вечер (18:00-19:00):
- Склад А → Адреса: 30-35 мин
- Склад Б → Адреса: 35-40 мин
html
Применение весового коэффициента надежности
Применение весового коэффициента надежности в оптимизации маршрутов
\( Z = \sum_{i=1}^{9} \sum_{j=1}^{3} \sum_{k=1}^{2} (c_{ijk}x_{ijk} - \lambda r_{ijk}x_{ijk}) \rightarrow \text{min} \)
Где:
- \( c_{ijk} \) — стоимость перевозки по маршруту
- \( x_{ijk} \) — объем перевозок
- \( r_{ijk} \) — коэффициент надежности маршрута
- \( \lambda \) — весовой коэффициент важности надежности
Роль коэффициента λ в оптимизации
Влияние на целевую функцию:
- При \( \lambda = 0 \) — минимизируется только стоимость
- При увеличении \( \lambda \) — растет значимость надежности
- При максимальном \( \lambda \) — приоритет отдается надежным маршрутам
Практическое применение коэффициента
Варианты использования:
- Для срочных доставок: \( \lambda = 0.7-0.8 \)
- Для стандартных грузов: \( \lambda = 0.5-0.6 \)
- Для хрупких грузов: \( \lambda = 0.8-0.9 \)
Пример расчета:
При \( \lambda = 0.6 \): \( Z = \sum (c_{ijk}x_{ijk} - 0.6r_{ijk}x_{ijk}) \)
Задание
- балл: 0описание:
- Выбрать два "склада", и район доставки с 4 "адресами" существующими в любом городе России. Выбрать два типа "транспорта"
- на основе данных из открытых источников - сформировать статистические оценки, для времени маршрута в зависимости от времени суток.(2-3 времени.)
- на основе данных из открытых источников или собственного исследования сформировать экспертные оценки для тех же маршрутов.
- рассчитать коэффициенты надежности маршрутов для каждого вида транспорта опираясь на рассчитанный коэффициент надежности.
- балл: 0intlinprogописание:
- реализация решения с использование intlinprog, с собственными ограничениями трех новых критериев зависимых от общего целого, не являющегося "аналогом стоимости"
вывод результата расчета с пояснения, обязательно для допуска к защите!
Примеры данных
