Содержание к диссертации
Введение
Глава 1. Модели задач планирования и диспетчеризации. их формализация и анализ методов решения 15
1.1. Модель задачи оперативного регулирования производственного процесса 15
1.2. Модели задач теории расписаний и планирования 19
1.3. Модель задачи распределительного типа 23
1.4. Принадлежность задачи линейных дизъюнктных неравенств к классу NP 24
1.5. Возможные варианты сведения системы линейных дизъюнктных неравенств к системе простых неравенств 26
1.6. Выводы 35
Глава 2. Математические методы на основе стратегии устранения невязок для решения задач на системах простых линейных неравенств 37
2.1 Стратегия устранения невязок и ее использование для создания математической платформы для решения задач планирования и диспетчеризации 37
2.1.1. Существо стратегии устранения невязок 38
2.12. Доказательство финитности стратегии устранения невязок 40
2.1.3. Градиентный метод для повышения скорости сходимости стратегии устранения невязок 45
2.1.4. Анализ скорости сходимости градиентного метода 48
2.1.5. Вариант реализации стратегии устранения невязок без неравенств 0-блока 50
2.2. Задача линейного программирования 52
2.3. Выводы 55
Глава 3. Математические методы на основе стратегии устранения невязок для решения задач на системах линейных дизъюнктных неравенств 56
3.1. Стратегия устранения невязок для решения задач на системах линейных дизъюнктных неравенств в вещественных числах 56
3.2 Построение модели времени счета задач на линейных дизъюнктных неравенствах 62
3.3. Задача оптимизации на системах линейных дизъюнктных неравенств, є- приближенный подход 66
3.4. Статистически оптимальный алгоритм для задач линейных дизъюнктных неравенств 68
3 5. Использование стратегии устранения невязок для систем линейных дизъюнктных неравенств для решения целочисленных и булевых задач 75
3.6. Выводы 76
Глава 4. Разработка комплекса программ для автоматизации исследования и решения задач, формализуемых системами линейных дизъюнктных неравенств 78
4.1. Объектно-ориентированные технологии в автоматизации прикладных задач 85
4.1.1. Иерархия классов 86
4.1.2. Диаграмма классов 96
4.2. Синтаксис спецификаций в форме Бэкуса-Наура 97
4.3. Реализация 102
4.4. Примеры моделей задач практической реализации І 08
4.4.1. Технологический процесс изготовления изделий на заводе крупно-панельного домостроения №1 108
4.4.2. Технологический процесс изготовления плат 111
4.4.3. Задача раскроя материала 114
4.5. Выводы 123
Заключение 126
Список использованных источников 127
- Модели задач теории расписаний и планирования
- Вариант реализации стратегии устранения невязок без неравенств 0-блока
- Построение модели времени счета задач на линейных дизъюнктных неравенствах
- Технологический процесс изготовления изделий на заводе крупно-панельного домостроения №1
Введение к работе
Современные системы автоматизации решения задач характеризуются широким спектром используемых моделей. К числу важнейших относятся модели задач диспетчеризации (оперативного регулирования) и планирования. Задачи планирования отличаются от задач диспетчеризации большей неопределенностью и большей длительностью временного интервала. Оперативное регулирование призвано обеспечить требуемую динамику производственного процесса с целью выхода на установленные директивные сроки и плановые показатели. Эти задачи имеют сложный математический характер, особенно для многономенклатурных дискретных производств (электронное машиностроение и оборудование, вычислительная техника и радиотехника, приборостроение и т.п.). Для решения этих задач применяются разнообразные методы теории оптимизации, как дискретной, так и вещественной, теории расписаний, теории очередей, массового обслуживания и другие, включая также эвристические и приближенные методы. Это разнообразие подходов и принципов не позволяет решать задачи планирования и управления современным производством на основе единой достаточно универсальной платформы. Наличие множества методик, подходов и алгоритмов, реализованных, как правило, на разных теоретических платформах не позволяет выбрать и единую программную платформу, и уже незначительное изменение условий производства при переходе от одних систем к другим связано зачастую с выбором новых пакетов и новых математических методов. Таким образом, создание универсальных программно-математических платформ является одним из важнейших направлений в автоматизации решения задач планирования, диспетчеризации и управления.
В настоящее время н развитии математических методов решения прикладных задач можно выделить два направления. С одной стороны, разрабатываются общие методы решения задач, содержащих большое количество переменных и ограничений, при этом рассматриваются задачи
без учета иу_ специальной структуры. С другой стороны, создаются методы. способные эффективно учесть особенности структуры конкретных классов задач, часто встречающихся в приложениях. Хотя область применения таких методов ограничена, они имеют и неоспоримое преимущество: позволяют решать узкие классы задач с высокой эффективностью. Первым представителем подобных методов явился метод потенциалов, созданный для решения транспортной задачи линейного программирования. Специальная реализация симплекс-метода позволила во много раз повысить его эффективность в применении к транспортным задачам, которые имеют специальную структуру ограничений.
Отметим наиболее значимые работы в развитии численных методов решения задач математического программирования.
Юдин Д-Ь., Гольштейн НЛ\, Немиронский А.С., Шор 11.3. [81, К2] разработали методы типа эллипсоидов для решения задач выпуклою программирования, а также указали случаи их эффективного решения.
Хачиян Л.Г. [76] разработал вариант метода эллипсоидов для задач линейного программирования. Метод совершенно отличается от большинства предыд>щих подходов к линейному программированию тем. что в нем почти полностью игнорируется комбинаторная природа задачи, имеет полиномиальную оценку сложности. Несмотря на большое теоретическое значение алгоритма, он оказался на практике менее эффективным в своей реализации по сравнению с симплекс-методом, характеризующимся с точки зрения теории сложности экспоненциальной временной сложностью. Наиболее очевидным среди большого числа препятствий является требование большой точности вычислений. С другой стороны нет убедительных свидетельств в пользу того, что алгоритм эллипсоидов заведомо не может использоваться на практике.
Н. Кармаркар [41] создал метод проективных преобразований, как основу полиномиальных алгоритмов в линейном программировании, hro
7 сложность, однако, лишь незначительно меньше сложности метода
эллипсоидов.
Большое распространение получил метод внутренних точек [87, 88] для линейной оптимизации, использующий эффективные алгоритмы, базирующиеся на ньютоновском подходе.
К сожалению, эти методы не удалось распространить на целочисленные и нелинейные задачи оптимизации в общем случае.
Отличительная особенность большинства исследований по дискретной оптимизации состоит в том., что значительная часть их базируется на использовании ранее предложенных алгоритмических схем, например:
последовательного анализа вариантов (разработанного Михалевичем B.C. и Шором Н,3. [50, 51J);
методов ветвей и границ (предложенного Лэндом и До игом и развитого Литтлом, Мурти, Суини и Кэрелом);
методов отсечений (идея которого предложена Данцигом [34] и развита в работах Гомори)
4) локальной оптимизации (предлагаемого Сергиснко И.В,[65]),
Разработанная методология последовательного анализа вариантов
оказала влияние на развитие вычислительных методов оптимального управления (например, метода локальных вариаций, предложенного H.I1. Моисеевым и его учениками [53]), с успехом использована для решения широкого класса дискретных задач оптимизации в работах В.А. Емеличева и его учеников [37].
Значительный интерес для практики представляют дискретные и дискретно непрерывные задачи большой размерности, для которых I-L3 Шором предложены процедуры, сочетающие методы ветвей и границ и обобщенного градиентного спуска [80].
Определенный интерес представляют исследования, связанные с решением широкого класса задач комбинаторного типа. Для решения такого рода задач к настоящему времени разработан ряд алгоритмов, сочетающих
я процедуры симплекс-метода и ветвей и границ, базирующихся на алгоритме
В,А. Трубина для решения целочисленных задач специального вида [71].
Близким к методам ветвей и границ является алгоритм Балаша [5],
предназначенный для решения целочисленных задач с булевыми
переменными, и его модификации.
К настоящему времени накопился значительный опыт в разработке и использовании алгоритмов, вкладывающихся в общую схему метода ветвей и границ. Эти алгоритмы отличаются между собой способами ветвления, вычислением оценок (границ) [43, 51, 74]. В [67, 78] предлагается комбинировать метод ветвей и границ с другими методами. Однако решение многих практических задач большой размерности с помощью алгоритмов ветвей и границ проблематично, при точном решении задач дискретной оптимизации обнаруживаются патологические задачи, для которых объем вычислений близок к полному перебору.
Эффективность методов отсечений находится в прямой зависимости от эффективности различных подходов построения отсечений. Реализация различных подходоп к построепию отсечений породила целое множество методов зтой фуппы |85[. Однако методы отсечений покачали свою непредсказуемость, меняющуюся от задачи к задаче, в частности, известны примеры задач, решение которых методом полного перебора веек допустимых значений переменных требует меньше времени, чем методами отсечений [7].
В [7, 67] отмечается, что трудности решения задач дискретной оптимизации носят не технический, а принципиальный характер, с ростом размерности задач трудности их решения весьма быстро возрастают,
В работах Габасова Р. и его учеников [1, 2, 3, 13, 14] развивается адаптивный метод, который возник в результате анализа классической) симплекс-метода. Основная цель обобщения - избавиться от некоторых недостатков симплекс-метода и создать метод, который можно использовать для решения динамических задач линейного программирования. Идеи
адаптивного метода получили развитие в алгоритмах решения различных задач математического программирования и оптимального управления. Они легли в основу разработанного Габасовым Рм Кирилловой Ф.М., Костюковой О-И- метода опорных задач, который также был обобщен на различные типы экстремальных задач.
Теория расписаний даже в пределах исследуемого ею класса задач характеризуется ярко выраженной спецификой и индивидуальным подходом к конкретным задачам. При этом очевидно, что именно теория расписаний является одной из главных математических платформ для производственного планирования, В таких условиях велико удельное «содержание» эвристических методов, что можно считать, вообще говоря, аномальным.
Для разработки достаточно универсальной математической платформы необходимо выделить класс задач, для которого можно сформулировать общий и эффективный подход к решению. Можно перечислить разнообразные, известные ич литературы, задачи планирования, диспетчеризации и управления, модели которых формально сводятся к системам линейных дизъюнктных неравенств. Анализ литературы показывает, что методов решения дизъюнктных задач, учитывающих их специфику, пет, а число работ, посвященных их решению незначительно, В [7, 43, 57] решение таких задач сводится к решению частично целочисленной задачи. Задача целочисленного линейного программирования (ЦЛП) (а тем более частично целочисленная) является NP—полной (при ограничении на размер величин переменных), такие задачи, по общему мнению, не разрешимы за полиномиальное время [30, 33, 47, 66]. Т.е. сведением дизъюнктных задач к задачам дискретной оптимизации, мы, возможно, получаем более сложную задачу, В [38] решение дизъюнктной задачи предлагается сводить к решению некоторой совокупности задач линейного программирования.
Таким образом, актуальность разработки «собственных» методов решения дизъюнктных задач очевидна»
И) В диссертации излагается достаточно общий подход для некоторого
класса моделей задач планирования, формализуемых дизъюнктными
неравенствами, дающий возможность автоматизировать их решение, начиная
от постановки задачи и кончая программной реализацией решения. Работа
развивает общее направление создания систем автоматизации планирования
и управления сложными дискретными производственными системами.
Результаты работы имеют оригинальный, важный для практики характер.
Объект и предмет исследования. Объектом исследования являются модели задач с ограничениями в форме линейных дизъюнктных неравенств, предметом исследования является математический аппарат на основе систем линейных дизъюнктных неравенств.
Цель и задачи исследования. Целью диссертации является разработка математических методов и проіраммньїх средств для повышения степени универсальности систем автоматизации исследования и решения задач, формализуемых на основе систем линейных дизъюнктных неравенств.
Поставленная цель требует решения следующих задач:
Построить математические модели и методы решения задач на основе систем дизъюнктных неравенств.
Разработать комплекс программ, позволяющий формулировать и ренті ь различные задачи, сводящиеся к системам линейных дизъюнктных неравенств.
Методы исследований. Решение поставленных задач основывается на
использовании аппарата математического программирования.
комбинаторной оптимизации, выпуклого анализа, математической
статистики, языков спецификаций, объектно-ориентированного
проектирования.
Научная повита диссертационной работы заключается в следующем; 1. Разработан алгоритм для решения задач оптимизации с линейным функционалом и линейными ограничениями, отличающийся от стандартного симплекс-метода тем, что не использует понятия базисных
переменных и не вводит дополнительные переменные при поиске решений, в общем случае.
Разработан метод для решения задач с ограничениями в форме линейных дизъюнктных неравенств в вещественных числах, позволяющий решать задачи, не используя сведения к более сложным вариантам смешанных вещественно-целочисленных задач математического программирования.
Разработан метод для решения задач оптимизации с линейным функционалом и ограничениями в форме линейных дизъюнктных неравенств.
Предложен градиентный метод для повышения скорости сходимости стратегии устранения невязок при решении задач с линейными простыми и дизъюнктными ограничениями в вещественных числах, позволяющий существенно увеличить скорость сходимости стратегии устранения невязок.
Разработан статистически оптимальный алгоритм для решения дизъюнктных задач на основе предложенных способов сведения к задаче о минимальном взвешенном покрытии, позволяющий решать дизъюнктные задачи большого размера за приемлемое время и регулировать точность результата в установленных пределах.
На защиту выносятся следующие основные положения:
Математические модели задач производственного планирования и диспетчеризации, формализуемые ограничениями в форме дизъюнктных неравенств*
Алгоритм для решения задач оптимизации с линейным функционалом и линейными ограничениями на основе стратегии устранения невязок,
Метод Для решения задач с ограничениями в форме линейных дизъюнктных неравенств в вещественных числах на основе стратегии устранения невязок.
4. Метод для решения задач оптимизации с линейным функционалом и
ограничениями в форме линейных дизъюнктных неравенств.
Градиентный метод для повышения скорости сходимости стратегии устранения невязок для задач с линейными простыми и дизъюнктными ограничениями.
Статистически оптимальный алгоритм для решения задач с ограничениями в форме дизъюнктных неравенств на основе предложенных сведений к задаче о минимальном взвешенном покрытии.
Практическая значимость полученных результатов,
Разработаны математические методы для решения задач оптимизации, формализуемых системами линейных простых и дизъюнктных неравенств,
На базе предложенных методов и алгоритмов разработан комплекс программ, который позволяет формулировать и решать задачи планирования и диспетчеризации с ограничениями в форме дизъюнктных неравенств и унифицировать подход к автоматизации решения некоторого класса задач.
Разработано программное средство для решения одного варианта задачи оптимального раскроя и упаковки материала, позволяющее повысить точность раскроя на 5-Ю фигур в сравнении с эвристическими методами за практически приемлемое время.
Результаты работы внедрены:
На заводе крупнопанельного домостроения №1 (г. Минск).
На экспериментально-опытном заводе «Политехник» (г. Минск).
В учебный процесс Белорусского государственного университета информатики и радиоэлектроники (БГУИР), Международного гуманитарно-экономического института (г. Минск).
Связь работы с крупными научными программами* Работа выполнялась в рамках двух научно-исследовательских работ БГУИР:
1. «Разработка теоретических основ исчисления спецификаций сложных
систем». Раздел II. № Гос. регистрации 1998235 К ГБЦТ97-321,
2. «Разработка программно-математического обеспечения для быстрого
логического вывода в системах принятия решений реального времени».
№ Гос. регистрации 19972927, ГБЦ Т97-8011.
Апробация работы* Результаты работы докладывались на 63-Й научно-технической конференции Белорусского государственного технологического университета (Минск, 1999г.); на XXXV, XXXVIII научно-технических конференциях аспирантов и студентов БГУИР (Минск, 1999, 2002гг.); на Шестой межвузовской научно-теоретической конференции «Человек. Цивилизация. Культура» (Международный гуманитарно-экономический институт, Минск, 2001г.); на Международной школе-семинаре по геометрии и анализу памяти Н.В. Ефимова (Абрау-Дюрсо, МГУ, РГУ, 2002г,).
Результаты изложены в 8 научных статьях, в 2 тезисах докладов конференций, в отчете о НИР.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников из 88 наименований и восьми приложений.
В первой главе рассмотрены некоторые модели прикладных задач, записанные с помощью линейных дизъюнктных неравенств. Данный класс задач достаточно широк. В настоящее время задачи с дизъюнктными ограничениями решаются путем сведения к типовым задачам математического программирования. Показано, что сведением дизъюнктной задачи к типовым задачам, может быть получена более сложная задача. Таким образом, обоснована необходимость поиска «собственных» методов решения дизъюнктных задач, учитывающих их специфику.
Во второй главе рассмотрена стратегия устранения невязок (СУН), как основа для разработки метода решения задач с дизъюнктными ограничениями. Разработан градиентный метод для повышения скорости сходимости СУН и алгоритм на базе СУН для решения задачи линейного
14 программирования. Проведено экспериментальное сравнение разработанных
методов с известными методами математического программирования.
Третья глава посвящена разработке математических методов для решения задач с ограничениями в форме линейных дизъюнктных неравенств. Рассмотрена возможность использования метода для решения задач с дизъюнктными ограничениями для решения булевых задач. Построена модель времени счета дизъюнктных задач. Разработан статистически оптимальный алгоритм для решения задач большой размерности на базе рассмотренных вариантов сведения дизъюнктной задачи к задаче о минимальном взвешенном покрытии.
В четвертой главе рассмотрена разработка программной платформы для исследования и решения задач, формализуемых системами линейных дизъюнктных неравенств, на основе «соединения» концепции объектно-ориентированного проіраммирования и языка математических спецификаций. Также рассмотрены модели задач практической реализации.
В заключении обобщены итоги и результаты проведенных исследований.
В приложениях приведены примеры реализации методов, результаты сравнения программной реализации СУН для задач с озраниченинми в виде линейных простых и дизъюнктных неравенств с коммерческими программами Microsoft Excel, MathCad, DiseoGrad, результаты сравнения реализации СУН и алгоритма Харрис для систем линейных простых неравенств, документы, подтверждающие внедрение результатов диссертационной работы.
Модели задач теории расписаний и планирования
Большое распространение получил метод внутренних точек [87, 88] для линейной оптимизации, использующий эффективные алгоритмы, базирующиеся на ньютоновском подходе. К сожалению, эти методы не удалось распространить на целочисленные и нелинейные задачи оптимизации в общем случае.
Отличительная особенность большинства исследований по дискретной оптимизации состоит в том., что значительная часть их базируется на использовании ранее предложенных алгоритмических схем, например: 1) последовательного анализа вариантов (разработанного Михалевичем B.C. и Шором Н,3. [50, 51J); 2) методов ветвей и границ (предложенного Лэндом и До игом и развитого Литтлом, Мурти, Суини и Кэрелом); 3) методов отсечений (идея которого предложена Данцигом [34] и развита в работах Гомори) 4) локальной оптимизации (предлагаемого Сергиснко И.В,[65]), Разработанная методология последовательного анализа вариантов оказала влияние на развитие вычислительных методов оптимального управления (например, метода локальных вариаций, предложенного H.I1. Моисеевым и его учениками [53]), с успехом использована для решения широкого класса дискретных задач оптимизации в работах В.А. Емеличева и его учеников [37]. Значительный интерес для практики представляют дискретные и дискретно непрерывные задачи большой размерности, для которых I-L3 Шором предложены процедуры, сочетающие методы ветвей и границ и обобщенного градиентного спуска [80]. Определенный интерес представляют исследования, связанные с решением широкого класса задач комбинаторного типа. Для решения такого рода задач к настоящему времени разработан ряд алгоритмов, сочетающих процедуры симплекс-метода и ветвей и границ, базирующихся на алгоритме В,А. Трубина для решения целочисленных задач специального вида [71]. Близким к методам ветвей и границ является алгоритм Балаша [5], предназначенный для решения целочисленных задач с булевыми переменными, и его модификации.
К настоящему времени накопился значительный опыт в разработке и использовании алгоритмов, вкладывающихся в общую схему метода ветвей и границ. Эти алгоритмы отличаются между собой способами ветвления, вычислением оценок (границ) [43, 51, 74]. В [67, 78] предлагается комбинировать метод ветвей и границ с другими методами. Однако решение многих практических задач большой размерности с помощью алгоритмов ветвей и границ проблематично, при точном решении задач дискретной оптимизации обнаруживаются патологические задачи, для которых объем вычислений близок к полному перебору. Эффективность методов отсечений находится в прямой зависимости от эффективности различных подходов построения отсечений.
Реализация различных подходоп к построепию отсечений породила целое множество методов зтой фуппы 85[. Однако методы отсечений покачали свою непредсказуемость, меняющуюся от задачи к задаче, в частности, известны примеры задач, решение которых методом полного перебора веек допустимых значений переменных требует меньше времени, чем методами отсечений [7]. В [7, 67] отмечается, что трудности решения задач дискретной оптимизации носят не технический, а принципиальный характер, с ростом размерности задач трудности их решения весьма быстро возрастают, В работах Габасова Р. и его учеников [1, 2, 3, 13, 14] развивается адаптивный метод, который возник в результате анализа классической) симплекс-метода. Основная цель обобщения - избавиться от некоторых недостатков симплекс-метода и создать метод, который можно использовать для решения динамических задач линейного программирования. Идеи адаптивного метода получили развитие в алгоритмах решения различных задач математического программирования и оптимального управления. Они легли в основу разработанного Габасовым Рм Кирилловой Ф.М., Костюковой О-И- метода опорных задач, который также был обобщен на различные типы экстремальных задач. Теория расписаний даже в пределах исследуемого ею класса задач характеризуется ярко выраженной спецификой и индивидуальным подходом к конкретным задачам. При этом очевидно, что именно теория расписаний является одной из главных математических платформ для производственного планирования, В таких условиях велико удельное «содержание» эвристических методов, что можно считать, вообще говоря, аномальным.
Для разработки достаточно универсальной математической платформы необходимо выделить класс задач, для которого можно сформулировать общий и эффективный подход к решению. Можно перечислить разнообразные, известные ич литературы, задачи планирования, диспетчеризации и управления, модели которых формально сводятся к системам линейных дизъюнктных неравенств. Анализ литературы показывает, что методов решения дизъюнктных задач, учитывающих их специфику, пет, а число работ, посвященных их решению незначительно, В [7, 43, 57] решение таких задач сводится к решению частично целочисленной задачи. Задача целочисленного линейного программирования (ЦЛП) (а тем более частично целочисленная) является NP—полной (при ограничении на размер величин переменных), такие задачи, по общему мнению, не разрешимы за полиномиальное время [30, 33, 47, 66]. Т.е. сведением дизъюнктных задач к задачам дискретной оптимизации, мы, возможно, получаем более сложную задачу, В [38] решение дизъюнктной задачи предлагается сводить к решению некоторой совокупности задач линейного программирования.
Вариант реализации стратегии устранения невязок без неравенств 0-блока
Рассмотрим вариант реализации СУН без неравенств 0-блока, который позволяет ускорить решение за счет уменьшения размера задачи. Рассмотрим систему неравенств (2.2). Неравенства z, 0., ..., zri 0 назовем неравенствами 0-блока. При реализации СУН неравенства 0-блока хранят подстановки переменных. Для примера рассмотрим невязку т: а,іЛіу+а ін2і7±... + переменной zi из невязки т преобразуется к неравенству, хранящему подстановку для z{: сама же невязка m преобразуется к О-неравенству В целях уменьшения размера матрицы не будем использовать неравенства 0-блока для хранения подстановок переменных, вместо них будем использовать основные неравенства: на месте образования 0-неравенства типа (2.8) будем записывать неравенство, хранящее подстановку переменной, типа (27). При этом заменяемая переменная привязывается к неравенству, хранящему ее решение, исходя из следующих правил: 1. Переменная z, заменяется впервые, например, из неравенства т переменная z, привязывается к неравенству т. 2.
Переменная z, заменяется, например, из неравенства п, к которому уже привязана переменная, например, z - привязка переменной г; заменяется на привязку к переменной zrt т.е. переменная z будет зависеть от z} (как только переменная z, будет заменена, например, из неравенства ш, привязка переменной z} заменяется на привязку к неравенству т). Переменная zl привязывается к неравенству п. 3. Переменная zi заменяется, например, из неравенства т, причем, с переменной zf связана переменная zJ - привязка переменной z; заменяется на привязку к неравенству т. Значения переменных определяются из неравенств, к которым они привязаны. Таким образом, мы сократили размер матрицы на п неравенств {п -число переменных). В приложении 2 приведены сравнительные результаты работы программ, реализующих СУН с использованием неравенств 0-блока и без его использования. Из результатов видно, что без использования 0-блока время решения задачи стабильно уменьшается, в отдельных случаях в 1,3 раза. В приложении 3 приведено описание алгоритма Харрис и сравнительные результаты работы программ, реализуюшик СУН (без 0-блока) и алгоритм Харрис применительно к СУН. Рассмотрим применение СУН для решения задачи линейного программирования [24]. Будем рассматривать систему, имеющую следующий общий вид: Алгоритм реализуется следующим образом: 1.
Выполняем СУН до тех пор, пока не будет: (A) получена стоп-невязка - система неравенств несовместна, конец; получена система без невязок: 4. Если и во все неравенства системы входит с положительным коэффициентом, то целевая функция не ограничена, иначе находим максимальное значение и;5 при котором образуется первая невязка, пусть это неравенство 1. Увеличиваем целевую функцию, полагая: wk a h +w/lbl (где wft+, 0 - переменная, заменяющая wk), проводим замену w{ на l +w f во всех неравенствах системы и целевой функции и переходим на шаг 5. 5. Возможны два варианта: (A) получена невязка /, в которой все коэффициенты при переменных а\} О - оптимальное решение находится автоматически, конец; (B) из невязки I выражаем переменную с положительным коэффициентом по правилам СУН, проводим замену этой переменной в текущей системе неравенств, переходим на шаг 4. Замечание. Начиная с шага 4 СУН «работает по принципу» стандартного симплексного алгоритма, не используя, впрочем, понятия базиса и базисных переменных. Теорема 11. Стратегия устранения невязок финитна при решении оптимизационной задачи линейного программирования в стандартной форме для систем простых неравенств. Доказательство. Пусть при итерациях СУП получена выполнимая система неравенств. Теперь невязки обусловлены только величинами характеристических переменных, которые СУН не заменяет, а лишь увеличивает их значения, полагая wk =я 0 tw(tl (Й „ 0). Тогда, из ранее доказанного, следует невозможность повторить конфигурацию 0-неравенствч если сразу задать wk = a (J+u M что и дает требуемый результат. Ясно, что нельзя бесконечно увеличивать wk и при этом все время получать уникальные конфигурации О-иеравенств. Так что в случае неограниченности F решение рано или поздно отыщется. Заметим, что целевая функция не ограничена, когда во всех неравенствах одна и та же переменная (не обязательно характеристическая) входит с положительным коэффициентом. Из теоремы 11, впрочем, следует, что если F не ограничена, то рано или поздно получим систему, где не ограничена будет характеристическая переменная-Пример реализации СУН для задачи линейного программирования приведен в приложении 4. В данной главе рассмотрена стратегия устранения невязок для решения задач с ограничениями в форме простых линейных неравенств в вещественных числах. Доказаны теоремы о сходимости стратегии устранения невязок, 1. Разработан градиентный метод для ускорения сходимости стратегии устранения невязок, предназначенный для поиска наиболее предпочтительной переменной для замены и неравенства, из которого определяется подстановка для этой переменной. Получены общие оценки сложности алгоритма. 2. Разработан алгоритм для реализации стратегии устранения невязок без неравенств О-блока, позволяющий уменьшить время решения задачи за счет сокращения размера задачи на число неравенств равное числу переменных. 3- Разработан алгоритм на основе стратегии устранения невязок для решения задач оптимизации на множестве простых линейных неравенств в вещественных числах, 4, Написаны программы, реализующие разработанные алгоритмы. Проведена практическая апробация методов и экспериментальное сравнение программной реализации разработанных методов с известными методами.
Построение модели времени счета задач на линейных дизъюнктных неравенствах
Можно поступить несколько иначе, например, положим х = 10у, так что 0 v 100. Полагаем далее При этом точность вычисления х не хуже 0,825 и т.п. Ясно, что достигаемая этим сложность сведения задачи к решению системы псевдобулевых неравенств имеет вид nO{clog2 b), где п - число переменных; b - максимальное значение верхней границы для вещественной переменной. Сведение полиномиально отлит (число ограничений) по затратам памяти и времени. Таким образом, мы получаем задачу псевдобулева программирования (ЗБП). Для ЗБП мы предлагаем технику сведения к задаче о взвешенном минимальном покрытии, для которой можно использовать статистически оптимальный алгоритм [16, 26]. Рассмотрим 0,1 - матрицу С. Строка / покрывает столбец у, если C(i,j) = l. Множество строк 7г является неизбыточным покрытием матрицы С, если каждый столбец матрицы покрывается как минимум одной строкой из л" и никакое собственное подмножество строк П П этим свойством не обладает. Задача минимального взвешенного покрытия (ЗМВП) сводится к поиску неизбыточного покрытия с минимальным суммарным весим образующих его строк. Для каждого ограничения ЗЬП мы строим матрицу (покрытия) ограничения следующим образом. Пусть ограничение имеет такой вид: 2х, + 16х, -4г. -8х4 10
Избавимся от отрицательных членов в правой части заменой х( = 1 - х,: 2х} + 16х? -4 + 4хз -8 + 8x4 10 или 2х( + 16х, + 4хч + 8х4 22. Расширим левую часть ограничения новыми переменными л,, контрарными к уже присутствующим и взятым с весьма малыми коэффициентами: 2х, + 1бх2+4хі+8хі+0,0Іхі +0,01x2+0.01 4 0.01xj 22. Для данного ограничения построим основную матрицу совместности В: Теперь, наконец, нам остается по матрице В построить нужную нам матрицу покрытия ограничения С по следующему правилу: Строки в С соответствуют инверсным строкам в В. Столбцов в С ровно половина от общего числа «1» в В, Каждый столбец С строится для конкретной «1» в верхней диагональной матрице В так, что если единица стоит в строке а и столбце ,то в С в данном столбце стоят ровно две единицы в строках а и /?. Пусть л-""" - минимальное взвешенное покрытие С, например я-тш = {а,/?,...,/}, Х- множество всех строк матрицы О, Тогда, если множество X W""n не удовлетворяет искомому ограничению G, то это ограничение не выполнимо, где \ —теоретико-множественная разность. Доказательство теоремы дано в [16].
Процесс решения ЗБП будет заключаться в формировании для каждого ограничения собственной матрицы покрытия ограничения с последующим наращиванием этих матриц путем присоединения к ним новых столбцов-следствий (резольвент). При этом для каждой матрицы покрытия можно оценить вероятность наличия покрытия меньшей стоимости. Если эта вероятность становится пренебрежительно малой, а решение не найдено, то с нысокой степенью уверенности можно утверждать, что исходная задача решения не имеет. Теперь опишем саму процедуру, 1- Ищем неизбыточное покрытие для всех матриц-ограничений. Для этого выстроим из всех таких матриц одну общую матрицу по схеме, указанной ниже: хг Все матрицы имеют общий набор строк. Назовем общую объединенную матрицу Gtt. Найдем покрытие тг матрицы G„, например, «жадным» алгоритмом. Данное покрытие тг хотя бы для одной из матриц-ограничений должно быть неизбыточным. Для проверки избыточности мы используем технику синдромных столбцов, как описано в [16, 26], Теперь заметим, что в решение исходной ЗБП не может войти никакая контрарная пара литер, В силу теоремы 13 минимальное взвешенное покрытие должно содержать ровно п строк, если все ограничения выполнимы; п - число индексов переменных. Итак, если покрытие л содержит более п строк, то построим резольвенту на матрице Gtl по технике, описанной в [26]. При этом веса строк не учитываем, т.е. попросту строим резольвенту в предположении, что тг не минимально, Резольвента есть новый дополнительный столбец. Если резольвента нулевая, то задача не имеет допустимого решения.
В противном случае присоединим резольвенту к матрице Go. 2. Пусть л содержит ровно п строк, т.е. неизбыточно ни для одной G, По теореме 13 получаем множество строк, дополнительное к л\ являющееся решением для исходной задачи ЗБП. Это решение может быть не допустимым, так как, скажем нарушает ограничение Gk. Теперь уже строим для Gk столбец-резольвенту для случая взвешенного покрытия к, т.е. учитываем веса строк из п в Gk. Техника построения резольвенты в этом случае описана в [16]. Опять, если резольвента нулевая, то решения нет. 3. Процесс присоединения резольвент не бесконечен и сопровождается проверкой соотношения для вероятности сущее і нонании в матрице G, покрытия с числом строк, равным п. Для матрицы нарушенного ограничения оценивается вероятность существования неизбьпочного покрытия меньшей стоимости.
Технологический процесс изготовления изделий на заводе крупно-панельного домостроения №1
Завод КПД-1 специализируется на выпуске изделий, предназначенных для панельного домостроения. Список изделий КПД-1 включает следующие наименования: 1) внутренние стеновые панели и перегородки; 2) наружные стеновые панели; 3) панели перекрытий; 4) панели покрытий; 5) кабины санитарно-технические; 6) лестничные марши и лестничные площадки; 7) шахты лифтов; 8) плиты перекрытий балконов и лоджий; 9) панели стеновые входов; 10) козырьки входов; 11) прогоны, ригели, балки; 12) плиты парапетные; 13) панели вентшахты и вентблоки; 14) блоки бетонные стен подвалов, ленточные фундаменты; 15) изделия МАФ; 16) плиты бетонные тротуарные, дорожные плиты; 17) ложки, балки, опорные подушки теплотрасс; 18) изделия канализационных колодцев; 19) камни бортовые; 20) оголовки свайных фундаментов; 21) сваи; 22) телефонные колодцы; 23) фундаменты подпорных стен; 24) ограждения лоджий; 25) камни стеновые; 26) элементы оград. Месячное задание на выпуск изделий доводит головная организация МАПИД. Производство изделий реализуется формовочным и металлообрабатывающим цехами. Основными материалами для изготовления изделий являются цементы различных маркировок, песок, вода, арматура, нитрит но-натрие вые добавки, щебень, гравий и т.д. Изготовление панелей осуществляется заливкой подготовленного раствора в соответствующие формы, где осуществляется последующее затвердевание.
Таким образом, пропускная способность формовочного цеха определяется емкостью форм предназначенных для различных конфигураций панелей и блоков, трудоемкостью операций, длительностью смены. Формализуем задачу оперативного планирования следующим образом; П, - план выпуска изделий г -го наименования (/ = 1, к); Фг - фактическое изготовление изделий /-го наименования к текущему моменту; Л, - максимально допустимое отставание от графика но изделию і-го наименования; t — время, истекшее с начала планового периода; Т- длительность планового периода; в —длительность смены; vm - запас m-го наименования материала; п1 - норма расхода т-го материала на изделие /-го наименования; S- рабочая площадь цеха; /, — площадь формы для /-го изделия. Все приведенные величины известны. хг- планируемые количества изделий /-го наименования на оперативном отрезке (смена/сутки) (подлежат определению). Пусть (л — количество каналов обслуживания цеха; S Ограничение (4.2) учитывает пропускную способность системы; ограничение (4.3) учитывает запасы материалов; ограничение (4.4) учитывает максимально-допустимое отставание от плана выпуска изделий; условия (4.5) означают, что количество изделий /-го наименования должно быть больше некоторого минимального количества xj1 (нет смысла выпускать, например, одно изделие). Для данной задачи разработана программная система, реализующая алгоритм на основе СУН для дизъюнктных задач. Получено практическое внедрение. Включает следующие операции: 1. Изготовление заготовки (резка материала). Фольгированный материал проверяют на соответствие ТУ и нарезают заготовки плат с припуском 5-10 мм, 2. Печатание рисунка схемы в слое светочувствительной эмульсии и защита схемы лаком. Печатание схемы ведут в светополировальной раме так, чтобы полировальный слой заготовки соприкасался с эмульсионной стороной негатива фотошаблона
После экскопирования производят проявление, окрашивание изображения и химическое дубление в растворе хромового ангидрида- Готовую заготовку высушиваю], термообрабатывают и покрывают со всех сторон слоем защитного лака. 3. Сверление отверстий согласно чертежу. Сверление производят на координатно-сверл ильных и вертикально-сверлильных станках с последующим зенкованием отверстий с обеих сторон заготовки. 4. Химическое осаждение меди в отверстиях. Эту операцию производят в специальных ваннах из винипласта, установленных в устройствах для встряхивания или вибрации. После нее защитный лак удаляют. Либо выполняется гальваническое осаждение меди в ваннах электрохимического меднения. После меднения заготовки промывают и сушат. 5, Лужение припоем или серебрение. Участки заготовки, не защищенные фоторезистом, покрывают сплавом ПОСВ-50 (олово 25%, свинец 25%, висмут 50%) или слоем серебра, после чего слой фоторезиста удаляют. 6. Травление фольги. Эту операцию производят путем химического травления в растворе хлорного железа.
