Математика для экономистов - Красс М.С.
ISBN 5-94723-672-9
Скачать (прямая ссылка):
Модель такой задачи имеет вид поиска минимума целевой функции стоимости транспортных затрат (14.17) при ограничениях
При введении фиктивных поставщика или потребителя открытая транспортная задача становится закрытой и решается по ранее рассмотренному алгоритму для закрытых транспортных задач, причем тарифы, соответствующие фиктивным поставщику или потребителю, принимаются большими или равными наибольшему из всех транспортных тарифов, иногда пх считают равными нулю. В найденном оптимальном решении целевой функции фиктивный поставщик или потребитель не учитываются.
Пример 3.
Составить оптимальный план перевозки грузов от трех поставщиков с грузами 240. 40. 110 т к четырем потребителям с запросами 90, ! 90,40 и 130 т. Тарифы на перевозку единицы груза от каждого поставщика к каждому потребителю даны матрицей
0
2>*
Jc^ > = 0, і = I гл + I1 J = In.
f 7 13 9 8^ 14 8 7 10
3 15 20 6
14.4, Транспортная задача 297
Решение.
м
Запасы грузов у поставщиков ^ at = 1190 т.
1*1
і -л і
Запросы потребителей ^h1 = 450 т, так как at < ]Т bt, то вводим
фиктивного поставщика с грузом = 450 — 3DO = 60 т. Тариф фиктивного поставщика 4ф примем равным 20 леи. ед. Таблица задачи имеет следующий втщ.
I
90
•>
IQO
3
¦10
•1
130
I
.3
ПО
9
8
111)
0
2
40
14
а
0
7
40
10
-5
г
110
90
15
20
Є
-2 7
60
20
со
20
20
20
5
13
12
8
Так как т + п — 1 = 7, а чисто занятых клеток равно 6, то для исключения вырожденности введем в клетку (2, 2) нулевую поставку. Оценки свободных клеток равны:
Д,, = -2, Д0 = 3, Л;( = 14, Дм = -7. Дщ = -4, Да, - -10, A4+1 = -8, Оценка свободной клетки (1,3) больше нуля, перераспределим грузы:
130
0
во
40 40
40
Запишем полученное перераспределение грузов в новую таблицу.
20-12 22
298 Глава 14. Линейное программирование
1
90
2
190
3
40
4
130
и,
¦
I
240
7
IS
90
9
40
8
110
0
2
40
14
8
40
7
10
-5
I
3
LlO
3
90
15
20
6
20
-2
60
20
20
GO
20
20
7
5
ІЗ
9
8
Теперь оценки свободных клеток вге отрицательны:
Дп = ~2, Д„ = -14. Дта = -3, Ди = -7, Дзг = -4Т Д.,, = -13, А«, = -7, До = -4. Л« = -5. Таким образом, напучено оптимальное решение
Ґ 0 90 40 HO1I 0 40 0 0 90 90 0 20
при котором стоимость транспортных расходов составляет: A(JC111) = 3120 дсн. ед.
Применение транспортных моделей в экономических задачах
Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих отношения к транспортировке грузов. В этом случае величины тарифов C1J имеют различный смысл в зависимости от конкретной задачи.
1. Оптимальное закрепление за станками операций по обработке деталей. В них величина cit является производительностью. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения с берутся с отрицательным знаком.
14.4. Транспортная задача 299
2. Оптимальные назначения или проблема выбора. Имеется т механизмов, которые могут выполнять п различных работ с производительностью (?. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности.
3. Задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции.
4. Увеличение произволнтелыгости автомобильного транспорта за счет минимизации порожнего пробега, сокращение которого позволит уменьшить количество автомобилей для перевозок за счет увеличения их производительности.
5. Решение задач с помощью метода запрещения перевозок. Используется в том глучае, если груз от некоторого поставщика по каким-то причинам не может быть направлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости.
Пример 4.
На предприятии имеется три группы станков, каждая из которых может выполнять пять операций по обработке деталей (операции могут выполняться в любом порядке). Максимальное время работы каждой группы станков равно 100, 250 и 180 ч соответственно. Время выполнения каждой операции составляет 100, 120, 70, 110 и 130 ч соответственно.
Определить, сколько времени и на какой операции нужно использовать каждую группу станков, чтобы обработать максимальное количество деталей.
Производительности каждой группы станков на каждой операции заданы матрицей
'3 5 11 10 51 5 10 15 3 2 . ч4 8 Є 12 10;
Решение.
Воспользуемся алгоритмом решения закрытой транспортной задачи (14.16)-(14.18), при этом под тарифом будем понимать производительность станков по операциям.
Так как в задаче требуется найти максимум, а согласно алгоритму транспортной задачи находится минимум, тарифы умножим на (-1).
