Составители:
Рубрика:
19 20
Пусть имеется m пунктов производства однородного продукта
(добыча руды в карьерах, производство автобусов, кондитерских
изделий, компьютеров и т.д.) и n пунктов потребления этого про-
дукта. Мощности пунктов производства составляют а
i
),1( mi =
единиц однородного продукта, а потребности каждого j-го пункта
потребления равны
),1( njb
j
= единиц. Известны затраты
ij
c на
перевозку единицы продукта от i-го поставщика j-му потребителю.
Составить такой план перевозок, при котором суммарные затраты
на все перевозки были бы наименьшими. Пусть спрос и предложе-
ние совпадают, т.е. .
∑∑
==
=
m
1i
n
1j
ji
ba Такую транспортную задачу на-
зывают
сбалансированной (закрытой). При этом предполага-
ется, что вся продукция от поставщиков будет вывезена и спрос
каждого из потребителей будет удовлетворен.
Составим математическую модель задачи. Обозначим через
ij
x − количество продукта, перевозимого из i-го пункта произ-
водства в j-й пункт потребления. Тогда матрица:
)11( n,j;m,ixΧ
ij
=== − план перевозок.
Матрицу
),1;,1( njmicC
ij
=== называют матрицей
затрат
(тарифов).
Внесем исходные данные и перевозки
ij
x в транспортную таблицу:
b
j
a
i
b
1
b
2
... b
n
a
1
c
11
x
11
c
12
x
12
... c
1n
x
1n
a
2
c
21
x
21
c
22
x
22
... c
2n
x
2n
...
... ... ... ...
a
m
c
m1
x
m1
c
m2
x
m2
...
c
mn
x
mn
Предположим, что транспортные затраты прямо пропорцио-
нальны количеству перевозимого продукта. Тогда суммарные за-
траты выразятся функцией цели:
,xcxcxс
mnmn12121111
+
⋅
⋅
⋅++
=
Ζ
которую необходимо минимизировать при ограничениях:
iinii
axxx
=
+
⋅
⋅
⋅
+
+
21
(весь продукт из каждого i-го
),1( mi = пункта должен быть выве-
зен полностью),
jmjjj
bxxx
=
+
⋅
⋅
⋅
+
+
21
(спрос каждого j-го
),1( nj = потребителя должен быть полно-
стью удовлетворен).
Из условия задачи следует, что все
).,1;,1(0 njmjx
ij
==≥
Итак, математическая модель
сбалансированной транс-
портной задачи имеет вид:
∑∑
==
→=
m
i
n
j
ijij
xс
11
min
Ζ
при ограничениях:
⎪
⎪
⎩
⎪
⎪
⎨
⎧
==
==
∑
∑
=
=
m
1j
jij
n
1j
iij
),n,1j(bx
),m,1i(ax
),1;,1(0 njmix
ij
==≥ .
1.5. Вопросы для самопроверки
1. Предмет математического программирования.
2.
Основные этапы решения задачи математического про-
граммирования.
3.
Краткая классификация моделей и методов математиче-
ского программирования.
4.
Понятие математической модели.
5.
Постановка задачи оптимального производственного пла-
нирования. Математическая модель.
6.
Задача о смесях. Постановка и математическая модель.
7.
Задача о раскрое. Постановка и математическая модель.
8.
Транспортная задача. Постановка и математическая модель.
9.
Этапы решения задачи математического программирова-
ния.
Пусть имеется m пунктов производства однородного продукта которую необходимо минимизировать при ограничениях:
(добыча руды в карьерах, производство автобусов, кондитерских x i1 + x i 2 + ⋅ ⋅ ⋅ + x in = a i
изделий, компьютеров и т.д.) и n пунктов потребления этого про-
(весь продукт из каждого i-го (i = 1, m) пункта должен быть выве-
дукта. Мощности пунктов производства составляют аi (i = 1, m) зен полностью),
единиц однородного продукта, а потребности каждого j-го пункта x1 j + x 2 j + ⋅ ⋅ ⋅ + x mj = b j
потребления равны b j ( j = 1, n) единиц. Известны затраты cij на
(спрос каждого j-го ( j = 1, n) потребителя должен быть полно-
перевозку единицы продукта от i-го поставщика j-му потребителю. стью удовлетворен).
Составить такой план перевозок, при котором суммарные затраты Из условия задачи следует, что все
на все перевозки были бы наименьшими. Пусть спрос и предложе-
m n
xij ≥ 0 ( j = 1, m ; j = 1, n ).
ние совпадают, т.е. ∑ ai = ∑ b j . Такую транспортную задачу на- Итак, математическая модель сбалансированной транс-
i =1 j =1 портной задачи имеет вид:
зывают сбалансированной (закрытой). При этом предполага- m n
ется, что вся продукция от поставщиков будет вывезена и спрос Ζ = ∑∑ сij xij → min
каждого из потребителей будет удовлетворен. i =1 j =1
Составим математическую модель задачи. Обозначим через при ограничениях:
xij − количество продукта, перевозимого из i-го пункта произ- ⎧ n
⎪⎪ ∑ xij = ai ( i = 1, m ),
водства в j-й пункт потребления. Тогда матрица: j =1
⎨m
Χ = xij (i = 1,m; j = 1,n) − план перевозок. ⎪∑ xij = b j ( j = 1, n ),
⎪⎩ j = 1
Матрицу C = cij (i = 1, m; j = 1, n) называют матрицей
xij ≥ 0 (i = 1, m; j = 1, n) .
затрат (тарифов).
Внесем исходные данные и перевозки xij в транспортную таблицу: 1.5. Вопросы для самопроверки
bj b1 b2 ... bn 1. Предмет математического программирования.
ai 2. Основные этапы решения задачи математического про-
a1 c11 c12 ... c1n граммирования.
x11 x12 x1n 3. Краткая классификация моделей и методов математиче-
a2 c21 c22 ... c2n
x21 x22 x2n ского программирования.
... ... ... ... 4. Понятие математической модели.
... 5. Постановка задачи оптимального производственного пла-
am cm1 cm2 ... cmn нирования. Математическая модель.
xm1 xm2 xmn 6. Задача о смесях. Постановка и математическая модель.
Предположим, что транспортные затраты прямо пропорцио- 7. Задача о раскрое. Постановка и математическая модель.
нальны количеству перевозимого продукта. Тогда суммарные за- 8. Транспортная задача. Постановка и математическая модель.
траты выразятся функцией цели: 9. Этапы решения задачи математического программирова-
Ζ = с11 x11 + c12 x12 + ⋅ ⋅ ⋅ + cmn xmn , ния.
19 20
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
