В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія - страница 102

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 

/0    15    0 \ X* = І   20    5    0   І ,

0   0 35

/тіп = 2 • 15 + 2 • 20 + 4 • 5 + 3 • 35 = 30 + 40 + 20 + 105 = 195 гр. од. ► Приклад 5. Розв'язати транспортну задачу, яка визначена таб-

Постачаль­ники

Споживачі

Запа­си

 

Вг

В2

Вз

В4

 

Аг

3 — 25

--2 -

5

+4

1

20

50

 

2 і

5 1

3

1 1

35

5

40

Аз

3 Г

"2~ ~ 20

4

4

20

Потреби

30

25

35

20

110

110

Маємо закриту (збалансовану) транспортну задачу, а тому можна будувати початковий опорний план. Побудуємо його за до­помогою методу мінімальної вартості. У клітинку (2, 3) з наймен­шою вартістю перевезень поміщаємо вантаж 35 од. і виключаємо з

300розгляду стовпчик Вз. Далі у клітинку (1,4) поміщаємо 20 од. ванта­жу - і виключаємо з розгляду стовпчик В4. Наступною заповнюємо клітинку (3, 2) і виключаємо з розгляду рядок Аз. Продовжуючи заповнення клітинок за зростанням вартості перевезень, одержимо початковий опорний план

25  5   0 20

Х0 = (   5    0    35    0   І .

0  20  0 0

Оскільки п + т — 1=4 + 3 1=6 і заповнених клітинок шість, то план невироджений.

Знайдемо потенціали «і, і Є {1, 2, 3}, вз, З Є {1, 2, 3,4}, склавши для заповнених клітинок систему рівнянь

вг «г = 3,   в2 «г = 2,   в4 «г = 1,

вг «2 = 2,   вз «2 = 1,   в2 «з = 2.

Якщо взяти «г = 0, то матимемо «г =0, вг = 3, в2 = 2, в4 = 1, «2 = 1, вз = 2, «з = 0.

Для порожніх клітинок обчислюємо оцінки (із :

(гз = 2 0 4 = —2,    (22 = 2 1 3 = —2,    (24 = 1 1 5 = —5,

(зг = 3 0 3 = 0,    (зз = 2 0 4 = —2,    (з4 = 1 0 4 = —3. Маємо, що всі (із < 0, а це означає, що план оптимальний:

25  5   0 20

Xi = (   5    0    35    0   І ,

0  20  0 0

/тіп = 3 • 25 + 2 • 5 + 1 • 20 + 2 • 5+1 • 35 + 2 • 20 = 190 гр. од.

Оскільки (зг = 0, то оптимальний план не єдиний. Для знаход­ження другого оптимального плану в клітинку (3, 1) треба помістити певний вантаж, зробивши перерозподіл вантажу серед клітинок, які зв'язані з нею циклом

3

5

2

25

4

1

20

2

5

3

1

35

5

3

20

2

4

4

301

Отже, другий оптимальний план має вигляд

5  25  0 20

Х2* = І   5    0    35    0   І .

20  0   0 0

Звідси випливає, що сукупність усіх розв'язків заданої задачі знахо­диться за формулою

X* = XX** + (1 - Х)Х**,   0 < X < 1,

а

/тіп = 190 гр. од. ►

Вправи

1. Знайти опорні плани пропонованих транспортних задач мето­дом північно-західного кута, мінімальної вартості та подвійної пере­ваги

1)

ь3

25

10

13

 

ь3

аі

20

25

30

25

18

4

1

5

; 2)

40

4

2

5

7

10

2

3

6

 

30

6

0

3

1

20

5

7

4

 

30

5

4

2

6

3)

ь3

аі

60

40

40

30

30

 

60

5

2

0

7

3

 

40

6

1

4

2

8

 

70

7

4

3

6

1

 

30

3

5

6

4

2

 

ь3

аі

50

40

10

15

25

30

70

6

3

1

5

7

4

50

8

4

2

4

3

6

20

3

5

5

6

2

4

30

5

1

1

3

6

2

4)

302

2. У пунктах постачання Аі, А2, А3 є однорідний вантаж в обсязі 250, 350, 300 одиниць відповідно: цей вантаж треба перевезти у пунк­ти Ві, В2, В3 і В4 в обсязі відповідно 180, 220, 230 і 270 од. Матриця перевезень одиниці вантажу має вигляд

11 4 15 7

С = І   20   9    7 14

18 9  3 8

Знайти оптимальний план перевезень, тобто такий план, для яко­го сума транспортних витрат є мінімальною.

3. Знайти оптимальний розв'язок транспортної задачі:

 

ь3

аі

80

80

60

80

 

ь3

аі

80

50

50

70

1)

160

5

4

3

4

; 2)

80

4

2

3

1

 

140

3

2

5

5

 

140

6

3

5

6

 

60

1

6

3

2

 

70

3

2

6

3

 

 

 

 

 

 

 

 

 

 

 

 

 

аі

85

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 


Похожие статьи

В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія