Порядок выполнения работы

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНОЙ РАБОТЕ

"Векторная решетка"

 

Порядок выполнения работы

 

1. Рассмотреть содержательную постановку оптимизационной задачи.

2. Осуществить ее формализованное описание как линейной комбинаторной задачи дискретного программирования. Привести эту задачу к ограничениям типа " " или " ", и также, если задача двухиндексная, то преобразовать ее к одноиндексной форме записи, осуществив сквозную перенумерацию оптимизационных переменных. Определить для рассматриваемой задачи содержательный смысл следующих параметров и переменных: m, n, i, j, c[j], a[i,j], b[i], x[j], - а также целевой функции и основных ограничений.

3. Подготовить исходные данные для машинного эксперимента:

по задаче малой размерности (ЗМР): n 10;

по задаче большой размерности (ЗБР): n 16 - 20.

Исходные данные должны быть подготовлены так, чтобы они не приводили к тривиальному решению.

4. Провести следующие машинные эксперименты с использованием программы LAB 302\TOP\ SVL:

- решить ЗМР при включенных в работу всех критериях метода неявного перебора по векторной решетке (МНПВР) с осуществлением трассировочной печати результатов работы программы;

- многократно решить ЗБР без трассировки с различными комбинациями включенных в работу критериев МНПВР, фиксируя при этом время решения задачи и количество рассматриваемых точек и их процент по отношению к полному перебору.

5. По результатам этих экспериментов составить следующую таблицу:

№	Включение критериев	Колитчество рассмотренных точек	% рассмотренных точек	Время счета
1	Все выключены
2	КН
3	КПИА
4	КПП
5	КН+КПИА
6	КН+КПП
7	КПП+КПИА
8	КН+КПП+КПИА

 

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

7. Составить отчет, отображающий все перечисленные выше пункты.

 

 

Варианты содержательных постановок оптимизационных задач

1. Задача об оптимальной комплектации приборами многоцелевого ЛА.

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

 

2. Задача о назначении механизмов на объекты (m x n)

На территориально разнесенных n объектах необходимо одновременно выполнить работы несколькими однородными механизмами (всего механизмов m). Известно время перемещения каждого механизма до каждого объекта. Решена задача количественного распределения механизмов по объектам: на каждый j-ый объект должно быть выделено mj механизмов (). Необходимо распределить конкретные на определенные объекты так, чтобы суммарное время перемещения механизмов к объектам было бы минимальным.

 

3. Задача о назначении механизмов на работы (n x n)

 Имеется n механизмов и такое же количество работ. Каждый механизм может выполнить любую работу. С выполнением каждой работы связаны затраты, определяемые номером работы и номером механизма. Каждый механизм может выполнить лишь одну работу. Для выполнения отдельной работы необходим лишь один механизм. Необходимо так распределить механизмы по работам, чтобы суммарные затраты на выполнение работ были минимальными.

 

4. Задача о назначении m механизмов на  n работ (m < n)

 Каждый механизм может выполнить любую работу. С выполнением каждой работы связаны стоимостные затраты, определяемые номером работы и номером механизма. Каждый механизм может выполнить лишь одну работу. Для выполнения отдельной работы необходим лишь один механизм.  Если некоторая работа не выполнена, то возникают определенные стоимостные потери, определяемые номером работы.  Необходимо так распределить механизмы по работам, чтобы суммарные затраты на выполнение работ и потери от невыполнения некоторых из них были минимальными.

 

5. Задача о назначении m механизмов на  n работ (m > n)

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

 

6. Задача о поднятии плит

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

 

Рис.2.6. Расположение кабелей и плит

 

 

7. Задача тематического планирования

Перед началом планового периода в портфеле заказов разрабатывающего предприятия имеется n тем, из которых необходимо сформировать тематический план. Выполнение определенной темы характеризуется эффективностью, задаваемой одним числом, и затратами складируемых ресурсов (всего ресурсов m). В тематический план может быть включено не более k тем (k≤ n). Сформировать тематический план разрабатывающего предприятия, таким образом, чтобы при выполнении указанных выше ограничений суммарная эффективность включенных в него тем была максимальной.