Лекция: ЗАДАЧИ.

Задание. По данной текстовой формулировке задачи построить ее математическую модель в виде задачи целочисленного линейного программирования (ЦЛП). Найти решение задач ЦЛП с помощью системы моделирования AMPL.

Варианты заданий

1. В области выделены шесть городов, которые нуждаются в службе скорой помощи. Станции скорой помощи могут быть расположены в некоторых или во всех шести городах. Однако в силу территориальной близости некоторых городов одна станция может обслуживать более одного населенного пункта. Единственным условием является время поездки; оно не должно превышать 15 минут. Приведенная ниже таблица содержит время поездки в минутах между шестью городами.

Сформулируйте задачу в виде задачи ЦЛП, оптимальное решение которой определит наименьшее количество станций и их расположение. Найдите оптимальное решение, используя систему моделирования AMPL.

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

Рис. 1.2. План музея.

3. Игральная доска состоит из девяти равных квадратов, расположенных 3x3. Требуется заполнить каждый квадрат числом из интервала от 1 до 9 таким образом, чтобы сумма чисел каждой строки, каждого столбца и каждой диагонали была равна 15. Определите числа в каждом квадрате для следующих случаев.

a) Числа в каждой строке и каждом столбце различны.

b) Числа во всех квадратах различны.

Запишите сформулированную задачу в виде задачи ЦЛП с ограничениями и решите ее с помощью системы моделирования AMPL.

4. Станок используется для производства двух взаимозаменяемых видов продукции. Производительность станка позволяет за день изготовить не более 20 единиц продукции первого вида и 10 единиц второго вида. Существует альтернативная наладка станка, позволяющая ежедневно изготовлять не более 12 единиц продукции вида 1 и 22 единицы вида 2. Анализ рынка показывает, что максимальный суммарный спрос на два вида продукции составляет 35 единиц ежедневно. Предположим, что прибыль от производства единицы продукции первого и второго вида составляет 10 и 12 грн. соответственно. Какая из двух возможных настроек станка должна быть выбрана? Сформулируйте задачу в виде задачи ЦЛП и решите ее с помощью системы моделирования AMPL.

5. Рассмотрите задачу планирования производственной линии, связанной с изготовлением двух различных изделий на одном станке. Последовательность выполнения необходимых для этого восьми операций изображена на рисунке 1.3 ниже. Пусть Pj— время выполнения j-й операции (j= 1, 2,…, n). Сроки сдачи изделий типа 1 и 2, которые определяются на основе некоторого исходного момента, равны dl и d2 соответственно. Предполагается, что любая выполняемая на станке операция должна быть завершена до начала другой операции. Сформулируйте задачу в виде задачи частично-целочисленного линейного программирования.

Рис. 1.3. Отношения предшествования операций для задачи 5.

6. Правая часть следующего ограничения может принимать одно из значений

, т.е.

.

Покажите, как можно представить это ограничение с помощью бинарных переменных.

7. Имеются следующие слова, состоящие из трех букв: AFT, FAR, TVA, ADV, JOE, FIN, OSF и KEN. Буквам алфавита приписаны числа (метки), начиная с А = 1 и заканчивая Z = 26. Каждое слово помечается числом, равным сумме числовых меток составляющих его трех букв. Например, слово AFT имеет метку 1+ 6 +20 = 27. Необходимо выбрать пять из заданных восьми слов таким образом, чтобы получить максимальную суммарную метку. Вместе с тем выбранные пять слов должны удовлетворять следующему условию: (сумма меток первых букв) < (сумма меток вторых букв) < (сумма меток третьих букв).

Сформулируйте задачу в виде задачи ЦЛП и найдите ее оптимальное решение, используя систему моделирования AMPL.

8. Фирма, специализирующаяся на грамзаписи песен, заключила договор с восходящей звездой эстрады на запись восьми песен. Продолжительность песен равна 8, 3, 5, 5, 9, 6, 7 и 12 минут соответственно. Фирма планирует использовать для записи двусторонние кассеты. Каждая сторона имеет длительность звучания 30 минут. Фирма намерена распределить песни на две стороны кассеты сбалансированным образом. Это значит, что продолжительность звучания песен на каждой стороне кассеты должна быть примерно одинаковой (насколько это возможно). Сформулируйте задачу в виде задачи ЦЛП и найдите оптимальное решение.

9. Для обеспечения безопасности студентов отдел безопасности университета устанавливает телефоны экстренного вызова на территории студенческого городка. Отделу желательно установить минимальное количество телефонов таким образом, чтобы на каждой из основных улиц этого городка был расположен по крайней мере один телефон. На рисунке 1.4 ниже представлены основные улицы (от А до К) студенческого городка.

Рис. 1.4. Схема улиц студенческого городка.

Сформулируйте задачу в виде задачи ЦЛП и найдите оптимальное решение, используя систему моделирования AMPL.

10. Построить модель ЦЛП для задачи о распределении ресурсов между проектами с целью максимизации прибыли. Имеется четыре проекта, для реализации которых нужно вкладывать некоторые средства. Исходные данные содержатся в таблице ниже.

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

12.Задача с постоянными платежами. Рассмотрим задачу

Минимизировать

при ограничениях

где

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

13.Сформулируйте задачу в терминах целочисленного программирования.

Максимизировать

при ограничениях

и выполняются либо три ограничения либо три ограничения .

14.Сформулируйте задачу в терминах целочисленного программирования.

Максимизировать

при ограничениях

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

15.Рассмотрим задачу

Максимизировать

при ограничениях

