Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




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

 

a2

 

 

an n m

 

На приведенной иллюстрации используются следующие обозначения:

- а1, …, аn – объемы предложений;

- b1, …, bm – объемы спроса;

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

- хi,j – объем перевозки единицы груза из пункта i в пункт j.

Цель задачи – найти план перевозок Х=(хi,j), минимизирующий суммарные затраты. Приведем математическую модель транспортной задачи:

при ограничениях

, i = 1, …, n,

, j = 1, …, m,

хi , j ³ 0, i = 1, …, n; j = 1, …, m.

 

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

 

Пункты предложения Пункты назначения Предложение (ед. продукции)
    ... m
  с1,1 х1,1 с1,2 х1,2 с1,m x1,m a1
  c2,1 x2,1 c2,2 x2,2 c2,m x2,m a2
n cn,1 xn,1 cn,2 xn,2 cn,m xn,m an
Спрос (ед.продукции) b1 b2 bm  

 

В соответствии с приведенной математической моделью, имеет место равенство суммарных предложения и спроса:

.

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

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

 

Пункты предложения Пункты назначения Предложение ед. продукции
    ... m Фиктивный
  с1,1 х1,1 с1,2 х1,2 с1,m x1,m сф xф1,m a1
  c2,1 x2,1 c2,2 x2,2 c2,m x2,m сф xф2,m a2
n cn,1 xn,1 cn,2 xn,2 cn,m xn,m сф xфn,m an
Спрос ед.продукции b1 b2 bm bф  

 

Стоимость доставки единицы груза из любого пункта предложения в фиктивный пункт назначения принимают равной 0: сф = 0.

Если суммарный спрос превышает суммарное предложение, то вводят фиктивный пункт предложения, который формально восполняет недостаток предложения:

 

Пункты предложения Пункты назначения Предложение ед. продукции
    ... m
  с1,1 х1,1 с1,2 х1,2 с1,m x1,m a1
  c2,1 x2,1 c2,2 x2,2 c2,m x2,m a2
n cn,1 xn,1 cn,2 xn,2 cn,m xn,m an
Фиктивный сф хфn,1 сф хфn,2   сф хфn,m аф
Спрос ед.продукции b1 b2 bm  

 

Стоимость доставки единицы груза из фиктивного пункта предложения в любой пункт назначения принимают равной 0: сф = 0.

Решение транспортных задач проводится в два этапа: первоначальный и основной. На первоначальном этапе получают допустимое базисное решение, которое также называют опорным планом перевозок. Допустимое базисное решение удовлетворяет всем условиям задачи, кроме, быть может, оптимальности. Опорный план перевозок предполагает выполнение не более чем m + n – 1 поставок (заметим, что m + n – 1 – число линейно независимых ограничений системы ограничений). Можно показать, что всегда найдется такое оптимальное решение транспортной задачи, в котором количество поставок (занятых клеток в матрице планирования) также не превосходит числа m + n – 1. Поэтому оптимальный план перевозок ищут среди опорных планов.

Для нахождения первоначального решения используют методы северо-западного угла, наименьшей стоимости, Фогеля и др. Все эти методы предполагают решение одной задачи – построение начального опорного плана. Однако качество начального решения зависит от того, какой метод был использован для его получения. Как правило, метод северо-западного угла (очень простой в применении) дает решение, более далекое от оптимального плана поставок, по сравнению с методами наименьшей стоимости и Фогеля.

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






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных