Открытая транспортная задача с промежуточными пунктами 3 — различия между версиями
(Новая страница: «[[Математическая модель ОТЗПП3]] == Обозначения: == '''n''' — число конеч…») |
|||
Строка 1: | Строка 1: | ||
[[файл:ОТЗПП03.JPG|thumb|300|[[Математическая модель]] ОТЗПП3]] | [[файл:ОТЗПП03.JPG|thumb|300|[[Математическая модель]] ОТЗПП3]] | ||
+ | '''Открытая транспортная задача с промежуточными пунктами 3''' – это открытая транспортная задача оптимизации перевозок с использованием промежуточных (транзитных) пунктов с избытком потребностей в грузах у потребителей. | ||
== Обозначения: == | == Обозначения: == | ||
'''n''' — число конечных пунктов (поставщиков и потребителей); | '''n''' — число конечных пунктов (поставщиков и потребителей); | ||
Строка 28: | Строка 29: | ||
'''x<sub>ij</sub>≤0, i=1,m, j=np+1,n''' — объём перевозок продукции со склада к потребителю. | '''x<sub>ij</sub>≤0, i=1,m, j=np+1,n''' — объём перевозок продукции со склада к потребителю. | ||
− | |||
== Математическая модель == | == Математическая модель == | ||
[[файл:ОТЗПП03.JPG]]. | [[файл:ОТЗПП03.JPG]]. | ||
− | |||
* Заметим, что в системе ограничений открытой задачи должно быть хотя бы одно строгое неравенство. | * Заметим, что в системе ограничений открытой задачи должно быть хотя бы одно строгое неравенство. | ||
− | |||
== Условия разрешимости == | == Условия разрешимости == | ||
Для разрешимости открытой задачи необходимо выполнение условий: | Для разрешимости открытой задачи необходимо выполнение условий: | ||
Строка 58: | Строка 56: | ||
[[файл:ОТЗПП13.JPG]] | [[файл:ОТЗПП13.JPG]] | ||
− | |||
== Вспомогательная задача == | == Вспомогательная задача == | ||
[[файл:ОТЗПП21.JPG]] | [[файл:ОТЗПП21.JPG]] | ||
− | |||
== Решение вспомогательной задачи == | == Решение вспомогательной задачи == | ||
Очевидно, что вспомогательная задача является закрытой '''[[Транспортная задача с промежуточными пунктами|транспортной задачей с промежуточными пунктами]]''', которая разрешима по построению. | Очевидно, что вспомогательная задача является закрытой '''[[Транспортная задача с промежуточными пунктами|транспортной задачей с промежуточными пунктами]]''', которая разрешима по построению. | ||
Для определения начального решения используется '''[[алгоритм северо-западного угла|метод северо-западного угла]]''', а для решения применяется '''[[Транспортная задача с промежуточными пунктами|метод потенциалов]]'''. | Для определения начального решения используется '''[[алгоритм северо-западного угла|метод северо-западного угла]]''', а для решения применяется '''[[Транспортная задача с промежуточными пунктами|метод потенциалов]]'''. | ||
Очевидно, что '''M'''-множители и метод потенциалов приводят к нулевым соответствующим (от поставщиков на фиктивный склад) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные и промежуточные пункты (без фиктивного склада) являются оптимальным решением исходной задачи. А перевозки с фиктивного склада являются не удовлетворёнными потребностями (в продукции) потребителей. | Очевидно, что '''M'''-множители и метод потенциалов приводят к нулевым соответствующим (от поставщиков на фиктивный склад) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные и промежуточные пункты (без фиктивного склада) являются оптимальным решением исходной задачи. А перевозки с фиктивного склада являются не удовлетворёнными потребностями (в продукции) потребителей. | ||
− | |||
== Другие задачи: == | == Другие задачи: == | ||
*[[Транспортная задача с промежуточными пунктами]]; | *[[Транспортная задача с промежуточными пунктами]]; | ||
Строка 74: | Строка 69: | ||
*[[Открытая транспортная задача с промежуточными пунктами 2]]; | *[[Открытая транспортная задача с промежуточными пунктами 2]]; | ||
*[[Открытая транспортная задача с промежуточными пунктами 4]]. | *[[Открытая транспортная задача с промежуточными пунктами 4]]. | ||
− | |||
== Ссылки == | == Ссылки == | ||
* Кривопалов В. Ю., Решение открытой транспортной задачи с промежуточными пунктами. Сборник научных трудов конференции ПИТ-2015, СГАУ, Т.2, стр.86-91. http://ssau.ru/files/events/2015/pit_2015_2.pdf | * Кривопалов В. Ю., Решение открытой транспортной задачи с промежуточными пунктами. Сборник научных трудов конференции ПИТ-2015, СГАУ, Т.2, стр.86-91. http://ssau.ru/files/events/2015/pit_2015_2.pdf | ||
− | * [[Участник:Logic-samara]] | + | * [[Участник:Logic-samara]] |
− | [[Категория:Математика]] [[Категория:Линейное программирование]] [[Категория:Транспортная задача]] | + | [[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]] |
Версия 18:58, 13 января 2016
Открытая транспортная задача с промежуточными пунктами 3 – это открытая транспортная задача оптимизации перевозок с использованием промежуточных (транзитных) пунктов с избытком потребностей в грузах у потребителей.
Содержание
Обозначения:
n — число конечных пунктов (поставщиков и потребителей);
np — число поставщиков;
n-np — число потребителей;
m — число промежуточных пунктов (складов);
mp — число складов с дополнительными (внутренними) потребностями;
m-mp — число складов с излишками продукции или нулевыми остатками;
bj>0, j=1,np — объём потребностей (в продукции) потребителей;
bj<0, j=np+1,n — объём поставок продукции поставщиков;
ai>0, i=1,mp — дополнительные (внутренние) потребности продукции (на складе);
ai≤0, i=mp+1,m — излишки продукции или нулевые остатки (на складе);
cij>0, i=1,m, j=1,np — транспортные тарифы на перевозку единицы продукции от поставщика на склад;
cij<0, i=1,m, j=np+1,n — транспортные тарифы на перевозку единицы продукции со склада к потребителю;
xij≥0, i=1,m, j=1,np — объём перевозок продукции от поставщика на склад;
xij≤0, i=1,m, j=np+1,n — объём перевозок продукции со склада к потребителю.
Математическая модель
- Заметим, что в системе ограничений открытой задачи должно быть хотя бы одно строгое неравенство.
Условия разрешимости
Для разрешимости открытой задачи необходимо выполнение условий:
Введём дополнительные обозначения:
am+1<0 — излишки продукции на фиктивном складе;
cm+1j>0, j=1,np — транспортные тарифы на перевозку единицы продукции от поставщика на фиктивный склад;
cm+1j<0, j=np+1,n — транспортные тарифы на перевозку единицы продукции с фиктивного склада к потребителю;
xm+1j≥0, j=1,np — объём перевозок продукции от поставщика на фиктивный склад;
xm+1j≤0, j=np+1,n — объём перевозок продукции с фиктивного склада к потребителю.
Пусть M — это достаточно большое положительное число.
Для построения вспомогательной эквивалентной закрытой задачи введём фиктивный склад (с излишками) с параметрами:
Вспомогательная задача
Решение вспомогательной задачи
Очевидно, что вспомогательная задача является закрытой транспортной задачей с промежуточными пунктами, которая разрешима по построению. Для определения начального решения используется метод северо-западного угла, а для решения применяется метод потенциалов. Очевидно, что M-множители и метод потенциалов приводят к нулевым соответствующим (от поставщиков на фиктивный склад) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные и промежуточные пункты (без фиктивного склада) являются оптимальным решением исходной задачи. А перевозки с фиктивного склада являются не удовлетворёнными потребностями (в продукции) потребителей.
Другие задачи:
- Транспортная задача с промежуточными пунктами;
- Транспортная задача с промежуточными пунктами с запретами;
- Транспортная задача с промежуточными пунктами и ограничением по транзиту;
- Открытая транспортная задача с промежуточными пунктами 1;
- Открытая транспортная задача с промежуточными пунктами 2;
- Открытая транспортная задача с промежуточными пунктами 4.
Ссылки
- Кривопалов В. Ю., Решение открытой транспортной задачи с промежуточными пунктами. Сборник научных трудов конференции ПИТ-2015, СГАУ, Т.2, стр.86-91. http://ssau.ru/files/events/2015/pit_2015_2.pdf
- Участник:Logic-samara