автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Генерирование столбцов в симплекс-методе

Введение

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 Постоптимизационое улучшение решения

Общая характеристика работы

Актуальность темы

Разработка программной поддержки для решения задач линейного программирования с помощью генерирования столбцов остается актуальной задачей. Использование метода генерирования столбцов много лет было особенностью советского подхода к решению больших задач линейного программирования, и в Ленинградском (С.-Петербургском) университете было предложено несколько разновидностей его реализации Теперь современное средство "сборочного программирования" — библиотеки динамического вызова (DLL) — позволяет более эффективно реализовать эти многолетние разработки.

В последние годы интерес к генерированию столбцов стал расти на Западе, и сравнительно недавно такая возможность была добавлена в широко распространенный коммерческий пакет CPLEX, причем это добавление было достигнуто по другой идее — за счет создания специального "пула столбцов", который должен периодически пополняться.

Цели работы

Изучить вопросы, связанные с созданием модульной системы симплекс-метода, основанной на объектно-ориентированном стиле программирования и использовании библиотек динамического вызова, и опробовать эту систему на конкретной задаче. В качестве этой конкретной задачи была выбрана интересная для приложений задача о прокладке кабелей в судне — своеобразная задача составления производственного расписания.

1 Обзор задач, решаемых этим методом, и подходов см. в статье J1. В. Канторовича и И. В. Романовского [5].

Целями диссертационного исследования было:

• предложить разбиение системы на автономные модули;

• построить модель обмена информацией между модулями;

• разработать типовую структуру модуля, описывающего конкретный класс задач линейного программирования;

• разработать в рамках принятой типовой структуры конкретный модуль и решить для него вопросы проверки оптимальности текущего решения (что требует создания алгоритма для решения специальной задачи дискретной оптимизации), вопросы построения эффективного начального решения и алгоритма постоптимизационного улучшения решения.

Общая методика

Изучались особенности строения общего алгоритма симплекс-метода и информационные связи между его компонентами. Возможности организации передачи данных рассматривались в рамках системы программирования Delphi. Для конкретной задачи о прокладке кабелей рассматривались различные методы точного и приближенного решения дискретных экстремальных задач, в том числе динамического программирования с перебором субоптимальных решений.

Реализованные методы оптимизации сопоставлялись по результатам достаточно представительного экспериментального расчета.

Основные результаты

В работе получены следующие основные результаты:

• Предложена структура программной реализации пакета симплекс-метода, основанная на принципах объектно-ориентированного проектирования.

• Проведена пробная реализация этой структуры в системе программирования Delphi с использованием библиотек динамической связи.

• Для конкретной прикладной задачи (линейно-программной модели задачи о прокладке кабеля) разработаны алгоритмы, позволяющие решать эту задачу методом генерирования столбцов. С этой целью разработаны новые алгоритмы для решения вспомогательной экстремальной задачи, связанной с проверкой допустимости двойственного решения, метод построения эффективного начального базисного решения и метод постоптимизационной корректировки оптимального решения задачи ЛП.

• Описанные алгоритмы оптимизации реализованы, а среди них вычислительным экспериментом выбран наилучший.

Научная новизна

Все основные научные результаты диссертации являются новыми.

Практическая и теоретическая ценность

Полученные результаты могут быть использованы при создании высокоэффективных алгоритмов для задач линейного программирования с алгоритмически задаваемыми матрицами ограничений и использованием генерирования столбцов.

Публикации

Диссертация защищается без публикаций.

Структура и объем диссертации

Диссертация состоит из двух глав и двух приложений. Текст основной части диссертации занимает 98 страниц, а приложения с программными текстами — 52 страницы. Список литературы содержит 10 наименований.

Содержание работы

В первой главе описывается общая структура симплекс-метода для решения задач линейного программирования, причем описание нацелено на последующее изложение метода генерирования столбцов.

Отдельно описываются действия, выполняемые с базисной матрицей — ее изменение от итерации к итерации, решение прямой и двойственной (транспонированной) систем, изменение базисной матрицы на одной итерации. Описывается принципиальная схема мультипликативного представления обратной матрицы.

Далее излагается общая структура системы, реализующей симплекс-метод в объектно-ориентированном подходе. А именно, эта система представляется в виде четырех отдельных модулей:

Ведущая программа осуществляет рабочую сборку программы из нескольких DLL, представляющих все остальные модули, организует совместную работу этих модулей при подготовке начального базисного решения, при итеративном процессе симплекс-метода, при постоптимизационом анализе и при выводе окончательных результатов.

Модуль обратной матрицы хранит в удобном виде информацию о ^„„„„.«t jriv-L^iviv^ , [ыiи 1-1111 ji v jya i»iм ими. j у I a i\ 1 Ii| ¿ \ V" 1 у i j и п ч A j IJ л: <411, н iw ; I i ->; l каждой итерации, в необходимых случаях делает повторное создание этой информации для текущего базисного решения и решает системы уравнений с текущей базисной матрицей.

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

Модуль системных столбцов похож по типу на предыдущий модуль, но он работает с так называемыми искусственными и дополнительными переменными, которым соответствуют единичные векторы, и, возможно, с еще одним искусственным вектором, называемым вектором Симмонара.

У всех этих модулей описывается схема их функционирования и детализируется информационное взаимодействие модулей. В связи с этим нужно отметить ряд принципиальных решений, положенных в основу структуры.

1. В качестве индекса базисной переменной используется пара неотрицательных чисел. Первый элемент этой пары определяет модуль, которому базисный столбец принадлежит: 0 — для системных столбцов и 1 — для основной части матрицы ограничений. Второй элемент, собственно номер столбца, на самом деле имеет трактовку, неизвестную программному окружению. Он соответствует используемому в программировании понятию handle — его смысл определяется только модулем, которому он принадлежит, точнее, реализацией этого модуля.

2. Для информационного обмена между модулями используется специальная структура данных, называемая "каналом связи". В целях экономии информационные поля этой структуры разными вызовами используются по-разному.

3. В системе Delphi есть некоторые особенности совместного использования "массовой памяти" (массивов, строк и т. п.) разными модулями. Однако, соблюдение формальных правил описания таких DLL сняло все трудности.

4. Без проблем был решен и вопрос о совместном выводе информации для визуализации и печати. Именно, компонент типа TStrings, передаваемый через упомянутый канал связи, оказался вполне удобным средством передачи такой информации.

Из описаний отдельных модулей отметим следующее.

Модуль обратной матрицы

Для представления обратной матрицы была использована так-называемая мультипликативная форма, в которой матрица, обратная текущей базисной матрице представляется в виде произведения мультипликаторов — невырожденных квадратных матриц, отличающихся от единичной матрицы одним столбцом. Была разработана схема представления информации о мультипликаторах в одной длинной байтовой строке. При этом были использованы разработки кафедры и лаборатории исследования операций.

Модуль системных переменных

Индексом столбца в этом модуле является число вида 4k+j, где к — номер строки, к которому относится данная системная переменная, a j — тип переменной. Для вектора Симмонара значение к выходит за число ограничений задачи.

Модуль матрицы ограничений

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

Различие трактовки индексов в двух последних модулях характерно. В типовых модулях, активно использующих генерирование столбцов, индекс рассматривается как ключ столбца в некоторой системе хранения столбцов, в которую столбцы включаются при их формировании и из которой они исключаются, когда становятся ненужными.

Ведущая программа организует простой и удобный интерфейс сборки рабочего варианта программы: пользователю предъявляется два списка названий — для реализаций модулей матрицы ограничений и для реализаций модулей обратной матрицы. Сделанный пользователем выбор определяет подключаемые DLL, они присоединяются, и задача переходит на счет. При необходимости к обязанностям ведущей программы легко добавляется и корректировка общих параметров счета.

Во второй главе рассматривается конкретная задача линейного программирования, в которой полезно использовать генерирование столбцов. Эта задача возникла в судостроении как задача о прокладке кабелей в строящемся судне 2.

Имеется конечное множество работ Р. Пусть работы индексируются буквой г, и / — множество этих индексов. Пусть задано положительное число R — количество рабочих, выделенных для выполнения задания, и множество N помещений на судне. Для каждой работы Pj заданы положительные числа ti — продолжительность выполнения этой работы и Гг — количество необходимых рабочих, а также конечное множество JVj помещений, которые должны быть заняты при прокладке кабелей, входящих в работу Рг. В каждый момент времени t можно выполнять несколько работ, но набор выполняемых работ должен удовлетворять следующим условиям:

2 См. диссертацию J1. Д. Бердичевского [1].

• Совместимость. Работы не должны мешать друг другу, т. е. если работы Pi и Pj выполняются в один момент, то множества Мг и Nj дизъюнктны.

• Выполнимость. Количество рабочих, занятых на выполнение работ в каждый момент времени, не превосходит заданного R.

Требуется составить совместимый и выполнимый план прокладки кабелей с минимальным сроком укладки.

Набор проектов, обладающий свойствами совместимости и выполнимости, назовем фронтом работ.

Мы не будем сейчас привязывать фронты работ к конкретным моментам времени, так что для нас план прокладки будет состоять из набора фронтов работ и продолжительностей их использования, а в качестве срока укладки будег использоваться сумма этих продолжительностей.

Рассмотрим множество всех возможных фронтов работ Т. Это множество велико, но конечно, поэтому его можно будет рассматривать как множество индексов в некоторой задаче линейного программирования. Получается следующая задача ЛП.

Задача о прокладке кабелей

Найти набор неотрицательных переменных x[f], / € J-, удовлетворяющих условиям x[J}> О, feFi, 5>[/] = *i, ¿е/,

FiBf где Fi — множество всех фронтов, содержащих работу г, с минимальной суммой fer

Эту задачу мы и решаем симплекс-методом с генерированием столбцов. В ходе решения нужно на каждом шаге симплекс-метода решать проверочную задачу, вспомогательную экстремальную задачу, формулируемую следующим образом.

Проверочная задача

При заданных оценках работ v[i], i Е Р, найти фронт работ / G Т с максимальной суммарной оценкой работ J2ief

Проверочная задача является вариантом известной задачи о ранце. Исходная задача о ранце может решаться методами динамического программирования и методами улучшенного перебора, но в нашем случае использование этих методов затрудняется условием совместимости работ, входящих в искомый фронт. Однако, можно и на основе схемы динамического программирования и на основе переборных алгоритмов построить процессы перебора субоптимальных решений, которые продолжать до тех пор, пока не будет найден набор работ, удовлетворяющий условию совместимости.

Мы разработали три варианта схемы динамического программировался и вариант улучшенного перебора, использующий предложенный И. В. Романовским 3 принцин упорядочения переменных по двум критериям. Вычислительное сравнение этих методов показало значительное превосходство переборного алгоритма, и он и был принят для окончательной реализации.

В окончательный алгоритм была добавлена схема построения начального базисного решения, основанная на идее В. А. Залгаллера для задачи линейного массового раскроя (схема была реализована в кандидатской диссертации А. М. Курмангалеевой). Идея заключается в том, что вычисления начинаются с обычного искусственного базиса, и пока в базисе остаются искусственные переменные, вычисление вводимых в базис фронтов идет по особой схеме. В нашем случая эта особая схема такова:

Выбрать для включения в фронт работу, искусственная переменная для которой еще находится в базисе и число рабочих для которой максимально. Дополнить фронт другими работами, соблюдая условия совместимости и выполнимости.

Из других алгоритмов, разработанных специально для этой задачи, можно назвать еще алгоритм построения матрицы совместимости работ и алгоритм постоптимизационной обработки решения, полученного из задачи линейного программирования.

Матрица совместимости <¿[1,1] определяется следующим образом. Имеется множество помещений судна ТУ, и каждой работе г € как уже говорилось, сопоставляется множество ^ С N. Положим с£[г, ]) — ((Л^ П Щ) = 0) (это логическое значение). За время 0(^ 1-^1) мы стро-3См. [7]. им в множестве I подмножества несовместимых работ Ik, к £ N, а затем для каждого к заполняем всю подматрицу d[Ik,Ik] значениями False.

