Транспортная задача. Филькин Г.В. - 2 стр.

UptoLike

ВУЗ: 

ИСОиП ДГТУ | Шахты

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

Рубрика: 

1
Транспортная задача.
Транспортная задача является задачей линейного программирования,
поэтому ее можно решать универсальный метод решения задач линейного
программирования - симплекс-метод, однако на практике удобно приме-
нять более простые методы.
Пусть некоторый однородный продукт, сосредоточенный у m постав-
щиков A
i
в количестве a
i
(i = 1,2,…, m) единиц соответственно, необходимо
доставить n потребителям B
j
в количестве b
j
(j=1,2,…,n) единиц. Известна
стоимость c
ij
перевозки единицы груза от i-го поставщика к j-му потреби-
телю.
Необходимо составить план перевозок, позволяющий вывезти все гру-
зы, полностью удовлетворить потребности и имеющий минимальную
стоимость.
Обозначим через x
ij
количество единиц груза, запланированных к пере-
возке от i-го поставщика к j-му потребителю; тогда условие задачи можно
записать в виде таблицы:
B
A
B
1
B
2
…
B
n
A
1
c
11
x
11
c
12
x
12
…
c
1n
x
1n
a
1
A
2
c
21
x
21
c
22
x
22
…
c
2n
x
2n
a
2
…
…
…
…
…
…
A
m
c
m1
x
m1
c
m2
x
m2
…
c
mn
x
mn
a
m
b
1
b
2
…
bn
∑
∑
=
ji
ba
Рисунок 1
Стоимость
Z= .min
11
→
∑∑
==
m
i
n
j
ijij
xс
Ограничения получаем из требований, чтобы все грузы были вывезены
и все потребности удовлетворены, т.е. 
                                                        1



                     Транспортная                                 задача.

   Транспортная задача является задачей линейного программирования,
поэтому ее можно решать универсальный метод решения задач линейного
программирования - симплекс-метод, однако на практике удобно приме-
нять более простые методы.
   Пусть некоторый однородный продукт, сосредоточенный у m постав-
щиков Ai в количестве ai (i = 1,2,…, m) единиц соответственно, необходимо
доставить n потребителям Bj в количестве bj (j=1,2,…,n) единиц. Известна
стоимость cij перевозки единицы груза от i-го поставщика к j-му потреби-
телю.
   Необходимо составить план перевозок, позволяющий вывезти все гру-
зы, полностью удовлетворить потребности и имеющий минимальную
стоимость.
   Обозначим через xij количество единиц груза, запланированных к пере-
возке от i-го поставщика к j-му потребителю; тогда условие задачи можно
записать в виде таблицы:


        B            B1                    B2               …            Bn
  A
               c11                   c12                           c1n
  A1                     x11                    x12         …             x1n       a1
               c21                   c22                           c2n
  A2                     x21                    x22         …             x2n       a2

    …                …                     …                …            …          …
               cm1                   cm2                           cmn
  Am                     xm1                    xm2         …             xmn       am
                     b1                    b2               …            bn     ∑ ai = ∑ b j

                                                      Рисунок 1

                               m n
   Стоимость         Z= ∑ ∑ сij xij → min .
                           i =1 j =1


    Ограничения получаем из требований, чтобы все грузы были вывезены
и все потребности удовлетворены, т.е.

Страницы