Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Рішення транспортної задачі методом потенціалів






 

Початковий опорний план перевіряють на оптимальність за допомогою потенціалів. Відповідно кожному постачальнику Аі ставимо потенціал uі, а кожному споживачеві Вj – vj.

Критерій оптимальності опорного плану транспортної задачі: якщо для деякого опорного плану (хіj) транспортної задачі існують такі числа-потенціали uі і vj, що для базисних клітинок виконуються рівності uі+vjіj, а для небазисних - uі+vj ≤ сіj для всіх , то такий опорний план є оптимальним.

Потенціали опорного плану визначаються з системи uі+vjіj, які записують для всіх заповнених клітинок таблиці транспортної задачі. За допомогою розрахованих потенціалів перевіряють умову оптимальності uі+vj ≤ сіj для незаповнених клітинок таблиці. Якщо хоча б для однієї небазисної клітинки ця умова не виконується, тобто uі+vj > сіj, то поточний план не є оптимальним і переходимо до нового опорного плану.

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

Циклом в транспортній задачі називають замкнуту ламану лінію, сторони якої проходять уздовж рядків і стовпчиків таблиці, і одна з вершин якої знаходиться в небазисній клітинці, для якої порушено умову оптимальності, а всі інші вершини – базисні клітинки.

Перерозподіл продукції в межах циклу здійснюють за такими правилами:

а) кожній вершині циклу приписують певний знак, причому незаповненій клітинці знак " +", а всім іншим почергово " –" і " +";

б) у пусту клітинку заносять менше з чисел, що стоять у клітинках зі знаком " –". Одночасно це число прибавляють до відповідних чисел, що стоять у клітинках зі знаком " +" і віднімають від клітинок, що розміщені у клітинках зі знаком " –".

Отже, клітинка, яка була вільною, стала заповненою, а відповідна клітинка, де знаходилося найменше число (у вершині з " -") стала незаповненою. У результаті такого перерозподілу продукції ми отримаємо новий опорний план транспортної задачі, який знову перевіряємо на оптимальність. Якщо рішення оптимальне, то обчислюємо мінімальне значення цільової функції (мінімальну вартість перевезення всієї продукції), а якщо неоптимальне, то знову будуємо цикл перерахунку і за допомогою зсуву по циклу переходимо до нового опорного плану. Процес повторюють до тих пір, поки не буде отримано оптимальне рішення транспортної задачі. Значення базисних клітинок, які не брали участі в циклі перерахунку, в новій таблиці залишаються без змін. Можуть зустрітися такі види циклів:

Приклад 2. Найти оптимальний план перевезень однорідного вантажу від постачальників А1, А2, А3, А4 із запасами а1=90, а2=85, а3=125, а4=І05 до споживачів В1, В2, В3 з потребами у цьому вантажі b1=110, b2=155, b3=140, який забезпечить мінімальну вартість перевезень вантажу, якщо відома вартість перевезень одиниці вантажу від постачальників до споживачів:

.

Перевіримо, чи є транспортна задача закритою. Обрахуємо:

Так як , то транспортна задача закритого типу.

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

.

 

Вартість перевезень за даним опорним планом буде складати: Z1=3·90+1·20+5·65+7·90+8·35+5·105=270+20+325+630+280+525=2050 гр. од.

Перевіримо, чи є знайдений опорний план оптимальним. Для базисних клітинок мають виконуватися рівності uі+vjіj:

 

Ми маємо систему з 6 рівностей з 7 невідомими. Ця система має багато рішень. Візьмемо однин з невідомих, що дорівнює любому числу, наприклад, u1=0, і знайдемо всі інші потенціали. Знайдені значення потенціалів запишемо до таблиці. Тепер виповнимо перевірку другої умови критерію оптимальності транспортної задачі, а саме: чи виконується для небазисних (незаповнених) кліток нерівності uі+vj ≤ сіj.

Для клітинки (А1В2): v2+u1≤ 6; 7+0> 6, отже нерівність не виконується;

Для клітинки (А1В3): v3+u1≤ 2; 8+0> 2, отже нерівність не виконується;

Для клітинки (А2В3): v3+u2≤ 7; 8+(-2) ≤ 7, отже нерівність виконується;

Для клітинки (А3В1): v1+u3≤ 9; 3+0 ≤ 9, отже нерівність виконується;

Для клітинки (А4В1): v1+u4≤ 4; 3+(-3) ≤ 4, отже нерівність виконується;

Для клітинки (А4В2): v2+u4≤ 3; 7+(-3)> 3, отже нерівність не виконується.

Маємо три клітинки (А1В2), (А1В3) та (А4B2), для яких не виконується нерівність uі+vj≤ сіj, а це означає, що опорний план не є оптимальним. У клітинках (А1В2), (А1В3) та (А4B2) у правому верхньому куті клітинки записуємо у скобках різницю між сумою потенціалів і вартістю перевезення одиниці вантажу окреслених клітинок та обираємо клітинку, для якої ця різниця є найбільшою, так обираємо клітинку (A1B3) і у ній ставимо зірочку (*). Для цієї клітинки будуємо цикл перерахунку на величину = mіn (90; 65; 35) = 35, тобто до чисел, які знаходяться у позитивних вершинах, додаємо 35, а від чисел, що знаходяться у негативних вершинах, віднімаємо 35:

а) до перерахунку б) після перерахунку

 

Всі інші клітинки залишаємо без змін.

 

 

Отримано новий опорний план:

 

Вартість перевезень складе при даному плані:

Перевіряємо план на оптимальність: знову записуємо систему рівнянь, знаходимо все потенціали, заносимо їх значення до таблиці і дивимося, чи виконуються нерівності uі+vj≤ сіj для небазисних клітинок:

v2+u1= 7 + 0 =7 > 6 нерівність не виконується;

v3+u 2 = 2 – 2 = 0 < 7;

v1+u3 = 3 + 0 = 3 < 9

v1+u4 = 3 + 3 = 6 > 4 нерівність не виконується;

v2+u4 = 7 + 3 = 10 > 3 нерівність не виконується.

Таким чином, є ще три клітинки, а саме (A1B2), (A4B1) та (A4B2), для яких ці нерівності не виконуються. Будуємо цикл перерахунку на розмір Ө = mіn (55; 30; 105) = 30 для клітинок (A4B2), так як різниця між сумою потенціалів та вартістю перевезень вантажів для неї є найбільшою (дорівнює 7). Переходимо до наступної таблиці.

Новий опорний план:

Вартість перевезень становить при даному плані:

 

Ще є небазисні клітинки (A3B1), (A3B3) і (A4B1), для яких не виконуються нерівності uі+vj≤ сіj. Тому будуємо цикл перерахунку на величину Ө = mіn (25; 75) = 25 для клітинки (A4B1), так як різниця між сумою потенціалів та вартістю перевезень одиниці вантажу для неї дорівнює 2 (найбільша). Отримаємо таблицю:

 

Новий опорний план:

Загальна вартість перевезень складе:

Так як у клітинці (А3В3) ще порушується друга умова критерію оптимальності транспортної задачі, а саме u3+v3> с33 (7+2> 9), то для цієї клітинки робимо цикл перерахунку на величину Ө = mіn (125; 50) = 50. У результаті отримаємо:

 

Знову обраховуємо всі потенціали та записуємо їх значення до таблиці. Для всіх небазисних клітинок останньої таблиці виконується нерівність uі+vj ≤ сіj, а це означає, що отримано оптимальний план перевезення вантажу:

 

Мінімальна вартість перевезення вантажу складе:

гр. од.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.01 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал