лучшие книги по экономике
Главная страница

Главная

Замовити роботу

Последние поступления

Форум

Создай свою тему

Карта сайта

Обратная связь

Статьи партнёров


Замовити роботу
Книги по
алфавиту

Б
В
Г
Д
Е
Ж
З
И
К
Л
М
Н
О

Математичне програмування

Страницы [ 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 ]

Знак «?» у перших трьох обмеженнях задачі пояснюється тим, що за умовою транспортна задача є відкритою:

У такій ситуації, коли попит менший за пропозицію, частина овочів залишиться в господарствах і фактично буде вивезено мен­ше, ніж зібрано.
Розв’язування. Щоб визначити оптимальний план поставленої задачі, її необхідно збалансувати, тобто звести до закритого типу. Це виконується шляхом уведення додаткового, умовного споживача B5 із попитом B5 = 100 – 90 = 10 т. Вартість перевезення одиниці продукції до умовного споживача дорівнює нулю.
Перший опорний план транспортної задачі побудуємо методом подвійної переваги.

Aj

Bj

ui

B1 = 30

B2= 30

B3= 10

B4= 20

B5= 10

A1= 50

2
30

3
20

4

2

0

u1= –4

A2= 30

5
1

7
–10

1
10

4
0+

0
10

u2= 0

A3= 20

9

4
1  +

3

2
20–

0

u3= –2

vj

v1= 6

v2= 7

v3= 1

v4= 0

v5= 0

 

Перший опорний план є виродженим, і тому в клітинку, наприклад A2B4, поставимо нуль і вважатимемо її заповненою.
Перевірка плану за допомогою потенціалів показує, що він є неоптимальним. Перехід до другого опорного плану виконується шляхом заповнення клітинки A3B2 згідно із побудованим циклом. Зазначену клітинку включено до циклу тому, що в разі кількох однакових найбільших порушень (D21 = D32 = 1) заповнюють таку клітинку таблиці, яка має меншу вартість перевезення одиниці продукції (с32 < c21).
Другий план транспортної задачі наведемо у вигляді таблиці:


Aj

Bj

ui

B1= 30

B2= 30

B3= 10

B4= 20

B5= 10

A1= 50

2
30

3
20

4

2

0

u1= –3

A2= 30

5

7

1
10

4
10

0
10

u2= 0

A3= 20

9

4
10

3

2
10

0

u3= –2

vj

v1= 5

v2= 6

v3= 1

v4= 4

v5= 0

 

Умова оптимальності для цього опорного плану виконується, і тому можна записати:
;
Zmin = 2 ? 30 + 3 ? 20 + 1 ? 10 + 4 ? 10 + 4 ? 10 + 2 ? 10 = 320 ум. од.
Згідно з оптимальним планом потреба магазинів у ранніх овочах задовольняється завдяки повному вивезенню продукції з першого та третього господарств і лише частково — з другого (залишок дорівнює 10 т). У цьому разі загальна вартість усіх перевезень буде найменшою і становитиме 230 ум. од.
Але виявляється, що розглянута транспортна задача має ще один альтернативний оптимальний план. Ознакою цього є виконання умови оптимальності для порожньої клітинки: ui + vj = cij. В останній таблиці це справджується для порожньої клітинки A2B1: u1 + v1 = 0 + 5 = с21 = 5.
Щоб отримати альтернативний оптимальний план, достатньо заповнити зазначену клітинку таблиці, виконавши перерозподіл продукції за таким циклом:

Наведемо транспортну таблицю, що відповідає другому оптимальному плану задачі.

Aj

Bj

ui

B1 = 30

B2 = 30

B3 = 10

B4 = 20

B5 = 10

А1 = 50

2
20

3
30

4

2

0

u1 = –3

A2 = 30

5
10

7

1
10

4
0

0
10

u2 = 0

A3 = 20

9

4

3

2
20

0

u3 = –2

vj

v1 = 5

v2 = 6

v3 = 1

v4 = 4

v5 = 0

 

Тому
;
Zmin = 2 ? 20 + 3 ? 30 + 5 ? 10 + 1 ? 10 + 2 ? 20 = 230 ум. од.

Другий оптимальний план задачі формулюється так. Перевезти з першого господарства 20 т овочів до першого магазину та 30 т — до другого; з другого господарства — 10 т до першого магазину та 10 т овочів до третього, залишаючи невивезеними 10 т, а також з третього господарства до четвертого магазину — 20 т овочів. У цьому разі загальні транспортні витрати становитимуть 230 ум. од. і також будуть найменшими.


Задача 5.3.

