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

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

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

Існують декілька розповсюджених методів знаходження початкового розв'язку транспортної задачі: метод північно-західного кута, метод мінімального елемента, метод подвійного переваги і метод аппроксимації Фогеля. Перші два є найпростішими, але основані на «грубому» переборі матриць перевезень і вартості, тому підходять лише для матриць невеликої розмірності. Метод подвійної переваги відрізняється від методу мінімального елемента лише додаванням умов при виборі наступного елемента для обробки. Метод аппроксимації Фогеля - на даний момент є одним з найефективніших для матриць великої розмірності.

1. Алгоритм методу потенціалів

Алгоритм методу потенціалів складається з попереднього етапу і кінцевого числа однотипних ітерацій. На попередньому етапі будується вихідний опорний план завдання T і складається матриця

,

де и - попередні потенціали, що відповідають вихідного плану .

На кожній ітерації розглядаються і перетворюються дві матриці

и .

Матриця являє собою опорний план завдання T, побудований в результаті k-й ітерації. Матриця складена з оцінок векторів щодо базису плану , тобто

де и - попередні потенціали, що відповідають плану .

Спочатку будемо припускати завдання T невиродженому. Необхідні зауваження щодо виродженого випадку будуть зроблені нижче.

Попередній етап. За допомогою методу північно-західного кута або методу мінімального елемента визначається вихідний опорний план досліджуваного завдання T. Далі, згідно з правилами, викладеним при описі 1-го етапу методу потенціалів, обчислюємо величини , , , і складаємо матрицю

.

Якщо всі елементи ненегативні, то - рішення задачі T. В іншому випадку переходимо до другого етапу, опис якого наводиться нижче. Процес обчислення попередніх потенціалів формулюється наступним чином. Нехай - номери тих стовпців матриці С, які містять - суттєві елементи в 1-му рядку; - номери рядків матриці С, які містять - суттєві елементи у стовпцях з номерами . Якщо множини і для вже визначені, то об'єднує номери тих стовпців матриці С, що не належать , які містять - суттєві елементи в рядках з номерами , а складається з номерів рядків цієї матриці, не включені до і які містять - суттєві елементи у стовпцях з номерами . Утворення множин і виробляється до тих пір, поки процес не переривається отриманням порожньої множини. Якщо , то під будемо розуміти такий елемент безлічі , що - - істотний елемент С. Аналогічно, для визначимо як елемент , при котрому є - істотним елементом С. З опорності плану випливає, що множини , так само як і множини , не пересікаються. Невиродженість плану призводить до того, що об'єднання всіх множин є , а об'єднання всіх множин становить . транспортний матриця ітерація

Вважаємо і обчислюємо

для .

Далі визначаємо

для .

Аналогічно обчислюються для і для і т.д. Таким чином, послідовно визначаються для , для для , для і т.д. до отримання значень всіх попередніх потенціалів.

Кожна ітерація алгоритмів складається з двох етапів. Припустимо, що вже приведено k ітерацій, в результаті яких отримано план і матриця

.

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

Етап 1. На етапі 1 обчислюється матриця , необхідна для перевірки плану на оптимальність. Процес перетворення матриці в матрицю полягає в наступному. Вибираємо від'ємний - істотний елемент матриці . Нехай це (такий елемент обов'язково існує і единий, решта - суттєві елементи - нулі). Виділимо рядок що його містить і через позначимо сукупність - істотних елементів цього рядка, не збігаються с . Потім виділимо стовпці , містять елемент і через позначимо множину - істотних елементів, що лежать в цих стовпцях і відмінних від елементів . Далі виділяються рядки , містять елемент , і аналогічно попередньому вводиться множина . Процес виділення рядків і стовпців матриці продовжується до тих пір, поки чергова множина , скажімо , не опиниться порожнім. Зауважимо, що, оскільки кожен рядок (кожен стовпець) не може бути виділений більше одного разу ( - опорний план!), . Закінчивши виділення ліній (рядків або стовпців) матриці , приступимо до побудови матриці . Для цього величину додамо до всіх виділених стовпчиків і віднімемо з усіх виділених рядків матриці . Очевидно, що матриця, отримана після зазначених перетворень, має вигляд

.

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

Після l - 1 кроків всі ненульові - суттєві елементи виявляються приналежними . Нехай l - непарне (парне) число. Оскільки - порожня безліч, всі - суттєві елементи матриці, отриманої після віднімання (додавання) величини з рядків (до стовпців) елементів , дорівнюють нулю. Отже, величини , задовільняють системі (1.3), відповідно плану .

Отже, - попередні потенціали, відповідні плану , а

.

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

.

Попередні потенціали, що відповідають плану , можна обчислювати і безпосередньо, вирішуючи систему (1.3). Формалізація процесу вирішення цієї системи була приведена при описі попередньо етапу (стосовно вихідного плану ).

Якщо всі елементи матриці ненегативні, - шукане рішення. Якщо ж серед величин є негативні, необхідний перехід до етапу 2.

Етап 2. На етапі 2 проводиться покращення плану . Основою етапу є процес складання ланцюжка з позитивних елементів цього плану. Виберемо найменший елемент матриці , розташований, скажімо, на пересіченні - го рядка і - го стовпця, і позначимо його через . За умовою . Переходимо до пошуку ланцюга з позитивних елементів матриці , що замикається на елементі (вочевидь, =0). з'єднаємо стрілками з усіма позитивними елементами його рядка, сукупність яких позначимо через . Потім кожен з елементів з'єднаємо стрілками з усіма позитивними елементами, розташованими в його стовпці. Сукупність усіх таких елементів позначимо через . Процес утворення множин триває до того часу, поки при деякому p (p - непарне число) серед стовпців, що містять елементи , виявиться стовпчик з номером . Зауважимо, що в силу опорності плану множини , не перетинаються, бо в іншому випадку існувала б замкнутий ланцюжок з ненульових перевезень плану . Ця обставина, а також те, що будь-які два пункти невиродженою задачі T можуть бути з'єднані комунікаціями з ненульовими перевезеннями, слугує доказом існування введеного вище числа . Наразі вже неважко утворити шуканий ланцюжок. від елемента перейдемо по стовпцю до елементу . Від по рядку перейдемо до з'єднаного з ним стрілкою елементу і т.д. Рухаючись таким чином уздовж намічених стрілок по рядках і стовпцях матриці , отримаємо зрештою послідовність позитивних елементів цієї матриці виду

,

утворюючу ланцюжок, який замикається на елементі .

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

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

Елементы матриці , що залишилися після процесу викреслювання, складають шуканий ланцюжок. Побудувавши ланцюжок, легко сформувати новий пла .

Позначимо сукупність пар індексів , через , а множини пар індексів виду , через . Нехай

Новий план визначається згідно з правилом

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

Отже, в результаті ітерації ми перейшли від плану і матриці оцінок

до поліпшеного плану і до нової матриці

.

Зі способу побудови плану випливає, що серед - істотних елементів лише один не дорівнює нулю.

2. Блок-схема алгоритму методу потенціалів

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Висновок

Швидкість побудови опорного плану перевезень є суттєвою для великорозмірних, а тим паче, і багатоіндексних масивів, де товар і транспорт є неоднорідними , а його «якість» значно прискорює побудову оптимального плану. Жоден з методів не може бути оптимальним в усіх випадках, бо в прикладах з малою кількістютю даних, при сучасних технологіях, різниця буде не помітною, а для великих об'ємів даних однозначно доречніше метод аппроксиміляції Фогеля.

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

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

Размещено на Allbest.ru