Введение к работе
Актуальность проблемы. Доказательство полиночиальной разре-шчноотк задачи линейного программирования (ЛП) породило новую проблему, связанную с существованием сильно полиномиальных алгоритмов решения задачи ЯП (или, что по сути то ке самое, системы линейных неравенств), т. е. такії полиномиальных алгоритмов, оценка числа операцій которых не зависит от цифровой длины входных коэффициентов, а зависит лишь от их количества.
В настоящее время проблема существования сильно полиноми-нль'ннх алгоритмов ЛП остается открытой. Известны линь некоторые частные случаи этой задачи, для которых существуют сильно полиномиальные алгоритмы решение (работы Л.Г. Хачияна, X. Папа-димжтриу, К. Стейглща, Е. Тардеш). К таким частным случаям относится задача ЛП вада ex* znz, Ах s Ъ, в которой коэффициенты матрицы Л принимают лишь фиксированный набор значення, например О, 1, -1; задача о максимальней потоке в сети; задача о потоке минимальной стоимости. Известны также частные случаи систем линейных неравенств, для которых Н. Мэгиддо получил сильно полиномиальные алгоритмы решения, а именно: системы, у которых в каадое неравенство входит на более двух неизвестных и системы линейных неравенств с фиксированным числом неизвестных. В такой ситуация представляется актуальный исследование новых классов задач математического'іптаггіаш^ировашія с сильно полиномиальными алгоритмами решения.
Цэльр работы является выделение классов задач математического прогрежировпния, допускайцах сильно полиномиальные алгоритмы реаония.
Методы исследования. Для достигения поставленной цели в работе использованы методы линейной алгебры, математического и выпуклого анализа.
Научная новизна работы заключается в следущем.
1. Предлозен метод, основанный на построении сечений, позволяющий в системе линейных нэравенста Еыделить ограничения, отбрасывание которых не изменяет множество решений исходной системы. Данный метод является сильно полиномиальным на классе енотом неравенств, характеризующемся постоянной разностью ыезду числом ограничений и числом неизвестных.
2. Предложен сильно полиномиальный метод решения дискретной макслминной задачи ня сфере, основанный на свойствах векторов, равноудаленных от систем линейно независимых векторов.
Практическая ценность и реализация результатов.
-
На базе полученных результатов разработаны алгоритмы, реализующие предложенные методы для решения соответствующих задач.
-
Разработан метод проверки совместности систем линейных . алгебраических уравнений, ориентированный на определение решений последовательности систем линейных уравнений с незначительно изменяющимися входными данными.
-
Предложен сильно полиномиальный алгоритм решения одномерной задачи минимизации на интервале максимума значений дробных функций специального вида.
-
Предложен евриотический алгоритм решения задачи огокма-льной упаковки трехмерных объектов, основанный на аффективных процедурах упаковки упорядоченных подмножеств однородных объектов, реализованный в автоматизированной системе упаковки изделий АИСТ, находящейся в промышленной эксплуатации.
Апробация работы. Основные результаты работы докладывались и обоуздалиоь на Y конференции молодых ученых Института технической кибернетики АН БССР (г. Минск, 1993)! на IY Всееошнои координационном совещании по автоматизации проектно-конструктор-екях работ в машиностроении (г. Минск, 19S9), на Республиканской конференции молодых ученых и специалистов (г. Минск, 1989), на
Ш Всесоюзной конференции по проблемам теоретической кибернетики
(р. Волгоград, 1990), а также на научных семинарах Института
математики и Института технической кибернетики АК Беларуси.
Публикации. По теме диссертационной работы опубликовано 15 научных работ.
Объем и структура работы. Диссертация состоит из введения, трех глав, списка литературы из 116 наименований и приложения, содержит 130 страниц машинописного текста.