Полиномиально разрешимые и NP - трудные двухуровневые задачи стандартизации

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

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. Двухуровневая задача стандартизации в условиях
однозначности выбора потребителей (ДЗСОВ)
§1. Постановка задачи
§2. Свойство связности
§3. Свойство квазивыпуклости
§4. Свойство согласованности
§5. ДЗСОВ и полиномы от булевых переменных
§6. Свойство обобщенной квазивыпуклости
§7. Подходы к построению оценки оптимума
§8. Дополнительные замечания
8.1. ДЗСОВ при заданных покупательных способностях потребителя
8.2. ДЗСОВ с фиксированным числом выбираемых производителем изделий
8.3. ДЗСОВ с нулевыми начальными затратами производителя
ГЛАВА 2. Кооперативная и антикооперативная двухуровневые задачи
стандартизации (КДЗС и АКДЗС)
§1. Постановка задач
§2. КДЗС и свойство квазивыпуклости
§3. КДЗС и свойство квазивогнутости
§4. КДЗС и свойство связности
§5. Сводимость к задаче минимизации полинома от булевых переменных

§6. АКДЗС и свойство квазивогнутости
§7. АКДЗС и свойство квазивыпуклости
§8. АКДЗС и свойство связности
§9. Подходы к построению оценок оптимумов
ГЛАВА 3. Двухуровневая задача стандартизации с коррекцией
дохода (ДЗСКД)
§1. Постановка задач
§2. Кооперативная ДЗСКД
2.1. Сводимость к задаче с парой матриц
2.2. Свойства квазивыпуклости и квазивогнутости
2.3. Свойство связности
§3. Антикооперативная ДЗСКД
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

ВВЕДЕНИЕ
Одним из классов прикладных задач дискретной оптимизации, получивших широкое распространение, являются задачи стандартизации и размещения. К задачам стандартизации относятся, например, задачи выбора оптимальных параметрических рядов [14]. Под параметрическим рядом понимается совокупность однородных изделий, обладающих ограниченной заменяемостью, которые различаются числовыми значениями параметров и предназначены для удовлетворения заданных потребностей. Выбор оптимального параметрического ряда заключается в определении совокупности изделий с такими значениями параметров, при которых заданные потребности удовлетворяются с наименьшими суммарными затратами.
Как и большинство дискретных и комбинаторных задач, задачи стандартизации и размещения допускают решение с помощью некоторого процесса перебора. Однако число шагов переборного метода растет экспоненциально в зависимости от размера задачи. Способом анализа эффективности методов решения таких задач является теория сложности алгоритмов. Принято измерять сложность алгоритма необходимым для реализации алгоритма количеством арифметических операций, называемым его трудоемкостью, и ячеек памяти ЭВМ, требуемых для хранения исходной и промежуточной информации. Эффективными называют алгоритмы, трудоемкость которых ограничивается сверху некоторым полиномом от длины записи исходной информации.
Теоретическую оценку сложности различных классов задач дает теория КР-полных проблем, основанная на работах Кука [28] и Карпа [25]. В этой теории рассматривается класс № задач распознавания
Определим матрицы (%), (<%), i € /, ] € /, соотношениями
= а0; + а1] + + <4- 1,я = I,
1 < I < п, j £ ,7.
Система перестановок, порожденная матрицей (с ), совпадает с системой перестановок (г{
Д%- = с.. = а0у, Дс;у = — с- = ау,
1 < I < п, j £ J.
Поэтому
(у) = Е с?(1 - у,-) + Е Е ДУр; уд-
«е/ ьо !
С учетом леммы 1.5 получаем
(У) = £с?(1-У0 +
г'ё
где индексы «(_?) £ / определяются из равенств
с?г(у)у = ш1п{у I Уг = 0, * £ /}, ; С 7.
Положим = 1 — у1 хц — 1, если г = г(), и хг-у = 0 в противном случае (г 6 /, 3 С Используя эту теорему, в случае когда матрица (б-) квазивыпуклая, удается решить задачу (2)-(5) с меньшей трудоемкостью, так как в этом случае она сводится к задаче минимизации правильного полинома от булевых переменных на множестве неединичных векторов: