Студопедия

КАТЕГОРИИ:

АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ТРАНСПОРТНА ЗАДАЧА ЗА КРИТЕРІЄМ ЧАСУ НА ПЕРЕВЕЗЕННЯ




 

Мета заняття:вивчення методу потенціалів для рішеннятранспортної задачі за критерієм часу на перевезення.

 

Стисла теоретична довідка

 

При перевезеннях вантажів, що швидко псуються, та деяких будівельних матеріалів виникає необхідність доставити вантаж у найбільш стислий термін. Математична постановка транспортної задачі за критерієм часу полягає у наступному.

 

Нехай є m пунктів зосередження вантажу (або пунктів виробництва) А1, А2, ..., Аm, в яких розміщено однорідний вантаж у кількості а1, а2, ..., аm одиниць. Цей вантаж повинен бути доставлений у n пунктів споживання В1, В2, ..., Вn з обсягом попиту відповідно b1, b2, ...,bn.Передбачається,що можливе транспортування з кожногопункту постачання до кожного пункту споживання. Задані тривалості транспортування Тij на доставку одиниці вантажу з пунктів Аi до

 

пунктів Вj( i=1, m ; j=1, n ).

 

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

 

32

 

а) запаси кожного постачальника повинні бути повністю вивезені; б) попит всіх пунктів споживання повинен бути задовільнений

 

за рахунок розподілу всього запасу вантажів, тобто

 

m n

ai =bj ;

i =1 j =1

 

в) мінімізувати максимальну тривалість транспортування вантажу. Умови транспортної задачі подають у вигляді таблиці, що аналогічна таблиці вихідних даних транспортної задачі лінійного програмування за критерієм вартості. У правих верхніх кутах клітинок вказується тривалість

 

транспортування вантажу між відповідними пунктами.

 

Поставлена задача не є задачею лінійного програмування, а є задачею на пошук мінімаксу. При її рішенні допустимим є складання планів, що є опорними і не опорними, виродженими і не виродженими.

 

Алгоритм рішення задачі полягає у виконанні наступних дій: а) скласти початковий план перевезень (методом північно-

західного кута, мінімальної вартості чи подвійної переваги); б) найти завантажену клітинку з максимальним значенням

тривалості перевезень. Обвести це значення кружечком. Виключити з подальшого аналізу порожні клітинки матриці, де значення тривалості перевезень перевищує це значення, проставляючи у цих клітинках хрестики;

 

в) побудувати розвантажувальний контур. Розвантажувальний контур є замкненим контуром, для якого виконуються наступні умови:

- до його вершин входять клітинки, не позначені хрестиком;

 

- у вершинах циклу по черзі проставляються знаки “+” та “–“, починаючи з клітинки з кружечком, в якій проставляється знак “–“;

- клітинки, позначені знаком “+”, є завантаженими;

г) визначити, чи є завантаження клітинки з кружечком найменшим у порівнянні з завантаженням клітинок , позначених у розвантажувальному контурі знаком “–”. Якщо воно є найменшим, то значення цього завантаження відняти від завантажень клітинок, позначених знаком “–“ та додати до завантажень клітинок, позначених знаком “+“.

 

Дії алгоритму повторюють, доки не буде отримане оптимальне рішення задачі (незмога побудувати розвантажувальний контур).

 

33

 

Зміст практичного заняття та вихідні дані до його виконання

 

Скласти оптимальний план перевезень бетону з пунктів виробництва (А1А5) до будівництв (В1В5), що забезпечує мінімальну тривалість виконання перевезень. Обсяги виробництва бетону та потреба у ньому будівництв по варіантах задані в таблицях 4.1–4.2. Варіанти матриці тривалостей транспортування між пунктами виробництва бетону та будівництвами наведені у таблицях 4.4–4.7.

 

 

Таблиця 4.1 – Обсяги виробництва бетону, т

       
Вар. Варіант матриці  

Обсяги виробництва бетону, т

 
  тривалостей А1   А2   А3 А4   А5
1 1 20   15   15 -   -
2 2 12   10   18 15   10
3 3 30   28   22 -   -
4 4 18   25   10 15   9
5 1 25   20   15 -   -
6 2 14   18   12 13   20
7 3 18   12   13 13   13
8 4 40   25   35 -   -
9 1 45   13   28 35   -
10 2 14   16   13 20   17
11 3 15   20   15 -   -
12 4 6   12   18 27   -
13 1 14   11   6 12   18
14 2 28   30   22 -   -
15 3 19   24   17 15   -
16 4 8   7   12 6   17
17 1 15   25   20 -   -
18 2 12   18   17 11   -
19 3 18   7   29 14   12
20 4 25   40   35 -   -
21 1 9   14   12 22   -
22 2 55   17   14 15   12
23 3 28   22   30 -   -
24 4 10   28   18 12   -
25 1 12   11   13 16   29
26 2 14   30   45 -   -
27 3 36   25   23 33   -
28 4 9   13   14 14   19
29 1 42   8   60 -   -
30 2 6   10   33 35   -

 

34

 

Таблиця 4.2 – Потреба у бетоні будівництв

 

Варіант  

Потреба у бетоні будівництв, т

 
  В1   В2 В3 В4   В5
1 9   10 7 13   11
2 17   20 10 18   -
3 18   14 19 12   17
4 20   10 14 18   15
5 19   12 9 10   10
6 18   21 16 22   -
7 10   13 16 19   11
8 20   17 23 22   18
9 26   39 23 33   -
10 13   7 18 16   26
11 16   7 9 8   10
12 18   9 25 6   5
13 15   10 18 9   9
14 17   12 19 14   18
15 10   13 25 27   -
16 10   10 9 13   8
17 19   12 9 10   10
18 14   10 8 26   -
19 12   15 11 9   33
20 30   16 20 18   16
21 11   9 16 21   -
22 18   23 25 26   21
23 19   14 18 12   17
24 11   9 15 33   -
25 14   13 17 9   28
26 20   20 20 20   9
27 25   22 29 41   -
28 12   10 7 30   10
29 28   30 24 8   20
30 31   13 8 10   22

 

35

 

Таблиця 4.3 – Матриця тривалостей транспортування, хв. (варіант 1)

 

Кар’єри

   

Підприємства

     

В1

В2

 

В3

 

В4

В5

 
       
А1 12 15   21   14 17  
А2 14 8   15   11 21  
А3 19 16   26   12 20  
А4 15 11   16   19 18  
А5 13 10   12   20 16  

 

Таблиця 4.4 – Матриця тривалостей транспортування, хв. (варіант 2)

 

Кар’єри

   

Підприємства

     

В1

В2

 

В3

 

В4

В5

 
       
А1 13 9   5   11 17  
А2 14 5   12   14 22  
А3 20 17   13   18 21  
А4 13 15   11   13 21  
А5 12 21   9   10 16  

 

Таблиця 4.5 – Матриця тривалостей транспортування, хв. (варіант 3)

 

Кар’єри

   

Підприємства

     

В1

В2

 

В3

 

В4

В5

 
       
А1 18 12   7   18 7  
А2 35 14   12   15 13  
А3 30 16   11   25 15  
А4 19 15   35   20 7  
А5 15 35   12   11 6  

 

Таблиця 4.6 – Матриця тривалостей транспортування, хв.(варіант 4)

 

Кар’єри

   

Підприємства

     

В1

В2

 

В3

 

В4

В5

 
       
А1 12 16   21   19 32  
А2 4 4   9   5 24  
А3 3 8   14   10 26  
А4 24 33   36   34 49  
А5 9 25   30   20 31  

 

36

 

Приклад виконання завдання

 

Розглянемо приклад виконання завдання за вихідних даних, заданих у таблиці

 

  В1 В2 В3 В4   Запас  

А1

9 3 9   10

9

 
           

А2

8 4 8   12

5

 
           

А3

5 5 10   14

2

 
           

А4

7 8 11   11

9

 
           
Потреба 5 10 7 3      

 

Розв’язок.

 

Побудуємо початковий опорний план перевезень методоммінімального елементу матриці(таблиця4.7).

 

 

Таблиця 4.7 – Початковий опорний план задачі

В1   В2  

В3

В4    

А1

  9

– 8

3

1

9

+

10  
           
А2   8   4 5 8 × 12  
А3 2 5   5   10 × 14  

А4

5

7

+

8

1

11

– 3

12  
         
Потреба 7   8   7   3    

 

Запас

 

9

 

5

 

2

 

9

 

 

Максимальна тривалість перевезень за цим планом складає 12 хвилин (клітинка А4В4). Позначаємо цю клітинку кружечком.

 

Виключаємо з розгляду всі клітинки, що мають тривалість транспортування більше 12 хвилин (позначаємо хрестиками).

Відшукуємо розвантажувальний контур, починаючи з клітинки з кружечком таким чином (у нашому випадку це контур А4В4 – А1В4 – А4В2 – А4В2) . Позначаємо вершини контуру знаками “–“ та “+”, починаючи з клітинки з кружечком. У правильно побудованому контурі повинні виконуватись умова: завантаження у клітинці з кружечком повинно бути найменшим з усіх завантажень у клітинках, позначених знаком “–“. Зауважимо, що не висувається вимоги щодо знаходження вершин контуру тільки у завантажених клітинках (у нашому випадку дві клітинки контуру є порожніми).

 

37

 

Додаємо значення завантаження клітинки з кружечком до завантажень у клітинках, позначених знаком “+” та віднімаємо з завантажень у клітинках, позначених знаком “–“. Отримаємо поліпшений план (таблиця 4.8).

 

Таблиця 4.8 – Поліпшений план задачі (2 ітерація)

 

  В1   В2   В3   В4   Запас  

А1

  9

5

3

1

9

3

10

9

 
           
А2   8   4 5 8

×12

5  
А3 – 2 5   5 + 10

×14

2  
А4 + 5 7

3 8

– 1 11

×12

9  
Потреба 7   8   7   3      

Максимальна тривалість транспортування у отриманому плані складає 11 хвилин (клітинка А4В3). Зауважимо, що після такого перетворення план задачі став виродженим (кількість завантажених клітинок дорівнює 8).

 

Позначаємо знаком “×” всі клітинки, що мають тривалість транспортування більше ніж 11.

Позначаємо клітинку А4В3 кружечком. Будуємо розвантажувальний контур А4В3 – А3В3 – А4В1 – А4В1. У вершинах контуру додаємо одиницю до завантажень клітинок, позначених знаком “+” та віднімаємо одиницю від завантажень клітинок, позначених знаком “–“. Отримуємо наступний план задачі (таблиця 4.9).

 

Таблиця 4.9 – Поліпшений план задачі (3 ітерація)

 

  В1   В2   В3   В4   Запас  

А1

  9

5

3

1

9

3

10

9

 
           
А2   8   4 5 8 × 12 5  
А3 1 5   5 1 10 × 14 2  
А4 6 7

38

×11

×12

9  
Потреба 7   8   7   3      

 

 

Максимальний час транспортування за цим планом складає 10 хвилин (клітинки А1В4 та А3В3). Виключаємо з розгляду всі клітинки, що мають тривалість транспортування більше ніж 10.

 

38

 

На цьому рішення припиняється, оскільки немає можливості побудувати розвантажувальний контур перерахунку (всі клітинки стовпчика А1В4 , що містить максимальну тривалість транспортування, позначені хрестиком).

 

Остаточно, оптимальний план забезпечує мінімальну тривалість транспортування бетону у 10 хвилин.

 


Контрольні запитання

 

1. Дайте формулювання транспортної задачі за критерієм часу.

 

2. Викладіть алгоритм покращення плану транспортної задачі за критерієм часу.

3. Яким умовам повинен відповідати правильно побудований розвантажувальний контур ?

4. Яка ознака оптимальності плану транспортної задачі за критерієм часу ?

 

 

САМОСТІЙНА РОБОТА №5

 










Последнее изменение этой страницы: 2018-04-12; просмотров: 473.

stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда...