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

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

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

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

Нехай є m пунктів зосередження вантажу (або пунктів виробництва) А₁, А₂, ..., А_m, в яких розміщено однорідний вантаж у кількості а₁, а₂, ..., а_m одиниць. Цей вантаж повинен бути доставлений у n пунктів споживання В₁, В₂, ..., В_n з обсягом попиту відповідно b₁, b₂, ...,b_n.Передбачається,що можливе транспортування з кожногопункту постачання до кожного пункту споживання. Задані тривалості транспортування Т_ij на доставку одиниці вантажу з пунктів А_i до

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

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

32

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33

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

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

34

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

35

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

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

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

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

36

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

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

Розв’язок.

Побудуємо початковий опорний план перевезень методоммінімального елементу матриці(таблиця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 хвилин (клітинка А₄В₄). Позначаємо цю клітинку кружечком.

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

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

37

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

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

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

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

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

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

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

38

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

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

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

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

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

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

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

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