Экономико-математическое моделирование транспортных процессов

 

С = 

И общая стоимость  перевозок груза составит:

Z = 120*20 + 30*6 + 140*15 + 110*16 + 200*15 + 30*19 + 220*8 = 11770р. 

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

1. Ищется опорный план. При этом число заполненных клеток должно быть m+n-1 (т.е. план должен быть не вырожденным).
2. Находим потенциалы u_i и v_j . чтобы для каждой базисной клетки (т.е. для той, в которой x_ij > 0) выполнялось условие v_j+u_i=c_ij, если x_ij>0
3. Для каждой свободной клетки определяем ∆_ij=u_i+v_j-c_ij и анализируем их значения:

• если среди оценок ∆_ij нет положительных, то получен оптимальный план транспортной задачи;
• если среди оценок нет положительных, но есть нулевые, то задача имеет бесконечное множество решений и найден только один из ее оптимальных планов;
• если есть оценка ∆_ij > 0, значит необходимо перейти к новому опорному плану.

4. Среди положительных оценок ∆_ij выбирается максимальная, и для клетки, которой эта оценка соответствует строится цикл пересчета и производится сдвиг по этому циклу.

5. Полученный новый опорный план проверяется на оптимальность, т.е. алгоритм начинается снова с п.2.

 
 

Алгоритм  сдвига по циклу пересчета:

1. Выбирается клетка с максимальной оценкой ∆_ij > 0.
2. Строится цикл пересчета (он единственный). Циклом называется замкнутая ломанная линия, вершины которой расположены в занятых клетках таблицы, а звенья параллельны строкам и столбцам.
3. Начиная с выбранной свободной клетки, в которой ставится знак «+», все вершины цикла чередуясь помечают знаками «+» и «-».
4. Среди клеток, помеченных знаком «-», ищется минимальный объем перевозки Q=min{x_ij}.
5. Изменяем опорный план:

• Прибавляем число Q ко всем клеткам, помеченным «+»;
• Вычитаем число Q из всех клеток, помеченных «-».

     Так как в нашей задаче самый минимальные  затраты на перевозку, получились при  помощи метода аппроксимации Фогеля, то будем анализировать полученный этим методом опорный план на оптимальность.

 

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

Пусть U1=0

V1=C11-U1= 20

V4=C14-U1= 15

U2=C24-V4=4

U3=C31-V1=-14

V5=C35-U3= 22

V2=C22-U2= 11

V3=C2,3-U2= 12 

Определяем значения оценок для всех свободных клеток:

∆12 = U1 + V2 - С12 < 0

∆13 = U1 + V3 - С13 < 0

∆15 = U1 + V5 - С15 < 0

∆21 = U2 + V1 - С21 < 0

∆25 = U2 + V5 - С25 < 0

∆32 = U3 + V2 - С32 < 0

∆33 = U3 + V3 - С33 < 0

∆34 = U3 + V4 - С34 < 0 

     Так как все оценки отрицательны, то полученный план является оптимальным  и минимальные транспортные расходы  для данного случая составят 11770 рублей.

     А оптимальный план перевозок будет  выглядеть следующим образом: 

 

С = 
 

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

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

Заключение

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

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

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

            Алгоритм и методы решения  транспортной задачи могут быть  использованы при решении некоторых  экономических задач, не имеющих  ничего общего с транспортировкой  груза. В этом случае величины  тарифов c_ij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие:

• оптимальное закрепление за станками операций по обработке деталей. В них c_ij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения c_ij берутся с отрицательным знаком;
• оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью c_ij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;
• задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции;
• увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;
• решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть отправлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки.

              Таким образом, важность решения  данной задачи для экономики  несомненна.