Проект линейного программирования: Шоу Трумана

Проект линейного программирования: Шоу Трумана

Этот проект требует знания линейное программирование алгоритмы комбинаторной оптимизации, включая Branch & Bound.

комбинаторная оптимизация линейного программирования проекта по ветвям и границам

«Нам надоело смотреть, как актеры вызывают у нас фальшивые эмоции. Мы устали от пиротехники и спецэффектов. Хотя мир, в котором он живет, в некотором смысле фальшивый, в самом Трумэне нет ничего фальшивого. Никаких сценариев, никаких подсказок. Это не всегда Шекспир, но это настоящее. Это жизнь».

Начало проекта

Проект линейного программирования: линейное программирование Шоу Трумана

Реалити-шоу приносят миллиарды долларов в год. Но чтобы изменить ситуацию, вы всегда должны осмелиться на большее. Будучи молодым выпускником знаменитой кино- и аудиовизуальной школы Herr Guerard's Blinded Academy, вы должны пробиться в профессию, причем как можно быстрее.

Вот так у вас появилась идея воплотить «Шоу Трумана» в реальность. В городах-призраках нет недостатка, но ваш бюджет ограничен, и вам нужно наскрести деньги, где вы можете. Чтобы не потерять ни капли своего реалити-шоу, вам предстоит колесить по городу с камерами. Их конструкция сильно варьируется от одной точки к другой. Но, к счастью, вы помните лекции выдающегося профессора Герара о линейных целочисленных задачах (ЦЛП).

вершинное покрытие Где поперечный одного график г это набор ПРОТИВ вершин таким образом, что каждое ребро г = (В, Е) инцидентна хотя бы одной вершине ПРОТИВv ∈ S {\ Displaystyle v \ в S} »

Конкретно это сводится к следующему примеру: необходимо контролировать 6 полос движения и необходимо разместить минимальное количество камер с обзором 360°, чтобы каждую полосу видела хотя бы одна камера. Минимальное количество равно 2, и две камеры формируют вершинное покрытие.

комбинаторная оптимизация линейного программирования проекта по ветвям и границам

Проблема написана так:

комбинаторная оптимизация линейного программирования проекта по ветвям и границам

С продолжить) стоимость установки камеры вверху в. Иксв стоит 1, если мы построим камеру на вершине в, иначе 0. Для каждого ребра (н,в), мы устанавливаем следующее ограничение Иксав меньше 1.

комбинаторная оптимизация линейного программирования проекта по ветвям и границам

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

Рейтинг

  1. Построить соответствующий граф (2 балла)
  2. Сделать НПИ (3 балла)
  3. Найти основное решение (5 точек)
  4. Развертывание алгоритма Branch&Bound (10 точек)

Вам разрешено использовать любой симплекс для решения LP.

Делиться
ru_RURU
%d такие блоггеры, как: