Методы уменьшения размерности задачи бинарного программирования

• Автор: Ахмедов, Фирудун Беюкага оглы
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Баку
• Количество страниц: 172 c. : ил

ГЛАВА I. МЕТОД ПОСЛЕДОВАТЕЛЬНОГО УМЕНЬШЕНИЯ РАЗМЕШОСТИ

ЗАДАЧИ БИНАРНОГО ПРОГРАММИРОВАНИЯ

§1.1. Обзор некоторых подходов к уменьшению размерности

задачи ЦЛП

§ 1.2. Уменьшение количества переменных и ограничений в

задаче бинарного программирования

§ 1.3. Описание алгоритма последовательного уменьшения

размерности задачи бинарной оптимизации

§1.4. О вычислительной реализации алгоритма ПУРЗ

§ 1.5. Некоторые результаты вычислительных экспериментов

Глава II. МЕТОДЫ ПОСТРОЕНИЯ НИЖНЕЙ ОЦЕНКИ ОПТИМАЛЬНОГО ЗНАЧЕНИЯ ЦЕЛЕВОЙ ФУНКЦИИ ЗАДАЧИ БИНАРНОГО ПРОГРАММИРОВАНИЯ
§2.1. Методы приближенного решения и методы, ориентированные на построение допустимого решения
§2.2. Методы типа последовательного назначения для приближенного решения задачи бинарного программирования с неотрицательными коэффициентами
§2.3. Алгоритмы улучшения приближенных решений задачи
бинарного программирования с неотрицательными
коэффициентами
§ 2.4. Обобщение методов типа последовательного назначения для приближенного решения некоторых классов
задач ЦЛП
§2.5. Пакет прикладных программ РАНЕЦ-1 для приближенного решения задачи бинарного программирования с неотрицательными коэффициентами

§ 2.6. Вычислительные эксперименты
Глава III. МЕТОДЫ ПОСТРОЕНИЯ ВЕРХНЕЙ ОЦЕНКИ ОПТИМАЛЬНОГО ЗНАЧЕНИЯ ЦЕЛЕВОЙ ФУНКЦИИ ЗАДАЧИ БИНАШОГО ПРОГРАММИРОВАНИЯ
§3.1. Некоторые подходы к вычислению верхней оценки оптимального значения целевой функции задачи
бинарного программирования
§ 3.2. Метод обхода вершин многогранника ограничений
задачи бинарной оптимизации
§ 3.3. Вычислительные аспекты алгоритма ОБХОД
§ 3.4. Результаты вычислительных экспериментов
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ I
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ

При решении таких важнейших проблем экономического развития страны, как повышение эффективности производства на основе комплексного внедрения достижений научно-технического прогресса, интенсификация производства, рациональное использование трудовых, материальных и финансовых ресурсов в народном хозяйстве, все больше применяются математические методы оптимизации.
Наряду с такой объективной необходимостью, все возрастающее использование экономико-математического моделирования и математических методов оптимизации основывается также, с одной стороны, на значительном развитии теории и вычислительных методов математического программирования, и с другой стороны, на огромном количестве АСУ различного уровня, функционирующих на базе мощной современной вычислительной техники и развивающихся, в первую очередь, за счет внедрения новых оптимизационных задач.
Одним из быстроразвивающихся разделов математического программирования является дискретное программирование, задачи которого выражаются в виде отыскания экстремума некоторой функции на некотором дискретном множестве. К задачам дискретной оптимизации сводятся многие оптимизационные задачи, имеющие важное народнохозяйственное значение. Это - задачи планирования работ, организации производства, размещения и реконструкции предприятий и др. [43, 54, 83,86,89] . За последние годы в связи с интенсивным развитием АСУ, теории и технологии вычислительных сетей в терминах дискретного программирования сформулированы многие задачи, возникающие при проектировании АСУ, вычислительных сетей и систем ЭВМ, а также при обработке данных в вычислительных центрах и системах [95,71,84]
Большинство из перечисленных практических задач выражается

Предположим, что при последнем выполнении шагов 4-5.2 алгоритма ПУРЗ удалось установить оптимальные значения некоторых переменных задачи (1.2.1) и выполняется условие £ V ]>. С-Х* > С *

В этом случае проводится проверка выполнения критерия (1.2.4) с использованием нового значения нижней оценки £ для всех переменных текущей остаточной задачи, как указано в алгоритме ПУРЗ (шаг 6.1). При этом необходимо использовать значения верхних оценок, вычисленных для всех переменных текущей задачи ранее на шагах 4.1 и 5.1. Значения этих верхних оценок сохраняются в процессе работы алгоритма именно с этой целью.
Пусть £, 1е N1^ ^ 1 п.} и ^ , С е Nс= Ц
(очевидно, /ЛиЛ/?^ { 1 уь] ) значения сохраненных
„ м
верхних оценок для целочисленных и дробных координат текущего X
В целях повышения эффективности вычислений повторную проверку критерия (1.2.4) целесообразно начинать с целочисленных координат Х^. Действительно, если будет выполнено условие Г: < £*ч£. С; х//е/У/ГО изменение текущей оптимальной симплекс-таблицы фактически сводится к удалению одной строки и одного столбца с последующим сжатием таблицы, как это описано в пункте 1.4.3 настоящего параграфа. Если же повторную проверку проводить сначала для дробных координат, то в случае выполнения условия £? < £^ + С. X,-. после проведения вычислений .для получения новой оптимальной симплекс-таблицы может оказаться, что некоторые переменные, которые в предшествующей оптимальной симплекс-таблице имели целочисленное значение, в новой таблице имеют дробное или альтернативное целочисленное значение. Это усложнит процесс преобразования оптимальной симплекс-таблицы при выполнении критерия для целочисленных координат Х*П в дальнейшем.
1,4.5. Удаление избыточных ограничений
С использованием текущей оптимальной симплекс-таблицы процесс