Логистика_Использование экономико-математических методов при оптиизации транспортных операций

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

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

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

Специальные методы решения

Для решения транспортной задачи разработаны специальные методы, позволяющие из множества возможных решений найти оптимальное. Одним из таких методов является распределительный метод, который имеет неЧ сколько разновидностей, отличающихся в основном способом выявления оптимального решения. Наиболее известны три разновидности: о метод Хичкова; о метод Креко; о модифицированный распределительный метод или метод потенциалов.

Отличаются они в основном способом выявления оптимального решения. Указанные методы достаточно широко представлены в литературе по экономико-математическим методам на автомобильном транспорте.

«Поиск решения»

В настоящее время для решения транспортной задачи и задачи определения кратчайших расстояний широко применяется «Поиск решения» - встроенная возможность Microsoft Excel, позволяющая получить точное решение с наименьшими затратами времени.

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

а) мощность i-го источника (объем поставок товара от i-го источника) равна Si>0, i=l,...,m;

б) мощность j-го стока (объем поставок товара к j-му стоку) равна Dj >0, j=1,...,n;

в) стоимость перевозки единицы товара (в условных денежных единицах) от i-го источника к j-му стоку равна сij;

г) суммарная мощность всех источников равна суммарной мощности всех стоков, т.е.:

     (1)

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

Для математического описания транспортной задачи вводят переменные xij, обозначающие объемы поставок товара от i-го источника j-му стоку. В этом случае xi1+xi2+...+xin – общий объем поставок товара от i-го источника, т.е. мощность этого источника; xij+xi2+...+xin – общий объем поставок товара к j-му стоку, т.е. мощность этого стока; c11x11+ c12x12+…+ cmnxmn – суммарная стоимость перевозок товара от источников к стокам. С учетом этого рассматриваемая задача может быть представлена в следующем виде:

      (2)

На рисунке 2 показано представление транспортной задачи в виде сети с m пунктами отправления и n пунктами назначения, которые показаны в виде узлов сети. Дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой (i,j), соединяющей пункт отправления i с пунктом назначения j, соотносятся два вида данных: стоимость cij перевозки единицы груза из пункта i в пункт j и количество перевозимого груза хij. Объем грузов в пункте отправления i равен Si, а объем грузов в пункте назначения j равен Dj. Задача состоит в определении неизвестных величин xij, минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, накладываемым на объемы грузов в пунктах отправления (предложение) и пунктах назначения (спрос).

 

Рисунок 2 – Представление транспортной задачи в виде сети

 

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

 

2.3 Транспортная задача с промежуточными пунктами.

 

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

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

На рисунке 3 представлена схема размещения складов, на которой указаны:

а) склады в виде узлов сети с номерами от 1 до 8;

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

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

г) возможность перевозки товара со склада i на склад j (ориентированная дуга от круга с номером i к кругу с номером j);

д) затраты, связанные с перевозкой единицы товара со склада i на склад j (величина cij рядом с соответствующей ориентированной дугой, выраженная в денежных единицах).

Рисунок 3 – Схема размещения складов

 

На рисунке 3 видно, что суммарный избыток товара, имеющийся на складах системы с номерами 1 и 4, равен суммарному недостатку товара, имеющемуся на складах с номерами 3, 6 и 8 той же системы. Перераспределение товара может происходить через склады с номерами 2, 4÷7, которые в рассматриваемой задаче и являются промежуточными или транзитными пунктами. Истинным пунктом отправления является лишь склад с номером 1, на котором имеется избыток товара и с которого товар можно только вывозить, а истинными пунктами назначения являются склады с номерами 3 и 8, на которых есть недостаток товара, и на эти склады товары можно только завозить. Заметим также, что между складами с номерами 4 и 5 возможны перевозки в обоих направлениях, но в общем случае c45≠c54 (например, наличие одностороннего движения по кратчайшему маршруту).

Объемы спроса и предложения, соответствующие этим пунктам отправления и назначения, вычисляются следующим образом.

Объем предложения истинного пункта отправления = объем исходного предложения.

Объем предложения транзитного пункта = объем исходного предложения + объем буфера.

Объем спроса истинного пункта назначения = объем исходного спроса.

Объем спроса транзитного пункта = объем буфера.

Объем буфера должен быть таким, чтобы вместить объем всего предложения (или спроса).

Пусть J —множество номеров складов, на которые товар может быть доставлен с k-то склада, а I — множество номеров складов, с которых товар может быть доставлен на k-й склад. Tk — величина чистого запаса товара, равная объему исходного предложения или исходного спроса. Тогда математическую модель данной задачи можно представить следующим образом:

 

      (4)

 

Задача о назначении

Предположим, что имеется n различных работ, каждую которых может выполнить любой из n привлеченных исполнителей. Стоимость выполнения i-й работы j-ым исполнителем известна и равна сij (в условных денежных единицах). Необходимо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.

В исследовании операций задача, сформулированная выше известна как задача о назначениях. Введем переменные хij, принимающие значение 1 в случае, когда i-ю работу выполняет i-й исполнитель и значение 0 во всех остальных случаях, ij = 1, n. Тогда ограничение

 

гарантирует выполнение каждой работы лишь одним исполнителем, ограничение:

 

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

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

 

Задача о назначениях является частным случаем классической транспортной задачи, в которой надо положить n=m, Si = 1, i = 1,...,n, Dj = 1, j = 1,...,n. При этом условие  , i,j = 1,...,n, означает выполнение требования целочисленности переменных хij. Это связано с тем, что мощности всех источников и стоков равны единице, откуда следует, что в допустимом целочисленном решении значениями переменных могут быть только 0 и 1.

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

В задаче о назначениях переменное хij, может принимать значение 0 или 1. При этом в любом допустимом решении лишь и переменных могут принимать значения 1. Таким образом, любое допустимое базисное решение задачи о назначениях будет вырожденным.

На практике встречаются задачи о назначениях, в постановках которых параметр cij для i.j = 1,...,n понимается как эффективность выполнения i-й работы j-м исполнителем. В этих случаях нужно так распределить работы между исполнителями, чтобы суммарная эффективность их выполнения был бы максимальной, т.е.

где максимум ищется при указанных выше ограничениях.

 

 

3. ПРИМЕР ТРАНСПОРТНОЙ  ЗАДАЧИ

 

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

Пусть для простоты заданы всего 4 месторождения М1, М2, М3, М4, причем их ежемесячная добыча составляет a1, а2, а3, а4 тонн угля. Предположим далее, что этот уголь надо доставить в пункты потребления b1, b2, b3, b4, b5, соответственно с ежемесячными потребностями этих пунктов. Будем считать, что общее производство угля равно суммарной потребности в нем (сбалансированность планов): a1, а2, а3, а4 = b1, b2, b3, b4, b5. Задача состоит в определении такого плана перевозок, при котором общая стоимость перевозок была бы наименьшей. Обозначим через x11 количество угля (в тоннах), предназначенное к отправлению из M1 в П1; вообще через xij обозначим количество угля, отправляемого из месторождения Mi в пункт потребления Пj. Схема перевозок примет вид, изображенный в таблице 1.

 

 

 

 

 

 

 

 

Таблица 1 – Схема перевозок

	ПН	в П1	в П2	в П3	в П4	в П5	Всего
ПО							отправлено
из Ì1		х11	х12	х13	х14	х15	a1
из Ì2		х21	х22	х23	х24	х25	а2
из Ì3		х31	х32	х33	х34	х35	а3
из Ì4		х41	х42	х43	х44	х45	а4
Всего привезено		b1	b2	b3	b4	b5