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


Реферат Методи лінійного програмування для вирішення транспортної задачі

Страница 1 из 3 | Следующая страница

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

Запровадження

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. Формулювання транспортної завдання

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

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

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

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

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

Означимо через x>ij плановане кількість одиниць вантажу для перевезення з і->ro пункту з j-і.

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

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

 - кількість вантажу,вивозимого з і->ro пункту;

 - кількість вантажу,доставляемого в j-і пункт.

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

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

знайти

за умов

;

;

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

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

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

знайти

за умов

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


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

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

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

Тут показники a>ij означають видатки перевезення одиниці вантажу від і-го постачальника (і=1,2,…,>k) до j-тому споживачеві (j=1,2,…,l), Mі - потужністьі-того постачальника в запланований період, Nj - попит j-того споживача цей самий період. Означимо через x>ij поставку (кількість вантажу), запланованій до перевезення від і-того постачальника до j-тому споживачеві.Математически завдання зводиться до пошуку мінімуму цільової функції, котра виражає сумарні видатки перевезення вантажу, тобто. функції

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

(1)

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

,(2)

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

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

,

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

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

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

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

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

Кількість змінних x>ij, які входять у цільову функцію й у систему рівнянь (1), одно твору >kl, тобто. числу клітин таблиці.

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

Будь-яке рішення транспортної завдання (x11, x12,…, x>kl) називається розподілом поставок. Оскільки поставки неможливо знайти негативними, то йдеться лише про допустимих рішеннях.

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

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


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

Обмеження (1) й умовинеотрицательности змінних, виключають зворотні перевезення x>ij>0; і= 1, 2, …, >k; j= 1, 2,., l.

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

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

Додаймо елементи x>ij матриці перевезень по рядкам, кожна рядок у сумі дає Mі, і через це одержимо . Додаймо самі елементи постолбцам, кожен стовпець дає Nj, і місто загалом одержимо . Але від перестановки доданків сума не змінюється, для будь-якого припустимого плану обов'язково виконуватиметься умова

.

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

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

Справді, нехай . Розглянемо такі числа:

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

>Просуммируем ці числа сьогодні за індексом і:

.

Але величини Nj,  від індексу і не залежать і можна винести за знак суми. Через війну

чи

,

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

>Просуммируем ці числа сьогодні за індексом j:

Виносячи постійні Mі і поза знак суми і у вигляді, що , отримуємо

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

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

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


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

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

.

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


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

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

За позитивного рішення завдання лінійного програмування можна зробити так: знайти будь-який з таких "відомих" рішень, необов'язково оптимальне, і прийняти його з вихідний пункт розрахунків. Таке рішення і буде базисним. Якщо з'ясується, що його та оптимальну, розрахунок у цьому закінчено, якщо ні - послідовно перевіряють, ні чи оптимальними сусідні верхові точки. Ту їх, у якій план ефективніше, приймають знову за вихідну і так, послідовно перевіряючи на оптимальність аналогічні вершини, дійдуть згаданої оптимуму. У цьому принципі будуються так званийсимплексний метод вирішення завдань лінійного програмування, і навіть низку інших способів, об'єднаних спільною назвою "методи послідовного поліпшення припустимого рішення (>МПУ)": метод зворотної матриці, чи модифікованийсимплекс-метод, метод потенціалів для транспортної завдання й інші. Вони відрізняються одна від друга обчислювальними особливостями переходу від однієї базисного рішення до іншого,улучшенному. [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.Испитиваем цього плану на оптимальність, тобто. кожної вільної клітини будуємо цикл перерахунку і обчислюємо алгебраїчну суму тарифів. Принеоптимальности плану знову включаємо вільну клітину до плану і робимо зрушення

Страница 1 из 3 | Следующая страница

Схожі реферати:

Навігація