трусики женские украина

На головну

 Методи лінійного програмування для вирішення транспортної задачі - Економіко-математичне моделювання

План реферату

Введення

1. Формулювання транспортної задачі

2. Математична модель транспортної задачі

3. Необхідна і достатня умови розв'язності транспортної задачі

4. Властивість системи обмежень транспортної задачі

5. Опорний рішення транспортної задачі

6. Методи побудови початкового опорного рішення

6.1 Побудова початкового плану за способом північно-західного кута

6.2 Побудова початкового плану за способом мінімального елемента

7. Перехід від одного опорного рішення до іншого

8. Розподільчий метод

9. Метод потенціалів

10. Особливості вирішення транспортних завдань з неправильним балансом

11. Алгоритм розв'язання транспортної задачі методом потенціалів

11.1 Попередній крок

11.2 Загальний повторюваний крок

12. Транспортна задача з обмеженнями на пропускну спроможність

13. Транспортна задача за критерієм часу

14. Застосування транспортної задачі для вирішення економічних завдань

Висновок

Список використаної літератури

Введення

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

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

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

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

Дуже типовою завданням, розв'язуваної за допомогою лінійного програмування, є транспортна задача. [1]

Транспортна задача (transportation problem) - одна з найбільш поширених задач математичного програмування (зазвичай - лінійного). У загальному вигляді її можна представити так: потрібно знайти такий план доставки вантажів від постачальників до споживачів, щоб вартість перевезення (або сумарна дальність, або обсяг транспортної роботи в тонно-кілометрах) була найменшою. Отже, справа зводиться до найбільш раціонального прикріплення виробників до споживачів і навпаки. [2]

1. Формулювання транспортної задачі

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

Вихідна інформація:

Mi-кількість одиниць вантажу в i-му пункті відправлення (i = 1, 2, ..., k);

Nj- потреба в j-му пункті призначення (j = 1, 2, ..., l) (в одиницях вантажу);

aij- вартість перевезення одиниці вантажу з i-гo пункту в j-й.

Позначимо через xijпланіруемое кількість одиниць вантажу для перевезення з i-ro пункту в j-й.

У прийнятих позначеннях:

- Загальна (сумарна) вартість перевезень;

- Кількість вантажу, що вивозиться з i-ro пункту;

- Кількість вантажу, що доставляється в j-й пункт.

У найпростішому випадку повинні виконуватися такі очевидні умови:

Таким чином, математичної формулюванням транспортної задачі буде:

знайти

при умовах

;

;

Це завдання носить назву замкнутої (закритою, збалансованої) транспортної моделі.

Зауважимо, що условіеявляется природною умовою можливості розв'язання замкнутої транспортної задачі.

Більш загальної транспортної завданням є так звана відкрита (незбалансована) транспортна модель:

знайти

при умовах

Ясно, що в цій задачі не передбачається, що весь вантаж, накопичений в i-му пункті, повинен бути вивезений. [3]

2. Математична модель транспортної задачі

Найпростішими транспортними завданнями є завдання про перевезення деякого однорідного вантажу з пунктів відправлення (від постачальників) в пункти призначення (до споживачів) при забезпеченні мінімальних витрат на перевезення.

Зазвичай початкові умови таких завдань записують у таблицю. Наприклад, для k постачальників і l споживачів така задача має наступний вигляд:

Тут показники aijозначают витрати на перевезення одиниці вантажу від i-го постачальника (i = 1,2, ..., k) до j-тому споживачеві (j = 1,2, ..., l), Mi- потужність i-того постачальника в планований період, Nj- попит j-того споживача на цей же період. Позначимо через xijпоставку (кількість вантажу), яка планується до перевезення від i-того постачальника до j-тому споживачеві. Математично задача зводиться до знаходження мінімуму цільової функції, що виражає сумарні витрати на перевезення вантажу, тобто функції

при обмеженнях

(1)

Якщо до цих обмежень додати ще одне:

, (2)

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

Завданням, в яких обмеження (2) відсутній, тобто

,

спочатку відповідає відкрита модель.

Відзначимо деякі особливості економіко-математичної моделі транспортної задачі.

Система обмежень (1) відразу має вигляд рівнянь, тому відпадає необхідність вводити додаткові змінні.

Матриця коефіцієнтів при змінних в системі (1) складається тільки з одиниць і нулів.

Система обмежень (1) включає k рівнянь, що зв'язують поставки i-того постачальника з потужністю Mi (i = 1,2, ..., k) цього постачальника, і l рівнянь, що зв'язують поставки j-тому споживачеві з попитом Nj (j = 1, 2 ..., l) цього споживача. Зауважимо, що число k дорівнює числу рядків вихідної таблиці, а число l - числу стовпців.

Число змінних xij, що входять в цільову функцію і в систему рівнянь (1), дорівнює добутку kl, тобто числу клітин таблиці.

Таким чином, система обмежень (1) є система з k + l рівнянь з kl змінними.

Будь-яке рішення транспортної задачі (x11, x12, ..., xkl) називається розподілом поставок. Так як постачання не можуть бути негативними, то мова йде тільки про допустимі рішеннях.

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

У результаті виконання завдання і потрібно отримати це оптимальний розподіл поставок, якому відповідає якесь допустиме базисне рішення системи обмежень (1). [4]

3. Необхідна і достатня умови розв'язності транспортної задачі

Обмеження (1) та умови невід'ємності змінних, що виключають зворотні перевезення xij> 0; i = 1, 2, ..., k; j = 1, 2,., l.

Ці умови утворюють систему обмежень. Будь-який план, компоненти якого задовольняють цій системі, буде допустимим.

Як бачимо, система обмежень задана в основному (k + l) рівняннями. Встановимо умови, за яких ця система буде спільної, тобто матиме рішення.

Складемо елементи xijматріци перевезень по рядках, кожен рядок в сумі дає Mi, і в підсумку отримаємо. Складемо ті ж елементи за стовпцями, кожен стовпець дає Nj, і в сумі отримаємо. Але від перестановки доданків сума не змінюється, тому для будь-якого допустимого плану обов'язково буде виконуватися умова

.

Равенствоявляется необхідною умовою спільності обмежень задачі.

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

Дійсно, нехай. Розглянемо такі числа:

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

Підсумуємо ці числа за індексом i:

.

Але величини Nj, від індексу i не залежить і їх можна винести за знак суми. В результаті

або

,

Отже, взяті числа задовольняють групі рівнянь (1).

Підсумуємо ці числа за індексом j:

Виносячи постійні Miіза знак суми і маючи на увазі, що, отримуємо

або в розгорнутому вигляді

Як бачимо, наші числа задовольняють групі рівнянь (1). Ці числа невід'ємні, тобто система обмежень повністю задовольняється. Таким чином, допустимий план існує, що й потрібно було довести.

Рівність запасів потребам є необхідна і достатня умова спільності і, отже, можливості розв'язання транспортної задачі. [5]

4. Властивість системи обмежень транспортної задачі

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

.

У цій системі обмежень рівнянь закритої транспортної задачі є k + l-1 лінійно-незалежних рівнянь, тобто ранг системи обмежень дорівнює k + l-1. [6]

5. Опорний рішення транспортної задачі

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

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

6. Методи побудови початкового опорного рішення 6.1 Побудова початкового плану за способом північно-західного кута

У цьому випадку не звертають уваги на показники витрат. Почавши заповнення з клітки (1.1) - "північно-західного кута" таблиці, ступенями спускаються вниз до клітини (k, l), викреслюючи або один рядок, або один стовпець. На останньому кроці викреслюються остання (k-я) рядок і останній (l-й) стовпець. При практичному заповненні таблиці, викреслювання рядків і стовпців проводиться лише подумки.

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

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

Спосіб мінімального елемента враховує тарифи і тому дозволяє знайти план, ближчий до оптимального.

Цей спосіб полягає в наступному.

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

лінійне програмування транспортна задача

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

Отриманий план буде ациклічним і буде складатися не більше ніж з k + l-1 компонент. Цей план і приймаємо за вихідний. Він буде краще плану, побудованого за способом північно-західного кута, і для знаходження оптимуму потрібно менше обчислень. [5]

7. Перехід від одного опорного рішення до іншого

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

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

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

Для вільної клітини сстроітся цикл (ланцюг, багатокутник), всі вершини якого, крім однієї, знаходяться в зайнятих клітинах; кути прямі, число вершин парне. Близько вільної клітини циклу ставиться знак (+), потім по черзі проставляють знаки (-) і (+). У вершин зі знаком (-) вибирають мінімальний вантаж, його додають до вантажів, що стоять біля вершин зі знаком (+), і віднімають від вантажів у вершин зі знаком (-). В результаті перерозподілу вантажу отримаємо нове опорне рішення. Це рішення перевіряємо на оптимальність і т.д. до тих пір, поки не отримаємо оптимальне рішення. [7]

8. Розподільчий метод

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

Алгоритм розподільного методу полягає в наступному.

1. Відшукуємо первісний ациклический план, що містить (k + l-1) компонент (при нестачі компонент дописуємо нулі).

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

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

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

5. У негативній полуцепі того циклу, який відповідає обраній клітці, відшукуємо найменшу перевезення і робимо зрушення по циклу на це число. Знаходимо новий допустимий план.

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

Для ручного рахунку більш зручний метод потенціалів. Однак на розподільному методі засновані деякі інші способи вирішення завдань, що і викликає необхідність його вивчення. [5]

9. Метод потенціалів

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

Основна частина макета виділена подвійними лініями. Вона містить k ? l клітин. Кожна клітина в цій частині позначається символом (i, j). Наприклад, клітина, що стоїть в другому рядку і першому стовпці, буде позначена (2, 1). Макет містить в собі матрицю тарифів. Призначення рядка vjі стовпця uiбудет з'ясовано надалі.

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

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

Приклад ланцюга наведено в табл.2.

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

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

Теорема. Нехай в макеті (або матриці) з k рядків і l стовпців довільно відзначено k + l клітин, причому k + l ? kl. В цьому випадку завжди можна побудувати цикл, вершини якого лежать у зазначених клітинах (може бути не у всіх).

Зауваження. Числа k і l цілі, і для них не завжди буде виконано нерівність k + l ? kl. Якщо одне з цих чисел - одиниця, ця нерівність не виконується. Наприклад, при k = 3, l = 1 маємо 3 + 1> 3 · 1. Однак при k = 2 і l = 2 буде 2 + 2 = 2 · 2, а при k і l, одночасно великих двох, нерівність завжди виконується.

Умова k + l ? kl виключає випадки матриць з одним рядком або одним стовпцем, в яких взагалі циклу побудувати не можна.

Доказ. Розглянемо мінімальний можливий випадок: k = 2, l = 2 (табл.4).

У макеті треба вибрати k + l = 4, тобто всі 4 клітини. Для цього випадку теорема справедлива: вибрані клітини утворюють цикл.

Візьмемо тепер будь-які k> 2, l> 2. Доказ будемо вести методом математичної індукції.

Припустимо, теорема справедлива для макета, у якого сума рядків і стовпців на одиницю менше взятих нами (k + l). Доведемо, що при цьому припущенні теорема буде справедлива для прийнятих (k + l).

Перший випадок. Серед відзначених клітин є одна клітина, єдина в ряду (рядку або стовпці) (табл.5).

Відмовимося від цієї клітини, виключимо цю рядок з розгляду. Тоді прийдемо до таблиці, у якій рядків на одиницю менше, а число стовпців збереглося. Число рядків в сумі з числом стовпців буде менше (k + l) на одну одиницю, а й число зазначених клітин зменшиться на одну. Для цього випадку можна побудувати цикл за прийнятим допущенню. Цей цикл візьмемо і для нашої таблиці, так як відповідно до застереженням вершини циклу можуть бути і не вo всex зазначених клітинах.

Другий випадок. Немає таких ситуацій, коли клітина одна. У кожному рядку (стовпці) більше ніж одна клітина (або немає жодної) (табл.6).

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

Вище було показано, що теорема справедлива для k = 2, l = 2, тобто для k + l = 4. За доведеним вона справедлива для випадків: k + l = 5, тобто k + l> 4; k + l = 6, тобто k + l> 5; k + l> 6 і т.д., тобто для будь-якого макета.

Допустимий план Х (xij) називається ациклічним (Нециклічні), якщо набір клітин з відмінними від нуля компонентами плану xij> 0 не містить жодного циклу.

Приклад ациклического плану наведено в табл.7,

де точки позначають клітини, в яких xij> 0 (xij <0 неприпустимі за змістом задачі). Як покажемо нижче, серед ациклических планів є оптимальний.

Якщо в ациклічному плані Х (xij) число позитивних компонентів

N = k + l - 1 (інші компоненти - нулі), то елементи aijматріци тарифів з набору клітин, в яких розташовані xij> 0, будемо називати Х-відзначеними.

Якщо ж число позитивних компонент плану N Більше (k + l - 1) число компонент ациклического плану не може бути :, так як вже при N = k + l по доведеною вище теоремі завжди з обраних клітин можна побудувати цикл.

Теорема 2 (основна теорема). Якщо для деякого плану Х = (xij) k?lтранспортной завдання можна підібрати систему з k + l чисел u1, u2, ..., ui, ..., uk; vl, v2, ..., vj, ..., vl, що задовольняє таким умовам: vj- ui ? aijдля всіх i = 1, 2,., k; j = 1, 2,., l, а для xij> 0 (xij (-X)) vj- ui = aij, то план Х буде оптимальним.

Числа ui, vjназиваются потенціалами пунктів відправлення і пунктів призначення; умови vj- ui ? aijі vj- ui = aijназивают умовами потенційності плану Х.

До кожній клітині (i, j) відносяться два потенціалу: i-ro пункту відправлення uiі j-ro пункту призначення vj.Условія потенційності словесно можна сформулювати так: різниця потенціалів для всіх без винятку клітин повинна бути менше або дорівнює тарифом, а для зайнятих ( Х-відзначених) клітин вона повинна бути точно дорівнює тарифом. План, що задовольняє цим умовам, називається потенційним.

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

Доказ. Припустимо, що для деякого плану Х (xij) умови потенційності виконані, тобто існує така система чисел uiі vj, яка задовольняє умовам vj- ui = aijі vj- ui ? aij (табл.8).

Іншими словами, нехай план Х потенціалом. Доведемо, що цей план буде оптимальним. План Х дає значення функціоналу

.

Так як ми ще не знаємо, оптимальний план Х чи ні, то візьмемо свідомо оптимальний план Х '(x ? ij) і подивимося, яке значення він доставляє функціоналу:

(Транспортні витрати мінімальні). Чи виконуються умови потенційності для плану Х '- невідомо, але кожній клітині (i, j) макета 8, виходячи з потенційності плану Х, відповідає нерівність vj- ui ? aijілі, навпаки, aij? vj- ui.Возьмем з кожної клітини макета відповідний х'ij, помножимо його на ліву і праву частини останнього нерівності і складемо. Одержимо нерівність

.

Подвійну суму в правій частині позначимо для стислості буквою S:

,

її можна переписати у вигляді різниці двох подвійних сум:

.

Перетворимо ці суми наступним чином. Перша з них в розгорнутому вигляді дає

або

.

Аналогічно другий подвійну суму можна записати так:

.

Тоді равенствозапішется в іншій формі:

.

Ноесть сума компонент плану по j-му стовпцю, вона

дорівнює потреби j-ro пункту призначення

.

Аналогічноесть сума компонент плану, взята по i-му рядку, вона дорівнює запасам в i-му пункті відправлення

.

Ці рівності сум компонент по рядку і стовпцю відповідно запасам і потребам будуть виконуватися для будь-якого допустимого плану, в тому числі і для взятого на самому початку плану Х (xij):

Тому для будь-яких допустимих планів матимемо

і в написаному вище равенствесумми x ? ijможно замінити відповідними сумами xij:

Тепер повернемося до форми запису

.

У плані Х (xij) за умовою його потенційності для кожної позитивної компоненти xij> 0 виконується рівність vj- ui = aij.

Інші компоненти плану дорівнюють нулю, і відповідні доданки в сумі звернуться в нулі. Тому отримана сума буде дорівнює

.

Подставляяв

,

приходимо до нерівності

або zmin? zX.Інимі словами, транспортні витрати за планом Х менше або дорівнюють мінімальним витратам. Але менше мінімальних вони бути не можуть, залишається тільки рівність zX = zmin..План Х доставляє мінімальні витрати, тобто він оптимальний, що потрібно було довести.

Таким чином, якщо план потенціалом, то він оптимальний. Це і є тим критерієм, за яким судять про оптимальність плану.

Справедливо і зворотне положення: якщо план оптимальний, то він о6язательно потенціалом. Ця умова (необхідність) приймається без доведення. [5]

10. Особливості вирішення транспортних завдань з неправильним балансом

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

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

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

Перший випадок ..

У математичну модель транспортної задачі введемо фіктивний (l + l) - й пункт призначення. Для цього в матриці завдання передбачимо один стовпець, для якого потреба буде дорівнює надлишку вантажу:

