Логистика: задача по грузоперевозке (речной транспорт)

ВЕДЕНИЕ 

     В обслуживании народного хозяйства  речной транспорт взаимодействует  с большим числом отправителей и получателей груза, со смежными видами транспорта. Многообразие путевых условий и родов груза предопределяет многотипность транспортных средств по грузоподъемности, скорости движения и целому ряду других характеристик. Большое число факторов, воздействующих на транспортный процесс по времени, приводит к тому, что состояние объектов и ситуаций, из которых складывается результирующий процесс, имеет значительную вариацию. Ее размер зависит не только от внутренних особенностей, присущих речному транспорту, но и от постоянного воздействия внешних источников на процесс перевозок грузов. Все это вносит аспект неопределенности в планирование и управление работой флота и портов, появляются операции и процессы, которые в математике определяются как случайные.

     Для изучения и математического описания таких процессов применяются вероятностные методы. При исследовании статистических данных эти методы опираются на математическую статистику и теорию вероятностей, которая изучает случайные величины и процессы.

     В применении к реальным системам в обслуживании различных сфер человеческой деятельности развитие вероятностных методов привело к созданию теории массового обслуживания. На речном транспорте эта теория изучает потоки различных заявок (судов, грузов, пассажиров, информации) поступающих в системы обслуживания (порты, шлюзы, вычислительные центры) с целью определения оптимальных режимов работы систем.

     Дальнейшее расширение применения вероятностных методов при решении практических задач привело к созданию численного метода решения математических задач моделированием случайных величин - метода                статистических испытаний (Монте - Карло).

     С появлением ЭВМ этот метод получил широкое распространение. Математической наукой разработаны различные методы оптимального планирования и управления разнообразными процессами в технике и экономике. Наиболее видное место среди них занимает математическое программирование - область математики, изучающая теорию и численные методы решения многомерных экстремальных задач.

     Общей идеей методов математического  программирования является принцип  последовательного приближения  к наилучшему варианту путем улучшения  ряда предшествующих вариантов, начиная с первого допустимого с точки зрения поставленных целей и наличия выделенных ресурсов. Такое решение может состоять из нескольких десятков последовательных шагов, называемых итерациями, которые осуществляются по определенным правилам (алгоритму).

     В перевозке грузов и пассажиров на внутренних водных путях участвуют  десятки типов судов; сотни причалов, судоходных гидротехнических сооружений и судоремонтных баз осуществляют обслуживание судов. Организация транспортного процесса требует проведения комплексных эксплуатационно-экономических обоснований. Среди задач, относящихся к обоснованиям основной деятельности речного транспорта, выделяются:

     прогнозирование и перспективное планирование развития перевозок и технических средств  речного транспорта;

     рациональное  распределение перевозок между видами транспорта и подвижного состава;

     оптимальное распределение технических средств  речного транспорта для освоения перевозок грузов и пассажиров в  процессе текущего и оперативного планирования;

     обоснование рационального технологического процесса работы флота, портов и других технических средств и систем обслуживания;

     учет  и анализ работы предприятий речного  транспорта и отдельных типов  подвижного состава.

     От  работников, выполняющих экономические  обоснования, требуются обширные знания в области современных методов оптимизации с использованием ЭВМ. Применению этих методов предшествует моделирование исследуемого процесса. Сущность моделирования - заменить оригинал адекватной моделью, отражающий основные черты исследуемого процесса.

     Целью данной курсовой работы является овладение  экономико-математическими методами и моделированием процессов перевозок  в водном транспорте.

     Процесс моделирования содержит следующие этапы:

     постановку  задачи и описание ее содержания;

     сбор и обработку исходных данных, анализ полученной информации с целью выявления наиболее существенных факторов технико- экономического и эксплуатационного обоснований, установление количественных и качественных взаимосвязей между ними;

     построение  экономико-математической модели в виде системы уравнений и неравенств, логических соотношений, определение целевой функции и системы ограничений;

     выбор соответствующего вычислительного алгоритма и машинной программы;

     выполнение  расчетов и анализ результатов решения.

     Математические  модели обычно состоят из двух частей:

     ограничений задачи в виде набора независимых  переменных и условий, характеризующих  их приемлемые значения;

     целевой функции, которую необходимо оптимизировать.

     Поиск оптимального решения в производственных и экономических системах связан с выбором критерия оптимальности - показателя, экстремальное значение которого характеризует предельно достижимую эффективность траектории развития объекта управления. В задачах математического программирования критерий оптимальности представляется как целевая функция, является мерой для сравнения количественных показателей решаемых задач и вариантов решений.

     1 Транспортная задача. 

     Цель задачи: взаимная увязка пунктов погрузки и пунктов выгрузки груза.

     Исходные  данные:

     Плановые объемы добычи и потребления песчано-гравийной смеси в порту: А₁ = 250 тыс. т; А₃ = 120 тыс. т; А₅ = 230 тыс. т;

       В₂ = 90 тыс. т; В₃ = 60 тыс. т; В₄ = 80 тыс. т; В₅ = 120 тыс. т.

     Транспортные  затраты между корреспондирующими пунктами в таблице 1.1. 

