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

• Автор: Пащенко, Михаил Георгиевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Новосибирск
• Количество страниц: 79 с.

ОГЛАВЛЕНИЕ

Введение
Глава 1. Многоэтапная задача
§1.1. Постановка задачи
§ 1.2. Нижние оценки
§ 1.3. Алгоритм решения релаксированной задачи
§ 1.4. Построение допустимого решения многоэтапной задачи
§ 1.5. Численный эксперимент
Глава 2. Двухуровневая многоэтапная задача
§ 2.1. Постановка задачи
§ 2.2. Нижние оценки
§ 2.3. Соотношение оценок П1Ж и РЬБ
§ 2.4. Результаты тестовых расчетов
Глава 3. Динамические задачи
§ 3.1. Постановка задачи
§ 3.2. Нижние оценки
§ 3.3. Общая схема алгоритма
§ 3.4. Динамические задачи с ограничениями на номенклатуру
изделий
§ 3.5. Динамические задачи с фактором серийности
§ 3.6. Результаты численных расчетов
Глава 4. Двухуровневая динамическая задача
§4.1. Постановка задачи
§ 4.2. Нижние оценки
§ 4.3. Алгоритмы решения релаксированных задач
Список литературы
Введение
В данной работе рассматриваются динамические задачи выбора оптимального состава системы технических средств. На содержательном уровне задача формулируется следующим образом. Под системой технических средств будем понимать множество изделий, объединяемых общностью функционального назначения. Система технических средств характеризуется своим составом, который определяется набором образцов изделий и количеством изделий каждого образца. Область возможного выбора средств задается исходным рядом, т.е. перечнем образцов, которые в принципе могут войти в состав системы. В исходный ряд могут быть включены как образцы, находящиеся в производстве, так и перспективные образцы. Сфера применения исследуемой системы технических средств характеризуется совокупностью работ, которые должны быть выполнены с использованием рассматриваемых технических средств. Процесс выполнения работ разбивается на несколько этапов (лет), для каждого из которых известны объемы выполняемых работ. Задача состоит в том, чтобы найти такой набор технических средств (состав системы), который позволил бы выполнить все работы и имел бы минимальные суммарные затраты, связанные с разработкой, производством и эксплуатацией технических средств. Динамические задачи являются естественным обобщением задач, в которых осуществляется разовый выбор оптимального состава системы технических средств, так называемых статических задач. С математической точки зрения задача выбора оптимального состава
системы технических средств относится к числу КР-трудных задач дискретной оптимизации даже в статическом варианте.
Первые постановки динамических задач выбора оптимального состава системы изучались в работе [5] в 1971 г. В ней получены первые результаты и, в частности, найдено точное решение задачи в предположении, что в определенные моменты времени может производиться полная замена старой системы технических средств на новую. В монографии [3] рассматривается простейшая динамическая задача выбора оптимального состава. Для ее решения предлагается алгоритм ветвей и границ, в котором в качестве нижней оценки используется некоторое достаточно хорошее решение двойственной задачи линейного программирования. В работе [4] эта же вычислительная схема реализована для модели, включающей некоторые дополнительные ограничения на процесс функционирования системы технических средств.
Одними из наиболее существенных и часто встречающихся в практических приложениях дополнительных ограничений являются ограничения на объемы производства технических средств. Задача выбора оптимального ряда изделий с ограничениями на объемы производства в статической постановке также рассматривалась в монографии [3], где для ее решения были использованы идеи метода ветвей и границ с модифицированным алгоритмом вычисления нижней границы. Однако применение ранее разработанных методов решения для динамической задачи связано со значительными трудностями, поскольку не удается получить приемлемых оценок для ее линейной релаксации.
В начале семидесятых годов была высказана одна очень продуктивная идея. Для многих ]УР-трудных задач множество ограничений можно разбить на две группы таким образом, что удаление одной из них превращает задачу в полиномиально-разрешимую. Эти ограничения заносятся в целевую функцию с некоторыми коэффициентами, так

технических средств, в состав которых входят узлы &-го вида.
Введем следующие обозначения:
у° — количество изделий г-го образца, имеющихся в составе системы;
с° — стоимость разработки изделий г-го образца;
с1°к — стоимость разработки узла к-го вида;
с; — стоимость производства одного изделий г-ого образца, включая стоимость входящих в его состав узлов;
Ц — максимальный объем производства изделий г-го образца;
рц — число изделий г-го образца, требующихся для выполнения работы;
Су — стоимость выполнения у-й работы;
вц — доля потерь изделий при выполнении работ на 1-м этапе.
Введем в рассмотрение следующие переменные:
1, если изделия г-го образца включены в состав системы,
О в противном случае;
1, если узлы к-го вида включены в состав системы ,
О в противном случае;

> 0 — объем производства изделий г-го образца;
Ху > О— доля 1~т работы, выполняемая изделиями г-го образца.
С использованием введенных обозначений двухуровневая задача выбора оптимального состава системы может быть записана следующим образом. Найти
2р ~ шт{Е(с- + с,- ьг + Е сч + Е Ук} (2.1)
101 кеК
при ограничениях:
ЕЪ’ = 11 3 (2.2)
г'е

' Рг] ЗСц "Ь г" &Ц' Р13 Ъ £ I I € Х», (2.3)
№1 1'