РЕФЕРАТ
з дисципліни МАТЕМАТИЧНІ ОСНОВИ ПРОГРАМУВАННЯ
на тему: В«Метод потенціалів для вирішення транспортної задачіВ»
Москва, 2010
1. Рішення транспортної задачі
Так як транспортна задача є задачею лінійного програмування, то основні етапи її рішення будуть такими:
Iетап. Знаходження початкового допустимого рішення.
IIетап. Виділення з небазисних змінних вводиться в базис змінної (метод потенціалів). Якщо все небазисних змінні задовольняють умові оптимальності, то слід закінчити обчислення, в іншому випадку - перейти до III етапу.
IIIетап. Вибір виведеної з базису змінної (використовуючи умови допустимості) із числа змінних поточного базису; потім перебування нового базисного рішення і повернення до II етапу.
Для кращого розуміння методу потенціалів, розглянемо докладніше всі етапи розв'язання транспортної задачі, враховуючи її специфіку.
I етап. Визначення початкового допустимого рішення
Для збалансованої транспортної задачі існує тільки m + n - 1 незалежних рівнянь. Таким чином, початкове базисне допустиме рішення повинно мати m + n-1 базисних змінних.
Початкове базисне рішення транспортної задачі отримують безпосередньо з транспортної таблиці. Для цього можна використовувати три процедури.
1. Правило "Північно-західного кута"
При знаходженні опорного плану транспортної задачі методом "північно-західного кута" на кожному кроці розглядають перший з решти пунктів відправлення і перший з решти пунктів призначення. Заповнення транспортної таблиці починається з лівого верхнього кута (Північно-західного), рухаючись далі по рядку вправо або по стовпцю вниз (Збільшення i, збільшення j). Змінної Х 11 приписують максимальне значення, що допускається обмеженнями на попит і запаси.
Після цього викреслюють відповідний стовпець або рядок, фіксуючи цим, що інші змінні викресленого стовпця (рядки) покладаються рівними нулю. Якщо обмеження виконуються одночасно, то можна викреслити або рядок, або стовпець. Процес завершується тоді, коли буде присвоєно значення змінної х min .
Вихідний опорний план, побудований за правилом "Північно-західного кута", зазвичай виявляється вельми далеким від оптимального, так як при його формуванні не враховується вартість перевезень (Величина з ij ). Більш досконалим правилом є правило "Мінімального елемента".
2.Право "мінімального елемента"
У методі "північно-західного кута" на кожному кроці потреба першого з решти пунктів призначення задовольняється за рахунок запасів першого з решти пунктів відправлення. Очевидно, що вибір пунктів призначення і відправлення доцільно виробляти, орієнтуючись на вартість перевезень, а саме на кожному кроці слід вибирати будь-яку клітку, що відповідає мінімальним тарифом (якщо таких клітин кілька, то слід вибирати будь-яку з них), і розглядати пункти призначення і відправлення, відповідні обраної клітці.
Правило "мінімального елемента" полягає в тому, щоб перевозити максимально можливі обсяги з пунктів відправлення маршрутами мінімальної вартості. Заповнення таблиці починаємо з клітини, якій відповідає найменша вартість перевезення (елемент c ij ) з усієї таблиці. Змінної цієї клітини х ij присвоюється максимально можливе значення з урахуванням обмежень. Потім залишок по стовпцю або рядку поміщається в клітку того ж стовпця або рядка, якій відповідає наступне за величиною значення з ij і т. д. Іншими словами, послідовність заповнення клітин визначається за величиною з ij , а поміщається в цих клітинах величина х ij така ж, як і в правилі "північно-західного кута ".
3.Метод апроксимації Фогеля.
При визначенні оптимального плану транспортної задачі методом апроксимації Фогеля на кожній ітерації по всіх стовпцях і по всіх рядках знаходять різницю між двома записаними в них мінімальними тарифами. Ці різниці записують у спеціально відведених для цього рядку і стовпці умов задачі. Серед зазначених різниць вибирають максимальну. В рядку (чи стовпці), якої дана різниця відповідає, визначають мінімальний тариф. Клітку, в якій він записаний, заповнюють на даній ітерації.
Цей метод дає найкраще початкове наближення, часто виявляється оптимальним планом.
Алгоритм вирішення транспортної задачі методом апроксимації Фогеля наступний:
I етап. Визначення початкового допустимого плану.
1. Для кожного рядка таблиці необхідно впорядкувати елементи вартості перевезень c ij по зростанню. Визначити величину "Штрафу" рядки як різниця значень другого і першого елемента в ранжируваному ряду.
2. Для кожного стовпця таблиці необхідно впорядкувати елементи вартості перевезень c ij по зростанню. Далі необхідно визначити величину штрафу стовпця.
3. Визначити рядок (або стовпець), що має (має) найбільший штраф за всіма штрафам рядків і стовпців, а в ній (в ньому) - елемент з мінімальною величиною вартості перевезень з ij . Зафіксувати індекси (i, j) цього елемента.
4. Присвоїти найбільшу значення з допустимих (з урахуванням обмежень) змінної х ij , індекси якої відповідають кроку 3.
5. Скорегувати величини а i і b j і викреслити рядок i, якщо а i = 0, або стовпець j, якщо b j = 0.
6. Перевірити, чи всі величини а i і b j . дорівнюють нулю, якщо так, то закінчити обчислення; в Інакше взяти в якості вихідної частину, що залишилася таблиці і перейти до кроку 3.
Як правило, застосування методу апроксимації Фогеля дозволяє отримати або опорний план, близький до оптимального, або сам оптимальний план.
II етап. Визначення вводиться в базис змінної ("метод потенціалів").
Відзначимо, що "метод потенціалів" еквівалентний принципом рішення задачі лінійного програмування і використання умови оптимальності в симплекс-методі. Спочатку знаходять опорний план транспортної задачі, а потім його покращують до отримання "оптимального плану ". Зміст "методу потенціалів" полягає в наступному:
1. Кожному рядку i і стовпцю j транспортної таблиці ставиться у відповідність числа u i і v j , звані потенціалами. Вони повинні для кожної базисної змінної х ij поточного рішення задовольняти умові u i + v j = з ij . Ці умови призводять до системи, що складається з m + N - 1 рівнянь (так як є всього m + N - 1 базис-змінних), в яких фігурують m + N невідомих. Значення потенціалів визначають з цієї системи рівнянь, надаючи одному з них довільне значення (наприклад, u i = 0).
2. Визначаються оцінки c ij для небазисних змінних відповідно до співвідношенням:
з ij = u i + v j - з ij
3. Якщо всі оцінки з ij негативні, то знайдене рішення оптимальне, в Інакше необхідно визначити нову вводимую в базис змінну.
4. Вводиться в базис змінної є небазисной змінна, яка має найбільшу позитивну оцінку з ij .
Найбільш ефективним методом визначення введеної змінної є метод диференціальних рент. Якщо при визначенні оптимального плану транспортної задачі методом потенціалів спочатку знаходився небудь її опорний план, а потім він послідовно поліпшувався, то при знаходженні вирішення транспортної задачі методом диференціальних рент спочатку найкращим чином розподіляють між пунктами призначення частину вантажу (так зване умовно оптимальний розподіл) та на наступних ітераціях поступово зменшують загальну величину нерозподілених поставок.
Початковий варіант розподілу вантажу визначають наступним чином. У кожному зі стовпців таблиці дан...