Таблица 1.1 – Транспортные затраты между корреспондирующими пунктами 

     Экономико-математическая модель задачи:

       Необходимо найти такой вариант решения задачи, который обеспечивал бы экстремальное значение критерия оптимальности при следующих условиях:

     все грузы, планируемые к отправке должны быть полностью отгружены;

     потребности грузополучателей в грузоперевозках  должны быть удовлетворены;

     масса груза, погруженного и отправленного в судах, не может принимать отрицательного значения.

     Вводятся  следующие обозначения:

     i – признак пункта погрузки;

     j – признак пункта выгрузки;

     X_ij – масса груза, перевезенного от i-того пункта погрузки в j-тый пункт выгрузки, тыс. т;

     с_ij – удельные транспортные затраты по доставке грузов из i-того пункта погрузки в j-тому потребителю, руб/т;

     G_i – грузооборот i-того пункта погрузки за навигацию, тыс. т;

     G_j – грузооборот j-того пункта выгрузки за навигацию, тыс. т. 

     Цель задачи взаимной увязки пунктов погрузки и выгрузки математически выражается функцией: 

      .                                                                                  (1.1)

     Ограничения задачи:

      ;                                                                                                                     (1.2)

      ;                                                                                                    (1.3)

      ; ; .                                                                             (1.4)

     Необходимым условием решения задачи является равенство

      = .                                                                                                 (1.5)

     Если  это условие не соблюдается, то вводится фиктивный пункт отправления. если

      , то   - .                                                                   (1.6)

      , то  - .                                                         (1.7) 

     Алгоритм  решения задачи.

     Решение задачи взаимной увязки пунктов погрузки и выгрузки проводится в матричной форме методом потенциалов в следующей последовательности:

     составляется  начальная матрица;

     составляется  начальный допустимый план методом  аппроксимации Фогеля;

     составляется  второй начальный  допустимый план любым другим приближенным методом решения транспортной задачи;

     из  двух начальных допустимых планов выбирается лучший, в котором показатель функции цели численно меньше;

     рассчитываются  вспомогательные оценочные числа (потенциалы);

     полученный  план проверяется на оптимальность. Если план оптимален - расчет заканчивается, если план не оптимален – находится звено с максимальным отклонением от оптимальности;

     составляется  контур перераспределения ресурсов, в котором отыскивается максимальный элемент, строится новый план;

     процесс повторяется до получения оптимального плана. Для проверки правильности расчетов на каждой итерации желательно рассчитывать показатель функции цели. Его значение не должно быть больше в сравнении с предыдущим. 
 

     Расчет.

     Рассчитываются  суммарные объемы добычи и потребления по формулам (1.3), (1.2).

      (тыс. т).

      (тыс. т).                                                                                                      

     Чтобы выполнялось условие (1.4) необходимо ввести фиктивного потребителя

      (тыс. т).

     Удельные  транспортные затраты по перевозкам грузов от поставщика фиктивному потребителю  принимается равным 1000 руб./т.

     Для решения задачи формируется расчетная  матрица (таблица 1.2). В матрице по строкам располагаются пункты отправления, а по столбцам – пункты потребления. В нижнем правом углу записываем удельные транспортные затраты между корреспондирующими пунктами. 

