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

Открытая транспортная задача с промежуточными пунктами (ТЗПП открытая) — транспортная задача с промежуточными пунктами, в которой нарушен баланс ресурсов и потребностей (дисбаланс).

Открытая ТЗПП

Обозначения

$n$ — число конечных пунктов (поставщиков и потребителей);

$np$ — число поставщиков;

$n-np$ — число потребителей;

$m$ — число промежуточных пунктов (складов);

$mp$ — число складов с дополнительными (внутренними) потребностями;

$m-mp$ — число складов с излишками продукции или нулевыми остатками;

$b_{j}>0,j=1,2,...,np$ — объём поставок продукции поставщиков;

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{np+j} <0, j=1, 2, ..., {n-np}} — объём потребностей (в продукции) потребителей;

$a_{i}>0,i=1,2,...,m$ — дополнительные (внутренние) потребности продукции (на складе);

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle a_i\le 0, i=1, 2, ..., {m-mp}} — излишки продукции или нулевые остатки (на складе);

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle c_{ij} >0, i=1, 2, ..., m, j=1, 2, ..., {np}} — транспортные тарифы на перевозку единицы продукции от поставщика на склад;

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle c_{inp+j} <0, i=1, 2, ..., m, j=1, 2, ..., {n-np}} — транспортные тарифы на перевозку единицы продукции со склада к потребителю;

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x_{ij}\ge 0, i=1, 2, ..., m, j=1, 2, ..., {np}} — объём перевозок продукции от поставщика на склад;

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x_{inp+j}\le 0, i=1, 2, ..., m, j=1, 2, ..., {n-np}} — объём перевозок продукции со склада к потребителю.

Условие дисбаланса

Условие нарушения баланса ресурсов и потребностей

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

В системе ограничений открытой задачи должно быть хотя бы одно неравенство.

В зависимости от вида неравенств различают следующие виды открытых ТЗПП.

Открытая ТЗПП 1

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

Постановка задачи

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \sum_{i=1}^{m} x_{inp+j}=b_j, j=1, 2, ..., {n-np}}

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x_{inp+j}\le 0, i=1, 2, ..., m, j=1, 2, ..., {n-np}}

Условие дисбаланса

Избыток продукта у поставщиков.

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

Открытая ТЗПП 2

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

Постановка задачи

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

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x_{inp+j}\le 0, i=1, 2, ..., m, j=1, 2, ..., {n-np}}

Условие дисбаланса

Избыточные запасы на складах.

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

Открытая ТЗПП 3

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

Постановка задачи

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \sum_{i=1}^{m} x_{inp+j}\ge b_j, j=1, 2, ..., {n-np}}

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x_{inp+j}\le 0, i=1, 2, ..., m, j=1, 2, ..., {n-np}}

Условие дисбаланса

Избыточные потребности у потребителей.

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

Открытая ТЗПП 4

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

Постановка задачи

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle L=\sum_{i=1}^{m} \sum_{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 \sum_{j=1}^{n} x_{ij} \le a_i, i=1, 2, ..., {mp}}

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x_{inp+j}\le 0, i=1, 2, ..., m, j=1, 2, ..., {n-np}}

Условие дисбаланса

Избыточные дополнительные потребности на складах.

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

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

1. Транспортная задача;
2. Распределительная задача;
3. Задача о назначениях;
4. Транспортная задача с промежуточными пунктами;
5. Транспортная задача с промежуточными пунктами с запретами;
6. Транспортная задача с промежуточными пунктами и ограничением по транзиту;
7. Открытая транспортная задача с промежуточными пунктами;
8. Открытая транспортная задача с промежуточными пунктами 1;
9. Открытая транспортная задача с промежуточными пунктами 2;
10. Открытая транспортная задача с промежуточными пунктами 3;
11. Открытая транспортная задача с промежуточными пунктами 4;
12. Трёхиндексная транспортная задача;
13. Трёхиндексная транспортная задача с аксиальными суммами;
14. Трёхиндексная транспортная задача с промежуточными пунктами.

Литература

• Кривопалов В. Ю., Решение открытой транспортной задачи с промежуточными пунктами. Сборник научных трудов конференции ПИТ-2015, СГАУ, Т.2, стр.86-91

Ссылки

• http://www.ssau.ru/files/events/2015/pit_2015_2.pdf стр.86-91.

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Открытая транспортная задача с промежуточными пунктами», расположенная по адресу: — «https://ru.ruwiki.ru/wiki/Открытая_транспортная_задача_с_промежуточными_пунктами» Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».