Метод Франка-Вульфа в моделировании информационных систем

Полный текст

ВВЕДЕНИЕ

Современный период развития общества характеризуется переходом от индустриального к информационному состоянию. Развитие информационных технологий является приоритетным направлением. Информационные технологии – совокупность технических и программных средств, приемов работы, с помощью которых выполняются операции по обработке информации. Повышение эффективности проектирования информационных систем является актуальной задачей. Для ее решения применяются математическое моделирование и реализация алгоритмов решения задачи на ПЭВМ. Математические модели нелинейного программирования имеют широкое применение в решении практических задач в проектировании информационных систем. Преимущества нелинейных математических моделей – небольшие финансовые и временные затраты на разработку, полный и точный учет зависимостей между факторами и показателями, влияющими на критерий эффективности и ограничения в системе ограничений [1; 2].

Максимизировать чистый приведенный эффект проектов информационных систем, предварительно отобранных в портфель инвестиций методом экспертных оценок. Финансирование проектов информационных систем распределено по периодам времени при выполнении условий ограничений:

1 сумма произведения инвестиционных затрат информационных проектов на доли финансирования в периодах времени не больше выделенных финансовых средств;

2 сумма долей финансирования информационных проектов равна 1.

РЕЗУЛЬТАТЫ И ОБСУЖДЕНИЕ

Математическая модель включает два этапа:

1. Методом экспертных оценок выбираются проекты информационных систем со спутниковым интернетом с наибольшими оценками.
2. Методом нелинейного математического программирования определяется оптимальный вариант из числа проектов информационных систем, выбранных на первом этапе.

Пусть $i=\overline{\mathrm{1,}n}$ – число вариантов проектов информационных систем со спутниковым интернетом; $q=\overline{\mathrm{1,}t}$ – число экспертов, оценивающих варианты проектов информационных систем; $k=\overline{\mathrm{1,}p}$ – число факторов; ${\beta }_{qk}$ – вес, присвоенный q экспертом k фактору, $Z_{qk}^i$ – оценка, данная q экспертом k фактору, тогда усредненная оценка i-го варианта проекта информационной системы рассчитывается по формуле:

$\overline{Z_i}=\frac{1}{q}\sum _{q=1}^t\sum _{k=1}^p{\beta }_{qk}*Z_{qk}^i$ (1)

Ранжирование позволяет выявить наиболее подходящие варианты проектов информационных систем [3–5].

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

Математическая модель выбора оптимального проекта информационной системы имеет вид:

$\overline{Z_i}=\frac{1}{q}\sum _{q=1}^t\sum _{k=1}^p{\beta }_{qk}*Z_{qk}^i$

$\max \leftarrow Z=\sum _{i=1}^n(P_i-k_i*X_i)*X_i=$

$(P_1-k_1*X_1)*X_1+\dots +(P_n-k_n*X_n)*X_n$

при ограничениях (2)

