Изменения
Новая страница: «[[файл:ОТЗПП02.JPG|thumb|300|[[Математическая модель]] ОТЗПП2]] == Обозначения: == '''n''' — число конеч…»
[[файл:ОТЗПП02.JPG|thumb|300|[[Математическая модель]] ОТЗПП2]]
== Обозначения: ==
'''n''' — число конечных пунктов (поставщиков и потребителей);
'''np''' — число поставщиков;
'''n-np''' — число потребителей;
'''m''' — число промежуточных пунктов (складов);
'''mp''' — число складов с дополнительными (внутренними) потребностями;
'''m-mp''' — число складов с излишками продукции или нулевыми остатками;
'''b<sub>j</sub>>0, j=1,np''' — объём потребностей (в продукции) потребителей;
'''b<sub>j</sub><0, j=np+1,n''' — объём поставок продукции поставщиков;
'''a<sub>i</sub>>0, i=1,mp''' — дополнительные (внутренние) потребности продукции (на складе);
'''a<sub>i</sub>≤0, i=mp+1,m''' — излишки продукции или нулевые остатки (на складе);
'''c<sub>ij</sub>>0, i=1,m, j=1,np''' — транспортные тарифы на перевозку единицы продукции от поставщика на склад;
'''c<sub>ij</sub><0, i=1,m, j=np+1,n''' — транспортные тарифы на перевозку единицы продукции со склада к потребителю;
'''x<sub>ij</sub>≥0, i=1,m, j=1,np''' — объём перевозок продукции от поставщика на склад;
'''x<sub>ij</sub>≤0, i=1,m, j=np+1,n''' — объём перевозок продукции со склада к потребителю.
== Математическая модель ==
[[файл:ОТЗПП02.JPG]].
* Заметим, что в системе ограничений открытой задачи должно быть хотя бы одно строгое неравенство.
== Условия разрешимости ==
Для разрешимости открытой задачи необходимо выполнение условий:
[[файл: ОТЗПП05.JPG]]
Введём дополнительные обозначения:
'''b<sub>n+1</sub><0''' — объём потребностей (в продукции) фиктивного потребителя;
'''c<sub>in+1</sub>≤0, i=1,m''' — транспортные тарифы на перевозку единицы продукции со склада к фиктивному потребителю;
'''x<sub>in+1</sub>≤0, i=1,m''' — объём перевозок продукции со склада к фиктивному потребителю.
Пусть '''M''' — это достаточно большое положительное число.
Для построения вспомогательной эквивалентной закрытой задачи введём фиктивного потребителя с параметрами:
[[файл:ОТЗПП08.JPG]]
[[файл:ОТЗПП12.JPG]]
== Вспомогательная задача ==
[[файл:ОТЗПП22.JPG]]
== Решение вспомогательной задачи ==
Очевидно, что вспомогательная задача является закрытой '''[[Транспортная задача с промежуточными пунктами|транспортной задачей с промежуточными пунктами]]''', которая разрешима по построению.
Для определения начального решения используется '''[[алгоритм северо-западного угла|метод северо-западного угла]]''', а для решения применяется '''[[Транспортная задача с промежуточными пунктами|метод потенциалов]]'''.
Очевидно, что '''M'''-множители и метод потенциалов приводят к нулевым соответствующим (со склада с дополнительными внутренними потребностями к фиктивному потребителю) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные (без фиктивного потребителя) и промежуточные пункты являются оптимальным решением исходной задачи. А перевозки к фиктивному потребителю являются не использованными остатками (излишками) складов.
== Другие задачи: ==
*[[Транспортная задача с промежуточными пунктами]];
*[[Транспортная задача с промежуточными пунктами с запретами]];
*[[Транспортная задача с промежуточными пунктами и ограничением по транзиту]];
*[[Открытая транспортная задача с промежуточными пунктами 1]];
*[[Открытая транспортная задача с промежуточными пунктами 3]];
*[[Открытая транспортная задача с промежуточными пунктами 4]].
== Ссылки ==
* Кривопалов В. Ю., Решение открытой транспортной задачи с промежуточными пунктами. Сборник научных трудов конференции ПИТ-2015, СГАУ, Т.2, стр.86-91. http://ssau.ru/files/events/2015/pit_2015_2.pdf
* [[Участник:Logic-samara]]
[[Категория:Математика]] [[Категория:Линейное программирование]] [[Категория:Транспортная задача]]
== Обозначения: ==
'''n''' — число конечных пунктов (поставщиков и потребителей);
'''np''' — число поставщиков;
'''n-np''' — число потребителей;
'''m''' — число промежуточных пунктов (складов);
'''mp''' — число складов с дополнительными (внутренними) потребностями;
'''m-mp''' — число складов с излишками продукции или нулевыми остатками;
'''b<sub>j</sub>>0, j=1,np''' — объём потребностей (в продукции) потребителей;
'''b<sub>j</sub><0, j=np+1,n''' — объём поставок продукции поставщиков;
'''a<sub>i</sub>>0, i=1,mp''' — дополнительные (внутренние) потребности продукции (на складе);
'''a<sub>i</sub>≤0, i=mp+1,m''' — излишки продукции или нулевые остатки (на складе);
'''c<sub>ij</sub>>0, i=1,m, j=1,np''' — транспортные тарифы на перевозку единицы продукции от поставщика на склад;
'''c<sub>ij</sub><0, i=1,m, j=np+1,n''' — транспортные тарифы на перевозку единицы продукции со склада к потребителю;
'''x<sub>ij</sub>≥0, i=1,m, j=1,np''' — объём перевозок продукции от поставщика на склад;
'''x<sub>ij</sub>≤0, i=1,m, j=np+1,n''' — объём перевозок продукции со склада к потребителю.
== Математическая модель ==
[[файл:ОТЗПП02.JPG]].
* Заметим, что в системе ограничений открытой задачи должно быть хотя бы одно строгое неравенство.
== Условия разрешимости ==
Для разрешимости открытой задачи необходимо выполнение условий:
[[файл: ОТЗПП05.JPG]]
Введём дополнительные обозначения:
'''b<sub>n+1</sub><0''' — объём потребностей (в продукции) фиктивного потребителя;
'''c<sub>in+1</sub>≤0, i=1,m''' — транспортные тарифы на перевозку единицы продукции со склада к фиктивному потребителю;
'''x<sub>in+1</sub>≤0, i=1,m''' — объём перевозок продукции со склада к фиктивному потребителю.
Пусть '''M''' — это достаточно большое положительное число.
Для построения вспомогательной эквивалентной закрытой задачи введём фиктивного потребителя с параметрами:
[[файл:ОТЗПП08.JPG]]
[[файл:ОТЗПП12.JPG]]
== Вспомогательная задача ==
[[файл:ОТЗПП22.JPG]]
== Решение вспомогательной задачи ==
Очевидно, что вспомогательная задача является закрытой '''[[Транспортная задача с промежуточными пунктами|транспортной задачей с промежуточными пунктами]]''', которая разрешима по построению.
Для определения начального решения используется '''[[алгоритм северо-западного угла|метод северо-западного угла]]''', а для решения применяется '''[[Транспортная задача с промежуточными пунктами|метод потенциалов]]'''.
Очевидно, что '''M'''-множители и метод потенциалов приводят к нулевым соответствующим (со склада с дополнительными внутренними потребностями к фиктивному потребителю) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные (без фиктивного потребителя) и промежуточные пункты являются оптимальным решением исходной задачи. А перевозки к фиктивному потребителю являются не использованными остатками (излишками) складов.
== Другие задачи: ==
*[[Транспортная задача с промежуточными пунктами]];
*[[Транспортная задача с промежуточными пунктами с запретами]];
*[[Транспортная задача с промежуточными пунктами и ограничением по транзиту]];
*[[Открытая транспортная задача с промежуточными пунктами 1]];
*[[Открытая транспортная задача с промежуточными пунктами 3]];
*[[Открытая транспортная задача с промежуточными пунктами 4]].
== Ссылки ==
* Кривопалов В. Ю., Решение открытой транспортной задачи с промежуточными пунктами. Сборник научных трудов конференции ПИТ-2015, СГАУ, Т.2, стр.86-91. http://ssau.ru/files/events/2015/pit_2015_2.pdf
* [[Участник:Logic-samara]]
[[Категория:Математика]] [[Категория:Линейное программирование]] [[Категория:Транспортная задача]]