Таблица 1.2  - Матрица исходных данных

     Составляется  начальный план методом аппроксимации  Фогеля. По каждой строке и каждому  столбцу матрицы находится разность между двумя наименьшими значениями с_ij. Эти разности заносятся в специальные «поля» разностей по строкам и столбцам, которые достраиваются к исходной матрице справа и снизу (таблица 3). Затем из всех полученных разностей выбирается наибольшее значение. Если это наибольшее значение разностей получилось в столбце, то для анализа выбирается этот столбец, в котором загружается клетка с наименьшим значением с_ij, исходя из условия

      .                                                                                            (1.8)

     Если  наибольшее значение разностей получилось в строке, то анализируются строки и также загружается клетка с  наименьшим значением , исходя из условия (1.8).

     Далее процесс повторяется, исключая те строки и столбцы, ресурсы которых исчерпаны. Указанные выше вычисления продолжаются до получения допустимого плана. 
 
 

Таблица 1.3 – Начальный план 1

      .

      .

      .

      .

      .

      .

      .

     Значение  целевой функции:

     Составляется  начальный план методом минимального элемента.

     Анализируется вся матрица, и все клетки матрицы  нумеруются в порядке возрастания, начиная с минимального. Если в  процессе оказывается две или  более клетки с одинаковыми значениями, то они нумеруются произвольно.

     Далее в той же последовательности загружаются базисные клетки из условия (1.8), исключая те столбцы и строки, ресурсы которых исчерпаны.

     В таблице 1.4 нумерация клеток дана в  правом верхнем углу каждой клетки.                                                                                    

Таблица 1.4 – Начальный план 1

      .

     Ресурсы третьего столбца исчерпаны. Следующей  будет загружаться клетка 1-1.

      .

      .

      .

      .

      .

     Проверяются ограничения задачи (1.2), (1.3), (1.4). При  суммировании по столбцам условия выполняются.

     Значение  целевой функции

     Для проверки на оптимальность выбирается начальный план, составленный методом минимального элемента. Проверяем план на невырожденность.

      ;                                                                                                 (1.9)

     где - необходимое число базисных клеток в матрице;

           - количество строк в матрице;

           - количество столбцов в матрице.

     В теории линейного программирования доказано, что оптимальный план всегда находится в числе невырожденных планов.

      ,  - следовательно, план невырожденный.

     План считается оптимальным, если выполняется условие для базисных клеток

      ;                                                                                                  (1.10)

     для свободных клеток

      ;                                                                                                  (1.11)

     где и - соответственно потенциалы строк и столбцов.

     Принимаем   .

     Далее по загруженным клеткам рассчитываются остальные потенциалы (таблица 1.4).

      ;          .

      ;          .

      ;          .

      ;          .

      ;          .

      ;          .

      ;          .

     Рассчитываем  характеристики свободных клеток

      ;    ; (-)

      ;    ;   (-)

      ;   ;     (+)

      ;    ;   (-)

      ;    ;   (-)

      ;    ;     (-)

      ;      ;     (+)

      ;     . (-)

     План, представленный в таблице 1.4 не оптимален, так как условие (1.11) не выполняется  для клеток (1-2) и (1-4). План может быть улучшен за счет перераспределения порожних перевозок.

     Выбирается  клетка с наибольшим отклонением  от оптимальности. Через эту клетку строится контур перераспределения.

     Перерасчет  неизвестных и контур перераспределения  начинается с клетки (1-2). Эту клетку необходимо загрузить на некоторую  величину .

     Клетка (1-2) ;          ;

     Клетка (1-4) ;        .

     Находим и

      ;    ;   ;

      ;    ;   .

     Минимальный элемент в цепи перераспределения  выбирается из условия

      .

     Подставляя  найденное значение , рассчитываются значения неизвестных и составляется новый план.