$\left\{\begin{array}{l}{\text{V}}_{\text{1}}^{\text{0}}{\text{*X}}_{\text{1}}{\text{+V}}_{\text{2}}^{\text{0}}{\text{*X}}_{\text{2}}{\text{++V}}_{\text{n}}^{\text{0}}{\text{*X}}_{\text{n}}{\text{£S}}^{\text{0}}\\ {\text{V}}_{\text{1}}^{\text{1}}{\text{*X}}_{\text{1}}{\text{+V}}_{\text{2}}^{\text{1}}{\text{*X}}_{\text{2}}{\text{++V}}_{\text{n}}^{\text{1}}{\text{*X}}_{\text{n}}{\text{£S}}^{\text{1}}\\ ⋮\\ {\text{V}}_{\text{1}}^{\text{m}}{\text{*X}}_{\text{1}}{\text{+V}}_{\text{2}}^{\text{m}}{\text{*X}}_{\text{2}}{\text{++V}}_{\text{n}}^{\text{m}}{\text{*X}}_{\text{n}}{\text{£S}}^{\text{m}}\\ {\text{X}}_{\text{1}}\text{+}\mathrm{...}{\text{+X}}_{\text{n}}\text{=1}\\ {\text{X}}_{\text{i}}\text{³0, i=}\overline{\text{1,n}}\text{, j=}\overline{\text{1,m}}\end{array}\right.$

где $P_i$ – чистый приведённый эффект проекта; млн руб; $V_i^j$ – инвестиционные затраты $i$-го проекта в $j$-ом периоде времени, млн руб.; $S^j$ – имеющиеся средства финансирования в j-ом периоде времени, млн руб.; $X_i$ – доля финансирования инвестиционного проекта; $k_i$ – коэффициент изменения чистого приведенного эффекта; $i=\overline{\mathrm{1,}n}$ – номер инвестиционного проекта; $j=\overline{\mathrm{1,}m}$ – номер периода времени, год.

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

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

Таблица 1. Таблица экспертных показателей выбора проекта.

После ранжирования проектов информационных систем со спутниковым интернетом получим проекты «Триколор» (196 баллов), «Open Sky» (175 баллов), «LanSat» (154 баллов), «Skydsl» (150 балла) и «GxSAT» (132 баллов). Выберем в портфель инвестиций первые два проект с наибольшими баллами «Триколор» (196 баллов), «Open Sky» (175 баллов).

В таблице 2 приведены затраты на реализацию проектов информационных систем со спутниковым интернетом, отобранных на первом этапе математической модели.

Таблица 2. Затраты на реализацию проектов.

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

Таблица 3. Исходные данные для определения оптимального проекта.

Пусть $X_1$ – доля финансирования проекта информационной системы со спутниковым интернетом «Триколор», $k_1=\mathrm{0,7}$ – коэффициент изменения чистого приведенного эффекта, $X_2$ – доля финансирования проекта информационной системы со спутниковым интернетом «Open Sky», $k_2=\mathrm{0,6}$ – коэффициент изменения чистого приведенного эффекта. Точность вычислений $\epsilon =0.0001$.

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

$\max \leftarrow Z=(\mathrm{1,53}-\mathrm{0,7}*X_1)*$

$X_1+(\mathrm{0,74}-\mathrm{0,6}*X_2)*X_2$

при ограничениях(3)

$\left\{\begin{array}{l}{\text{5,4*X}}_1+\mathrm{3,2}*X_2\le \mathrm{6,5}\\ \mathrm{2,0}*X_1+\mathrm{1,5}*X_2\le \mathrm{3,0}\\ X_1+X_2=1\\ X_1,{X_2}_5\ge 0\end{array}\right.$

Оптимальное решение задачи нелинейного программирования определяется методом условного градиента. Сущность градиентных методов заключается в последовательном изменении значения целевой функции при движении от начальной точки $X^0$ области допустимых решений до $X^{*}$ оптимального значения функции [6–12].

Алгоритм метода Франка-Вульфа включает этапы.

Этап 1. Определение начального допустимого значения $X^0=\left(x_1^0\mathrm{,...,}{x}_n^0\right)$.

Этап 2. Вычисление градиента $\nabla f\left(X^0\right)$ в точке $X^0=\left(x_1^0\mathrm{,...,}{x}_n^0\right)$.

Этап 3. Определение оптимального решения $Q^l=\left(q_1^l\mathrm{,...,}{q}_n^l\right)$ задачи линейного программирования, целевая функция математической модели которой равна скалярному произведению вектора-градиента $\nabla f\left(X^l\right)$ и вектора $X=\left(x_1\mathrm{,...,}{x}_n\right)$ при ограничениях исходной задачи ( $l$ – номер итерации, $l=\overline{1.f}$).

Этап 4. Переход в новую точку $X^{(l+1)}$, принадлежащую области допустимых решений. Значения координат новой точки $X^{(l+1)}$ рассчитываются по формуле

$X^{(l+1)}=X^l+{\lambda }_l(Q^l-X^{\left(l\right)})$ (4)

Этап 5. Определение величины шага ${\lambda }_l$ ( $0\le {\lambda }_l\le 1$). Подстановка правой части уравнения 4 в целевую функцию математической модели исходной задачи, определение производной целевой функции по ${\lambda }_l$ и приравнивание нулю, определение значения ${\lambda }_l$. Расчет значений точки $X^{(l+1)}$ и целевой функции $f\left(X^{(l+1)}\right)$.

Этап 6. Проверка условия окончания итерационного процесса по математическому выражению

$\left|f\right(X^{(l+1)})-f(X^l\left)\right|\le \epsilon$,(6)

где $\epsilon$ – заданная точность вычислений [6].

Если условие неравенства 6 не выполняется, то переход к новой точке на этап 2.

Определим оптимальное решение математической модели 3.

Итерация 0. 1 Начальное допустимое значение $X^0=(0.4;0.6)$. Значение целевой функции

$f\left(X^0\right)=\mathrm{1,53}*\mathrm{0,4}-\mathrm{0,7}*{\mathrm{0,4}}^2+$

$\mathrm{0,74}*\mathrm{0,6}-\mathrm{0,6}*{\mathrm{0,6}}^2=\mathrm{0,728}$

2 Определение градиента

$\nabla f\left(X^0\right)=(\mathrm{1,53}-\mathrm{1,4}*x_1;$

$\mathrm{0,74}-\mathrm{1,2}*x_2)=\left(\mathrm{0,97};\mathrm{0,02}\right)$ в точке $X^0$.

3 Определение оптимального решения математической модели задачи линейного программирования, целевая функция которой определяется как скалярное произведение вектора-градиента $\nabla f\left(X^0\right)$ и вектора $X=\left(x_1\mathrm{,.}{x}_2\right)$ при ограничениях исходной задачи

$\max \leftarrow F_0\left(X^0\right)=\mathrm{0,97}{x}_1+\mathrm{0,02}{x}_2$

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

$\left\{\begin{array}{l}\mathrm{5,4}{x}_1+\mathrm{3,2}{x}_2\le \mathrm{6,5}\\ 2x_1+\mathrm{1,5}{x}_2\le 3\\ x_1+x_2=1\\ x_1\ge \mathrm{0,}{x}_2\ge 0\end{array}\right.$

Оптимальное решение задачи линейного программирования

$X^{0*}=(1;0)$, $F_0\left(X^{0*}\right)=\mathrm{0,97}$.

4 Переход в новую точку $X^1=(x_1^1,x_2^1)$. Определяем значения искомых переменных $x_1$ и $x_2$.

$x_1^1=x_1^0+{\lambda }_0(x_1^{*0}-x_1^0)=$

$\mathrm{0,4}+{\lambda }_0(1-\mathrm{0,4})=\mathrm{0,4}+\mathrm{0,6}{\lambda }_0$

$x_2^1=x_2^0+{\lambda }_0(x_2^{*0}-x_2^0)=$

$\mathrm{0,6}+{\lambda }_0(0-\mathrm{0,6})=\mathrm{0,6}-\mathrm{0,6}{\lambda }_0$

5 Определяем шаг вычислений ${\lambda }_0$ ($0\le {\lambda }_0\le 1$ ). Подставим $x_1^1$ и $x_2^1$ в целевую функцию исходной математической модели

$\max \leftarrow f(\mathrm{0,4}+\mathrm{0,6}{\lambda }_0;\mathrm{0,6}-\mathrm{0,6}{\lambda }_0)=$

$\mathrm{0,728}+\mathrm{0,570}{\lambda }_0-\mathrm{0,468}{\lambda }_0^2$

Находим первую производную функции по ${\lambda }_0$ и приравниваем к нулю

$f^{\text{'}}\left(X^1\right)=\mathrm{0,570}-\mathrm{0,936}{\lambda }_0=0$.

Значение шага вычислений

${\lambda }_0=\frac{\mathrm{0,570}}{\mathrm{0,936}}=\mathrm{0,609}$.

Значение

$x_1^1=\mathrm{0,4}+\mathrm{0,609}(1-\mathrm{0,4})=\mathrm{0,765}$.

Значение $x_2^1=\mathrm{0,6}-\mathrm{0,6}*\mathrm{0,609}=\mathrm{0,235}$.

6 Определим значение целевой функции в точке $X^{1\text{'}}$.

$f(x_1^1;x_2^1)=f(\mathrm{0,765};\text{ 0,235})=\mathrm{0,902}$

7 Проверим условие точности вычислений

$\left|f\left(X^1\right)-f\left(X^0\right)\right|=\left|\mathrm{0,902}-\mathrm{0,728}\right|=$

$\mathrm{0,174}>\mathrm{0,0001}$.

Разность значений функций

$\left|f\left(X^1\right)-f\left(X^0\right)\right|$

больше заданной точности вычислений $\epsilon =\mathrm{0,0001}$, следовательно переходим на следующую итерацию.

Итерация 1.

1 Значение

$X^1=(\mathrm{0,765};\mathrm{0,235})$ принадлежит области допустимых решений. Значение целевой функции математической модели

$f\left(X^1\right)=f(\mathrm{0,765};\mathrm{0,235})=\mathrm{0,902}$.

2 Определение градиента

$\nabla f\left(X^1\right)=(\mathrm{0,459};0.458)$ в точке $X^1$.

3 Определение оптимального решения математической модели задачи линейного программирования, целевая функция которой определяется как скалярное произведение вектора-градиента $\nabla f\left(X^1\right)$ и вектора $X=\left(x_1\mathrm{,.}{x}_2\right)$ при ограничениях исходной задачи

$\max \leftarrow F_1\left(X^1\right)=\mathrm{0,459}{x}_1+\mathrm{0,458}{x}_2$

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

$\left\{\begin{array}{l}\mathrm{5,4}{x}_1+\mathrm{3,2}{x}_2\le \mathrm{6,5}\\ 2x_1+\mathrm{1,5}{x}_2\le 3\\ x_1+x_2=1\\ x_1\ge \mathrm{0,}{x}_2\ge 0\end{array}\right.$

Оптимальное решение задачи линейного программирования

$X^{1*}=(1;0)$, $F_1\left(X^{1*}\right)=\mathrm{0,459}$.

4 Переход на новую точку $X^2=(x_1^2,x_2^2)$. Определяем значения искомых переменных $x_1$ и $x_2$.

$x_1^2=x_1^1+{\lambda }_1(x_1^{1*}-x_1^1)=$

$\mathrm{0,765}+{\lambda }_1(1-\mathrm{0,765})=\mathrm{0,765}+\mathrm{0,235}{\lambda }_1$

$x_2^1=x_2^1+{\lambda }_1(x_2^{1*}-x_2^1)=$

$\mathrm{0,235}+{\lambda }_1(0-\mathrm{0,235})=\mathrm{0,235}-\mathrm{0,235}{\lambda }_1$

5 Определяем шаг вычислений ${\lambda }_0$ ($0\le {\lambda }_0\le 1$ ). Подставим $x_1^2$ и $x_2^2$ в целевую функцию исходной математической модели

$\max \leftarrow f(\mathrm{0,765}+\mathrm{0,235}{\lambda }_1;\mathrm{0,235}-\mathrm{0,235}{\lambda }_1)=$

$\mathrm{0,9015575}+\mathrm{0,000235}{\lambda }_1-\mathrm{0,0717925}{\lambda }_1^2$

Находим первую производную функции по ${\lambda }_1$ и приравниваем к нулю

$f^{\text{'}}\left(X^2\right)=\mathrm{0,000235}-\mathrm{0,0717925}{\lambda }_1=0$.

Значение шага вычислений

${\lambda }_1=\frac{\mathrm{0,000235}}{\mathrm{0,0717925}}=\mathrm{0,003273}$.

Значение

$x_1^2=\mathrm{0,765}+\mathrm{0,235}*\mathrm{0,003273}=\mathrm{0,766}$.

Значение

$x_2^2=\mathrm{0,235}-\mathrm{0,235}*\mathrm{0,0,003273}=\mathrm{0,234}$.

6 Определим значение целевой функции в точке $X^{1\text{'}}$.

$f(x_1^2;x_2^2)=f(\mathrm{0,766};\text{ 0,234})=\mathrm{0,901557}$

7 Проверим условие точности вычислений

$\left|f\left(X^2\right)-f\left(X^1\right)\right|=\left|\mathrm{0,901557}-\mathrm{0,901555}\right|=$.

$\mathrm{0,000002}<\mathrm{0,0001}$

Разность значений функций $\left|f\left(X^2\right)-f\left(X^1\right)\right|$ меньше заданной точности вычислений $\epsilon =0.0001$, следовательно конец итерационного процесса.

Оптимальное решение

$X^{*}=\{\mathrm{0,766};\text{ 0,234}\}$, $f\left(X^{*}\right)=\mathrm{0,901557}$.

Проект информационной системы с интернетом «Триколор» имеет максимальную долю финансирования, равную 0,766. Проект информационной системы с интернетом «Open Sky» имеет минимальную долю финансирования, равную 0,234. Максимальный чистый приведенный эффект проектов информационной системы

$f\left(X^{*}\right)=\mathrm{0,901557}$ миллионов рублей.

ЗАКЛЮЧЕНИЕ И ВЫВОДЫ

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

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

1. Определены предварительные проекты информационных систем с помощью метода экспертных оценок.
2. Использована нелинейная математическая модель оптимизации информационных систем.
3. Найдено оптимальное решение математической модели нелинейного программирования методом Франка-Вульфа.
4. Математическая модель определения оптимального проекта информационной системы позволит повысить эффективность и обоснованность принимаемых решений, сократить финансовые затраты и сроки проектирования информационных систем.
5. Полученные результаты могут быть использованы для разработки визуального программного приложения на ПЭВМ и в дальнейших исследованиях по данной теме.

Об авторах

Андрей Михайлович Семахин

Автор, ответственный за переписку.
Email: Semakhinandrew@yandex.ru
ORCID iD: 0000-0002-7331-3249
SPIN-код: 6818-1422

кандидат технических наук, доцент доцент кафедры программного обеспечения автоматизированных систем,

Список литературы

Дополнительные файлы