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

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

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

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

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

Обозначим:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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