Урок 11. Дискретная оптимизация при ограниченных ресурсах
📋 План занятия
- 00:00–00:08 Постановка задачи и выделение ограничений.
- 00:08–00:20 Модель выбора грузов, полный перебор и жадный алгоритм.
- 00:20–00:35 Ручной расчёт для четырёх грузов.
- 00:35–00:40 Сравнение результатов и разбор домашнего задания.
📚 Основной материал
Бинарная модель выбора
Транспорт может выполнить один рейс. У каждой партии груза есть масса и ценность в рублях. Каждая партия либо отправляется целиком, либо остаётся на складе. Требуется получить наибольшую суммарную ценность и уложиться в грузоподъёмность.
Для каждого груза задаётся переменная xi. Если груз включён в рейс, она равна 1, если оставлен на складе, она равна 0. Поэтому запись 101 означает выбор грузов A и C при порядке A, B, C.
Ограничение по массе — Σ mixi ≤ M
Целевая функция — Σ vixi → максимум
Здесь mi — масса груза, vi — его ценность, M — грузоподъёмность. Знак Σ обозначает сумму по всем грузам. Решение считается допустимым, если оно выполняет ограничение. Оптимальное решение имеет наибольшую ценность среди допустимых.
Точное и приближённое решение
Грузоподъёмность учебного робота составляет 6 кг. Груз A весит 2 кг и даёт 30 баллов ценности, B — 3 кг и 40 баллов, C — 4 кг и 50 баллов.
Полный перебор. Для каждого груза возможны два решения, поэтому при трёх грузах получается 2³ = 8 наборов, включая пустой. Для каждого набора вычисляются масса и ценность.
| Набор | Масса, кг | Ценность, баллы | Допустим |
|---|---|---|---|
| 000 | 0 | 0 | Да |
| 001 | 4 | 50 | Да |
| 010 | 3 | 40 | Да |
| 011 | 7 | 90 | Нет |
| 100 | 2 | 30 | Да |
| 101 | 6 | 80 | Да |
| 110 | 5 | 70 | Да |
| 111 | 9 | 120 | Нет |
Набор 101 допустим при точном равенстве массы лимиту. Его ценность 80 баллов, и среди допустимых строк большей ценности нет.
Жадный алгоритм. Грузы упорядочиваются по убыванию ценности на килограмм. Получается порядок A (15), B (≈13,33), C (12,5). Если очередной груз помещается, он добавляется. При равном отношении раньше рассматривается груз с меньшим номером. После добавления A и B остаётся 1 кг. Груз C пропускается, итоговая ценность составляет 70 баллов. При сравнении близких отношений используются исходные числа без предварительного округления.
Жадный алгоритм даёт допустимый набор. Для неделимых грузов его ценность может оказаться ниже оптимальной, как в этом примере. Если груз пропущен, проверяются следующие по порядку грузы.
Лабораторная работа
Данные для лабораторной работы. Лимит составляет 7 кг. Массы грузов A, B, C и D равны 2, 3, 4 и 2 кг. Их ценности составляют соответственно 30, 40, 50 и 18 баллов.
Требуется перебрать вручную 16 наборов от 0000 до 1111 и для каждого зафиксировать массу, ценность и допустимость. Затем строится жадное решение и вычисляется разница в ценности. Порядок разрядов в коде соответствует порядку A, B, C, D.
Проверка классной работы
При лимите 7 кг полный перебор даёт набор 0110 (B и C) ценностью 90 баллов. Жадный алгоритм даёт набор 1101 (A, B и D) ценностью 88 баллов. Оба набора весят 7 кг. Разница составляет 2 балла.
📝 Домашнее задание
Модель и сравнение алгоритмов
В рабочей тетради заполняются пункты 1.1–1.3.
- 1.1 Исходные данные назначенного варианта и модель.
- 1.2 Полный перебор 16 наборов.
- 1.3 Жадное решение и сравнение результатов.
📤 Формат сдачи
На проверку представляется раздел 1 рабочей тетради.
