Математическая модель транспортной задачи

Лабораторная работа №3

Транспортные задачи и логистика, задачи о назначениях и отборе

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

Математическая модель транспортной задачи

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

Задача №2.1.

В районе имеется два песчаных карьера, с которых песок вывозится на 5-ти тонных грузовиках. Предприятия, S₁и S₂, разрабатывающие карьеры (поставщики песка), могут поставлять соответственно 100 и 200 грузовиков с песком в день. В этом районе имеется три завода железобетонных конструкций (потребители песка) D₁, D₂ и D₃, которым требуется соответственно 80, 90 и 130 грузовиков с песком в день. Стоимости перевозки песка одним грузовиком от карьера S_i(i=1, 2) к заводу D_j(j=1, 2, 3) в условных единицах, приведены в таблице 2.1.

Таблица 2.1. Параметры задачи №2.1

Математическая модель задачи №2.1. В нашей задаче шесть маршрутов.

Обозначим количество грузовиков X_ij, перевозимое с карьера S_iна завод D_j.

Таким образом, у нас шесть переменных. Целевая функция в данной задаче -суммарные транспортные издержки – равна сумме произведений переменных решения X_ijна стоимости перевозки единицы груза C_ij, приведённые в табл. 2.1.

Таким образом,

Чтобы удовлетворить все требования потребителей, т.е. выполнить все заказы, надо чтобы:

Чтобы удовлетворить поставщиков, т.е. вывести весь груз, необходимо, чтобы

Так как поставки не могут быть отрицательными, то Xij≥ 0.

При этом предполагается, что спрос и предложение отвечают условию баланса, т.е.S1+S2=D1+D2+D3.

В общем случае ТЗ выглядит так: Пусть имеется «m» поставщиков некоторойоднородной продукции и «n» потребителей этой продукции. В «m» пунктахотправления А1, А2, …, Аm сосредоточено определённое количество некоторогооднородного груза, (i=1, 2, …, m). Данный груз потребляется в «n» пунктах B1, B2, …, Bn. Объёмы потребления bj (j=1, 2, …n). Известны расходы на перевозку единицы груза из пункта Ai в пункт Bj, которые равны cij.

МатрицаС = (с_{i, j}), i = 1, …, m; j = 1, …, n. называется тарифной матрицей.

где cij – стоимость перевозки единицы груза от i-го поставщика к j-му потребителю.

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

Пусть Xij – количество груза, перевозимого из пункта Ai в Bj, тогда целевая функция имеет вид:

при ограничениях: . (20)

Условия (20) означают полное удовлетворение спроса во всех пунктах потребления и полный вывоз продукции от всех поставщиков. Условие баланса для ТЗ имеет вид:

.

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

Алгоритм решение транспортной задачи с помощью MS–Excel

Для практического решения ТЗ с помощью MS-Excel рассмотрим более сложный пример, на тему «рациональных перевозок грузов».

Задача №2.2. Пусть имеется 4 поставщика и 5 потребителей. Издержки перевозки единицы груза от i-го поставщика в j-й пункт назначения, запасы поставщиков и заказы потребителей даны в таблице 2.4. Оптимизировать план перевозок.

Таблица 2.4. Параметры задачи №2.2

Организуем данные так, как показано в таблице 2.5.

Таблица 2.5. Организация данных задачи №2.2 на листе MS-Excel

1. В ячейках I4-I7 стоят суммы произведений цены единицы груза на объём перевозок от i-го поставщика к любому потребителю.

В ячейке I8 сумма этих сумм (т.е. двойная сумма), это и есть целевая функция, минимум которой надо найти.

В ячейки I10: I13 внесены ограничения на количества груза, вывезенного от каждого поставщика, т.е. запасы.

В ячейки B14: F14 внесены ограничения на количества груза, необходимого потребителям, т.е. заказы.

2. Далее вызываем «Поиск решения».

а) Целевая ячейка: I8, - Мин;

б) Изменяя ячейки: B11: F14;

с) Ограничения: B11: F14≥ 0 (перевозки не могут быть отрицательными), I10: I13=0 (ограничения на количества груза от каждого поставщика), B14: F14=0 (ограничения на количества груза каждому потребителю). При такой организации данных все перевозки окажутся целыми числами, если целыми являются числа в колонках «Запасы» и строке «Заказы».

3. Надо проверить, чтобы в полученном решении было ровно m+n-1 ненулевых перевозок.

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

Ответ: F_min=980 (усл.ден.ед) при плане .

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