Дискретная математика БГУИР

Индивидуальное задание 7. Оптимизационные задачи на графах

Индивидуальное задание предусматривает решение двух задач.

Задача 7.1.

1. Найти пути минимальной длины из  вершины х_s в вершину х_t  нагруженного графа, длины ребер которого выбираются из таблицы по трехзначному шифру из таблиц в₁, в₂ , в₃. (i-я цифра шифра соответствует номеру строки в таблице в_{i )}. (шифры взять у Поттосиной С.А.)

1. Построить максимальное (минимальное) остовное дерево для данного нагруженного графа.

Задача 7.2 . Исходя из содержательного описания ситуации, сформулировать оптимизационную задачу в терминах теории графов. Для ее решения предложить алгоритм и возможное решение.

1. Задача о перекачке нефти. Пусть скорости перекачки  нефти между различными емкостями нефтеперерабатывающего завода заданы следующей таблицей

Найдите два лучших способа перекачки нефти.

2. Задача финансиста. Финансист крупной компании решил вложить ее  свободный капитал  в облигации, от которых можно было бы иметь доход в последующем пятилетнем периоде. В течение рассматриваемого пятилетнего периода можно реализовывать облигации и освобождающиеся при этом средства вкладывать в облигации других видов. В распоряжении финансиста имеется несколько видов облигаций. Как в такой ситуации финансист должен распределить во времени вложения имеющегося капитала?

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

3. Задача о транспортировке товара.  Предположим, что при транспортировке товара от пункта производства к пункту продажи на каждом из возможных участков маршрута теряется определенная доля товара. Каким путем следует выбрать маршрут перевозки, чтобы минимизировать величину потерь?

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

4. Задача фирмы «Электрон». Фирма,  выпускающая сложную электронную аппаратуру, получила заказ на несколько тысяч изделий, собирающихся из нескольких блоков. Руководство фирмы приняло решение разместить заказы на изготовление n блоков и выбрало n фирм-поставщиков, которые зарекомендовали себя как производители высококачественной продукции. Каждый заказ настолько велик, что фирма-поставщик не может выполнять более одного заказа. Каждому поставщику предложено определить стоимость выполнения заказа. Располагая этой информацией, фирма электронной аппаратуры должна заключить  n контрактов на поставку ей n видов блоков, минимизируя при этом свои общие затраты на приобретение комплектующих узлов со стороны.

5 .Задача агенства «Таксолюк». Транспортное агенство «Таксолюкс» разрабатывает план аренды транспортного оборудования на период n-1 лет. Агенство может выполнить свои обязательства  по перевозке грузов, взяв в аренду новую транспортную единицу в начале года 1 и эксплуатируя ее до начала года j<n. Если j<n , то агенство заменяет эту единицу в начале года j и эксплуатируют эту единицу до начала года k  и т.д. Величина затрат c_ij  включает арендную плату плюс ожидаемые расходы на ремонт и обслуживание оборудования, взятого в аренду в начале года i и замененного в начале года j. Предложить оптимальный план аренды оборудования.

6. Задача о мостах или об  «узких» местах нагруженного графа.  Рассматривается транспортная сеть, включающая мосты. Предполагается, что при превышении грузоподъемности некоторого моста последний разрушается. Определить максимальный вес груза, который можно транспортировать в сети из пункта А в пункт В без превышения грузоподъемности находящихся на маршруте движения транспорта мостов.

Примечание. Узким местом пути называется кратчайшая из входящих в него дуг. Длины дуг, соответствующие мостам, равны нагрузкам, допустимым для соответствующего моста.

7. Задача о пилотах. Во время мировой войны многие летчики из других стран бежали в Англию, чтобы поступить на службу в Королевские военно-вооруженные силы (КВВС). Для выполнения полетов требуется наличие двух пилотов, у которых умение управлять самолетом сочетается со знанием языка. КВВС заинтересован в том, чтобы в воздухе одновременно находилось максимальное количество самолетов. Предложите наилучший способ решения этой задачи, сведя ее к некоторой задачи теории графов.

Указание: Вершины графа – пилоты, ребра – отношение совместимости двух пилотов

8. Задача о маршрутах полетов. Предположим, что вершины графа соответствуют аэропортам, а ребра - этапам полетов (беспересадочные перелеты), которые осуществляются в заданное время. Любой маршрут  в этом графе соответствует  реально выполняемому маршруту полета. Имеется n возможных маршрутов и для каждого из них подсчитана стоимость. Найти множество маршрутов с наименьшей суммарной стоимостью и такое, что каждый этап полета содержится хотя бы в одном из выбранных маршрутов. Граф перелетов задан матрицей смежности.

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

10.Задача агента по недвижимости.  Агентство по продаже недвижимости имеет для продажи целый ряд домов и некоторое количество потенциальных покупателей. Каждый такой покупатель может проявить интерес к более чем одному дому. Агент может достаточно точно оценить, сколько каждый покупатель заплатит за представляющий для него интерес дом.

Поскольку агент получает 7% комиссионных отчислений от каждой сделки, он заинтересован в максимизации общего объема совершенных им продаж в долларах. Каким образом может быть достигнут  этот максимум?

11. Задача администратора гостиницы. Туристская группа из 30 человек должна быть размещена в гостинице. Каждый номер имеет две двуспальных кровати. Администратор желает разместить гостей в возможно меньшем числе номеров таким образом, чтобы в одном номере не находились лица противоположного пола, не связанные родственными узами. Допускаются сочетания соседей по номеру типа: муж-жена, отец-дочь, брат-сестра. Каким образом администратору гостиницы решить стоящую перед ним задачу?

12. Задача о комитете. Некоторый комитет должен быть сформирован таким образом, чтобы в него входил по крайней мере по одному представителю от каждого из 50 штатов и по крайней мере по одному представителю каждой из 65  имеющихся  в США основных этнических групп. Свои услуги для участия в работе комитета  в общенациональном масштабе предложили 170 человек. Необходимо определить состав комитета, включающего наименьшее число претендентов и удовлетворяющего всем отмеченным выше требованиям.

13. .Информационный поиск как задача о покрытии. Предположим, что некоторое количество информации хранится в N массивах информация длины C_j,, j = 1,2,…N. причем, на каждую единицу информации отводится по меньшей мере один массив. В некоторый момент времени делается запрос о M единицах информации. Они могут быть получены различными способами при поиске в массиве. Как решить задачу получения  всех M единиц информации и при этом произвести просмотр массивов наименьшей длины?

Указание. При решении воспользуйтесь двудольным графом, вершины   которого соответствуют единицам информации и массивам, а ребра соединяют некоторые вершины-единицы информации к некоторыми вершинами- массивами.  Решить задачу при всех C_j равных 1. 

14. Задача управляющего гостиницей. Управляющий гостиницей должен забронировать номера для новобрачных на следующий месяц. Он получил определенное количество заявок на бронирование с различными датами приезда и отъезда. Каждое возможное бронирование дает гостинице определенный доход, зависящий от того, кем являются клиенты ( студенты, служащие, персонал авиакомпаний и т.п.). Каким образом выработать расписание бронирования номеров, приносящее гостинице максимальный доход?

Указание:  представьте каждую заявку на бронирование дугой , соединяющей вершины, соответствующие датам приезда и отъезда.

15. Задача о развозке. Граф представляет сеть дорог, одна из вершин представляет склад, а остальные изображают потребителей. Транспорт, покидающий склад, снабжает товаром некоторых потребителей, после чего возвращается на склад. Стоимость маршрута равна C_j, j=1,2,…,N. Сколько машин следует использовать на разных маршрутах, чтобы в один и тот же день доставить всем потребителям товары )каждому доставляется все сразу же) и чтобы суммарная стоимость проходных маршрутов была минимальной.

16. Задача о размещении центров, покрывающих заданную область.  Территория разделена на N районов. Некоторый объект, расположенный в каком-либо районе, может контролировать или обслуживать не только этот район, но и соседние, граничащие с ним районы. Требуется найти наименьшее возможное число объектов и места для их расположения, чтобы обеспечить контроль или обслуживание всей территории.

Рассмотреть случаи а) территория размерности 4 на 4; б) территория размерности 6 на 6; в) территория размерности 7 на 7.

17. Задача мелкого вкладчика. Мелкий вкладчик решает вопрос о целесообразном размещении своего капитала в следующем году. Он располагает некоторым набором вариантов возможного размещения (можно положить деньги на сберкнижку, вложить средства в депозитарный сертификат, облигации и т.п) Для упрощения предположим, что вклады могут производиться и изыматься в начале каждого месяца. Как найти наилучшую стратегию вложения капитала?

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

18. Задача о покупке автомобиля. Предположим, что вам  необходимо иметь в своем распоряжении автомобиль на протяжении ближайших 5 лет до выхода на пенсию. В настоящее время имеется большой выбор автомобилей, которые вы можете купить, либо взять на прокат. Автомобили имеют различный срок эксплуатации и разную стоимость. Каким образом вы должны сделать выбор в такой ситуации?

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

19. Задача о доставке пассажиров. Предположим, что перед вами стоит задача найти кратчайшие маршруты полетов между всевозможными парами аэропортов Европы. При этом необходимо учесть, что из-за отсутствия въездных виз аэропорты некоторых стран могут быть закрыты для тех или иных пассажиров. Кроме того, возможны отмены некоторых полетов и, наконец, вследствие большой загрузки авиалиний, принадлежащих кратчайшему маршруту, им нельзя пользоваться. Выберете наиболее эффективный способ решения задачи. 

20.Задача о проекте строительств дорог. В управлении шоссейных дорог рассматривается проект  строительства новых дорог, которые должны связать N городов некоторого района (причем,  не обязательно непосредственно каждую пару городов). Стоимость прокладки дорог между каждой парой городов известна. Как построить проект минимальной стоимости?