Реферат Рішення транспортних задач

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

>СОДЕРЖАНИЕ

ЗАПРОВАДЖЕННЯ 5

1. СПІЛЬНА ЧАСТИНА 8

1.1 Математична завдання 8

1.2 Алгоритм виконання завдання 11

1.3Блок-схема (алгоритм рішення) 25

2. Форми вхідний інформації 27

3. Форми вихідний інформації 28

4. Інструкція для користувача 29

5. Інструкція для програміста 30

>ЗАКЛЮЧЕНИЕ 33

СПИСОКИСПОЛЬЗОВАННЫХИСТОЧНИКОВ 34

>ПРИЛОЖЕНИЕ А 35


ЗАПРОВАДЖЕННЯ

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

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

Добре сказав звідси Галілей:

«Філософія (на нашій мові- фізика) написана в найбільшої книзі, яка постійно відкрита вашому погляду, але зрозуміти її лише той, хто спочатку навчиться розуміти її язик, і тлумачити знаки, які вона написана.Написана вона мовою математики».

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

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

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

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

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

Відзначені напрями вимагають знання основного математичного апарату: основ лінійної алгебри і математичного аналізу, теорії ймовірностей і математичного програмування.

Отже, математика і математичну освіту потрібні на підготовку до майбутню професію.

Одне з класів математичних моделей- завдання лінійного програмування. Однією із завдань лінійного програмування є транспортна завдання- завдання складання оптимального плану перевезень, що дозволяє мінімізувати сумарний кілометраж. Транспортна завдання, як і завдання лінійного програмування була вперше поставлена радянським економістомА.Н.Толстим в 1930 року. Розробка загальних методів виконання завдання лінійного програмування та його математичне дослідження пов'язаний з ім'ям радянського вченогоЛ.В.Канторовича. 1939-го року методам виконання завдання лінійного програмування присвячено також велика кількість робіт зарубіжних провідних вчених. Основний метод виконання завдання лінійного програмування –симплекс метод- опублікований 1949 рокуДандигом.Симплекс метод дає розв'язання будь-якої завдання лінійного програмування, якщо змінних дуже багато, те решіння дуже важко й у складніших завдань симплекс метод стали модифікувати.

Транспортна завдання ділиться на два виду: транспортна завдання критерієм вартості- визначення плану перевезень, у якому вартість вантажу було б мінімальна; транспортна завдання критерієм часу- важливішим є виграш за часом.

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


1. ОСНОВНА ЧАСТИНА

1.1МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАВДАННЯ

Транспортна завдання-

>Однородний вантаж зосереджений у т постачальників обсягом .

Цей вантаж необхідно доставити п споживачам обсягах .

Відомі (>i=1,2,…,m;j=1,2,…,n)- вартості перевезення одиниці вантажу від кожноїi-го постачальника кожномуj-му споживачеві. Потрібна скласти такий план перевезень, у якому запаси всіх постачальників вивозяться повністю, запити всіх споживачів задовольняються цілком і сумарні видатки перевезення усіх вантажів мінімальні.

Вихідні дані транспортної завдання записуються в таблиці виду

Таблиця 1

 

 

 …

 

 

 

 …

 

 

 

 …

 

 …

 …

 …

 …

 

 

 …

 

>Переменними(неизвестними) транспортної завдання є (>i=1,…,m;i=1,2,…,n)- обсяги перевезень від кожноїi-го постачальника кожномуj-му споживачеві. Ці перемінні можуть бути записані в матриці перевезень

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

 (1.1)

 >i=1,2,…,m, (1.2)

 >j=1,2,…,n, (1.3)

 >i=1,2,…,m;j=1,2,…,n. (1.4)

Цільова функція завдання (1.1) висловлює вимоги забезпечити мінімум сумарних витрат за перевезення усіх вантажів. Перша група т рівнянь (1.2) описує те що, що запаси всіх т постачальників вивозяться повністю. Друга з n рівнянь (1.3) висловлює вимоги цілком задовольнити запити всіх n споживачів.Неравенства (1.4) є умоваминеотрицательности всіх змінних завдання.

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

 >i=1,2,…,m;j=1,2,…,n,

що задовольнить системі обмежень (1.2), (1.3), умовамнеотрицательности (1.4) і забезпечує мінімум цільової функції (1.1).

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

.

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

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

Приклад 1:

Скласти математичну модель транспортної завдання перевезення вантажу з цих двох складів 3 магазину:

Таблиця 2

  

50 70 80
90 9 5 3
110 4 6 8

Рішення.Введем переміннізадачи(матрицу перевезень)

Запишемо матрицю вартостей

.

Цільова функція завдання дорівнює сумі творів всіх відповідних елементів матриць З повагою та Х:

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

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

Це означає, що запаси постачальників вивозяться повністю.

Суми перевезень, котрі стоять у кожному стовпці матриці Ч, би мало бути рівні запитам відповідних споживачів:

Це означає, що запити споживачів задовольняються повністю.

Слід також враховувати, що перевезення неможливо знайти негативними:

 >i=1,2,…,m;j=1,1,…,n.

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

і задовольняють системі обмежень

й умовамнеотрицательности

 >i=1,2,…,mj=1,2,…,n.


1.2 АЛГОРИТМ РІШЕННЯТРАНСПОРТНОЙ ЗАВДАННЯ

1.2.1СБАЛАНСИРОВАННОСТЬТРАНСПОРТНОЙ ЗАВДАННЯ

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

.

Якщо транспортна завдання збалансована, то виникають особливості її вирішити.

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

>1.Если сумарні запаси постачальників перевершують сумарні запити споживачів, тобто.

необхідно запровадити фіктивного (>n+1)-го споживача з запитами рівними різниці сумарних запасів постачальників і запитів споживачів, і нульовими вартостями перевезень одиниць вантажу

2. Якщо сумарні запити споживачів перевершують сумарні запаси постачальників, тобто.

необхідно запровадити фіктивного (>m+1)-го постачальника з запасами рівні різниці сумарних запитів споживачів і запасів постачальників, і нульовими вартостями перевезень одиниць вантажу

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

1.2.2ОПОРНОЕ РІШЕННЯТРАНСПОРТНОЙ ЗАВДАННЯ

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

Через те, що ранг системи векторів умов транспортної завдання дорівнюєN=m+n-1, опорне рішення неспроможна мати відмінних нуля координат більше, ніж N.

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

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

Система векторів умов транспортної завдання лінійно незалежна тоді й тільки тоді, коли з відповідних клітин таблиці не можна утворити жодного циклу. Отже, дозволене рішення транспортної завдання ,i=1,2,…,m;j=1,2,…,n є опорним в тому разі, коли з зайнятих їм клітин таблиці не можна утворити жодного циклу.

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

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

Метод мінімальної вартості. Він дозволяє побудувати опорне рішення, який достатній близько оптимального, оскільки використовує матрицю вартостей транспортної завдання ,i=1,2,…,m;j=1,2…,n. Він складається з низки однотипних кроків, кожному у тому числі заповнюється лише одне клітина таблиці, відповідна мінімальної вартості , і виключається з розгляду лише однестрока(поставщик) чи одинстолбец(потребитель). Чергову клітину, відповідну , заповнюють також. Постачальник виключається з розгляду, якщо його закінчуються. Споживач виключається з розгляду, якщо його запити задоволені повністю. На кожен крок виключається або один постачальник, або один споживач. У цьому якщо постачальник не виключений, та його запаси рівні нулю, то, на тому кроці, коли від неї потрібно поставити вантаж, в відповідну клітину таблиці заноситься базисний нуль і потім постачальник виключається з розгляду. Аналогічно надходять із споживачем.

Приклад 2:

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

Таблиця 3

  

 

80 120 160 120
120 1 3 4 2
160 4 5 8 3
200 2 3 6 7

Рішення. Запишемо окремо матрицю вартостей у тому, щоб зручніше було вибирати вартості, викреслювати рядки - і стовпчики:

1 4 6 3

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

Таблиця 4

  

 

80 120 160 120
120

1

80

3 4

2

40

160 4 5

8

80

3

80

200 2

3

120

6

80

7

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

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

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

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

У матриці З залишився єдиний елемент .Записиваем у клітину таблиці (2,3) перевезення .

Перевіряємо правильність побудови опорного рішення. Кількість зайнятих клітин таблиці одноN=m+n-1=3+4-1=6. Застосовуючи метод викреслювання, перевіряємо лінійну незалежність векторів умов, відповідних позитивним координатам рішення. Порядок викреслювання показаний на матриці Х:

 1 2 5 6

Рішення є «>вичеркиваемим» і, отже, опорним.

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

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

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

>Сдвигом по циклу на величину називається на збільшення обсягів перевезень переважають у всіх непарних клітинах циклу, відзначених знаком «+», і зменшення обсягів перевезень

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

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

Нові надходження

Замовлення реферату

Реклама

Навігація