Математические методы в коммерческой деятельности. Буравлева О.Ю. - 33 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

В некоторых задачах требуется запретить перевозки от отдельных поставщиков отдельным потре-
бителям. В таких случаях либо зачеркивают клетку таблицы транспортной задачи, либо назначают со-
ответствующую этой клетке стоимость перевозки единицы груза сколь угодно большой, равной М >> 1.
В остальном задача решается обычным способом. Для разрешимости данной задачи необходимо суще-
ствование начального опорного решения.
5.4 Транспортная задача по критерию времени
Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспорт-
ной задаче, имеется m поставщиков с запасами однородного груза в количестве а
1,
а
2
, …, а
m
и n потре-
бителей, которым этот груз должен быть доставлен в объеме b
1
, b
2
, …, b
n
. Известно t
ij
, i = 1, 2, …, m, j =
1, 2, …, n – время, за которое груз доставляется от каждого i-го поставщика каждому j-му потребителю.
Требуется составить такой план перевозок груза, при котором запасы всех поставщиков вывозятся пол-
ностью, запросы всех потребителей удовлетворяются полностью и наибольшее время доставки всех
грузов является минимальным.
Составим математическую модель этой задачи. Обозначим x
ij
– объем перевозимого груза от i-го
поставщика j-му потребителю. Система ограничений задачи не отличается от системы ограничений
обычной транспортной задачи. Пусть X = (x
ij
), i = 1, 2, …, m, j = 1, 2, …, n – некоторое опорное решение
задачи. Запишем целевую функцию задачи. Обозначим через T(X) наибольшее значение элементов мат-
рицы T = (t
ij
), i = 1, 2, …, m, j = 1, 2, …, n, соответствующих клеткам таблицы, занятым опорным решени-
ем: T(X) = =
{
}
ij
x
t
ij
0
max
>
. Таким образом, за время T(X) план перевозок будет выполнен полностью. Матема-
тическая модель имеет вид:
T(X) =
{
}
ij
x
t
ij
0
max
>
→ min, (5.12)
∑
=
=
n
j
iij
ax
1
, i = 1, 2, …, m, (5.13)
∑
=
=
m
i
jij
bx
1
, j = 1, 2, …, n, (5.14)
x
ij
≥ 0, i = 1, 2, …, m, j = 1, 2, …, n. (5.15)
Задача решается в следующем порядке. Находится начальное опорное решение X
1
. Определяется зна-
чение целевой функции T(X
1
) =
{
}
ij
x
t
ij
0
max
>
=
.
11
kl
t
Все свободные клетки, которым соответствуют значения
t
ij
> T(X
1
), исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так
как повысится значение целевой функции. Чтобы понизить ее значение, необходимо освободить клетку (l
1
,
k
1
), в которой t
ij
достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут
включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружае-
мой клетки (l
1
, k
1
), расставляются поочередно знаки «–» и «+» и осуществляется сдвиг на величину 0 =
max{x
ij
}. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). По-
лучается новое опорное решение X
2
, на котором значение целевой функции меньше, чем на X
1
. Далее
снова пытаются разгрузить клетку, соответствующую T(X
2
) =
{
}
ij
x
t
ij
0
max
>
=
22
kl
t
. Процесс продолжается до
тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.
Пример. Найти минимальное время на осуществление всех перевозок для задачи, исходные данные
которой приведены в табл. 5.18.
Р е ш е н и е. Составим начальное опорное решение X
1
по методу северо-западного угла (см. табл.
5.18). Базисные нули не записываем. Максимум целевой функции T(X
1
) =
{}
4,12,5,8,10max
0>
ij
x
= 12 достига-
ется в клетке (3, 4). Перечеркнем клетку (4, 1), в которой время доставки груза t
41
= 15 больше T(X
1
) =12.
Таблица 5.18
b
j
a
i
20 30 40 60
20
10
20
6 3 2
30
5 8
– 30
74
+
2 4 512

Страницы