Методы оптимизации процессов

Размещено на http://allbest.ru

Содержание

Ведение

1. Построение математической модели

2. Теоретический материал

3. Численный пример

Заключение

Список используемой литературы

Введение

По компьютерной сети из компьютеров С1…Сn требуется за секунду переслать Z Мбайт с компьютера C1 на Cn. Известны максимальные пропускные способности Dij Мбайт/с для всех имеющихся каналов связи между компьютерами, конфигурация сети, с также стоимость Aij пересылки 1 Мбайта с компьютера C1 на Cj.

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

Оптимизация -- целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Поиски оптимальных решений привели к созданию специальных математических методов и уже в XVIII веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины XX века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

- количество продукции - расход сырья

- количество продукции - качество продукции

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

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

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

Разновидностью оптимизационных задач является задачи о распределении ресурсов.

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

а) заданы работы и ресурсы. Распределить ресурсы между работами таким образом, чтобы максимизировать некоторую меру эффективности (прибыль) или минимизировать ожидаемые затраты (издержки производства).

б) заданы только наличные ресурсы. Определить, какой состав работ можно выполнить с учетом этих ресурсов, чтобы обеспечить максимум некоторой меры эффективности.

в) заданы только работы. Определить, какие ресурсы необходимы для того, чтобы минимизировать суммарные издержки производства.

1. Построение математической модели

Планируется распределение начального числа Мбайт между каналами связи. Выделение ij -тому каналу объема данных xij приносит затраты на пересылку xij*aij. Таким образом функция затрат имеет вид:

Так как по заданию затраты суммарные затраты необходимо свести к минимуму, то данная функция должна стремиться к минимуму

При этом

Где Z- число Мбайт, которое необходимо передать.

Каналу связи могут быть выделены данные, не превышающие его пропускную способность, отсюда следует формула

2.Теоретический материал

Динамическое программирование (ДП) - это метод, приспособленный для решения оптимизационных задач, связанных с многошаговыми процессами. В задачах динамического программирования находится ряд оптимальных решений последовательно для каждого этапа, обеспечивающих оптимальное развитие всего процесса в целом. Многошаговый процесс можно интерпретировать так: весь цикл разбить на несколько этапов и на каждом этапе требуется принять то или иное решение. При решении задач методом ДП вводят функцию Беллмана fk, которая представляет собой максимальную эффективность многошагового процесса, состоящего из К шагов. Для вычисления функции Беллмана составляется так называемое функциональное уравнение Беллмана, позволяющее находить значения функции Беллмана fк+1, если известно fk. При выводе уравнения Беллмана используется та или иная форма принципа оптимальности. Если на первом шаге принято решение, то дальнейшее решение должно приниматься таким образом, чтобы за оставшееся число шагов достичь максимального (минимального) результата.

Пусть, например, n предприятий использует некоторые ресурсы. Известно, что, если “K” -ому предприятию выделить X единиц ресурсов, то количество произведенной продукции будет равно цk(X). Требуется распределить A единиц ресурсов между всеми предприятиями так, чтобы выпуск продукции был максимальным. Обозначим через Xk количество ресурсов, которое нужно выделить K - му предприятию, тогда математическая модель задачи запишется так:

ц1(X1)+ц2(X2)+…+цn(Xn)>max

при ограничениях

X1+X2+…+Xn=A

Если ц1, … цn - заданы таблично, то задача решается методами динамического программирования. Рассмотрим оптимальное распределение ресурсов с помощью метода динамического программирования. При решении задачи о распределении ресурсов введем функцию Беллмана fk(X) - максимальное количество продукции, которое могут выпустить K предприятий, при этом бk(X) - количество ресурса, получаемое K - ым предприятием при оптимальном распределении ресурса между первыми предприятиями. Предположим, что fk(X) известно, тогда вычислим fk+1 (X). Пусть К+1 - ое предприятие получает t единиц (0 ? t ? X) ресурса, тогда оно выпускает цk+1 (t) единиц продукции. На долю же первых K предприятий останется X - t единиц ресурса. В силу принципа оптимальности: чтобы получить больше продукции, необходимо распределить оптимально оставшиеся (X - t) единиц ресурса между K предприятиями. Тогда общий выпуск продукции будет равен

К = цk+1(t)+fk(X - t).

Но, чтобы этот общий выпуск продукции был максимальным, необходимо t подобрать так, чтобы эта сумма достигала наибольшего значения, т.е. fk+1 (X). Функциональное уравнение Беллмана:

3. Численный пример

Для решения задачи примем следующие исходные данные:

- объем данных, которые необходимо передать - 80 Мбайт;

- пропускные способности для всех каналов примем равными 40 Мбайт/с;

- стоимости пересылки примем равными 0,1, 0,05, 0,2 и 0,3 руб. для первого, второго, третьего и четвертого каналов соответственно.

Таким образом значения функций стоимости будут иметь вид

Расчеты начинаем с последнего шага. Таблица этого имеет вид:

Таблица третьего шага:

Таблица второго шага

Таблица первого шага

Из таблицы первого шага видно, что канал 1 является самым оптимальным для пересылки данных. Однако его пропускная способность ограничена 40 Мбайтами/с. Поэтому остальные 40 Байт будут переданы по каналу 2. Распределение по каналам имеет вид: u*=(40,40,0,0). Суммарная стоимость пересылки составит 2+4=6 руб.

Заключение

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

Численный эксперимент показал, что разработанная математическая модель может быть применена для решения данного класса задач.

Список использованных источников

компьютерный данные математический программирование

1. Теория принятия решений: сборник заданий для практических занятий / А.В. Зыкина, О.Н. Канева - Омск: ОмГТУ, 2006. - 56 с.

2. Методы оптимизации: конспект лекций / А.В. Зыкина. - Ом

Размещено на Allbest.ru