Генерирование столбцов в симплекс-методе : Вопросы программной реализации

• Автор: Ли Хе Ран
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Санкт-Петербург
• Количество страниц: 150 с. : ил

Оглавление
Введение
1 Симплекс-метод с генерированием столбцов
1.1 Использование DLL в симплекс-методе
1.1.1 Задача линейного программирования
1.2 Реализация симплекс-метода с DLL
1.2.1 Индексы столбцов
1.3 Необходимые DLL
1.3.1 Процедура RunSimplex
1.3.2 Мультипликативная форма обратной матрицы
1.3.3 Хранение мультипликаторов
1.4 Описание программных модулей
1.4.1 Ведущая программа SMX
1.4.2 Решатель линейных систем Solver
1.4.3 Библиотека системных столбцов Orts
1.4.4 Библиотека основной задачи Problem
2 Задача о прокладке кабелей
2.1 Постановка задачи
2.2 Решение задачи с помощью генерирования столбцов
2.2.1 Вспомогательная экстремальная задача
2.2.2 Варианты решения вспомогательной задачи
2.2.3 Подготовка исходных данных
2.2.4 Первый метод. Перебор ^-оптимальных решений . .
2.2.5 Второй метод. Проверка совместимости на всех шагах
2.2.6 Третий метод. Предварительная подготовка для сокращения проверок
2.2.7 Четвертый метод. Предварительное упорядочение .

2.2.8 Сравнение методов
2.2.9 Программная реализация четвертого метода
2.3 Реализация DLL Problem
2.4 Посгоптимизационое улучшение решения
Заключение
А Программы
А.1 Общие описания для всех модулей системы
А.2 Ведущая программа SMX
А.З Модуль LSolver для решения линейных систем
A.4 Модуль Ort для работы с системными переменными
В Задача о прокладке кабелей
B.1 Модуль Problem
В.2 Программа постоптимизационной обработки

Введение
Общая характеристика работы
Актуальность темы
Разработка программной поддержки для решения задач линейного программирования с помощью генерирования столбцов остается актуальной задачей. Использование метода генерирования столбцов много лет было особенностью советского подхода к решению больших задач линейного программирования, и в Ленинградском (С.-Петербургском) университете было предложено несколько разновидностей его реализации 1. Теперь современное средство “сборочного программирования” — библиотеки динамического вызова (БЬЬ) — позволяет более эффективно реализовать эти многолетние разработки.
В последние годы интерес к генерированию столбцов стал расти на Западе, и сравнительно недавно такая возможность была добавлена в широко распространенный коммерческий пакет СРЬЕХ, причем это добавление было достигнуто по другой идее — за счет создания специального “пула столбцов”, который должен периодически пополняться.
Цели работы
Изучить вопросы, связанные с созданием модульной системы симплекс-метода, основанной на объектно-ориентированном стиле программирования и использовании библиотек динамического вызова, и опробовать эту систему на конкретной задаче. В качестве этой конкретной задачи была выбрана интересная для приложений задача о прокладке кабелей в судне — своеобразная задача составления производственного расписания.
1Обзор задач, решаемых этим методом, и подходов см. в статье Л. В. Канторовича и И. В. Романовского [5].

vec_p: array of real);
// Вычисляет элементы мультипликатора, используя массив // vec_p и если они больше нуля сохраняет их в массиве // Sbuf.

procedure Primal(var x: array of real; b: array of real);
// Вычисляет решение прямой системы, вызывая multDX //
procedure DuaKc: array of real; var v: array of real);
// Вычисляет решение двойственной системы, вызывая multXD

procedure Update(var sCh: PDataChannel);
// Корректирует представление обратной базисной матрицы,
// подробное описание этой процедуры будет дано ниже

procedure Init(var sCh: PDataChannel);
// Готовит обратную базисную матрицу, для этого вызовами II процедур PrPtrC[dllnum](problemExpand,sCh) находит II каждый столбец соответствующий базисной паре II (dllnum,handle). Эти пары берет из массива базисных // элементов BasicSet, ссылка на который находится II в канале обмена.

procedure order(var BS: array of spos);
// По окончании всех процедур возвращает исходный порядок // базисных переменных //
procedure close;
II Завершает все процедуры и закрывает все открытые файлы

Когда в SMX вызывается SolvSys(solmodOpen, myCh), Solver вызывает процедуру Init(sCh). В ней готовится матрица, обратная начальной базисной матрице, данные о которой передаются через канал обмена myCh. Вызовами процедур PrPtrC [dllnum] (problemExpand, sCh) алгоритм последовательно получает каждый столбец, соответствующий очередной паре [dllnum, handle), и вычисляет элементы мультипликатора для него. Мультипликаторы после их вычисления сохраняются в сжатом виде в массиве Sbuf.