Экономико-математическая модель транспортной задачи
Важным частным случаем задачи линейного программирования является так называемая транспортная задача. Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта (или взаимозаменяемых продуктов) из пунктов производства в пункты потребления. Экономико-математическая модель транспортной задачи в общем виде может быть сформулирована следующим образом: Имеется m пунктов производства однородного продукта и n пунктов потребления. Для каждого пункта производства i задан объем производства Аi, для каждого пункта потребления j известна потребность (спрос) Вj (в тех же единицах измерения). Известны издержки сij, связанные с перевозкой единицы продукта из пункта i в пункт j. Требуется составить план перевозок, обеспечивающий наиболее экономным путем (т.е. при наименьших транспортных издержках) удовлетворение всех пунктов потребления за счет реализации всего продукта, произведенного пунктами производства. При этом предполагается, что суммарный спрос (В=∑jВj) равен суммарному объему производства (А=∑iАi). Такие задачи называются закрытыми транспортными задачами. Что такое план перевозок? План перевозок определяет: Сколько единиц продукта перевозится от каждого пункта производства к каждому пункту потребления, т.е. план представляется набором чисел х ij (всего таких чисел m×n), где х ij показывает, сколько единиц продукта должно быть перевезено от i-го производителя j-му потребителю. Отметим также, что в термин «транспортные издержки» (сij) не всегда вкладывается строгий экономический смысл. Это могут быть расстояния, тарифы, время, расход топлива и т.п. В каждой конкретной задаче оговаривается конкретный смысл коэффициентов сij. Система ограничений примет вид
123 ∑ = n j ijx 1 = Аi (i=1,2,…,m), (2.3.1) ∑ = m i ijx 1 = Вj (j=1,2,…n). (2.3.2) Система (2.3.1) включает в себя уравнения баланса по поставщикам, а система (2.3.2) – по потребителям. Суммарные транспортные издержки выражаются в виде следующей линейной функции, которую необходимо минимизировать
F =∑∑ == n j m i ijijxc 11 巸 min (2.3.3) Математическая модель транспортной задачи в общей постановке будет следующей: на множестве неотрицательных решений системы ограничений (2.3.1), (2.3.2) (мы будем называть такие решения допустимые ) найти такое решение Х=( х 11, х 12,…, х ij ,…, х mn), при котором значение целевой функции (2.3.3) минимально. Условия транспортной задачи весьма удобно представлять в табличной форме. Таблица 2.3.1 Пункты потребления j и их спрос Вj 1 2 … n Пункт произ- водства i Объем произ- водства Аi В1 В2 … Вn
1
А1
с11
х 11 с12
х 12 … с1n
х 1n
2
А2
с21
х 21 с22
х 22
… с2n
х 2n … … … … … …
m
Аm сm1
х m1 сm2
х m2 … сmn
х mn В левом верхнем углу произвольной клетки (i,j) (i – номер строки, j–номер столбца) стоит показатель транспортных затрат сij, в правом нижнем – значения переменных х ij(план перевозок). Любое решение Х=( х 11, х 12,…, х ij ,…, х mn) системы ограничений (2.3.1) – (2.3.2) назовем распределением поставок. Рассмотрим простейший числовой пример (таб. 2.3.2). Здесь параметры задачи принимают следующие значения: с11 =2, с12 =1, с13 =5, с21 =3, с22 =4, с23 =3, с31 =4, с32 =6, с33=6; А1 =50, А2 =60, А3 =70, В1 =40, В2 =85, В3=55.
124 Таблица 2.3.2 40 85 55 50 2
х 11 1
х 12 5
х 13 60 3
х 21 4
х 22 3 х 23 70 4
х 31 6
х 32 6
х 33 Составим систему уравнений для этого примера. Чтобы объем производства каждого поставщика был реализован, необходимо выполнение баланса по каждой строке таблицы, т.е. х 11 + х 12 + х 13 =
50 х 21 + х 22 + х 23 = 60 (2.3.4) х 31 + х 32 + х 33 = 70 Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса выписываем для каждого столбца таблицы: х 11 + х 21 + х 31 = 40 х 12 + х 22 + х 32 = 85 (2.3.5) х 13 + х 23 + х 33 = 55 Суммарные транспортные затраты F(целевая функция) выражаются через издержки и поставки следующим образом:
F = 2 х 11 + х 12 + 5 х 13 + 3 х 21 +4 х 22 + 3 х 23 +4 х 31 + 6 х 32 + 6 х 33. В этом примере шесть уравнений и девять переменных, система (2.3.4)–(2.3.5) имеет бесчисленное множество решений (допустимых поставок). Вот одно из них: Таблица 2.3.3 40 85 55 50 2
40
1
10
5
0
60 3
0
4
60 3 0
70 4
0
6
15 6
55
Суммарные транспортные затраты для данного распределения:
F = 2×40 +1×10 + 5×0 + 3×0 +4×60 + 3×0 +4×0 + 6×15 + 6×55=750. Всего в этом примере около 3600 только целочисленных решений, а если допустить дробность – то бесконечное множество. Все допустимые решения удовлетворяют системе ограничений, но отличаются друг от друга величиной суммарных транспортных издержек. Вот еще одна допустимая поставка:
125 Таблица 2.3.4 40 85 55 50 2
1
50 5
60 3
40 4
3 20 70 4
6
35 6
35 Суммарные транспортные затраты для данного распределения:
F = 1×50 + 3×40 +3×20 + 6×35 + 6×35=650. Наша задача научиться находить оптимальное решение, т.е. такое, для которого целевая функция имеет наименьшее значение.
Ви переглядаєте статтю (реферат): «Экономико-математическая модель транспортной задачи» з дисципліни «Математична економіка»