Три нафтопереробних заводи А1, А2, А3, із максимальною щоденною продуктивністю відповідно 30, 20, 15 тис. т бензину забезпечують чотири бензосховища B1, B2, B3, B4, потреба яких становить відповідно 10, 20, 25 та 20 тис. т. бензину. Бензин транспортується до бензосховищ за допомогою трубопроводів. Вартість перекачування 1000 т бензину від заводів до сховищ (в умовних одиницях) наведено в таблиці.


Завод

Вартість, ум. од., перекачування 1000 т бензину до сховищ

 

В1

В2

В3

В4

А1

4

5

3

7

А2

7

6

2

5

А3

2

3

9

8

Cформулювати та розв’язати відповідну транспорту задачу з неодмінним виконанням таких умов:
1)  повністю задовольнити попит бензосховища B4;
2) недопостачання бензину до сховища B2 штрафується 5 ум. од. вартості за кожні 1000 т бензину;
3) у зв’язку з виконанням ремонтних робіт на трубопроводі постачання бензину із заводу А1 до сховища B1 тимчасово неможливе.
Розв’язування. Визначимо, до якого типу належить транспортна задача:
,   .
За умовою транспортна задача є відкритою, незбалансованою. Зведення її до закритого типу потребує введення додаткового
фіктивного постачальника А4 з продуктивністю а4 = 75 – 65 = 10 (тисяч тон). Кількість бензину, що «відправляється» фіктивним заводом до бензосховищ, в оптимальному плані означатиме обсяг незадоволеного попиту в цьому пункті призначення. Тому для виконання першої додаткової вимоги задачі необхідно блокувати клітинку фіктивного постачальника А4 та споживача B4, записавши в ній досить високу вартість М. Тоді в оптимальному плані транспортної задачі ця клітинка обов’язково буде незаповненою.
Виконання другої умови задачі забезпечується тим, що в рядку фіктивного постачальника у стовпчику B2 вартість транспортування 1000 т бензину дорівнюватиме 5 ум. од. замість нуля.
Оскільки неможливо транспортувати бензин від заводу А1 до сховища B1, необхідно також блокувати маршрут А1B1. Для цього в зазначеній клітинці замість с11 = 4 записуємо величину М.
З огляду на викладене таблиця для першого плану транспортної задачі має такий вигляд (початковий опорний план побудовано методом апроксимації Фогеля).


Aj

Bj

ui

Різниці для
рядків

B1= 10

B2= 20

B3= 25

B4= 20

 

A1= 30

М

 

5
–15

3
5

7
10+

u1= 0

2  2  2

A2= 20

7

6

2
20

5
1

u2= –1

3  3  3

A3= 15

1
–10

3
5+

9

8

u3= –2

2  5

A4= 10

0
М – 4

5

М – 7

0

М – 4

М

10–

u4= М –7

 

vj

v1= 3

v2= 5

v3= 3

v4= 7

 

 

Різниці для
стовпчиків

6

2
2
1

1
1
1

2
2
2

 

 

Отже, перший опорний план задачі неоптимальний. Найбільше порушення умови оптимальності відповідає порожнім клітинкам А4B1 та А3B3 таблиці. Оскільки обидві вони мають однаковий коефіцієнт с41 = с43 = 0, то для заповнення можна вибрати будь-яку з них, наприклад А4B1. Перехід до другого плану виконується за таким циклом:

При цьому заблокована клітинка А4B4 звільняється.
Подальше розв’язування задачі подано у вигляді таблиць.


Aj

Bj

ui

B1= 10

B2= 20

B3= 25

B4= 20

A1= 30

М

 

5
5

3
+5

7
20–

u1= 0

A2= 20

7

6

2
–20

+   5
1

u2= –1

A3= 15

1
0

3
15

9

8

u3= –2

A4= 10

0
10

5

 

0

 

М

 

u4= –3

vj

v1= 3

v2= 5

v3= 3

v4= 7

 

Aj

Bj

ui

B1= 10

B2= 20

B3= 25

B4= 20

A1= 30

М

 

5
5

3
25

7
М

u1= 0

A2= 20

7

6

2
0

5
20

u2= –1

A3= 15

1
0

3
15

9

8

u3= –2

A4= 10

0
10

5

 

0

 

М

 

u4= –3

vj

v1= 3

v2= 5

v3= 3

v4= 6

 

В останній таблиці маємо оптимальний план транспортної задачі.
Тому
,
Zmin = 5 ? 5 + 5 ? 25 + 5 ? 20 + 3 ? 15 = 245 ум. од.

Страницы [ 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 ]


ВНИМАНИЕ! Содержимое сайта предназначено исключительно для ознакомления, без целей коммерческого использования. Все права принадлежат их законным правообладателям. Любое использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие или полученные в связи с использованием содержимого сайта.
© 2007-2022 BPK Group.