Математическая модель для критерия.

Теория принятия решений

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

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

В данной задаче, нам необходимо разместить n файлов по m узлов. Положим, что если файл помещен на какой-либо узел, то соответствующая переменная принимает значение «Истина», иначе «Ложь». Т.е. переменная может принимать только два значения (0 и 1), причем значению «Истина» соответствует значение переменной равное 1, «Ложь» равна 0.

Обозначим:

Vi - объем i-го узла.

ti - время доступа к i-му узлу.

Qj - размер j-го файла.

fj - средняя частота обращений к j-му файлу.

Вводим переменную - Xij- факт записи файла на узел.

гдеXij = (0 , 1 ) , i=(1,m) , j=(1,n)

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

Математическая модель для критерия.

При размещении файлов необходимо руководствоваться тем, чтобы наиболее часто требуемые файлы размещались на узлах с минимальным временем обращения. Следовательно, модель можно представить как

L = ∑( fj * ti )* Xij => min , величина ( fj * ti ) несет смысл затраченного времени на обращение к файлу с частотой fj , т.е. данную величину необходимо минимизировать.

Ограничения принимают вид.

кроме того, необходимо учесть, "Xj =(0,1)

Итак, математически задача расположения файлов сводится к определению таких Xj, удовлетворяющих приведенным линейным ограничениям, которые минимизируют линейную функцию L.

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

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

Пример:

размер
частота
Файлы
время память Узлы




Строится ЛВС с кольцевой топологией, размещение компьютеров известно. Какую модель и метод решения использовать для нахождения оптимального варианта прокладки кабеля.


0441448105794711.html
0441538422303228.html
    PR.RU™