Просмотр исходного текста страницы Открытая транспортная задача с промежуточными пунктами 1

[[файл:ОТЗПП01.JPG|thumb|300|[[Математическая модель]] ОТЗПП1]]
'''Открытая транспортная задача с промежуточными пунктами 1''' – это открытая [[Транспортная задача с промежуточными пунктами|транспортная задача]] оптимизации перевозок с использованием промежуточных (транзитных) пунктов с избытком грузов (для перевозок) у поставщиков.
== Обозначения: ==
'''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''' — объём перевозок продукции со склада к потребителю. 
== Математическая модель ==
[[файл:ОТЗПП01.JPG]].
* Заметим, что в системе ограничений открытой задачи должно быть хотя бы одно строгое неравенство.
== Условия разрешимости ==
Для разрешимости открытой задачи необходимо выполнение условий:

[[файл: ОТЗПП05.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]]

[[файл:ОТЗПП11.JPG]]
== Вспомогательная задача ==
[[файл:ОТЗПП21.JPG]]
== Решение вспомогательной задачи ==
Очевидно, что вспомогательная задача является закрытой '''[[Транспортная задача с промежуточными пунктами|транспортной задачей с промежуточными пунктами]]''', которая разрешима по построению. 
Для определения начального решения используется '''[[алгоритм северо-западного угла для ТЗПП|метод северо-западного угла]]''', а для решения применяется '''[[Транспортная задача с промежуточными пунктами|метод потенциалов]]'''.
Очевидно, что '''M'''-множители и метод потенциалов приводят к нулевым соответствующим (с фиктивного склада к потребителям) перевозкам в оптимальном решении. В оптимальном решении вспомогательной задачи все перевозки через конечные и промежуточные пункты (без фиктивного склада) являются оптимальным решением исходной задачи. А перевозки на фиктивный склад являются остатками не использованной продукции поставщиков.
== [[Транспортные задачи|Другие задачи:]] ==
{{Список ЗТТ}}
== Ссылки ==
*Кривопалов В. Ю., Решение открытой транспортной задачи с промежуточными пунктами. Сборник научных трудов конференции ПИТ-2015, СГАУ, Т.2, стр.86-91. http://ssau.ru/files/events/2015/pit_2015_2.pdf 
*[[Участник:Logic-samara]]
[[Категория:Математика]][[Категория:Линейное программирование]][[Категория:Транспортная задача]]