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

Математическая модель ОТЗПП1

Открытая транспортная задача с промежуточными пунктами 1 — открытая транспортная задача оптимизации перевозок с использованием промежуточных (транзитных) пунктов с избытком грузов (для перевозок) у поставщиков.

Обозначения

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

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

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

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

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

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

b_j>0, j=1,np — объём поставок продукции поставщиков;

b_j<0, j=np+1,n — объём потребностей (в продукции) потребителей;

a_i>0, i=1,mp — дополнительные (внутренние) потребности продукции (на складе);

a_i≤0, i=mp+1,m — излишки продукции или нулевые остатки (на складе);

c_ij>0, i=1,m, j=1,np — транспортные тарифы на перевозку единицы продукции от поставщика на склад;

c_ij<0, i=1,m, j=np+1,n — транспортные тарифы на перевозку единицы продукции со склада к потребителю;

x_ij≥0, i=1,m, j=1,np — объём перевозок продукции от поставщика на склад;

x_ij≤0, i=1,m, j=np+1,n — объём перевозок продукции со склада к потребителю.

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

Невозможно разобрать выражение (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}\le b_j, \ \forall j\in N_{np} \\ \sum\limits_{i=1}^m x_{inp+j}=b_{np+j}, \ \forall j\in N_{n-np} \\ 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}} .

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

Условия разрешимости

Для разрешимости открытой задачи необходимо выполнение условий:

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

Введём дополнительные обозначения:

a_m+1>0 — дополнительные (внутренние) потребности продукции на фиктивном складе;

c_m+1j>0, j=1,np — транспортные тарифы на перевозку единицы продукции от поставщика на фиктивный склад;

c_m+1j<0, j=np+1,n — транспортные тарифы на перевозку единицы продукции с фиктивного склада к потребителю;

x_m+1j≥0, j=1,np — объём перевозок продукции от поставщика на фиктивный склад;

x_m+1j≤0, j=np+1,n — объём перевозок продукции с фиктивного склада к потребителю.

Пусть M — это достаточно большое положительное число.

Для построения вспомогательной эквивалентной закрытой задачи введём фиктивный склад (с дополнительными внутренними потребностями) с параметрами:

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

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

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

Вспомогательная задача

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

Решение вспомогательной задачи

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

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

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.