Сильно полиномиальные алгоритмы решения некоторых классов задач математического программирования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

дклдага наук езялруси икотитут »Атзкктло.

На правах рукописи

ГОРОХ Олег Еимдагарович

СИЛЬНО ПОЛШОаШЛЬНКЕ АЛГОРИТМЫ РЕВЕКИЯ HSitOTOPœ КЛАССОВ ЗАДАЧ МАТВШЙЧКСКОГО ПРОГРАШИРОВАШЯ

Специальность 01.01.09 - " Математическая кибернетика "

ДЗТ0РЕФ2РАТ

диссертации на ссискйнйэ ученой степени кандидата ^лзяко-матемастчаеют каук

Минск - 1992

Работа выпоаненв в орден» Трудового Крчокого Зннмени. Институте техническое кибернетики АН Бвлядопи

Научный руководитель! доктор Зиэико-ыатеиэтнчвских наук,

профессор Танеев Вячеслав Сергеевич

Научный консультант; доктор физико-математических наук

Сотеу.оу. Юра£ Нагадим

Сфициялььыа оппоненты; доктор Зияик^-математичвпкия. наук,

щюфэссор Емелячев Владимир Алексеевич;

кандидат физико-математических наук, старом» научный сотрудник Д&ыиденхо Виталий Михайлович

Вэдущео прэдтфиятие: Институт кибернетики АН Украины

Защита диссертации состоится " 29 января 1993 г. в " 16 " часов ня заседании специализированного совета К 006.19.01 в Институте математики АН Беларуси (220072, г. Минск, ул. Сурганова, 11).

С диссертацией «окно ознакомиться б библиотеке Института математики АН Беларуси.

Гу

Автореферат разослан " ^ " 1992г.

Учений секретарь

специализированного совета, -Здс-гл'^- д. и. Астровский кандидат физико-математических наук

ОЕЩ№ ХАРАКТЕРИСТИКА РАБОТЫ

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

В настоящее время проблема существования сильно полиноми-пльннх алгоритмов ЛП остается открытой. Известны линь некоторые частные случал этой задачи, для которых существуют сильно полиномиальные алгоритмы решения (работы Л.Г. Хачияна, X. Папа-дамктриу, К. Стейглнца, Е. Тардеш). К таким частным случаяи относится задача ЛП вада ог» гса. Ах £ Ь, в которой коэффициенты матрицы Л принимают лишь фиксированный набор значения, например О, 1, -1; задача о кахсимальнсы потоке в сети; задача о потоке минимальной стоимости. Известны тагам частные случаи систем линейных неравенств, для которых Н. Мзгидцо получил сильно полиномиальные алгорит?ш решения, а именно: системы, у которых в каздое неравенство входит на более двух неизвестных и системы линейных неравенств с фиксированным числом неизвестных. В такой ситуации представляется актуальным исследование новых классов задач математического •программирования о сильно полиномиальными алгоритмами решения.

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

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

Научная новизна работы заключается в следущем.

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

2. Предложен сильно полиномиальный метод решения дискретной макстамнной задачи на сфере, основанный на свойствах векторов, равноудаленных от систем линейно независимых векторов.

Практическая ценность и реализация результатов.

1. На базе полученных результатов разработаны алгоритмы, реализующие предложенные методы для решения соответствующих задач.

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуздались на У конференции молодых ученых Института технической кибернетики АН БССР (г. Минск, 1993)! на IV Всесоюзной координационном совещании по автоматизации проектно-конструктор-скях работ в машиностроении (г. Минск, 1969), на Республиканской конференции молодых ученых и специалистов (г. Минск, 1989), на

XI Всесоюзной конференции по проблемам теоретической кибернетики

(г. Волгоград, 1930), а также на научных семинарах Института

математики и Института технической кибернетики АН Беларуси.

Публикации. По теме диссертационной работы опубликовано 15 научных работ.

Объем и структура работы. Диссертация состоит из введения, трех глав, списка литературы из 116 наименований и приложения, содержит 130 страниц машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Выделение несущественных ограничений производятся посредством построения сечений исходной системы неравенств, которые по существу совпадают с сечениями, введенными С.Н. Черниковым. Отличив заключается лишь в том, что там рассматривались сечения исходной системы неравенств •

a b(, t е ¡l = í 1,2, ... ' (1)

координатными плоскостями вида Xj = О, здесь же рассматриваются сечения системы неравенств (1) при помощи плоскостей, входящих в ее задание, иными словами; .рассматриваются собственные сечения системы неравенств (1) вида

<2>

|a(iab(, { с 1Г =• а \ I к ).

Теорема 1.2. Пусть система линейных неравенств (1) совершенна и вектор afe ненулевой. Если сечение (2) системы неравенств (1) относительно fe-го ограничения несовместно, то либо система неравенств (1) несовместна, либо fe-e неравенство несущественно для исходной системы неравенств (1).

В §2 рассматриваются последовательности сечений системы линейных неравенств, позволяющие либо найти решение исходно®

системы, либо указать несущественное неравенство.

Пусть система линейных алгебраических неравенств

Л ? * Ь (3)

совершенна и ее матрица А = (а^), I -- 3 = 77л. имеет отличный от куля элемент ат. Тогда приведенное сечение системы неравенств (3) по т-му ограничению определяется смешанной системой линейных ограничений

*

где г - (п-1 вектор неизвестных, а влзменты (т-1)х(п-

-?.)-матрицы у!1' ^ и (т-1)-мерного вектора Ъ1^ получены из соответствующих элементов матрицы А и вектора Ь по правилу прямоугольника о ведущим влементом а (метода исключения неизвестных Гаусса).

Определение 2.1. Последовательность сыеианных систем линейных ограничений 30>3]> ••• »£>п назовем последовательностью вложенных .сечений (ПВС) совершенной системы линейных неравенств (3), если система неравенств Б совпадает о исходной системой ограничений (1)

* Ъ(0>,

где - А, ъ<°> = Ь, хп = х, а какдея последующая система

Г .т" " а

^ I <¿4 1 - <4 ' г =

4 яг-1 (Л-1

получается из предыдущей системы 3^, если заменить в ней под-' систему неравенств на приведенное сечение этой подсистемы по последнему ограничению. При втом предполагаемся, что выполняются условия

ат-1 п-г * 1"0~п=1. Пусть 50,В1.... ,Вп- ПВО совершенной системы неравенств (3), тогда имеют место следующие утверждения.

Теорема 2.2. Если сечение Бр совместно, то совместны все

предыдущие сечения ( = о,р-1. Если сечение несовместно,

то несовместны вое последующие сечения ( = 1+1,п.

Тесремп а.з ■ Если сечениа Е^^ , где О « к < п, нс^овместно, то либо сечение нееовкэстно, либо неравенство несу-

цосттгао для сечения

Теорема 2.4. Кс.та 1-е неравенство, 1 & \ & я-п. несущественно для сеченил и 5 Р. $ п, то это неравенство несущественно для всех последующих печений , { = й*I,п.

На основании последовательностей вложенш сечений предлагается алгоритм определения рекешы системы линейных неравенств, имевший оценку трудоемкости ОСтР'11** ). Данией оценка позволяет выделить класс с ютем .'ганейных неравенств, характеризующийся постоянной разностью й = т - п мевду числом ограничений и числом переменных, на котором предлагаемый метод вложенных сечений является сильно долинамиальным.

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

В §4 рассматриваются последовательности систем линейных уравнений, часто встречаемся в приложениях: последовательность систем линейных уравнений, в которой каадая последующая система является результатом окаймления предыдущей; последовательность систем линейных уравнений, отличащихся лишь правой частью; ' последовательность систем линейных уравнений, отличающихся только одним и тем йв уравнением; последовательность систем линейных уравнений, в которой системы отличаются от некоторой исходной

система одним, но (в отличие от предыдущего случая) произвольным уравнением.

Применение метода расширяющихся подсистем к решение гадах, последовательностей позволяет не менее, чем на порядок уменьшить оценку трудоемкости определения решения каадсй системы по сравнений (! независимым решением систем, входящих в последовательность.

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

ранга л совпадает с трудоемкость» решения системы уравнений с

з

невырожденной квадратной матрицей порядка п и составляет 0(п ).

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

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

Во второй главе предлагается метод решения одной дискретной

максиминной задачи на сфере радиуса г в n-мерном евклидовом

пространстве К.: найти максимум функции t(x) = min а.х по всем

71 ieU 1

х, принадлежащим сфере % = ix <= |ii х п = г).

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

и достаточно простого ограничения - сферы, радиус которой нота, не ограничивая общности, принять равным единице. Данное замечание позволяет свести рассматриваемую задачу с ограничением к задаче оптимизации, вообще говоря, более сложной функции нормированного аргумента, но уже без ограничений, то есть задача максимизации функция t на сфере Я эквивалентна задаче максимизация функции У на пространстве 3„, где

F(x) = min /{(х), }{(х) = TJ5J atx, i « U. (4)

В §1 рассматривается некоторое одномерное обобщение задачи максимизации фуш-ции ? (о переходом от максимина к мшимаксу), а именно! задача минимизации на интервале максимума дробных функций вида

ßi * + It

d,(x) =----,-i-----í-77, , i с 1f, (5)

fa^Z"-* SLgZ + a3;

Предлагается алгоритм решения этой задачи, имеющий оценку трудоемкости 0(md).

В §2 предлагается алгоритм построения интервального представления функции максимума от значений одномерных неоднородных линейных функций на отрезке, заключающийся в упорядочении составляющих максимума по значениям на концах отрезка. Алгоритм имеет оценку трудоемкости 0(т log т), где m - число линейных функций, и позволяет с такой see трудоемкостью решать задачу (5).

В §3 рассматриваются свойства так называемых, центральных векторов. Пусть в n-мерном евклидовом пространстве задана сфера единичного радиуса 9, = (х е Еп ¡11111= 1), для множества и = (1,2,—,т), ш s п, определена система S^ = (a<, а2,...,ат) линейно независимых нормированных векторов а{, i е il.

Определение 3-1. Вектор х е ín назовем равноудаленным от векторов системы S^ = {а( | I е V ), если для всех l,J е И выполняется условие а{ х = Oj х.

Введем множество Q,^ (х € KJ а(х = аух, I J е И ) векторов, равноудаленных от системы векторов Sy и линейную оболочку Ъы = (х е Еп| х ai} векторов системы S^, а тайке прост-

ранство Ру как пересечение пространств Ь^ и Q^.

Определение 3.5. Р^ назовем пространством собственных равноудаленных векторов системы S^.

п

- 1С -

Можно показать, что пространство собственны! равноудаленных векторов системы Зу совпадает с ортогональной проекцией пространства Qu на 7-ц.

Введем в рассмотрение функцию t, определяемую системой векторов S„ следующим образом: t(x) = min а.х.

. Ulf 1

Теорема 3-3. На любом ненулевом собственном равноудаленном

векторе скстеж фушшия t принимает отличные от нуля значение.

Теорема 3.3. Пространство собственных равноудаленных векторов Ру одномерно для кажцоР. линейно независимой системы S^,

Определение 3.3. Нормированный собственный равноудаленный вектор с системы Sj., для которого t(c) > О, назовем централ ь н н м вектором системы S^.

Обозначим через Q^j множество всех норьыровашшх равноудаленных векторов системы S^, т.е. Q^ = Qy fl X.

Теорема 3.4. Максимальное значение функции t на множестве достигается на центральном векторе е системы S.j". тах t(x) - t(a).

Теорема 3-5. Для произвольной линейно независимой системы Sjj центральный вектор с однозначно представим в виде линейкой комбинации векторов атой системы

с = £ Х.а,. (6)

Uli 1 1

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

Теорема 4.1. Если произвольная система линейно независимых векторов Sy . содержит не менее двух векторе®, то в разложении центрального вектора с системы Sg по векторам втой системы имеется не менее двух строго положительных коэффициентов.

Пусть Ы+ - множество индексов I е М , для которых коэффициенты в разложении (6) центрального вектора с системы Sy по векторам втой системы строго положительны. Обозначим через с+ центральный вектор оистемы = (а{|U И+),

с+=£ Ц аг (7)

UM*

Теорема 4.3- Для произвольной системы линейно гэзависишх векторов Sj, центральный вектор с+ он яодсиотоии имеет воо строго псло'-китолышй коэффициенты в разложении (7).

Теореме 4-4- Для произвольней еистеш линейно независимых нормированных векторе« S.j о центральным вектороу с имеет место соотношение

п'.п а.с* - nln а.с*, t«ií 1 «гЗГ 1

где с - центральный вектор системы

Теорема 4-5- Для произвольной системы линейно независимых нормированных векторов функция í достигает локально максимальное на сфере Я значение t^ на центральном векторп с* подсистемы S„i- .

• ¡rí

Предлагается алгоритм определения кокекмэльяого на сфере Я

значения функции t для случал, когда в^.торы системы S„ линейно

3 я

независимы. Оценка трудоемкости алгоритма равна 0(т ).

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

В §1 приводится постановка следующей задачи оптимальной упаковки трехмерных объектов (изделий} в прямоугольную тару. Требуется упаковать изделия п наименований в прямоугольную тару (ящики, коробки) а типов. Для к&кдого наименования изделий заданы габариты, вес, способ упаковки, допустимость второго яруса и количество изделий данного наименования. Для каждого типа ящиков заданы габариты, вес и коэффициент возможного заполнения. Мелкие изделия долулш быть предварительно упакованы в коробку заданных размеров. Изделия и коробки с изделиями упаковываются в ящики в один, .два или три яруса, разделяющиеся платформой или перегородкой в зависимости оi способа упаковки. Для казгдого способа упаковка задается величина зазора мекду соседними изделиями. Допускается упаковывать в один ящик изделия о разными способами упаковки. Такие изделия разделяются вертикальной перегородкой на высоту всего ящика. Кроме того, задается толщина платформ и перегородки, высота незаполняемой части ящика, а также максимальный sec упакованного ящика. В качестве критерия оптимальности упаковки рассматривается

минимизация суммарного объема ящиков, ь которые упаковываются все заданные изделия. При в том предполагается, что ящиков какого типа имеется достаточное количество.

Необходимо отмстить, что даже в одномерном случае задаче упаковки является №-трудяой в сильном смысле, что оказывает влияние на выбор алгоритма решения практических задач, которые имеют, как правило, значительную размерность. В связи с втим в основу метода били положены быстра выполнимые (полиномиальные) процедуры упаковки упорядоченных партий однородных (по способу упаковки) изделия, описанные в §2. Такой подход, вообще говоря, не гарантирует получение оптимальной упаковки изделий,однако позволяет быстро получать некоторое рациональное решение задачи, как правило, удовлетворяющее практическим запросам пользователей.

В втором параграфе содержится краткое описание автоматизированной система упаковки изделий АИСТ, в составе которой программы упаковки внедрены на производственном объединении "Квант" (г. Новгород) и показали за время вксплуатации (более трех лет) достаточно высокую эффективность и надежность.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

5. Предложен эвристический алгоритм решения задачи оптимальной упаковки трехмерных объектов, реализованный в автоматизированной системе АИСТ, и находявд£ся в промышленной эксплуатации.

Основные результаты диссертации опубликованы в оледущях работах

1. Горох О.В. Метод расширяющихся подсистем для решения систем линейных алгебраических уравнений // Изв. АН БССР. Сер. физ.-матем. н. - 1981. - N 6. - С. 126.

2. Горох О.В. Программная реализация метода расширяющихся подсистем для решения систем линейных алгебраических уравнений // Алгоритмы и программы решения екстремальных задач и смежна вопросы. - МИНСК! ИТК АН БССР, 1392. - С. 17-22.

3. Горох О.В. Об одной дробной минимаксной задаче // Сложность и методы решения задач оптимизации. - Минск: НТК АН БССР, 1934. - С. 28 - 36.

4. Горох О.В. О решении последовательности расширяЕЩихся систем линейных алгебраических уравнений // Теория и методы автоматизации проектирования сложных систем и автоматизации научных исследований.- Минск: ИТК АН БССР, 1S85.- С. 3-55. Горох О.В. О построении функции максимума конечного множества линейных функций // Метода, алгоритмы и программы решения экстремальных задач. - Минск: ИТК АН БССР, 1985- - С. 112 - 121.

6. Горох О.В., Андреев Г.В. Об одном эвристическом методе решения задачи оптимальной упаковки // Применение информатики и вычислительной техники при решении народно-хозяйственных задач. Тез. докл. Республ. конференции. - Минск, 1989. - С. 164.

7. Горох О.В. Свойства центральных векторов // Методы решения екстремальных задач.- Минек: ИТК АН БССР, 1989.- С. 74-88.

8. Горох О.В., Андреев Г.В., Сотеков Ю.Н. Оптимизация упаковки изделий в стандартную тару // IY Всесоюзное координационное совещание по автоматизация! проектко-конструкторских работ в машиностроении. - Минск, 1S89. - С. 197 - 203.

9. Горох О.В. О решении последовательности линейных алгебраических уравнений, отличающихся одним уравнением // Методы решения экстремальных задач и смекные вопросы. - Минск: ИТК A4

БССР, 1990. - С. 117 - 122.

10. Горох О.В., Сотоков D.H., Андреев С.И., Андреев Г.В., Антиповь H.A. Автоматизированная система оптимальной упаковки изделий. - Минск! ИТК АН БССР, 1990. - 64 с.

11. Горох О.В. Выделение несущественных ограничений в системах линейных неравенств // Методы решения екстремальных задач и смежные вопросы. - Минск: ИТК АН БССР, 1990. - С. 123 - 128.

12. Горох О.В. Об одном подходе к решению систем линейных неравенств // Проблемы теоретической кибернетики. Тез. докл. XI

Всесоюзной конф. Ч. I (2). - Волгоград; ВГУ, 1990. - С. 23.

13. Горох О.В., Сотоков Ю.К., Андреев С.И., Андреев Г.В. Пакет программ оптимизации упаковки изделий // УС и М. - 1991.

- N 2. - С. 100 - 103.

".4. Горсх О.В. Об одном методе решения систем линейных неравенств // Изв. АН БССР. Сер. физ. - матем. н.- 1991. - 12 о.

- Деп. в ВИНИТИ 17.05.91, И 2036 - В91-

15. Горох О.В. Модифицированный метод вложенных сечений // Экстремальные задачи оптимального планирования и проектирования.

- Минск: ИТК АН БССР, 1991. С. 54 - 66.