Алгоритм - линейное программирование
Cтраница 2
Следует заметить, что для решения задачи по вычислению стратегии управления используют не только метод динамического программирования. В частности, возможно решать задачи, считавшиеся традиционно задачами динамического программирования, с помощью алгоритмов линейного программирования. Такой подход более удобен в вычислительном отношении и поэтому используется в дальнейшем для определения марковских однородных стратегий управления. [16]
 |
Сложность алгоритмов построения паросочетании. [17] |
Сейчас мы представим выполняемый за полиномиальное время алгоритм для нахождения паросочетания максимального веса. Поскольку хорошая характеризация была получена из теоремы двойственности, мы вправе ожидать, что этот алгоритм можно построить, применяя алгоритм линейного программирования к политопу паре-сочетании. Однако ситуация не столь проста, ибо описание политопа паросочетании как множества решений системы линейных неравенств включает экспоненциально много ограничений. [18]
Несмотря на то что аппаратные и программные средства устарели и локальная сеть не используется, основные компоненты и программы системы являются типичными для задач управления предприятием. Система SIVA содержит подсистему подготовки решений, основанную на статистическом анализе сводных данных, и оптимизации состава изделий на базе алгоритмов линейного программирования. Программная подсистема позволяет минимизировать время простоя оборудования, расход энергии, сырья и возможность реализации на рынке. [19]
Для различных типоразмеров ТА величина а отлична, однако в операциях синтеза ТС принимается постоянная величина. Значение К принимается постоянным. Для решения ЗОН - используется алгоритм линейного программирования - модифицированный симплекс-метод, а не методы целочисленного линейного программирования. Матрица декомпозиции исходных потоков на тепловые элементы носит вспомогательный характер, размерность которой растет при увеличении числа исходных и результирующих потоков. От этой матрицы предусмотрен переход к матрице назначения с большой размерностью без учета условия физической реализуемости операции теплообмена. [20]
Существуют и другие способы, среди которых особый интерес с вычислительной точки зрения представляют те методы, которые сформулированы на основе двойственной задачи. Вообще говоря, методы типа симплекс-метода есть не что иное, как несколько усложненные методы градиентного спуска, предназначенные для отыскания экстремумов линейных функций при наличии ограничений в виде линейных неравенств. Подготовка алгоритма линейного программирования для решения на ЭВМ обычно представляет собой более сложную задачу по сравнению с такой же операцией, примененной для более простых процедур спуска, которые мы описывали ранее. [21]
Линейное программирование ( ЛП) - это метод оптимизации моделей, в которых целевые функции и ограничения строго линейны. ЛП успешно применяется в военной области, индустрии, сельском хозяйстве, транспортной отрасли, экономике, системе здравохранения и даже в социальных науках. Широкое использование этого метода также подкрепляется высокоэффективными компьютерными алгоритмами, реализующими данный метод. На алгоритмах линейного программирования ( учитывая их компьютерную эффективность) базируются оптимизационные алгоритмы для других, более сложных типов моделей и задач исследования операций, включая целочисленное, нелинейное и стохастическое программирование. [22]
В данной книге кроме математического описания марковских управляемых процессов и алгоритмов нахождения оптимальных управлений этими процессами авторы рассмотрели такие интересные в теоретическом и прикладном отношении вопросы, как полумарковские управляемые процессы, обобщенные процессы принятия решений, стохастические игры, теоремы существования оптимальных и почти оптимальных стратегий. Приведены итерационные алгоритмы и алгоритмы линейного программирования решения задач оптимизации. Особое внимание уделяется связи между этими алгоритмами. [23]
Один из методов именуется методом секущих плоскостей; в нем используется линейная верхняя грань ( 8) из разд. На любой итерации k имеется текущая проверяемая допустимая точка xh, а также система линейных ограничений, включающая ограничения исходной задачи и некоторые отсекающие ограничения, которые описываются ниже. Задача дополняется переменной х0, входящей во все отсекающие ограничения. Переменную х0 необходимо максимизировать, так что на итерации k задача решается с помощью алгоритма линейного программирования. [24]
Необходимо при известной стоимости замены ( под профилактикой в этих работах понимается замена элементов системы) определить такую стратегию ( правило) замены, которая минимизирует средние удельные затраты на проведение профилактик в единицу времени. Такие задачи рассмотрены в работах [12, 121, 122] и относятся к стареющим радиоэлектронным системам. В работе [12] для решения задачи увеличения показателей готовности и надежности сложных объектов на основе определения оптимальной стратегии управления поведением системы используется математическая модель марковского процесса переходов системы из состояния в состояние. Показано, что задачи по вычислению стратегии управления, считавшиеся задачами динамического программирования, можно решать с использованием алгоритмов линейного программирования. Однако в этих работах [12, 121, 122] не излагается практическая реализация результатов решения указанной задачи. [25]
В 1968 г., - возможно, под влиянием общественных волнений, охвативших страну - я решил перебраться в Калифорнийский университет в Беркли, который был центром студенческого движения. Возможность работать с такими выдающимися учеными, как Алан Хофман, Раймонд Миллер, Арнольд Розенберг и Шмуэль Виноград, была просто бесценной. Мой новый круг коллег включал Майкла Харрисона, известного специалиста по теории языков, который и соблазнил меня перебраться в Беркли; Юджина Лоулера, эксперта по комбинаторной оптимизации; Мануэля Блюма, основателя теории сложности, который потом выполнил выдающуюся работу на границе теории чисел и криптографии, и Стивена Кука, чья работа но теории сложности повлияет на меня так сильно через несколько лет. В Отделении математики работали Джулия Робинсон, чья работа над 10 - й проблемой Гильберта вскоре принесет плоды; Роберт Соловей, знаменитый логик, открывший важный рандомизированный алгоритм распознавания простоты числа, и Стив Смейл, чья потрясающая работа по вероятностному анализу алгоритмов линейного программирования оказала на меня влияние через несколько лет. [26]
Страницы: 1 2