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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

5.3 Транспортная задача с ограничениями на пропускную способность
Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером
l к потребителю с номером k. Возможны ограничения двух типов: 1) x
lk
≥ a; 2) x
lk
≤ b, где a и b – постоян-
ные величины.
1 Если x
lk
≥ a, то необходимо прежде, чем решать задачу, сократить запасы l-го поставщика и за-
просы k-го потребителя на величину а (зарезервировать перевозку x
lk
≥ a). После решения задачи в оп-
тимальном решении следует увеличить объем перевозки x
lk
на величину a.
2 Если x
lk
≤ b, то необходимо вместо k-го потребителя с запросами b
k
ввести двух других потреби-
телей. Один из них с номером k должен иметь запросы b
k
= b, а другой с номером n + 1 – запросы b
n+1
=
b
k
– b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости
c
l(n+1)
, которая принимается равной сколь угодно большому числу М (М >> 1). После получения опти-
мального решения величины грузов, перевозимых к (n + 1)-му потребителю, прибавляются к величинам
перевозок k-го потребителя. Так как c
l(n+1)
= M – самая большая стоимость перевозки, то в оптимальном
решении клетка с номером (l, n + 1) останется пустой, x
l(n+1)
= 0 и объем перевозки x
lk
не превзойдет b.
Пример. Решить транспортную задачу, исходные данные которой приведены в табл. 5.14, при до-
полнительных условиях: объем перевозки груза от l-го поставщика 2-му потребителю должен быть не
менее 100 единиц (x
12
≥ 100), а от 3-го 1-му не более 200 единиц (x
31
≤ 200).
Таблица 5.14
b
j
a
i
500 400 300
200
156
300
267
500
378
Р е ш е н и е. Для того чтобы в оптимальном решении объем перевозки x
12
был не менее 100 еди-
ниц, при решении задачи будем предполагать, что запасы 1-го поставщика а
1
и запросы 2-го потребите-
ля b
2
меньше фактических на 100 единиц. После получения оптимального решения объем перевозки x
12
увеличим на 100 единиц.
Для того чтобы удовлетворить требованию x
31
≤ 200, вместо 1-го потребителя введем двух других.
Один из них под прежним первым номером имеет запасы b
1
= 200 единиц и прежние стоимости перево-
зок единиц груза. Другому присвоим четвертый номер. Его запросы равны b
4
= 500 – 200 = 300 единиц и
стоимости перевозок единиц груза те же, что и у 1-го потребителя за исключением с
34
, которую примем
равной сколь угодно большому числу М, т.е. с
34
= М. После нахождения оптимального решения задачи
объемы перевозок для 4-го потребителя необходимо прибавить к соответствующим объемам перевозок
для 10-го потребителя.
В результате указанных преобразований таблица исходных данных задачи будет иметь вид, пред-
ставленный в табл. 5.15.
Таблица 5.15
b
j
a
i
200 300 300 300
100 1 5 6 1
300 2 6 7 2
500 3 7 8
M
Далее задачу решаем обычным методом потенциалов. Проверяем выполнение необходимого
и достаточного условия существования решения задачи. Находим суммарные запасы постав-
щиков и запросы потребителей:
а
1
+ а
2
+ а
3
= 100 + 300 + 500 = 900;

Страницы