Магистратура
  1. Введение в математический анализ  1.1. Теория множеств и логика в реальном анализе  1.1.1. Множества и операции в теории множеств и логике в реальном анализе  1.1.2. Отношения и функции  1.1.3. Логика и кванторы  1.1.4. Мощность множеств  1.2. Метрика  1.2.1. Введение в открытые и замкнутые множества в метрических пространствах  1.2.2. Сходимость последовательностей в метрическом пространстве  1.2.3. Непрерывная функция в метрическом пространстве  1.2.4. Компактность и полнота в метрических пространствах в реальном анализе  1.3. Последовательности и ряды  1.3.1. Сходимость последовательностей  1.3.2. Бесконечные ряды  1.3.3. Равномерная сходимость  1.3.4. Ряды степеней  1.4. Дискриминация  1.4.1. Теорема о среднем значении  1.4.2. Ряд Тейлора  1.4.3. Функции нескольких переменных  1.4.4. Частная производная  1.5. Интеграция  1.5.1. Интегрирование Римана и Лебега  1.5.2. Неправильные интегралы  1.5.3. Теория меры: фундаментальный инструмент в интеграции  1.5.4. Теорема Фубини  1.6. Функциональный анализ  1.6.1. Понимание пространства Банака  1.6.2. Пространства Гильберта  1.6.3. Операторы на пространствах  1.6.4. Спектральная теория
  2. Абстрактная алгебра  2.1. Понимание групп в абстрактной алгебре  2.1.1. Определения и примеры групп в абстрактной алгебре  2.1.2. Гомоморфизмы групп  2.1.3. Введение в нормальные подгруппы  2.1.4. Теорема Силова  2.2. Кольца и поля  2.2.1. Идеалы и фактор-кольца  2.2.2. Расширения полей  2.2.3. Теория Галуа  2.2.4. Полиномиальные кольца  2.3. Введение в модули в абстрактной алгебре  2.3.1. Гомоморфизм модуля  2.3.2. Свободные модули  2.3.3. Введение в тензорные произведения  2.3.4. Точная последовательность в модулях  2.4. Линейная алгебра  2.4.1. Векторное пространство  2.4.2. Собственные значения и собственные векторы  2.4.3. Векторное пространство с внутренним произведением  2.4.4. Диагонализация
  3. Топология  3.1. Общая топология  3.1.1. Открытые и закрытые множества  3.1.2. Компактность и связность  3.1.3. Непрерывные отображения  3.1.4. Аксиома отделимости  3.2. Алгебраическая топология  3.2.1. Понимание фундаментальных групп в алгебраической топологии  3.2.2. Гомотопия и гомология  3.2.3. Симплициальный комплекс  3.2.4. Точные последовательности в гомологии  3.3. Дифференциальная топология  3.3.1. Понимание многообразий в дифференциальной топологии  3.3.2. Гладкие функции  3.3.3. Тангенциальное и котангенциальное пространство  3.3.4. Векторные расслоения
  4. Дифференциальные уравнения  4.1. Обыкновенные дифференциальные уравнения  4.1.1. Дифференциальные уравнения первого порядка  4.1.2. Линейные уравнения второго порядка  4.1.3. Системы дифференциальных уравнений  4.1.4. Анализ устойчивости в обыкновенных дифференциальных уравнениях  4.2. Частные дифференциальные уравнения  4.2.1. Классификация уравнений с частными производными  4.2.2. Понимание рядов Фурье в уравнениях с частными производными  4.2.3. Введение в функции Грина  4.2.4. Метод характеристик  4.3. Динамические системы в дифференциальных уравнениях  4.3.1. Теория устойчивости  4.3.2. Предельные циклы в динамических системах  4.3.3. Теория хаоса  4.3.4. Теория бифуркаций
  5. Теория вероятностей и статистика  5.1. Теория вероятностей  5.1.1. Случайные переменные  5.1.2. Распределения вероятностей  5.1.3. Закон больших чисел  5.1.4. Центральная предельная теорема  5.2. Статистическое вывод  5.2.1. Проверка гипотез  5.2.2. Доверительный интервал  5.2.3. Байесовские методы  5.2.4. Метод максимального правдоподобия  5.3. Стохастические процессы  5.3.1. Цепи Маркова  5.3.2. Броуновское движение  5.3.3. Понимание процессов Пуассона  5.3.4. Мартингейлы: всестороннее исследование в вероятности и статистике
  6. Численный анализ  6.1. Численное решение уравнений  6.1.1. Оригинальное открытие  6.1.2. Итерационные методы  6.1.3. Анализ сходимости  6.1.4. Границы ошибок в численных решениях уравнений  6.2. Численная линейная алгебра  6.2.1. Факторизация матриц  6.2.2. Вычисление собственных значений  6.2.3. Разреженные матрицы  6.2.4. Методы предобработки  6.3. Численное интегрирование и дифференцирование  6.3.1. Методы квадратур  6.3.2. Введение в конечные разности  6.3.3. Анализ ошибок в численном интегрировании и дифференцировании  6.3.4. Адаптивные методы в численном интегрировании и дифференцировании
  7. Комплексный анализ  7.1. Комплексные числа  7.1.1. Полярная форма  7.1.2. Комплексные сопряженные  7.1.3. Экспоненциальная форма комплексных чисел  7.1.4. Корни из единицы  7.2. Аналитические функции  7.2.1. Уравнения Коши — Римана  7.2.2. Степенные ряды  7.2.3. Конформное отображение  7.2.4. Гармонические функции  7.3. Интегрирование на комплексной плоскости  7.3.1. Теорема Коши  7.3.2. Теорема о вычетах  7.3.3. Контурное интегрирование  7.3.4. Интегральные преобразования
  8. Математическая логика и основания  8.1. Пропозициональная логика  8.1.1. Таблицы истинности  8.1.2. Логическая эквивалентность в пропозициональной логике  8.1.3. Техники доказательства в пропозициональной логике  8.1.4. Решение в пропозициональной логике  8.2. Логика предикатов  8.2.1. Кванторы в предикатной логике  8.2.2. Формальные системы в предикатной логике  8.2.3. Полнота и правильность  8.2.4. Модельная теория  8.3. Теория множеств  8.3.1. Кардинальность и ординальность  8.3.2. Аксиоматические системы  8.3.3. Понимание теории множеств Цермело-Френкеля  8.3.4. Силы в теории множества
  9. Настройка  9.1. Линейное программирование  9.1.1. Метод симплекс  9.1.2. Двойственность в линейном программировании  9.1.3. Анализ чувствительности в линейном программировании  9.1.4. Методы внутренних точек  9.2. Нелинейное программирование  9.2.1. Градиентный спуск  9.2.2. Множители Лагранжа  9.2.3. Выпуклая оптимизация  9.2.4. Квадратичное программирование  9.3. Комбинаторная оптимизация  9.3.1. Алгоритмы графов  9.3.2. Целочисленное программирование  9.3.3. Сетевой поток  9.3.4. Алгоритмы аппроксимации
  10. Дискретная математика  10.1. Теория графов  10.1.1. Представление графов  10.1.2. Плоскость и цвет  10.1.3. Алгоритм поиска кратчайшего пути  10.1.4. Сетевой поток  10.2. Компаньонство  10.2.1. Перестановка и сочетание  10.2.2. Порождающая функция  10.2.3. Рекуррентные соотношения  10.2.4. Понимание принципа включения-исключения  10.3. Криптография  10.3.1. Применение теории чисел в криптографии  10.3.2. Симметричное и асимметричное шифрование  10.3.3. RSA и криптография на эллиптических кривых  10.3.4. Постквантовая криптография

Магистратура → Настройка → Комбинаторная оптимизация ↓


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


Целочисленное программирование - это раздел математической оптимизации или математического программирования. В этом контексте «оптимизация» означает выбор наилучшего элемента из заданного множества доступных альтернатив в соответствии с каким-либо критерием. Целочисленное программирование специально занимается задачами оптимизации, в которых некоторые или все переменные должны быть целыми числами.

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

  • Чисто целочисленное программирование (PIP): Все переменные решений должны принимать целые значения.
  • Смешанное целочисленное программирование (MIP): Только некоторые переменные должны быть целыми, а другие могут быть нецелыми.
  • Бинарное целочисленное программирование: Особый случай целочисленного программирования, где переменные ограничены 0 или 1. Часто используется для решений "да" или "нет".

Значение в комбинаторной оптимизации

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

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

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

Максимизировать (или Минимизировать): c 1 x 1 + c 2 x 2 + ... + c n x n 
С учетом: 
a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1 
a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2 
... 
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m 
Где: x 1 , x 2 , ..., x n — целые числа

Здесь c i обозначает коэффициенты целевой функции, которую вы хотите максимизировать или минимизировать, a ij обозначает коэффициенты ограничений, а b i обозначает границы ограничений.

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

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

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

  • Предметы: 4 предмета с весами w = [2, 3, 4, 5] и значениями v = [3, 4, 5, 6]
  • Емкость: Этот рюкзак может нести вес не более 5 человек.

Сформулируем задачу о рюкзаке с использованием целочисленного программирования:

Максимизировать: 3x 1 + 4x 2 + 5x 3 + 6x 4 
С учетом: 2x 1 + 3x 2 + 4x 3 + 5x 4 ≤ 5 
Где: x 1 , x 2 , x 3 , x 4 ∈ {0, 1}

Ограничение x i ∈ {0, 1} гарантирует, что каждый предмет может быть включен в рюкзак или нет.

Визуальное представление

5 (вес) 4 (вес) 3 (вес) 2 (вес)

Этот вид показывает упрощенную модель рюкзака с уложенным весом в порядке убывания.

Решение задач целочисленного программирования

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

1. Метод ветвей и границ

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

2. Метод отсечения

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

Практические приложения целочисленного программирования

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

Пример задачи: планирование задач

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

Пример:

  • Работы: Работа 1, Работа 2, Работа 3, время обработки 2, 4, 3 и крайние сроки 2, 6, 5 соответственно.

Сформулируем эту задачу на составление расписания с использованием целочисленного программирования:

Минимизировать: T 1 + T 2 + T 3 
С учетом: 
x 1,1 + x 1,2 + x 1,3 = 1 
x 2,1 + x 2,2 + x 2,3 = 1 
x 3,1 + x 3,2 + x 3,3 = 1 
Ограничения по завершению: 
C 1 = 2x 1,1 + 4x 2,1 + 3x 3,1 
C 2 = C 1 + 2x 1,2 + 4x 2,2 + 3x 3,2 
C 3 = C 2 + 2x 1,3 + 4x 2,3 + 3x 3,3 
Где: 
T i = max(0, C i - крайний срок i ) 
x i,j ∈ {0, 1}

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

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

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

Заключение

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


Магистратура → 9.3.2


U
username
0%
завершено в Магистратура

← предыдущая (9.3.1)
Алгоритмы графов
следующая (9.3.3) →
Сетевой поток

комментарии 



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

https://www.buddymath.com/g/9.3.2?bmal=ru