Задача о назначении (Assignment Problem) является частным случаем транспортной задачи и заключается в назначении $n$ работ $n$ исполнителям с минимальными суммарными затратами. Условие — каждый исполнитель получает ровно одну работу, и каждая работа выполняется ровно одним исполнителем. Венгерский алгоритм, предложенный Гарольдом Куном в 1955 году, стал классическим инструментом решения этой задачи за полиномиальное время.

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

Задача коммивояжера (Traveling Salesperson Problem, TSP) — одна из самых известных задач комбинаторной оптимизации. Коммивояжер должен посетить $n$ городов по одному разу и вернуться в исходную точку, пройдя при этом минимальное суммарное расстояние. Несмотря на внешнюю простоту, задача является фундаментальной для теории графов и транспортной логистики.

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