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

UptoLike

ВУЗ: 

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

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

Рубрика: 

5
мостью и процесс заполнения продолжают до тех пор, пока все запасы не
будут распределены, а потребности удовлетворены.
Найдём план методом наименьших стоимостей:
B
A
40
25
20
50
60
5
4
1
20
2
40
40
4
5
2
25
6
3
10
35
7
35
3 5 4
Начинаем заполнение с клетки со стоимостью равной 1, затем 2 и т.д.
x
13
= min {60, 20} = 20
x
14
= min {60-20, 50} = 40
x
22
= min {40, 25} = 25
x
24
= min {40-25, 50-40} = 10
x
21
= min {40-(25+10), 40} = 5
x
31
= min {35, 40-5} = 35.
Заполненных клеток шесть (3 + 4 – 1 = m+ n – 1).
План ацикличен.
f = 20·1 + 40·2 + 5·4 + 25·2 + 10·3 + 35·7 = 445.
Метод потенциалов.
Для отыскания оптимального плана используем метод потенциалов.
Теорема.
Если план
()
∗
∗
=
ji
xx транспортной задачи является оптимальным, то ему
соответствует система из
m+ n чисел u
i
и v
j
, удовлетворяющих условиям:
u
i
+ v
j
= с
i j
, для 0>
∗
ji
x
u
i
+ v
j
≤
с
i j
, для 0=
∗
ji
x
(
i= 1,2,…., m; j = 1,2,…, n). 
                                                  5


мостью и процесс заполнения продолжают до тех пор, пока все запасы не
будут распределены, а потребности удовлетворены.

   Найдём план методом наименьших стоимостей:


                              B
                                       40             25           20           50
                     A
                                   5              4            1            2
                         60                                        20           40

                                   4              2            6            3
                         40             5             25                        10

                                   7              3            5            4
                         35            35


   Начинаем заполнение с клетки со стоимостью равной 1, затем 2 и т.д.
                                   x13 = min {60, 20} = 20
                                 x14 = min {60-20, 50} = 40
                                   x22 = min {40, 25} = 25
                               x24 = min {40-25, 50-40} = 10
                               x21 = min {40-(25+10), 40} = 5
                                  x31 = min {35, 40-5} = 35.

   Заполненных клеток шесть (3 + 4 – 1 = m+ n – 1).
   План ацикличен.

                   f = 20·1 + 40·2 + 5·4 + 25·2 + 10·3 + 35·7 = 445.

                                       Метод потенциалов.

   Для отыскания оптимального плана используем метод потенциалов.
   Теорема.
               ∗
                     ( )
   Если план x = xi∗j транспортной задачи является оптимальным, то ему
соответствует система из m+ n чисел ui и vj , удовлетворяющих условиям:
                         ui + vj = сi j,   для xi∗j > 0
                                ui + vj ≤ сi j,            для xi∗j = 0
                              (i= 1,2,…., m;               j = 1,2,…, n).

Страницы