Відмінності між версіями «Транспортна задача з додатковими умовами»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(Створена сторінка: == Вступ == <br> На практиці в задачах, що пов’язані з перевезеннями, часто доводиться врахов...)
 
 
(не показані 13 проміжних версій 2 учасників)
Рядок 1: Рядок 1:
 
== Вступ ==
 
== Вступ ==
<br> На практиці в задачах, що пов’язані з перевезеннями, часто доводиться враховувати додаткові умови: неможливість здійснення перевезень за окремими маршрутами; необхідність перевезень неоднорідної продукції тощо. Такі умови ускладнюють математичну постановку транспортної задачі та вимагають особли¬вих підходів до її розв’язання.
+
На практиці в задачах, що пов’язані з перевезеннями, часто доводиться враховувати додаткові умови: неможливість здійснення перевезень за окремими маршрутами; необхідність перевезень неоднорідної продукції тощо. Такі умови ускладнюють математичну постановку транспортної задачі та вимагають особли¬вих підходів до її розв’язання.
 
<br>  
 
<br>  
 
== Особливості відкритих транспортних задач з додатковими умовами ==
 
== Особливості відкритих транспортних задач з додатковими умовами ==
<br> Розглянемо кілька особливостей відкритих транспортних задач з додатковими умовами.
+
Розглянемо кілька особливостей відкритих транспортних задач з додатковими умовами.
 
<br> '''1. Додаткова умова заборони перевезень від певного постачальника до певного споживача. '''В такому разі в оптимальному плані відповідні клітини обов’язково мають бути вільними <math>(x_{ij}=0)</math>.
 
<br> '''1. Додаткова умова заборони перевезень від певного постачальника до певного споживача. '''В такому разі в оптимальному плані відповідні клітини обов’язково мають бути вільними <math>(x_{ij}=0)</math>.
<br> Розв’язуючи транспортну задачу з додатковою умовою на заборону окремих постачань, необхідно у відповідних клітинах замінити значення вартостей перевезень одиниці продукції на деяке велике число (ставиться досить велике число М). Оскільки розглянуті вище методи розв’язання транспортних задач уможливлюють організацію перевезень у такий спосіб, що мінімізується загальна вартість витрат на транспортування, то це зумовить виключення з розгляду перевезень з надто великими варто¬стями, що і забезпечить виконання такої додаткової умови.
+
<br> Розв’язуючи транспортну задачу з додатковою умовою на заборону окремих постачань, необхідно у відповідних клітинах замінити значення вартостей перевезень одиниці продукції на деяке велике число (ставиться досить велике число М). Оскільки розглянуті вище методи розв’язання транспортних задач уможливлюють організацію перевезень у такий спосіб, що мінімізується загальна вартість витрат на транспортування, то це зумовить виключення з розгляду перевезень з надто великими вартостями, що і забезпечить виконання такої додаткової умови.
<br> '''2. Додаткова умова перевезення за окремими маршрутами строго визначеного обсягу продукції, тобто виконання обов’яз¬кових постачань. ''' В оптимальному плані відкритої транспортної задачі з такою додатковою умовою клітини відповідних фіктив¬но введених постачальників чи споживачів мають бути віль¬ними.
+
<br> '''2. Додаткова умова перевезення за окремими маршрутами строго визначеного обсягу продукції, тобто виконання обов’язкових постачань. ''' В оптимальному плані відкритої транспортної задачі з такою додатковою умовою клітини відповідних фіктивно введених постачальників чи споживачів мають бути вільними.
 
<br> Розв’язуючи такого типу транспортну задачу, необхідно у відповідних клітинах також збільшити значення вартостей перевезень (ставиться досить велике число М).  
 
<br> Розв’язуючи такого типу транспортну задачу, необхідно у відповідних клітинах також збільшити значення вартостей перевезень (ставиться досить велике число М).  
 
<br> '''3. Додаткова умова необхідності перевезення від і-го постачальника j-му споживачеві не менше <math>k_{ij}</math> одиниць продукції, тобто вводиться додаткове обмеження виду: <math>x_{ij}\ge k_{ij}</math>'''.
 
<br> '''3. Додаткова умова необхідності перевезення від і-го постачальника j-му споживачеві не менше <math>k_{ij}</math> одиниць продукції, тобто вводиться додаткове обмеження виду: <math>x_{ij}\ge k_{ij}</math>'''.
 
<br> Розв’язуючи транспортну задачу з такою додатковою умовою, необхідно змінити початкові умови: обсяг постачання <math>k_{ij}</math> відняти від обсягу запасу і-го постачальника <math>(a_i^' = a_i - k_{ij})</math> та від потреби j-го споживача <math>(b_j^' = b_j - k_{ij})</math>. Знайдений оптимальний план транспортної задачі зі зміненими умовами (де використані значення  <math>a_i^' , b_j^'</math> ) коригується, враховуючи обмеження <math>x_{ij}\ge k_{ij}</math>.
 
<br> Розв’язуючи транспортну задачу з такою додатковою умовою, необхідно змінити початкові умови: обсяг постачання <math>k_{ij}</math> відняти від обсягу запасу і-го постачальника <math>(a_i^' = a_i - k_{ij})</math> та від потреби j-го споживача <math>(b_j^' = b_j - k_{ij})</math>. Знайдений оптимальний план транспортної задачі зі зміненими умовами (де використані значення  <math>a_i^' , b_j^'</math> ) коригується, враховуючи обмеження <math>x_{ij}\ge k_{ij}</math>.
 
<br> '''4. Додаткова умова необхідності перевезення від і-го постачальника j-му споживачеві не більше <math>k_{ij}</math> одиниць продукції, тобто вводиться додаткове обмеження виду: <math>x_{ij}\le k_{ij}</math>'''.
 
<br> '''4. Додаткова умова необхідності перевезення від і-го постачальника j-му споживачеві не більше <math>k_{ij}</math> одиниць продукції, тобто вводиться додаткове обмеження виду: <math>x_{ij}\le k_{ij}</math>'''.
<br> Для виконання такої додаткової умови необхідно в транспорт¬ну таблицю j-го споживача записати двічі. Один раз його потреби визначатимуться величиною <math>k_{ij}</math>, а другий раз — різницею <math>b_j - k_{ij} = b_j^'</math>. Витрати на перевезення одиниці продукції в обох стовпцях повинні бути однаковими за винятком клітини на перетині і-го постачальника і j-го споживача з потребою <math>b_i^'</math>. У цій клітині ставиться досить велике число М. В такій постановці задача розв’язується відомими методами.
+
<br> Для виконання такої додаткової умови необхідно в транспортну таблицю j-го споживача записати двічі. Один раз його потреби визначатимуться величиною <math>k_{ij}</math>, а другий раз — різницею <math>b_j - k_{ij} = b_j^'</math>. Витрати на перевезення одиниці продукції в обох стовпцях повинні бути однаковими за винятком клітини на перетині і-го постачальника і j-го споживача з потребою <math>b_i^'</math>. У цій клітині ставиться досить велике число М. В такій постановці задача розв’язується відомими методами.
 
<br> 5. На практиці часто потрібно '''оптимальний план перевезень неоднорідної продукції, тобто розв’язати багатопродуктову задачу.''' Її математична модель має такий вигляд:
 
<br> 5. На практиці часто потрібно '''оптимальний план перевезень неоднорідної продукції, тобто розв’язати багатопродуктову задачу.''' Її математична модель має такий вигляд:
<br> [[Файл:Формула_1.JPG]]
+
<br>[[Файл:Qwerty.jpg]]
 
<br> де k — індекс виду продукції, що необхідно перевезти.
 
<br> де k — індекс виду продукції, що необхідно перевезти.
 
<br> Розв’язуючи багатопродуктову транспортну задачу, потрібно заблокувати ті клітини, які зв’язують постачальників і споживачів щодо постачань різної продукції. Таке блокування здійснюється введенням досить високих вартостей перевезень одиниці продукції (великого числа М), але слід зауважити, що наявність заблокованих клітин може призвести до неможливості розв’язання задачі. Тому в такому разі необхідно перевіряти, чи є достатня кількість незаблокованих перевезень для побудови опорного плану задачі, який повинен містити  додатну змінну.  
 
<br> Розв’язуючи багатопродуктову транспортну задачу, потрібно заблокувати ті клітини, які зв’язують постачальників і споживачів щодо постачань різної продукції. Таке блокування здійснюється введенням досить високих вартостей перевезень одиниці продукції (великого числа М), але слід зауважити, що наявність заблокованих клітин може призвести до неможливості розв’язання задачі. Тому в такому разі необхідно перевіряти, чи є достатня кількість незаблокованих перевезень для побудови опорного плану задачі, який повинен містити  додатну змінну.  
 
<br>
 
<br>
<br> == Приклад ==
+
== Приклад ==
<br>
+
Три нафтопереробних заводи А1, А2 та А3 із максимальною щоденною продуктивністю відповідно 30, 20 і 15 тис. т бензину забезпечують чотири бензосховища B1, B2, B3, B4, щоденна потреба яких становить відповідно 10, 20, 25 та 20 тис. т. бензину. Бензин постачається до бензосховищ трубопроводами. Вартості перекачування 1000 т бензину від заводів до сховищ (в умовних одиницях) наведені в табл. 1.
<br>  Три нафтопереробних заводи А1, А2 та А3 із максимальною щоденною продуктивністю відповід¬но 30, 20 і 15 тис. т бензину забезпечують чотири бензосховища B1, B2, B3, B4, щоденна потреба яких становить відповідно 10, 20, 25 та 20 тис. т. бензину. Бензин постачається до бензосховищ трубопроводами. Вартості перекачування 1000 т бензину від заводів до сховищ (в умовних одиницях) наведені в табл. 1.
+
<br>[[Файл:Таблица 1.jpg]]
<br>
+
<br>
+
<br>
+
 
<br> Сформулювати та розв’язати відповідну транспорту задачу з неодмінним виконанням таких умов:
 
<br> Сформулювати та розв’язати відповідну транспорту задачу з неодмінним виконанням таких умов:
 
<br> 1) повністю задовольнити потребу бензосховища B4;
 
<br> 1) повністю задовольнити потребу бензосховища B4;
Рядок 28: Рядок 25:
 
<br> 3) у зв’язку з виконанням ремонтних робіт на трубопроводі постачання бензину із заводу А1 до сховища B1 тимчасово неможливе.
 
<br> 3) у зв’язку з виконанням ремонтних робіт на трубопроводі постачання бензину із заводу А1 до сховища B1 тимчасово неможливе.
 
<br>
 
<br>
<br> ''Розв’язання.'' Визначимо, до якого типу належить транспортна задача:
+
<br> ''Розв’язання.'' Визначимо, до якого типу належить транспортна задача:[[Файл:Формула 2.jpg]]
 
<br>
 
<br>
<br>
+
За умовою ця транспортна задача є відкритою, незбалансованою. Зведення її до закритого типу потребує введення додаткового фіктивного постачальника А4 з продуктивністю а4 = 75 – 65 = 10 (тисяч тонн). Кількість бензину, що «відправляється» фіктивним заводом до бензосховищ, в оптимальному плані означатиме обсяг незадоволеного попиту в цьому пункті призначення. Тому для виконання першої додаткової вимоги задачі необхідно заблокувати клітинку фіктивного постачальника А4 та споживача B4, записавши в ній досить високу вартість перевезення М. Тоді можна бути впевненим, що в оптимальному плані транспортної задачі ця клітинка обов’язково буде незаповненою.
<br>
+
<br> За умовою ця транспортна задача є відкритою, незбалансованою. Зведення її до закритого типу потребує введення додаткового фіктивного постачальника А4 з продуктивністю а4 = 75 – 65 = 10 (тисяч тонн). Кількість бензину, що «відправляється» фіктивним заводом до бензосховищ, в оптимальному плані означатиме обсяг незадоволеного попиту в цьому пункті призначення. Тому для виконання першої додаткової вимоги задачі необхідно заблокувати клітинку фіктивного постачальника А4 та споживача B4, записавши в ній досить високу вартість перевезення М. Тоді можна бути впевненим, що в оптимальному плані транспортної задачі ця клітинка обов’язково буде незаповненою.
+
 
<br> Виконання другої умови задачі забезпечується тим, що в рядку фіктивного постачальника у стовпчику B2 вартість транспортування 1000 т бензину дорівнюватиме 5 ум. од. замість нуля.
 
<br> Виконання другої умови задачі забезпечується тим, що в рядку фіктивного постачальника у стовпчику B2 вартість транспортування 1000 т бензину дорівнюватиме 5 ум. од. замість нуля.
 
<br> Оскільки неможливо транспортувати бензин від заводу А1 до сховища B1, то необхідно також заблокувати маршрут А1B1. Для цього в зазначеній клітинці замість С11 = 4 записуємо величину М.
 
<br> Оскільки неможливо транспортувати бензин від заводу А1 до сховища B1, то необхідно також заблокувати маршрут А1B1. Для цього в зазначеній клітинці замість С11 = 4 записуємо величину М.
 
<br> З огляду на викладене табл. 2 з першим планом транспортної задачі має такий вигляд (початковий опорний план побудовано методом апроксимації Фогеля):  
 
<br> З огляду на викладене табл. 2 з першим планом транспортної задачі має такий вигляд (початковий опорний план побудовано методом апроксимації Фогеля):  
<br>  
+
<br> [[Файл:Таблица 2.jpg]]
<br>
+
 
<br> Отже, перший опорний план задачі неоптимальний. Найбільше порушення умови оптимальності відповідає порожнім клітинкам А4B1 та А4B3 таблиці. Оскільки обидві вони мають однакові коефіцієнти С41 = С43 = 0, то для заповнення можна вибрати будь-яку з них, наприклад, А4B1. Перехід до другого плану виконується за таким циклом:
 
<br> Отже, перший опорний план задачі неоптимальний. Найбільше порушення умови оптимальності відповідає порожнім клітинкам А4B1 та А4B3 таблиці. Оскільки обидві вони мають однакові коефіцієнти С41 = С43 = 0, то для заповнення можна вибрати будь-яку з них, наприклад, А4B1. Перехід до другого плану виконується за таким циклом:
<br>  
+
<br>[[Файл:Цикл.jpg]]
<br>
+
 
<br> Після цього кроку заблокована клітинка А4B4 стає порожньою.  
 
<br> Після цього кроку заблокована клітинка А4B4 стає порожньою.  
 
Дальше розв’язування задачі подано у вигляді табл. 3 та табл. 4
 
Дальше розв’язування задачі подано у вигляді табл. 3 та табл. 4
<br>
+
<br>[[Файл:Таблици 3,4.jpg]]
<br>  
+
<br>[[Файл:Финиш!.jpg]]
<br>
+
== Література ==
<br>
+
http://fingal.com.ua/content/view/463/76/1/1/ ,
<br>
+
<br> http://uk.wikipedia.org/wiki/Транспортна_задача
<br>
+
<br>
+
<br>
+

Поточна версія на 22:28, 10 травня 2012

Вступ

На практиці в задачах, що пов’язані з перевезеннями, часто доводиться враховувати додаткові умови: неможливість здійснення перевезень за окремими маршрутами; необхідність перевезень неоднорідної продукції тощо. Такі умови ускладнюють математичну постановку транспортної задачі та вимагають особли¬вих підходів до її розв’язання.

Особливості відкритих транспортних задач з додатковими умовами

Розглянемо кілька особливостей відкритих транспортних задач з додатковими умовами.
1. Додаткова умова заборони перевезень від певного постачальника до певного споживача. В такому разі в оптимальному плані відповідні клітини обов’язково мають бути вільними Неможливо розібрати вираз (невідома помилка): (x_{ij}=0) .
Розв’язуючи транспортну задачу з додатковою умовою на заборону окремих постачань, необхідно у відповідних клітинах замінити значення вартостей перевезень одиниці продукції на деяке велике число (ставиться досить велике число М). Оскільки розглянуті вище методи розв’язання транспортних задач уможливлюють організацію перевезень у такий спосіб, що мінімізується загальна вартість витрат на транспортування, то це зумовить виключення з розгляду перевезень з надто великими вартостями, що і забезпечить виконання такої додаткової умови.
2. Додаткова умова перевезення за окремими маршрутами строго визначеного обсягу продукції, тобто виконання обов’язкових постачань. В оптимальному плані відкритої транспортної задачі з такою додатковою умовою клітини відповідних фіктивно введених постачальників чи споживачів мають бути вільними.
Розв’язуючи такого типу транспортну задачу, необхідно у відповідних клітинах також збільшити значення вартостей перевезень (ставиться досить велике число М).
3. Додаткова умова необхідності перевезення від і-го постачальника j-му споживачеві не менше Неможливо розібрати вираз (невідома помилка): k_{ij}

одиниць продукції, тобто вводиться додаткове обмеження виду: Неможливо розібрати вираз (невідома помилка): x_{ij}\ge k_{ij}

.
Розв’язуючи транспортну задачу з такою додатковою умовою, необхідно змінити початкові умови: обсяг постачання Неможливо розібрати вираз (невідома помилка): k_{ij}

відняти від обсягу запасу і-го постачальника Неможливо розібрати вираз (невідома помилка): (a_i^' = a_i - k_{ij})
та від потреби j-го споживача Неможливо розібрати вираз (невідома помилка): (b_j^' = b_j - k_{ij})

. Знайдений оптимальний план транспортної задачі зі зміненими умовами (де використані значення Неможливо розібрати вираз (невідома помилка): a_i^' , b_j^'

) коригується, враховуючи обмеження Неможливо розібрати вираз (невідома помилка): x_{ij}\ge k_{ij}

.
4. Додаткова умова необхідності перевезення від і-го постачальника j-му споживачеві не більше Неможливо розібрати вираз (невідома помилка): k_{ij}

одиниць продукції, тобто вводиться додаткове обмеження виду: Неможливо розібрати вираз (невідома помилка): x_{ij}\le k_{ij}

.
Для виконання такої додаткової умови необхідно в транспортну таблицю j-го споживача записати двічі. Один раз його потреби визначатимуться величиною Неможливо розібрати вираз (невідома помилка): k_{ij} , а другий раз — різницею Неможливо розібрати вираз (невідома помилка): b_j - k_{ij} = b_j^' . Витрати на перевезення одиниці продукції в обох стовпцях повинні бути однаковими за винятком клітини на перетині і-го постачальника і j-го споживача з потребою Неможливо розібрати вираз (невідома помилка): b_i^' . У цій клітині ставиться досить велике число М. В такій постановці задача розв’язується відомими методами.
5. На практиці часто потрібно оптимальний план перевезень неоднорідної продукції, тобто розв’язати багатопродуктову задачу. Її математична модель має такий вигляд:
Qwerty.jpg
де k — індекс виду продукції, що необхідно перевезти.
Розв’язуючи багатопродуктову транспортну задачу, потрібно заблокувати ті клітини, які зв’язують постачальників і споживачів щодо постачань різної продукції. Таке блокування здійснюється введенням досить високих вартостей перевезень одиниці продукції (великого числа М), але слід зауважити, що наявність заблокованих клітин може призвести до неможливості розв’язання задачі. Тому в такому разі необхідно перевіряти, чи є достатня кількість незаблокованих перевезень для побудови опорного плану задачі, який повинен містити додатну змінну.

Приклад

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

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

Література

http://fingal.com.ua/content/view/463/76/1/1/ ,
http://uk.wikipedia.org/wiki/Транспортна_задача