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