Открытая транспортная задача с промежуточными пунктами 4 — различия между версиями
(Новая страница: «[[Математическая модель ОТЗПП4]] == Обозначения: == '''n''' — число конеч…») |
|||
Строка 1: | Строка 1: | ||
[[файл:ОТЗПП04.JPG|thumb|300|[[Математическая модель]] ОТЗПП4]] | [[файл:ОТЗПП04.JPG|thumb|300|[[Математическая модель]] ОТЗПП4]] | ||
+ | '''Открытая транспортная задача с промежуточными пунктами 4''' – это открытая транспортная задача оптимизации перевозок с использованием промежуточных (транзитных) пунктов с избытком потребностей в грузах у транзитных пунктов. | ||
== Обозначения: == | == Обозначения: == | ||
'''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''' — объём перевозок продукции со склада к потребителю. | ||
− | |||
== Математическая модель == | == Математическая модель == | ||
[[файл:ОТЗПП04.JPG]]. | [[файл:ОТЗПП04.JPG]]. | ||
− | |||
* Заметим, что в системе ограничений открытой задачи должно быть хотя бы одно строгое неравенство. | * Заметим, что в системе ограничений открытой задачи должно быть хотя бы одно строгое неравенство. | ||
− | |||
== Условия разрешимости == | == Условия разрешимости == | ||
Для разрешимости открытой задачи необходимо выполнение условий: | Для разрешимости открытой задачи необходимо выполнение условий: | ||
Строка 54: | Строка 52: | ||
[[файл:ОТЗПП14.JPG]] | [[файл:ОТЗПП14.JPG]] | ||
− | |||
== Вспомогательная задача == | == Вспомогательная задача == | ||
[[файл:ОТЗПП24.JPG]] | [[файл:ОТЗПП24.JPG]] | ||
− | |||
== Решение вспомогательной задачи == | == Решение вспомогательной задачи == | ||
Очевидно, что вспомогательная задача является закрытой '''[[Транспортная задача с промежуточными пунктами|транспортной задачей с промежуточными пунктами]]''', которая разрешима по построению. | Очевидно, что вспомогательная задача является закрытой '''[[Транспортная задача с промежуточными пунктами|транспортной задачей с промежуточными пунктами]]''', которая разрешима по построению. | ||
Для определения начального решения используется '''[[алгоритм северо-западного угла|метод северо-западного угла]]''', а для решения применяется '''[[Транспортная задача с промежуточными пунктами|метод потенциалов]]'''. | Для определения начального решения используется '''[[алгоритм северо-западного угла|метод северо-западного угла]]''', а для решения применяется '''[[Транспортная задача с промежуточными пунктами|метод потенциалов]]'''. | ||
Очевидно, что '''M'''-множители и метод потенциалов приводят к нулевым соответствующим (от фиктивного поставщика на склады с излишками продукции) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные (без фиктивного поставщика) и промежуточные пункты являются оптимальным решением исходной задачи. А перевозки от фиктивного поставщика являются не удовлетворёнными внутренними потребностями складов. | Очевидно, что '''M'''-множители и метод потенциалов приводят к нулевым соответствующим (от фиктивного поставщика на склады с излишками продукции) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные (без фиктивного поставщика) и промежуточные пункты являются оптимальным решением исходной задачи. А перевозки от фиктивного поставщика являются не удовлетворёнными внутренними потребностями складов. | ||
− | |||
== Другие задачи: == | == Другие задачи: == | ||
*[[Транспортная задача с промежуточными пунктами]]; | *[[Транспортная задача с промежуточными пунктами]]; | ||
Строка 70: | Строка 65: | ||
*[[Открытая транспортная задача с промежуточными пунктами 2]]; | *[[Открытая транспортная задача с промежуточными пунктами 2]]; | ||
*[[Открытая транспортная задача с промежуточными пунктами 3]]. | *[[Открытая транспортная задача с промежуточными пунктами 3]]. | ||
− | |||
== Ссылки == | == Ссылки == | ||
* Кривопалов В. Ю., Решение открытой транспортной задачи с промежуточными пунктами. Сборник научных трудов конференции ПИТ-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:59, 13 января 2016
Открытая транспортная задача с промежуточными пунктами 4 – это открытая транспортная задача оптимизации перевозок с использованием промежуточных (транзитных) пунктов с избытком потребностей в грузах у транзитных пунктов.
Содержание
Обозначения:
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 — объём перевозок продукции со склада к потребителю.
Математическая модель
- Заметим, что в системе ограничений открытой задачи должно быть хотя бы одно строгое неравенство.
Условия разрешимости
Для разрешимости открытой задачи необходимо выполнение условий:
Введём дополнительные обозначения:
bn+1>0 — объём поставок продукции фиктивного поставщика;
cin+1≥0, i=1,m — транспортные тарифы на перевозку единицы продукции от фиктивного поставщика на склад;
xin+1≥0, i=1,m — объём перевозок продукции от фиктивного поставщика на склад.
Пусть M — это достаточно большое положительное число.
Для построения вспомогательной эквивалентной закрытой задачи введём фиктивного поставщика с параметрами:
Вспомогательная задача
Решение вспомогательной задачи
Очевидно, что вспомогательная задача является закрытой транспортной задачей с промежуточными пунктами, которая разрешима по построению. Для определения начального решения используется метод северо-западного угла, а для решения применяется метод потенциалов. Очевидно, что M-множители и метод потенциалов приводят к нулевым соответствующим (от фиктивного поставщика на склады с излишками продукции) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные (без фиктивного поставщика) и промежуточные пункты являются оптимальным решением исходной задачи. А перевозки от фиктивного поставщика являются не удовлетворёнными внутренними потребностями складов.
Другие задачи:
- Транспортная задача с промежуточными пунктами;
- Транспортная задача с промежуточными пунктами с запретами;
- Транспортная задача с промежуточными пунктами и ограничением по транзиту;
- Открытая транспортная задача с промежуточными пунктами 1;
- Открытая транспортная задача с промежуточными пунктами 2;
- Открытая транспортная задача с промежуточными пунктами 3.
Ссылки
- Кривопалов В. Ю., Решение открытой транспортной задачи с промежуточными пунктами. Сборник научных трудов конференции ПИТ-2015, СГАУ, Т.2, стр.86-91. http://ssau.ru/files/events/2015/pit_2015_2.pdf
- Участник:Logic-samara