Постоптимизационная обработка решения оказалась достаточно трудоемкой и выделена в отдельный параграф главы и отдельную программу системы. Здесь был предложен метод локального улучшения решения. Задача заключается в том, чтобы упорядочить найденные фронты работ таким образом, чтобы по возможности ликвидировать разрывы в выполнении работ, попавших в несколько разных фронтов. Для ликвидации разрывов кроме переупорядочения работ предпринимаются округления интенсивностей: фронты работ с пренебрежимо малыми интенсив-ностями удаляются из решении, а искавшимся работам интенсивности увеличиваются для компенсации потери в суммарной продолжительности работ.

Этот алгоритм служит лишь примером постоптимизационной обработки. Ясно, что практические схемы должны строиться с учетом практических потребностей конкретного производства. Для нас важнее всего здесь была организация связи по данным между основным пакетом линейного программирования, который при завершении работы готовит специальный файл, и программой улучшения решения.

Перейдем к вопросам организации модуля матрицы ограничений. Этот модуль внешне является таким же, как все другие модули этого типа; он экспортирует процедуру Problem с фиксированным интерефей-сом procedure Problem(modeP: TModeP;var sCh: PDataChannel); где параметр перечислительного класса modeP определяет режим вызова, а указатель sGh передает структуру канала обмена, где находятся все остальные данные. Такой интерфейс, по нашему мнению, удобнее для межмодульной связи чем большой набор режимов с различными интерфейсами.