где, а х может принимать только значения 0, 1, 4, 6. Сформулируйте и решите эквивалентную задачу в терминах целочисленного программирования.

16.Сформулируйте постановку такой оптимизационной задачи. Студент университета решил в течение первого семестра прослушать лекции по пяти предметам, обозначенным А, В, С, D и Е. Каждый предмет читают в четырех группах, занимающихся в различное время. Обозначим через А1 группу 1, в которой читают предмет А, а через — начало занятий по этому предмету в данной группе. Для простоты предположим, что каждый предмет читают ежедневно, а занятия в группах начинаются в 8, 9, ..., 16 час. На выбор студента оказывает влияние время проведения занятий и репутация преподавателя. Пусть обозначает предпочтение, которое отдает студент предмету А в группе 1. К сожалению, он не может выбрать самое привлекательное, с его точки зрения, распределение предметов по группам в связи с перекрытием занятий во времени. Постройте модель выбора допустимого расписания, максимизирующего сумму оценок предпочтения студента.

17.Фирма снабжает своими изделиями сеть небольших ресторанов, отпускающих обеды на дом. Фирма стремится обеспечить каждому владельцу такого ресторана достаточную прибыль. Рассматривается возможность размещения n новых точек подобного типа в крупном микрорайоне. По имеющейся оценке, размещение ресторана в пункте j обеспечит получение приемлемого дохода Rj при условии, что в радиусе 5 км от него аналогичная торговая точка отсутствует. Примем, если пункты i и j размещения ресторанов находятся в пределах радиуса 5 км, и в противном случае. Фирма рассчитала все возможные и стремится выбрать схему размещения новых ресторанов, обеспечивающую максимизацию общего дохода. Сформулируйте эту задачу в виде математической оптимизационной модели.

18. Баланс сборочной линии. Сборочная линия состоит из ряда рабочих мест, на каждом из которых можно в процессе сборки изделия выполнять одну или более операций. Всего нужно выполнить шесть операций и изделие проходит по сборочной линии, двигаясь от рабочего места 1 к рабочему месту 2,… вплоть до последнего рабочего места. На каждую операцию затрачивается ti мин. Суммарное время выполнения всех операций на одном рабочем месте не должно превышать величины Т, называемой продолжительностью цикла линии. Примем в рассматриваемом примере Т = 10. Операции должны выполняться в определенном порядке. Отношение следования между операциями и их продолжительности заданы таблицей ниже. Оптимизационная задача заключается в минимизации числа рабочих мест при условии соблюдения заданной продолжительности цикла и сохранения заданного отношения следования. Постройте математическую оптимизационную модель этой задачи. (Указание: принять в качестве бинарной переменной, равной 1, если операция i выполняется на рабочем месте j. При осуществлении операций на каждом рабочем месте должен выполняться заданный порядок следования. Продолжительность выполнения всех операций на любом рабочем месте не должна превышать Т мин.)

19. Построить математическую модель задачи выполнимости SAT, заданной в конъюнктивной нормальной форме, состоящей из 7 элементарных дизъюнкций, называемых дизъюнктами:

в виде задачи ДО.

20. Построить модель линейного (одномерного) раскроя. Пусть имеется большое (практически неограниченное) число одномерных заготовок одинаковой длины L. Это могут быть трубы, прутки и т. п. Заготовки следует разрезать на полосы (детали) m типов; длина полосы типа i равна,. По данным числам L и можно составить матрицу всевозможных способов раскроя, где каждое указывает количество полос типа i, получающееся из одной заготовки при раскрое ее по способу j,. Таким образом, каждый способ раскроя j изображается столбцом матрицы; он характеризуется набором целых чисел, подчиненных лишь условию (суммарная длина выкраиваемых из заготовки полос не превосходит длины заготовки). Важно отметить, что матрица А этой задачи не задана изначально, а строится, быть может, уже в ходе решения задачи. Заданы потребности, в полосах типа i. Требуется удовлетворить эти потребности, раскроив минимальное число заготовок. (Указание: введите переменные, означающие количество заготовок, подлежащее раскрою по способу j, .

[1] Напомним, что в конце 50-х годов прошлого века, появились компьютеры, как инструмент, с помощью которого фактически стало возможно оптимизировать бизнес-процессы.

[2] В системе мобильной телефонной связи коммуникация между парами телефонов достигается за счет беспроводных соединений, использующих частоты из некоторой полосы. Задача назначения частот (ЗНЧ) (Frequency Assignment Problem (FAP)) является трудной дискретной задачей, тесно связанной с задачей раскраски графа.

[3] В [21] для решения этой задачи был использован оператор элиминации ‑ резолюция, которая по двум дизъюнктам и выводит дизъюнкт, называемый резольвентой, в которой литерал элиминирован. Оператор элиминации (в данном случае ‑ резолюция) порождает новые дизъюнкты, которым соответствуют новые ребра в графе взаимосвязей.

[4] Финкелъштейн Ю. Ю. Приближенные методы и прикладные задачи дискретного программирования. — М.: Наука, 1976.

[5] Михалевич В. С. Последовательные алгоритмы оптимизации и их применение. 1. // Кибернетика. 1965. № 1. С. 45-56; П. // Кибернетика. 1965. № 2. С. 85-88.

[6] Емеличев В. А., Комлик В. И. Метод построения последовательности планов для решения задач дискретной оптимизации. — М.: Наука, 1981. – 208 с.

[7] Хачатуров В. Р., Веселовский В. Е., Злотов А. В. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. ‑ М.: Наука, 2000. ‑ 354 с.