Циклопедия:Списки:Математические модели

Информатика. Выпуск 8. Математические модели // LiveMSIU (Ведущий — Верещагин Алексей Георгиевич, ассистент кафедры информационных систем и технологий МГИУ) [7:22]

Математическое моделирование и вычислительная математика — Александр Шапеев // ПостНаука [16:00]

Mатематические модели — перечисление формул, уравнений, неравенств или их систем, описывающих задачу, объект или процесс.

Задачи линейного программирования

Каноническая задача

$L(X)=\sum \limits _{j=1}^{n}c_{j}x_{j}\rightarrow \max$

${\begin{cases}\sum \limits _{j=1}^{n}a_{ij}x_{j}=b_{i},\ \forall i\in N_{m}\\x_{j}\geq 0,\forall j\in N_{n}\end{cases}}$

Классическая транспортная задача

$L(X)=\sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}c_{ij}x_{ij}\rightarrow \min$

${\begin{cases}\sum \limits _{j=1}^{n}x_{ij}=a_{i},\ \forall i\in N_{m}\\\sum \limits _{i=1}^{m}x_{ij}=b_{j},\ \forall j\in N_{n}\\x_{ij}\geq 0,\forall (i,j)\in N_{m}\times N_{n}\end{cases}}$

Другие задачи:

• Производственная задача (ПЗ);
• Общая прямая задача (ОПЗ);
• Общая двойственная задача (ОДЗ);
• Задача о назначениях (ЗН);
• Распределительная задача (РЗ);
• Трёхиндексная транспортная задача (ТТЗ).

Транспортные задачи с промежуточными пунктами

Транспортная задача с промежуточными пунктами

$L(X,Y)=\sum \limits _{t=1}^{k}\sum \limits _{i=1}^{m}d_{ti}x_{ti}+\sum \limits _{t=1}^{k}\sum \limits _{j=1}^{n}q_{tj}y_{tj}\rightarrow \min$

${\begin{cases}\sum \limits _{t=1}^{k}x_{ti}=a_{i},\ \forall i\in N_{m}\\\sum \limits _{t=1}^{k}y_{tj}=b_{j},\ \forall j\in N_{n}\\\sum \limits _{i=1}^{m}x_{ti}-\sum \limits _{j=1}^{n}y_{tj}=c_{t},\ \forall t\in N_{k}\\x_{ti}\geq 0,\forall (t,i)\in N_{k}\times N_{m}\\y_{tj}\geq 0,\forall (t,j)\in N_{k}\times N_{n}\end{cases}}$.

Классическая транспортная задача с промежуточными пунктами

$L(X)=\sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}c_{ij}x_{ij}\rightarrow \min$

${\begin{cases}\sum \limits _{j=1}^{n}x_{ij}=a_{i},\ \forall i\in N_{m}\\\sum \limits _{i=1}^{m}x_{ij}=b_{j},\ \forall j\in N_{n}\\x_{ij}\geq 0,\forall (i,j)\in N_{m}\times N_{np}\\x_{inp+j}\leq 0,\forall (i,j)\in N_{m}\times N_{n-np}\end{cases}}$,

Другие задачи:

• Транспортная задача с промежуточными пунктами с запретами;
• Транспортная задача с промежуточными пунктами и ограничением по транзиту;
• Открытая транспортная задача с промежуточными пунктами 1;
• Открытая транспортная задача с промежуточными пунктами 2;
• Открытая транспортная задача с промежуточными пунктами 3;
• Открытая транспортная задача с промежуточными пунктами 4.

Задачи целочисленного программирования

Задача целочисленного программирования

$L^{\text{ц}}(X)=\sum \limits _{j=1}^{n}c_{j}x_{j}\rightarrow \max$

${\begin{cases}\sum \limits _{j=1}^{n}a_{ij}x_{j}\leq b_{i},\ \forall i\in N_{m}\\x_{j}\in \mathbb {N} \cup \{0\},\forall j\in N_{n}\end{cases}}$

Другие задачи:

• Задача о рюкзаке;
• Задача о рюкзаке без повторений;
• Задача о рюкзаке с ограниченным числом повторений.