,

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

min

Фіктивний споживач забезпечує спільність обмежень, не вносячи спотворень у вирішення.

Другий випадок.

Якщо запасів не вистачає для задоволення потреб, тобто, то вводимо фіктивний (k + 1) - й пункт відправлення, якому приписуємо запас вантажу, рівний

,

тарифи на доставку вантажів з цього фіктивного складу знову, вважаємо нульовими. У матриці додасться один рядок. На функціоналі це не позначиться, а система обмежень задачі стане спільною, тобто стане можливим відшукання оптимального плану на мінімум вартості перевезень. [5]

11. Алгоритм розв'язання транспортної задачі методом потенціалів

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

Цей крок включає наступних три етапи.

1. Знаходимо допустимий ациклический план.

2. Складаємо систему чисел - потенціалів пунктів відправлення і пунктів призначення.

3. Аналізуємо систему на потенційність. Якщо вона потенційна (тобто план потенціалом), то знайдений план оптимальний. Якщо система не потенційна, приступаємо до загального кроці.

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

Незважаючи на тарифи, починаємо складання плану з заповнення лівої верхньої клітини (1,1) (з північно-західного кута).

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

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

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

Другий етап попереднього кроку: визначення системи потенціалів.

Потенціал приписується кожному пункту відправлення (позначається ui) і кожному пункту призначення (vj). Всього потенціалів k + l чисел. Вони вносяться у спеціально відведені для цього рядок і стовпець макета.

Для Х-відзначених тарифів aij, число яких завжди дорівнює (k + l - 1), повинні виконуватися рівності vj- ui = aij. Ці рівності і будуть служити тими рівняннями, з яких перебувають потенціали. Однак таких рівнянь буде тільки (k + l - 1), а невідомих у системі (k + l), тобто на одиницю більше. Така система рівнянь має незліченну безліч рішень, кожне з яких годиться для нашої мети. Щоб знайти якесь одне рішення, значення одного потенціалу вибираємо довільно. Решта потенціали визначаємо з рішення системи. Третій етап попереднього кроку: випробування плану або системи потенціалів на потенційність. Потенційність полягає в тому, щоб нерівність vj- ui Виділяємо позитивні різниці dij:

dij = vj- ui- aij> 0.

На цьому попередній крок закінчений.

11.2 Загальний повторюваний крок

Загальний крок виконується в такій послідовності.

1. З позитивних різниць dijнаходім найбільшу різницю di0j0:

diojo = mах (vj- ui- aij> 0).

Нехай цей максимум має місце для клітини (i0, j0). Включаємо цю клітку в набір Х-відзначених (k + l - 1) клітин. Клітин стає (k + l), а для такої їх кількості завжди можна побудувати цикл. Цей цикл буде в даній ситуації єдиним.

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

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

3. Вибираємо найменше значення перевезення в клітинах негативною полуцепі (xij) -.Пусть воно дорівнює Q:

min (xij) - = Q.

Якщо таких значень декілька, беремо одне з них, байдуже яке.

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

Процес зсуву змінює план, але план залишається допустимим.

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

Після зсуву в клітці негативною полуцепі з мінімальною перевезенням буде стояти нуль, а в клітці (i0, j0), включеної в набір, виявиться число Q. Першу клітку з плану виключаємо, а другий включаємо; план залишається як і раніше ациклічним, так як єдиний наявний цикл порушується винятком клітини.

Отриманий після зсуву план можна записати наступним чином:

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

Для зайнятих клітин повинні виконуватися рівності.

Тому беремо в таблиці клітку, зайняту в результаті зсуву, і виправляємо для неї потенціали так, щоб їх різниця дорівнювала тарифом. Краще змінювати один з них - той, який стоїть в рядку або стовпці з меншим числом зайнятих клітин.

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

