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

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

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

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}\sum\limits_{j=1}^n a_{ij}x_j=b_i, \ \forall i\in N_m \\ x_j \ge 0, \forall j\in N_n\end{cases}}

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = \sum\limits_{i=1}^m\sum\limits_{j=1}^n c_{ij}x_{ij} \rightarrow \min}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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} \ge 0, \forall (i,j)\in N_m\times N_n\end{cases}}

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

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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} \ge 0, \forall (t,i)\in N_k\times N_m \\ y_{tj} \ge 0, \forall (t,j)\in N_k\times N_n \end{cases}} .

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L(X) = \sum\limits_{i=1}^m\sum\limits_{j=1}^n c_{ij}x_{ij} \rightarrow \min}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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} \ge 0, \forall (i,j)\in N_m\times N_{np} \\ x_{inp+j} \le 0, \forall (i,j)\in N_m\times N_{n-np} \end{cases}} ,

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

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L^{\text{ц}}(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}\sum\limits_{j=1}^n a_{ij}x_j \le b_i, \ \forall i\in N_m \\ x_j \in \mathbb{N} \cup \{0\}, \forall j\in N_n\end{cases}}

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

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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}^Ty(t)dt \rightarrow \min}

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

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}p_0'(t)=-\lambda_0p_0(t)+\mu_1p_1(t) \\ p_1'(t)=\lambda_0p_0(t)-(\lambda_1+\mu_1)p_1(t)+\mu_2p_2(t) \\ p_2'(t)=\lambda_1p_1(t)-(\lambda_2+\mu_2)p_2(t)+\mu_3p_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_np_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}}

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

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle V(P,v)=v \rightarrow \max}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}\sum\limits_{i=1}^m a_{ij} p_i \ge v, \forall j\in N_n \\ \sum\limits_{i=1}^m p_i=1 \\ p_i \ge 0, \forall i\in N_m \end{cases}}

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle U(Q,u)=u \rightarrow \min}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{cases}\sum\limits_{j=1}^n a_{ij} q_j \le u, \forall i\in N_m \\ \sum\limits_{j=1}^n q_j=1 \\ q_j \ge 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.