Транспортная задача была поставлена еще в 18 веке, но решена лишь во время Великой Отечественной Войны советским математиком Леонидом Витальевичем Кантаровичем. Транспортная задача – это частный случай задачи линейного программирования. Линейность подразумевает, что все зависимости линейные. Программирование предполагает, что для решения задачи необходимо составить некий алгоритм, программу перевозок или план поставок.
Транспортная задача была поставлена еще в 18 веке, но решена лишь во время Великой Отечественной Войны советским математиком Леонидом Витальевичем Кантаровичем. Транспортная задача – это частный случай задачи линейного программирования. Линейность подразумевает, что все зависимости линейные. Программирование предполагает, что для решения задачи необходимо составить некий алгоритм, программу перевозок или план поставок.
Решение транспортной задачи позволяет составить такой оптимальный план перевозок или схему распределения (откуда, куда и сколько углеводородов поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна. Алгоритм решения ТЗ начинается с поиска исходных данных, далее идет проверка сбалансированности задачи, затем строится сбалансированная транспортная матрица, далее ставится условие – решать задачу по минимуму или максимуму, затем при необходимости вводятся ограничения. После того как все этапы пройдены ТЗ решается одним из выбранных методов.
Решение транспортной задачи позволяет составить такой оптимальный план перевозок или схему распределения (откуда, куда и сколько углеводородов поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна. Алгоритм решения ТЗ начинается с поиска исходных данных, далее идет проверка сбалансированности задачи, затем строится сбалансированная транспортная матрица, далее ставится условие – решать задачу по минимуму или максимуму, затем при необходимости вводятся ограничения. После того как все этапы пройдены ТЗ решается одним из выбранных методов.
Поставщиками могут быть – склады, нефтебазы, производители УВ, а также другие пункты отправления. Потребителями могут выступать АЗС, небольшие склады, другие пункты назначения УВ.
Поставщиками могут быть – склады, нефтебазы, производители УВ, а также другие пункты отправления. Потребителями могут выступать АЗС, небольшие склады, другие пункты назначения УВ.
Спрос это тоже самое что потребность в пунктах назначения.
Спрос это тоже самое что потребность в пунктах назначения.
Транспортный тариф может зависеть от расстояния, объема перевозок, времени в пути. В широком смысле тариф может быть представлен в денежном выражении, времени или километрах.
Транспортный тариф может зависеть от расстояния, объема перевозок, времени в пути. В широком смысле тариф может быть представлен в денежном выражении, времени или километрах.
В случае когда общая потребность в углеводародах равна запасам этих углеводородов, транспортная задача является закрытой, замкнутой или сбалансированной. В противном случае мы имеем дело с открытой, не замкнутой или несбалансированной задачей. В реальной жизни мы чаще всего имеем дело с открытыми транспортными задачами. Решить ТЗ можно только закрытого типа. Если в задаче наблюдается дисбаланс, то вводится либо фиктивный потребитель либо фиктивный поставщик.
В случае когда общая потребность в углеводародах равна запасам этих углеводородов, транспортная задача является закрытой, замкнутой или сбалансированной. В противном случае мы имеем дело с открытой, не замкнутой или несбалансированной задачей. В реальной жизни мы чаще всего имеем дело с открытыми транспортными задачами. Решить ТЗ можно только закрытого типа. Если в задаче наблюдается дисбаланс, то вводится либо фиктивный потребитель либо фиктивный поставщик.
Наиболее распространённый случай – это когда целевая функция ТЗ стремится к минимуму. ТЗ может решаться как по минимуму финансовых затрат, так и с целью минимизации времени на доставку. В отдельных случаях ТЗ может решаться с целью максимизации целевой функции, это случаи когда транспортная компания стремится максимизировать свою прибыль. По итогам решения ТЗ определяются искомые xij и суммарные затраты на распределение УВ.
Наиболее распространённый случай – это когда целевая функция ТЗ стремится к минимуму. ТЗ может решаться как по минимуму финансовых затрат, так и с целью минимизации времени на доставку. В отдельных случаях ТЗ может решаться с целью максимизации целевой функции, это случаи когда транспортная компания стремится максимизировать свою прибыль. По итогам решения ТЗ определяются искомые xij и суммарные затраты на распределение УВ.
Первая группа ограничений указывает, что запас УВ в любом пункте отправления должен быть равен суммарному объему перевозок продукции из этого пункта. Вторая группа ограничений указывает, что суммарные перевозки УВ в некоторый пункт потребления должны полностью удовлетворить спрос на УВ в этом пункте. Третья группа ограничений говорит о том что объем перевозок не может быть отрицательным числом.
Первая группа ограничений указывает, что запас УВ в любом пункте отправления должен быть равен суммарному объему перевозок продукции из этого пункта. Вторая группа ограничений указывает, что суммарные перевозки УВ в некоторый пункт потребления должны полностью удовлетворить спрос на УВ в этом пункте. Третья группа ограничений говорит о том что объем перевозок не может быть отрицательным числом.
Метод северо-западного угла также называют диагональным (или улучшенным) методом. Метод наименьшей стоимости также называют методом минимального элемента или ведущего элемента. Часто метод аппроксимации Фогеля называют просто метод Фогеля. Существует метод построения опорного плана называемый – метод двойного предпочтения. Решение ТЗ можно осуществлять с помощью теории графов. Важно! Какой бы метод не использовался при решении ТЗ конечный ответ всегда будет одинаковым.
Метод северо-западного угла также называют диагональным (или улучшенным) методом. Метод наименьшей стоимости также называют методом минимального элемента или ведущего элемента. Часто метод аппроксимации Фогеля называют просто метод Фогеля. Существует метод построения опорного плана называемый – метод двойного предпочтения. Решение ТЗ можно осуществлять с помощью теории графов. Важно! Какой бы метод не использовался при решении ТЗ конечный ответ всегда будет одинаковым.
Рассмотрим примеры построения опорного плана для сбалансированной задачи. В методе северо-западного угла заполнение свободных ячеек начинается с верхней строчки с крайней левой ячейки. Далее строчка заполняется слева направо, до тех пор пока имеющиеся запасы не закончатся, далее действие повторяется для следующей нижней строчки. Если потребность в столбце удовлетворена то переходят к следующей свободной ячейки. Заполнение идет слева направо сверху вниз. После того как производится заполнение свободной ячейки она становится базисной. Базисная ячейка – это ячейка в которой имеется некоторый объем груза. Общие затраты для данного случая составляют 1200 условных единиц.
Рассмотрим примеры построения опорного плана для сбалансированной задачи. В методе северо-западного угла заполнение свободных ячеек начинается с верхней строчки с крайней левой ячейки. Далее строчка заполняется слева направо, до тех пор пока имеющиеся запасы не закончатся, далее действие повторяется для следующей нижней строчки. Если потребность в столбце удовлетворена то переходят к следующей свободной ячейки. Заполнение идет слева направо сверху вниз. После того как производится заполнение свободной ячейки она становится базисной. Базисная ячейка – это ячейка в которой имеется некоторый объем груза. Общие затраты для данного случая составляют 1200 условных единиц.
Составим для предыдущей задачи опорный план методом ведущего элемента. Заполнение свободных ячеек идет в последовательности от наименьшего тарифа к максимальному. При этом для спрос стараются удовлетворить по максимуму для наименьшего тарифа. Общие затраты для данного метода составляют 1120 условных единиц.
Составим для предыдущей задачи опорный план методом ведущего элемента. Заполнение свободных ячеек идет в последовательности от наименьшего тарифа к максимальному. При этом для спрос стараются удовлетворить по максимуму для наименьшего тарифа. Общие затраты для данного метода составляют 1120 условных единиц.
Рассмотрим метод аппроксимации Фогеля. Находим для каждого столбца и каждой строчки разницу между двумя минимальными тарифами. Если у нас два минимальных тарифа равны, разница между ними записывается как нуль. После того как все разницы определены выбираем из них максимальное значение. Для этого максимального значения определяем минимальное значения тарифа в соответствующем ему столбце или строчке. В ячейку с этим минимальным тарифом заносят максимально возможное количество груза. Далее действие повторяется. Если у поставщика исчерпались запасы или потребитель удовлетворил спрос, то соответствующие строчки или столбцы далее не заполняются. Если разницы между тарифами равны и среди них нет минимального, то строчка или столбец для заполнения выбирается произвольно. Важно отметить что по мере заполнения таблицы разницы между минимальными значениями тарифов могут меняться, как увеличиваться так и уменьшаться, по сравнению с предыдущими значениями в соответствующих строчках или столбцах. Общие затраты для данного метода составляют 1140 условных единиц.
Рассмотрим метод аппроксимации Фогеля. Находим для каждого столбца и каждой строчки разницу между двумя минимальными тарифами. Если у нас два минимальных тарифа равны, разница между ними записывается как нуль. После того как все разницы определены выбираем из них максимальное значение. Для этого максимального значения определяем минимальное значения тарифа в соответствующем ему столбце или строчке. В ячейку с этим минимальным тарифом заносят максимально возможное количество груза. Далее действие повторяется. Если у поставщика исчерпались запасы или потребитель удовлетворил спрос, то соответствующие строчки или столбцы далее не заполняются. Если разницы между тарифами равны и среди них нет минимального, то строчка или столбец для заполнения выбирается произвольно. Важно отметить что по мере заполнения таблицы разницы между минимальными значениями тарифов могут меняться, как увеличиваться так и уменьшаться, по сравнению с предыдущими значениями в соответствующих строчках или столбцах. Общие затраты для данного метода составляют 1140 условных единиц.
Выбор метода построения опорного плана является весьма субъективным решением. Зачастую, наиболее близким к оптимальному плану является метод Фогеля, так же достаточно высокую эффективность показывает метод наименьшей стоимости. Для данных условий, минимальное значение целевой функции показывает метод наименьшей стоимости. При дальнейшем решении данной ТЗ методом потенциалов минимальное значение затрат получается 1070.
Выбор метода построения опорного плана является весьма субъективным решением. Зачастую, наиболее близким к оптимальному плану является метод Фогеля, так же достаточно высокую эффективность показывает метод наименьшей стоимости. Для данных условий, минимальное значение целевой функции показывает метод наименьшей стоимости. При дальнейшем решении данной ТЗ методом потенциалов минимальное значение затрат получается 1070.
Итерации (перераспределение поставок) в методе потенциалов ведутся до такого состояния плана поставок когда косвенные тарифы не станут меньшими или равными реальным. После этих итерация целевая функция примет минимальное значение, а план поставок УВ станет оптимальным.
Итерации (перераспределение поставок) в методе потенциалов ведутся до такого состояния плана поставок когда косвенные тарифы не станут меньшими или равными реальным. После этих итерация целевая функция примет минимальное значение, а план поставок УВ станет оптимальным.
Для анализа полученных планов и их последующего улучшения удобно ввести дополнительные характеристики пунктов отправления и назначения, называемые потенциалами. Каждому поставщику Ai и каждому потребителю Bj величины Ui и Vj соответственно так, чтобы для всех базисных клеток плана было выполнено соотношение: Ui + Vj = Cij. После определения всех потенциалов, с их помощью вычисляют косвенные тарифы. Если косвенный тариф больше реального, то план поставок может быть улучшен. Если косвенный тариф равен реальному, то решение оптимальное но не единственное. Если косвенный тариф меньше реального, то решение оптимальное и единственное.
Для анализа полученных планов и их последующего улучшения удобно ввести дополнительные характеристики пунктов отправления и назначения, называемые потенциалами. Каждому поставщику Ai и каждому потребителю Bj величины Ui и Vj соответственно так, чтобы для всех базисных клеток плана было выполнено соотношение: Ui + Vj = Cij. После определения всех потенциалов, с их помощью вычисляют косвенные тарифы. Если косвенный тариф больше реального, то план поставок может быть улучшен. Если косвенный тариф равен реальному, то решение оптимальное но не единственное. Если косвенный тариф меньше реального, то решение оптимальное и единственное.
ТЗ номер 4 является закрытой. Построение опорного плана выполняется методом северо-западного угла. Данная ТЗ невырожденная. Находим максимальный тариф среди всех базисных ячейках. Для данного тарифа произвольно задаем значения его потенциалов в виде целых чисел. Определяем все значения потенциалов. Потенциалы могут быть найдены как с помощью уравнений там и быть определены непосредственно в таблице. В дальнейшем уравнения не будут записываться. Определяем косвенные тарифы для свободных (незаполненных) ячеек. В данном случае в свободной ячейке 1:3 косвенный тариф равен реальному. Решение оптимальное но не единственное.
ТЗ номер 4 является закрытой. Построение опорного плана выполняется методом северо-западного угла. Данная ТЗ невырожденная. Находим максимальный тариф среди всех базисных ячейках. Для данного тарифа произвольно задаем значения его потенциалов в виде целых чисел. Определяем все значения потенциалов. Потенциалы могут быть найдены как с помощью уравнений там и быть определены непосредственно в таблице. В дальнейшем уравнения не будут записываться. Определяем косвенные тарифы для свободных (незаполненных) ячеек. В данном случае в свободной ячейке 1:3 косвенный тариф равен реальному. Решение оптимальное но не единственное.
ТЗ пять является закрытой. Выполняется построение опорного плана. Данная ТЗ невырожденная. Находим максимальный тариф среди всех базисных ячейках равный 7. Для данного тарифа задаем значения потенциалов 4 и 3. Определяем все значения потенциалов. Определяем все косвенные тарифы для свободных ячеек. В данном случае в свободный ячейках 3:1 и 3:2 косвенные тарифы больше реальных. Решение не оптимальное и план поставок может быть улучшен. Мы переносим максимально возможный объем из базисной ячейки 2:2 с максимальным тарифом 7 в свободную ячейку 3:2 с меньшем значением тарифа – 2, этот объем составляет 30 условных единиц. При этом согласно метода потенциалов мы должны из строчки 3, из одной из базисных ячеек, в нашем случае это ячейка 3:3, переместить такой же объем груза, составляющего 30 условных единиц, в строчку 2.
ТЗ пять является закрытой. Выполняется построение опорного плана. Данная ТЗ невырожденная. Находим максимальный тариф среди всех базисных ячейках равный 7. Для данного тарифа задаем значения потенциалов 4 и 3. Определяем все значения потенциалов. Определяем все косвенные тарифы для свободных ячеек. В данном случае в свободный ячейках 3:1 и 3:2 косвенные тарифы больше реальных. Решение не оптимальное и план поставок может быть улучшен. Мы переносим максимально возможный объем из базисной ячейки 2:2 с максимальным тарифом 7 в свободную ячейку 3:2 с меньшем значением тарифа – 2, этот объем составляет 30 условных единиц. При этом согласно метода потенциалов мы должны из строчки 3, из одной из базисных ячеек, в нашем случае это ячейка 3:3, переместить такой же объем груза, составляющего 30 условных единиц, в строчку 2.
Производим перераспределение объемов поставки. Производим проверку плана на вырожденность. Находим максимальный тариф среди всех базисных ячейках равный 7. Для данного тарифа вновь задаем значения потенциалов 4 и 3, хотя эти значения могут быть и другими. Снова определяем все значения потенциалов. Определяем все косвенные тарифы для свободных ячеек. В данном случае, абсолютно все косвенные тарифы меньше реальных. Решение оптимальное и единственное.
Производим перераспределение объемов поставки. Производим проверку плана на вырожденность. Находим максимальный тариф среди всех базисных ячейках равный 7. Для данного тарифа вновь задаем значения потенциалов 4 и 3, хотя эти значения могут быть и другими. Снова определяем все значения потенциалов. Определяем все косвенные тарифы для свободных ячеек. В данном случае, абсолютно все косвенные тарифы меньше реальных. Решение оптимальное и единственное.
ТЗ номер 6 является сбалансированной. Выполняется построение опорного плана методом наименьшей стоимости. Данная ТЗ невырожденная. Находим максимальный тариф среди всех базисных ячейках. Для данного тарифа произвольно задаем значения его потенциалов в виде целых чисел. Определяем все значения потенциалов. Определяем косвенные тарифы для свободных ячеек. В данном случае в свободной ячейке 3:1 косвенный тариф равен реальному. Решение оптимальное но не единственное.
ТЗ номер 6 является сбалансированной. Выполняется построение опорного плана методом наименьшей стоимости. Данная ТЗ невырожденная. Находим максимальный тариф среди всех базисных ячейках. Для данного тарифа произвольно задаем значения его потенциалов в виде целых чисел. Определяем все значения потенциалов. Определяем косвенные тарифы для свободных ячеек. В данном случае в свободной ячейке 3:1 косвенный тариф равен реальному. Решение оптимальное но не единственное.
ТЗ номер 7 является закрытой. Выполняется построение опорного плана. Условие не вырожденности соблюдается. Максимальный тариф среди всех базисных ячейках равен 7. Для данного тарифа произвольно задаем значения его потенциалов в виде целых чисел 3 и 4. Определяем все значения потенциалов. Определяем косвенные тарифы для свободных ячеек. В данном случае, абсолютно все косвенные тарифы меньше реальных. Решение оптимальное и единственное.
ТЗ номер 7 является закрытой. Выполняется построение опорного плана. Условие не вырожденности соблюдается. Максимальный тариф среди всех базисных ячейках равен 7. Для данного тарифа произвольно задаем значения его потенциалов в виде целых чисел 3 и 4. Определяем все значения потенциалов. Определяем косвенные тарифы для свободных ячеек. В данном случае, абсолютно все косвенные тарифы меньше реальных. Решение оптимальное и единственное.
В данном случае у нас ТЗ открытого типа. Чтобы привести ее к закрытой задачи вводится фиктивный потребитель, и ему как бы направляется избыток в 26 единиц. При этом тарифы на поставку ему УВ равны нулю. Построение опорного плана выполняется методом потенциалов, потребность удовлетворяется сначала для ячеек с минимальным тарифом, и далее по возрастающей. Далее опорный план проверяется на вырожденность, в нашем случае он не вырожден. Находим максимальный тариф из всех базисных клеток. Определяем все значения потенциалов. Определяем косвенные тарифы для свободных (незаполненных) ячеек. В данном случае в свободных ячейках все косвенные тарифы все меньше реальных. Решение оптимальное и единственное.
В данном случае у нас ТЗ открытого типа. Чтобы привести ее к закрытой задачи вводится фиктивный потребитель, и ему как бы направляется избыток в 26 единиц. При этом тарифы на поставку ему УВ равны нулю. Построение опорного плана выполняется методом потенциалов, потребность удовлетворяется сначала для ячеек с минимальным тарифом, и далее по возрастающей. Далее опорный план проверяется на вырожденность, в нашем случае он не вырожден. Находим максимальный тариф из всех базисных клеток. Определяем все значения потенциалов. Определяем косвенные тарифы для свободных (незаполненных) ячеек. В данном случае в свободных ячейках все косвенные тарифы все меньше реальных. Решение оптимальное и единственное.