6. Виробляємо дослідження нової системи на потенційність, тобто дослідження знайденого плану на оптимальність. Для цього перевіряємо виконання нерівностей vj- ui? aijдля всіх незайнятих клітин. Якщо для них нерівності виконуються, то система потенціальна і план оптимальний, тобто рішення закінчено. Якщо для якихось клітин нерівності не виконуються, обчислюємо різниці dijі робимо знову спільний крок і т.д., до тих пір, поки не буде отриманий оптимальний план. Виродження в транспортній задачі виявляється в тому, що серед (k + l-1) Х-відзначених клітин виявляється клітина з нульовою перевезенням. Якщо ця клітина не потрапляє в цикл, на неї не звертаємо уваги. Якщо вона потрапляє в позитивну полуцепь циклу, то на наступному кроці замість нуля отримаємо в цій клітці позитивне число. Якщо ж нульова клітина виявляється в негативній полуцепі, то Q = 0, тобто зрушення треба робити на число нуль. Такий нульовий зсув плану не змінює, але нуль переходить в іншу клітку, змінюється набір Х-відзначених клітин і система потенціалів. Це дає можливість на черговому кроці здійснити вже не нульовий зсув і змінити план у бік його поліпшення. Контроль обчислень здійснюється таким чином. У процесі виконання завдання на кожному кроці отриманий план перевіряється на допустимість. Для цього компоненти плану підсумовуються по рядках і стовпцях; суми повинні рівнятися відповідно запасам і потребам пунктів. Остаточний (оптимальний) план перевіряється за формулою, яка витікає з докази основної теореми:

,

при цьому контролюються і потенціали. [5]

12. Транспортна задача з обмеженнями на пропускну спроможність

Транспортна задача з обмеженими пропускними спосо6ностямі комунікацій вирішується з додатковим обмеженням :, де dij- пропускна здатність ланки (i, j) в одиницю часу. Математична модель задачі така:

,

при обмеженнях

Це завдання можна залагодити при виконанні умов

.

Для транспортної задачі з обмеженими пропускними здатностями справедливі наступні умови оптимальності отриманого рішення:

[8]

13. Транспортна задача за критерієм часу

Крім транспортної задачі за критерієм вартості існує задача транспортного типу за критерієм часу. Постановка такого завдання полягає в наступному.

Дана матриця часу (tij) k?l, де tij- час на перевезення вантажу з i-того пункту відправлення в j-тий пункт призначення. Матриця перевезень вантажів (xij) k?l, де xij- кількість перевезеного вантажу з i-того пункту відправлення в j-тий пункт призначення. Відомо також наявність вантажу Miі попит на нього Nj ,. Потрібно визначити такий план перевезень, при якому весь вантаж буде доставлений споживачам в найкоротший термін.

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

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

Вихідний опорний план можна отримати за правилами "північно-західного кута", "мінімального елемента", наближеним методом. Далі переглядаємо всі зайняті клітини і в них вибираємо максимальний час t, за який здійснюється опорний план перевезень, тобто Т = max (tij), де клітини (i; k) зайняті. Кожному плану перевезень буде відповідати цілком певне значення Т, залежне від плану, тобто T = f (x). Отже, потрібно знайти такий план доставки вантажу споживачам, для якого Т буде мінімальним.

Визначивши максимальне значення Т для вихідного плану, переглядаємо ту клітку, для якої t = Т = max (tij). Наприклад, такий клітиною є (p, q). Для цієї клітини будується цикл, який включає в себе зайняті і вільні клітини. Таких циклів може бути декілька. Однак при побудові його слід врахувати умови. Зайнята клітина (p, q), для якої tiq = Т буде непарної, наступна клітина за годинниковою або проти годинникової стрілки - парна, наступна - непарна і т.д. Цикл містить два напів - парного і непарного. Для непарних клітин циклу обов'язково повинна бути завантаження більше нуля, а для парних - час менше Т. Вільні клітини, для яких час tij> Т, прочеркиваются і в розрахунок не приймаються.

Побудувавши цикл для розвантажувальної клітки (p, q), для якої t (p, q) = Т, визначаємо найменшу завантаження в непарних клітинах циклу. Отримана кількість вантажу віднімається з вантажів непарних клітин і додається до чисел парних клітин циклу. При цьому може виявитися, що після зміщення по циклу клітина (p, q) не розвантажиться, тоді знову будується цикл і здійснюється розвантаження клітини до тих пір, поки кількість вантажу стане рівним нулю. Після розвантаження клітини, що має максимальний проміжок часу, отримуємо новий план перевезень, для якого відшукується розвантажувальна клітка і знову проводиться процедура побудови циклу і зміщення вантажу по циклу. Процес продовжується до тих пір, поки можна буде будувати розвантажувальні цикли. У разі неможливості побудувати такий цикл в отриманих зайнятих клітинах плану вибираємо максимальний час, який і буде шуканим з реалізації оптимального плану. [9]

14. Застосування транспортної задачі для вирішення економічних завдань

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

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

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

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

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

3. Завдання про скорочення виробництва з урахуванням сумарних витрат на виготовлення і транспортування продукції.

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

5. Рішення задач за допомогою методу заборони перевезень. Використовується в тому випадку, якщо вантаж від деякого постачальника з якихось причин не може бути направлений одному із споживачів. Дане обмеження можна врахувати, присвоївши відповідній клітині достатньо велике значення вартості. [7]

Висновок

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

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

Раціональне прикріплення споживачів до постачальників в значній мірі визначає структуру господарських зв'язків, їх економічну ефективність. Під оптимальним ми розуміємо такий план їх прикріплення, який дозволяє при мінімальних витратах на поставки і утримання запасів максимально використовувати виробничі потужності постачальників і безперебійно живити споживачів. [8]

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

Список використаної літератури

1) Баканов, М.І. Економічний аналіз: Навчальний посібник / М.І. Баканов, А.Д. Шеремет. - М .: Фінанси і статистика, 2002. - С.40-41.

2) Лопатников, Л.І. Словник сучасної економічної науки / Л.І. Лопатников // Економіко-математичний словник. - М .: ABF, 1996. - С.43-44, 543-545.

3) Карманов, В.Г. Математичне програмування: Підручник для вузів. - М .: Наука, 1975. - С.16-18.

4) Карасьов, А.І. Курс вищої математики для економічних вузів: Підручник для економічних вузів / А.І. Карасьов, З.М. Аксютіна, Т.І. Савельєва - М .: Вища школа, 1982. - С.279-285.

5) Полунін, І.Ф. Курс математичного програмування: Підручник для вузів. - Мінськ: Вища школа, 1970. - С. 194-230.

6) Сакович, В.А. Дослідження операцій: Підручник для вузів. - Мінськ: Вища школа, 1985. - С.75.

7) Красс, М.С. Математика для економістів: Підручник для економічних вузів. - Санкт-Петербург: Питер, 2006. - С.289-299.

8) Сакович, В.А. Управління комплексними поставками: Підручник для вузів. - Мінськ: Вища школа, 1989. - С.100-108.

9) Холод, Н.І. Математичні методи аналізу і планування: Підручник для вузів. - Мінськ: Ураджай, 1989. - С.97-99.

10) Холод, Н.І. Посібник з вирішення завдань з лінійної алгебри та лінійному програмуванню: Посібник для вузів. - Мінськ: видавництво БДУ, 1971. - С.159.

Авіація і космонавтика
Автоматизація та управління
Архітектура
Астрологія
Астрономія
Банківська справа
Безпека життєдіяльності
Біографії
Біологія
Біологія і хімія
Біржова справа
Ботаніка та сільське господарство
Валютні відносини
Ветеринарія
Військова кафедра
Географія
Геодезія
Геологія
Діловодство
Гроші та кредит
Природознавство
Журналістика
Зарубіжна література
Зоологія
Видавнича справа та поліграфія
Інвестиції
Інформатика
Історія
Історія техніки
Комунікації і зв'язок
Косметологія
Короткий зміст творів
Криміналістика
Кримінологія
Криптологія
Кулінарія
Культура і мистецтво
Культурологія
Логіка
Логістика
Маркетинг
Математика
Медицина, здоров'я
Медичні науки
Менеджмент
Металургія
Музика
Наука і техніка
Нарисна геометрія
Фільми онлайн
Педагогіка
Підприємництво
Промисловість, виробництво
Психологія
Психологія, педагогіка
Радіоелектроніка
Реклама
Релігія і міфологія
Риторика
Різне
Сексологія
Соціологія
Статистика
Страхування
Будівельні науки
Будівництво
Схемотехніка
Теорія організації
Теплотехніка
Технологія
Товарознавство
Транспорт
Туризм
Управління
Керуючі науки
Фізика
Фізкультура і спорт
Філософія
Фінансові науки
Фінанси
Фотографія
Хімія
Цифрові пристрої
Екологія
Економіка
Економіко-математичне моделювання
Економічна географія
Економічна теорія
Етика

8ref.com

© 8ref.com - українські реферати


енциклопедія  бефстроганов  рагу  оселедець  солянка