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