Внутри модуля организовано хранение сгенерированных фронтов работ. Они хранятся в цепных списках, для хранения голов которых создан массив размера, лишь немного превышающего количество ограничений задачи. Внешне используемым индексом столбца является индекс в этом массиве, определяющий голову цепного списка.

Процедура проверки оптимальности Check написана на основе метода улучшенного перебора с предварительным упорядочением переменных и со специальным режимом (реализуемым процедурой alaZalgallerCheck) построения эффективного начального приближения.

Характерным для модулей, действительно использующих генерирование столбцов и вынужденных хранить используемые столбцы, является использование режима Delete, освобождающего память.

Постоптимизационная обработка описана в последнем параграфе второй главы.

В приложениях А и R ппттедрны полные тексты программ, написанные для системы Delphi 5.0: основная версия пакета симплекс-метода (основная программа, модули обратной матрицы, системных переменных и матрицы ограничений для модельной задачи); модуль матрицы ограничений для задачи о прокладке кабелей; программа постоптимизационной обработки решения для прокладки кабелей.

Заключение

В работе получены следующие основные результаты:

• Разработана действующая программная модель симплекс-метода, предназначенная для оперативной сборки действующих программ для различных конкретных типов задач линейного программирования, в частности, для реализации в них метода генерирования столбцов. С этой целью в модели использована техника DLL — библиотек динамической сборки.

• Эта модель использована для решения задачи линейного программирования, моделирующей практическую ситуацию составления производственного расписания для прокладки кабелей в корпусе строящегося судна. В модуле, соответствующем этой задаче, разработаны специальные алгоритмы:

Для проверки оптимальности на каждом шаге итеративного процесса.

Для эффективного построения начального базисного решения.

Для постоптимизационной доработки полученного непрерывного решения.