Разработка математической модели оптимизации распределения ресурсов
Оптимизация выбора варианта распределения ресурсов для сокращения общего времени выполнения некоторого задания. Оценка длительности выполнения каждого действия, общего времени выполнения всех действий. Алгоритмы решения общей задачи распределения ресурса.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 14.06.2017 |
| Размер файла | 469,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
8
Размещено на http://www.allbest.ru/
Содержание
- Введение
- Содержательная постановка и формализация задачи оптимизации выбора варианта распределение ресурсов
- Оценка длительности выполнения каждого действия
- Оценка общего времени выполнения всех действий
- Алгоритмы решения общей задачи распределения ресурса
- Заключение
Введение
При решении задач управления особая роль отводится работе управляющей системы, в состав которой входит логико-вычислительная подсистема, информационная подсистема, исполнительная подсистема. Логико-вычислительная подсистема представляет совокупность элементов для переработки информации и синтеза решений; информационная подсистема представляет собой совокупность элементов для восприятия и представления информации, необходимой для синтеза решений; исполнительная подсистема представляет совокупность элементов для формирования управляющих воздействий на объект управления. Одним из способов оптимизации управления является оптимизация работы исполнительной подсистемы. Данная подсистема при решении задач управления выполняет некоторые действия с целью формирования управляющих воздействий на управляемую систему. Эти действия выполняются в определенной последовательности, выполнение отдельных последующих действий может зависеть от предыдущих. Отдельные действия могут выполняться параллельно.
В качестве критерия оптимизации выступает время выполнения всей совокупности действий по принятию решения. Для сокращения времени выполнения всех действий могут использоваться различные варианты распределения ресурсов. С этой целью необходимо определить оптимальный выбор распределения ресурсов.
Целью работы является разработка математической модели оптимизации распределения ресурсов для сокращения времени на принятие управленческих решений и алгоритмов решения общей задачи распределения ресурса.
оптимизация математическая модель алгоритм
Содержательная постановка и формализация задачи оптимизации выбора варианта распределение ресурсов
Рассмотрим задачу оптимизации выбора варианта распределения ресурсов для сокращения общего времени выполнения некоторого задания. Будем считать, что задание предполагает выполнение некоторой совокупности частично упорядоченных действий группами исполнителей. При этом каждое действие закреплено за конкретной группой. В свою очередь действие представляет собой совокупность частично упорядоченных операций (поддействий), каждую из которых может выполнять любой человек из соответствующей группы. Следовательно, время выполнения действия зависит от количества исполнителей. Под распределением ресурса будем понимать увеличение числа человек в группах. Это может приводить к общему сокращению времени выполнения данного задания. Указанная задача является сложной трёхуровневой комбинаторной задачей, для решения которой необходимо осуществить решение следующих частных задач:
1) оценить длительность выполнения каждого действия в зависимости от числа исполнителей, входящих в группу, выполняющую этого действия;
2) оценить общее время выполнения всех действий в зависимости от количественного состава групп исполнителей;
3) найти такое распределение имеющегося ресурса исполнителей по группам, чтобы минимизировать общее время выполнения всех действий.
Осуществим формализацию этой задачи. Обозначим Д D1,D2,.,Dn - множество действий (n - количество действий). На множестве Д определим отношение частичного порядка E Д Д такое, что Di,Dj, если действие Di должно предшествовать действию Dj. Будем считать, что для каждого произвольного действия D Д задана группа исполнителей G (D) И G1,.,Gm (m - количество групп исполнителей, m ? n) и время выполнения действия TD. Каждое действие Di Д предполагает выполнение множества операций Di di1,.,diki (ki - количество операций при выполнении действий Di). В свою очередь каждая операция di j характеризуется временем ее выполнения ti j. Будем считать, что на множестве Di также задано отношение частичного порядка Ei Di Di такое, что di j,dik Ei, если операция di j должна предшествовать операции dik. Для каждого варианта распределения ресурса каждая группа Gj характеризуется имеющимся количеством исполнителей NGj.
Оценка длительности выполнения каждого действия
Первоначально рассмотрим задачи оценки длительности выполнения всей совокупности действий для заданных количеств исполнителей каждой группе N1, N2,., Nm.
На первом этапе необходимо оценить длительность Ti выполнения каждого действия Di. Очевидно Ti определяется значениями длительности операций tij, отношением частичного порядка Ei и количеством исполнителей Ni в группе, которая выполняет это действие. Учитывая, что ti j и Ei в дальнейшем не изменяются, а количество исполнителей при распределении ресурса может варьироваться, будем считать Ti f Ni.
Рассмотрим вопрос оценки величин Ti f Ni. Представим процесс выполнения операций действия Di как последовательность шагов такую, что каждый шаг - выполнение одной операции одним исполнителем. Обозначим исполнителей группы GИ, выполняющей действие Di. Обозначим
Обратимся к описанию функциональных зависимостей между операциями и исполнителями. Обозначим Ai j - момент начала выполнения операции di j, тогда Ai j ti j - момент ее окончания. Действие заканчивается после последнего шага выполнения операций. Следовательно,
Ti max (Aij (X) tij) X kjs, где i 1,.,n. (1)
Зададим отношение частичного порядка Ei матрицей Bi (bsti),s,t 1,.,kj, где
Опишем ограничения на последовательность выполнения шагов: bsti (Ais (X) tis) Ait (X) - условие того, что операция dis должна заканчиваться раньше начала операции dit; (2), Ais (X) tis) Xsjk-1 Xtjk Ait Xsjk-1 Xtjk - условие того, что если на k 1шаге выполняется операция dis, а на k-м шаге - операция dit, то dis должна завершиться до начала dit; (3), Xsjk Xtjk 0, s t - условие того, что на каждом шаге выполняется только одна операция. (4), - условие того, что каждая операция выполняется только на одном шаге. (5)
Общая задача оценки времени выполнения действия Di имеет вид задачи нелинейного булева программирования нахождения X*, минимизирующего (1) при ограничениях (2) - (5).
Оценка общего времени выполнения всех действий
Значение T определяется значениями длительностей Ti отдельных действий, определенных на предыдущем этапе, а также отношением частичного порядка E и распределением групп исполнителей по действиям. Вновь будем считать, что выполнение действий представляет собой последовательность шагов такую, что каждый шаг - выполнение одного действия соответствующей группой исполнителей. Обозначим
AY - момент начала выполнения действия Di.
Вся совокупность действий завершается, когда завершилось последнее действие, т.е.
T max (Ai (Y) Ti), где i 1,.,n. (6)
Зададим отношение частичного порядка E матрицей B bst,s,t,.,ki,, где
По аналогии с предыдущим этапом определим ограничения на последовательность действий
bst (As (Y) Ts) At (Y) (7)
(A (Y) Ts) Ys (k1) mYtkm At (Y), гдеYs (k 1) mYtk 0,s t, (8)
(9)
Кроме того, однозначность задания группы исполнителей для каждого действия определяется условием
(10)
Распределение ресурса исполнителей для минимизации общего времени выполнения всех действий.
Обозначим Z Z1,.,Zm - вариант распределения ресурса исполнителей по группам Z j, - ресурс, выделяемый группе Gj.
Тогда время выполнения действия Di, осуществляемое группой G +j определяется как Ti Ti (X,Z), где Ti - функция, описывающая решение задачи (1) - (6).
T TY,TiX,Z,
где T - функция, описывающая результат решения задачи (1) - (6) на втором этапе [4].
Для значений Z Z1,.,Zm, таких, что Zi Ж, где Z - множество целых чисел, должны быть выполнены следующие ограничения
(11)
Zi 0 (12)
Таким образом, общая задача распределения ресурса имеет следующий вид вид:
Найти (X*,Y*,Z*) = ArgminT (Y, Ti (X,Z)) при ограничениях (2) - (5), (7) - (12).
Алгоритмы решения общей задачи распределения ресурса
Для построения алгоритма нахождения оптимального варианта распределения ресурса необходимо определить группы Gi, которые выполняют свои действия Di за максимальное время TD. Это обусловлено тем, что использование ресурса при максимальной продолжительности выполнения действий приводит к более значительному сокращению времени выполнения действий. Ti jMi - длительность операции при добавлении M количества исполнителей. Необходимо найти максимальное количество исполнителей Mimax, которое целесообразно добавлять в группы Gi, для максимального сокращения времени выполнения всех действий TD.
Если количество единиц ресурса невелико, то задача может быть решена полным перебором. В остальных случаях может быть найдено только приближённое решение. В рамках данной работы приведём общее описание двух алгоритмов без их детализации.
1. На первом этапе с помощью алгоритма, относящегося к классу "жадных алгоритмов", найдём приближенное решение использования выделенного ресурса, который позволяет максимально использовать имеющийся ресурс Zmax.
Будем считать, что все группы исполнителей упорядочены по убыванию суммарной длительности выполняемых операций.
Первоначально выделим такую минимальную часть ресурса, которая обеспечивает максимальное сокращение суммарного времени выполнения всех действий.
Аналогично выделяем ресурс для второй и последующих групп исполнителей до тех пор, пока он не будет исчерпан. Графически это выглядит следующим образом (рис.1).
На последующих этапах осуществляется улучшение полученного результата на основе выбора альтернативных вариантов распределения ресурса по группам.
Сначала рассматриваются все рациональные, т.е. приводящие к сокращению общего времени, варианты распределения последних исполнителей из ресурса. Если при этом улучшается общее время T, то запомним новый вариант.
Далее рассматриваем варианты распределения двух последних исполнителей и т.д. Процесс продолжается до тех пор, пока не будут рассмотрены все варианты или, исчерпан лимит времени на решение задачи.
2. Другой алгоритм решения задачи может быть основан на идеях алгоритмов "градиентного спуска". Каждый раз распределяется одна единица ресурса и выбирается вариант, обеспечивающий максимальное сокращение времени (рис. 2). Алгоритм продолжается до тех пор, пока не будет исчерпан весь ресурс.
Заключение
Разработанные модель и алгоритмы могут быть использованы для оптимизации выбора варианта распределения ресурсов в подсистемах органа управления с целью сокращения общего времени выработки управляющих воздействий в системах управления различного назначения.
Размещено на Allbest.ru
...Подобные документы
Построение базовой аналитической модели оптимизации распределения затрат на рекламу и ее времени между радио и телевидением. Разработка приложения для решения оптимизационной задачи с помощью симплекс-метода. Испытание модели на чувствительность.
курсовая работа [3,2 M], добавлен 11.02.2014Постановка простейшей задачи оптимального распределения ограниченного ресурса. Эффективное использование и распределение ограниченных ресурсов. Эффективность каждого из рассматриваемых технологических процессов. Вычислительная схема решения задачи.
курсовая работа [308,9 K], добавлен 12.01.2009Путь обработки запроса в реляционной СУБД. Оптимизации запросов на примере Oracle 9.2. Исследования по оптимизации планов выполнения запросов за счёт нормализации таблиц, выбора табличного пространства и распределения таблиц по этому пространству.
курсовая работа [364,8 K], добавлен 12.01.2012Функционирование систем массового обслуживания с разными типами заявок. Построение математической модели. Постановка задачи оптимизации среднего времени ожидания. Решение задачи оптимизации и разработка программного кода для оптимизации системы.
курсовая работа [538,5 K], добавлен 11.08.2017Теория распределения ресурсов по разным пунктам для обеспечения эффективного обслуживания транспортных перевозок или операций, которые невозможно совместить во времени. Решение задачи о назначениях при помощи преобразования матрицы. Расчет плана продаж.
курсовая работа [2,7 M], добавлен 10.04.2019Разработка программной реализации для решения задач бесприоритетного и приоритетного распределений. Контрольный пример решения задачи бесприоритетного распределения со структурой иерархии 5-4-2. Алгоритм расчета задачи одноресурсного распределения.
курсовая работа [2,3 M], добавлен 05.01.2013Определение оптимального плана производства продукции при наличии определенных ресурсов, проблемы оптимизации распределения неоднородных ресурсов на производстве с помощью системы символьной математики Mathcad. Составление алгоритма симплекс-метода.
курсовая работа [676,5 K], добавлен 20.09.2009Функция записи в сжатое представление массива. Распечатка внутреннего представления матрицы. Результат работы программы при Xm=4. Построение графика зависимости T=F(Xm) по начальному значению времени выполнения алгоритма. Запись элементов в массив.
лабораторная работа [471,8 K], добавлен 05.12.2015Модель динамического программирования для решения задач оптимального распределения ресурсов. Принцип оптимальности, уравнение Беллмана. Двумерная и дискретная динамическая модель. Значение метода в решении прикладных задач различных областей науки.
курсовая работа [400,2 K], добавлен 01.10.2009Общая характеристика задач фиксации времени выполнения программ: выполнение процессов реального времени, профилирование. Программируемый интервальный таймер как весьма сложная система. Анализ основных функций, возвращающих стандартное время Windows.
курсовая работа [82,7 K], добавлен 18.05.2014Функционирование систем массового обслуживания с разными типами заявок. Построение математической модели, постановка задачи оптимизации среднего времени ожидания. Решение задачи оптимизации системы. Разработка программного кода для оптимизации системы.
дипломная работа [581,7 K], добавлен 27.10.2017Разработка структурной, функциональной и принципиальной схем блока выполнения арифметической операции над числами, представленными в дополнительном коде в форме с плавающей запятой. Алгоритмы выполнения операции умножения. Анализ временных задержек.
курсовая работа [287,7 K], добавлен 07.06.2013Моделирование работы генератора случайных двоичных чисел с ограниченной последовательностью 0 и 1, подчиняющегося равномерному закону распределения, заданному с помощью модели Гильберта. Представление программного решения задачи средствами языка С++.
лабораторная работа [857,7 K], добавлен 05.06.2011Понятие и функции комплексных чисел. Правила выполнения арифметических операций с комплексными числами. Действия с комплексными числами: сложение, вычитание, произведение, деление. Программная реализация решения задачи. Пример выполнения программы.
курсовая работа [398,8 K], добавлен 01.02.2010Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение.
курсовая работа [784,0 K], добавлен 21.05.2015Разработка дневного рациона минимальной стоимости при сохранении содержания баланса питательных веществ. Определение ресурсов на максимум выручки от реализации готовой продукции. Построение баланса производства и распределения продукции предприятий.
контрольная работа [792,5 K], добавлен 23.04.2013Применение циклической управляющией структуры для организации многократного выполнения некоторого оператора. Конструкция цикла: заголовок и тело, и алгоритм выполнения операторов while, do while и for. Отличия циклов с постусловием и предусловием.
контрольная работа [65,8 K], добавлен 30.12.2010Схематическое изображение операций и элементов производственного процесса (программы), а также взаимосвязи порядка и последовательности их выполнения. Оптимизация сетевого графика. Организация ведения информационной базы, среды программирования.
курсовая работа [37,8 K], добавлен 14.03.2009Проведение урока по теме: "Действия с векторами". Повторение правил действий над векторами и применение знаний предмета информатики для решения геометрических задач по готовым чертежам. Закрепление приобретенных навыков выполнения действий над векторами.
разработка урока [531,8 K], добавлен 14.10.2010Автоматизация проектирования на основе применения ЭВМ. Алгоритм решения задачи расчета плоскоконической передачи. Контроль корректности функционирования и пригодности программы к эксплуатации. Оптимизация конической передачи. Условия выполнения программы.
курсовая работа [796,6 K], добавлен 24.06.2013