Системы управления запасами

Система управления запасами

$L(Y,T)={\frac {g}{T}}+{\frac {s}{T}}\int \limits _{0}^{t_{1}+t_{2}}y(t)dt-{\frac {p}{T}}\int \limits _{t_{1}+t_{2}}^{T}y(t)dt\rightarrow \min$

Примеры систем:

• СУЗ с постоянным спросом;
• СУЗ с естественной убылью.

Системы массового обслуживания

Система массового обслуживания

${\begin{cases}p_{0}'(t)=-\lambda _{0}p_{0}(t)+\mu _{1}p_{1}(t)\\p_{1}'(t)=\lambda _{0}p_{0}(t)-(\lambda _{1}+\mu _{1})p_{1}(t)+\mu _{2}p_{2}(t)\\p_{2}'(t)=\lambda _{1}p_{1}(t)-(\lambda _{2}+\mu _{2})p_{2}(t)+\mu _{3}p_{3}(t)\\\ldots \\p_{n}'(t)=\lambda _{n-1}p_{n-1}(t)-(\lambda _{n}+\mu _{n})p_{n}(t)+\mu _{n+1}p_{n+1}(t)\\p_{n+1}'(t)=\lambda _{n}p_{n}(t)-(\lambda _{n+1}+\mu _{n+1})p_{n+1}(t)+\mu _{n+2}p_{n+2}(t)\\\ldots \\p_{n+m-1}'(t)=\lambda _{n+m-2}p_{n+m-2}(t)-(\lambda _{n+m-1}+\mu _{n+m-1})p_{n+m-1}(t)+\mu _{n+m}p_{n+m}(t)\\p_{n+m}'(t)=\lambda _{n+m-1}p_{n+m-1}(t)-\mu _{n+m}p_{n+m}(t)\\\sum \limits _{i=0}^{n+m}p_{i}(t)=1\\p_{0}(0)=1,\ p_{1}(0)=0,\ p_{2}(0)=0,\ldots ,\ p_{n+m}(0)=0\end{cases}}$

Примеры систем:

• СМО с отказами;
• СМО с очередью;
• СМО с ограниченным временем ожидания;
• СМО замкнутая с очередью;
• СМО с взаимопомощью с очередью;
• СМО с отказами и взаимопомощью;
• СМО с бесконечным числом каналов;
• СМО с бесконечной очередью;
• СМО замкнутая без очереди.

Матричные игры

Задача первого игрока

$V(P,v)=v\rightarrow \max$

${\begin{cases}\sum \limits _{i=1}^{m}a_{ij}p_{i}\geq v,\forall j\in N_{n}\\\sum \limits _{i=1}^{m}p_{i}=1\\p_{i}\geq 0,\forall i\in N_{m}\end{cases}}$

Задача второго игрока

$U(Q,u)=u\rightarrow \min$

${\begin{cases}\sum \limits _{j=1}^{n}a_{ij}q_{j}\leq u,\forall i\in N_{m}\\\sum \limits _{j=1}^{n}q_{j}=1\\q_{j}\geq 0,\forall j\in N_{n}\end{cases}}$

Примеры моделей

• Модели ЗЛП;
• Модели ТЗПП;
• Модели ЗЦП;
• Модели СУЗ;
• Модели СМО.

Литература

• Юдин Д. Б., Гольштейн Е. Г. Линейное программирование — М., 1963.
• Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа — М., 1969.
• Овчаров Л. А. Прикладные задачи теории массового обслуживания — М.: «Машиностроение», 1969.
• Рыжиков Ю. И. Управление запасами — М.: «Наука», 1969.
• Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование — М.: «Наука», 1969.
• Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация. — М., 1981, стр.313.
• Справочник по математике для экономистов / Под ред. проф. В. И. Ермакова — М.: «Высшая школа», 1987.
• Krivopalov V. Y., Krivopalov Y. A. The potential method for solving the transportation problem with transit points. New Magenta Papers. Magenta Technology, 2013. — Vol.2 — P.31-38.
• Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1, стр.23-29.