Міжнародний університет
Калінінградський філіяЗаочне відділення
Спеціальність-менеджмент
Курсова робота
з дисципліни економіко-математичні методиТранспортна задача
лінійного програмування
Виконав: Перевірив (уч.степень, звання): |
Курсова робота
з вищої математики
Тема:
"Транспортна задача лінійного програмування"
Зміст:
1. Історія зародження та створення лінійного програмування.
2. Транспортна задача. Загальна постановка, цілі, завдання. Основні типи, види моделей.
3. Методи складання початкового опорного плану.
4. Поняття потенціалу і циклу.
5. Критерій оптимальності базисного розв'язку транспортної задачі. Методи відшукання оптимального рішення.
6. Завдання, двоїста до транспортної.
7. Приклад розв'язання транспортної задачі.
8. Висновки.
1.Історія зародження і створення лінійного програмування.
Кожна людина щодня, не завжди усвідомлюючи це, вирішує проблему: як отримати найбільший ефект, володіючи обмеженими засобами. Наші засоби і ресурси завжди обмежені. Життя було б менш цікавою, якщо б це було не так. Не важко виграти бій, маючи армію в 10 разів більшу, ніж у супротивника. Щоб досягти найбільшого ефекту, маючи обмежені кошти, треба скласти план, або програму дій. Раніше план у таких випадках складався "на око" (тепер, втім, часто теж). У середині XX століття було створено спеціальний математичний апарат, що допомагає це робити "по науці". Відповідний розділ математики називається математичним програмуванням. Слово "програмування" тут і в аналогічних термінах ("лінійне програмування, динамічне програмування" тощо) зобов'язана почасти історичного непорозуміння, почасти неточного перекладу з англійської. По-русски краще було б вжити слово "планування". З програмуванням для ЕОМ математичне програмування має лише те загальне, що більшість виникаючих на практиці завдань математичного програмування дуже громіздкі для ручного рахунку, вирішити їх можна лише за допомогою ЕОМ, попередньо склавши програму. Часом народження лінійного програмування прийнято вважати 1939р., Коли була надрукована брошура Леоніда Віталійовича Канторовича "Математичні методи організації і планування виробництва". Оскільки методи, викладені Л. В. Канторовичем, були мало придатні для ручного рахунку, а швидкодіючих обчислювальних машин у той час не існувало, робота Л. В. Канторовича залишилася майже не поміченою.
Своє друге народження лінійне програмування отримало на початку п'ятдесятих років з появою ЕОМ. Тоді почалося загальне захоплення лінійним програмуванням, що викликало в свою чергу розвиток інших розділів математичного програмування. У 1975 році академік Л. В. Канторович і американець професор Т. Купманс отримали Нобелівську премію з економічних наук за "внесок у розробку теорії і оптимального використання ресурсів в економіці".
В автобіографії, поданій до Нобелівського комітету, Леонід Віталійович Канторович розповідає про події, що трапилися в 1939 році. До нього, 26-річному професору-математику, звернулися за консультацією співробітники лабораторії планерного тресту, яким потрібно було вирішити задачу про найбільш вигідному розподіл матеріалу між верстатами. Ця задача зводилася до знаходження максимуму лінійної функції, заданої на многограннику. Максимум такої функції досягався у вершині, однак число вершин у цьому завданні досягало мільярда. Тому простий перебір вершин не годився. Леонід Віталійович писав: "виявилося, що це завдання не є випадковою. Я виявив велику кількість різноманітних за змістом завдань, що мають аналогічний математичний характер: найкраще використання посівних площ, вибір завантаження обладнання, раціональний розкрій матеріалу, розподіл транспортних вантажопотоків ... Це наполегливо спонукало мене до пошуку ефективного методу їх вирішення ". І вже влітку 1939 року була здана в набір книга Л. В. Канторовича "Математичні методи організації і планування виробництва", в якій закладалися підстави того, що нині називається математичної економікою.
Однак ідеї Л. В. Канторовича не зустріли розуміння в момент їх зародження, були оголошені єрессю, і його робота була перервана. Концепції Леоніда Віталійовича незабаром після війни були перевідкрили на заході. Американський економіст Т. Купманс протягом багатьох років привертав увагу математиків до низки завдань, пов'язаних з військовою тематикою. Він активно сприяв тому, щоб була організована математичний колектив для розробки цих проблем. У підсумку було усвідомлено, що треба навчитися вирішувати задачі про знаходження екстремумів лінійних функцій на багатогранника, що задаються лінійними нерівностями. За пропозицією Купманса цей розділ математики отримав назву лінійного програмування.
Американський математик А. Данциг в 1947 році розробив досить ефективний конкретний метод чисельного рішення задач лінійного програмування (він отримав назву симплекс методу). Ідеї лінійного програмування протягом п'яти шести років отримали грандіозне поширення у світі, і імена Купманса і Данцига стали всюди широко відомі.
Приблизно в цей час Купманс дізнався, що ще до війни в далекій Росії вже було зроблено щось схоже на розробку почав лінійного програмування. Як легко було б Данцигу і Купманса проігнорувати цю інформацію! Маленька книжечка, видана нікчемним тиражем, звернена навіть не до економістів, а до організаторів виробництва, з мінімумом математики, без чітко описаних алгоритмів, без доказів теорем - словом, чи варто приймати таку книжку до уваги ... Але Купманс наполягає на переведенні та виданні на заході книги Канторовича. Його ім'я й ідеї стають відомі всім. Віддамо належне шляхетності американського вченого!
А самому Леоніду Віталійовичу - як природно було б йому, випробувавши перші грізні удари ретроградів, утриматися від "гріхів" молодості, забути про всю цю економіку і повернутися до математики. Але Л. В. Канторович продовжує писати математичні праці, навіяні економічними ідеями, бере участь і в конкретних розробках на виробництві. При цьому (одночасно з Данцигом, але, не знаючи його робіт) він розробляє метод, пізніше названий симплекс-методом. Як тільки в 50-ті роки утворюється маленький просвіт, і дещо з забороненого стає можливим, він організовує групу студентів на економічному факультеті ЛДУ для навчання методам оптимального планування. А, починаючи з 1960 року, Леонід Віталійович займається тільки економічної і пов'язаної з нею математичної проблемами. Його внесок у цій області був відзначений Ленінською премією в 1965 році (присуджена йому спільно з В. С. Немчинова і В. В. Новожиловим) і, як уже говорилося, Нобелівською премією в 1975 році.
2.Транспортно завдання. Загальна постановка, цілі, завдання. Основні типи, види моделей.
Під назвою "транспортна задача" об'єднується широке коло завдань з єдиною математичною моделлю. Дані завдання відносяться до завдань лінійного програмування і можуть бути вирішені симплексним методом. Однак матриця системи обмежень транспортної задачі настільки своєрідна, що для її рішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, поліпшуючи його, отримати оптимальне рішення.
У загальній постановці транспортна задача полягає у знаходженні оптимального плану перевезень деякого однорідного вантажу з
Розрізняють два типи транспортних завдань: але критерієм вартості (план перевезень оптимальний, якщо досягнуть мінімум витрат на його реалізацію) і за критерієм часу (план оптимальний, якщо на його реалізацію витрачається мінімум часу).
|
|
|
|
- Відкриту модель транспортної задачі.
Очевидно, у випадку закритої моделі весь наявний вантаж розвозиться повністю, і всі потреби замовників повністю задоволені; у разі ж відкритої моделі або всі замовники задоволені і при цьому на деяких базах залишаються надлишки вантажу
Так само існують одноетапні моделі задач, де перевезення здійснюється безпосередньо від, наприклад, бази або заводу виробника до споживача, і двохетапні, де між ними є "перевалочний пункт", наприклад - склад.
План перевезень із зазначенням запасів і потреб зручно записувати у вигляді такої таблиці, званої таблицею перевезень:
Пункти Відправлення | Пункти призначення | Запаси | |||
... | |||||
... | |||||
... | |||||
... | ... | ... | ... | ... | ... |
... | |||||
Потреби | ... | або |
Очевидно, змінні
|
|
Система (2.1) містить
Така структура системи (2.1) дозволяє легко встановити її ранг. Дійсно, покажемо, що сукупність невідомих, які утворюють перший рядок і перший стовпець матриці перевезень, можна прийняти як базису. При такому виборі базису, принаймні, один з двох їхніх індексів дорівнює одиниці, а, отже, вільні невідомі визначаються умовою
|
де символи
При цьому легко помітити, що під символами такого підсумовування об'єднуються тільки вільні невідомі (тут
У розглянутій нами системі тільки два рівняння, а саме перше горизонтальне і перше вертикальне, містять більше одного невідомого з числа обраних нами для побудови базису. Виключивши з першого горизонтального рівняння базисні невідомі
або коротше
|
де символ
|
Так як для закритої моделі транспортної задачі
Отже, перетворення системи (2.1) звелося до заміни двох рівнянь (першого горизонтального і першого вертикального) рівнянням (2.2). Решта рівняння залишаються незмінними. Система прийняла вигляд
|
У системі (2.3) виділено зазначений вище базис: базисні невідомі з перших т рівнянь утворюють перший стовпець матриці перевезень, а базисні невідомі решти рівнянь утворюють перший рядок матриці перевезень без першого невідомого
Для вирішення транспортної задачі необхідно крім запасів і потреб знати також і тарифи
Сукупність тарифів
Пункти Відправлення | Пункти призначення | Запаси | ||||||||
... | ||||||||||
... | ||||||||||
... | ||||||||||
... | ... | ... | ... | ... | ... | |||||
... | ||||||||||
Потреби | ... | або | ||||||||
|
Необхідно в області допустимих рішень системи рівнянь (2.1) та (2.1.1) знайти рішення, яке мінімізує лінійну функцію (2.4).
Таким чином, ми бачимо, що транспортна задача є задачею лінійного програмування. Для її вирішення застосовують також симплекс-метод, але в силу специфіки завдання тут можна обійтися без симплекс-таблиць. Рішення можна отримати шляхом деяких перетворень таблиці перевезень. Ці перетворення відповідають переходу від одного плану перевезень до іншого. Але, як і в загальному випадку, оптимальне рішення шукається серед базисних рішень. Отже, ми будемо мати справу тільки з базисними (або опорними) планами. Так як в даному випадку ранг системи обмежень-рівнянь дорівнює
Для контролю треба перевіряти, дорівнює чи сума чисел в заповнених клітках кожного рядка таблиці перевезень запасу вантажу на відповідній базі, а в кожному стовпці - потреби замовника [цим підтверджується, що цей план є рішенням системи (2.1)].
Зауваження 1. Не виключаються тут і вироджені випадки, тобто можливість звернення до нуль однієї або кількох базисних невідомих. Але ці нулі на відміну від нулів вільних невідомих вписуються у відповідну клітину, і ця клітина вважається заповненою.
Зауваження 2. Під величинами
3. Методи складання початкового опорного плану.
Як і в загальному випадку, рішення транспортної задачі починається з відшукання першого опорного плану (вихідного базису). Ми розглянемо два найбільш поширені методи побудови такого базису. Суть обох цих методів полягає в тому, що базисний план складається послідовно, у кілька кроків (точніше,
§ У першому випадку ми можемо виключити стовпець, що містить заповнену на цьому кроці клітку, і вважати, що завдання звелася до заповнення таблиці з кількістю стовпців, на одиницю меншим, ніж було перед цим кроком, але з тією ж кількістю рядків і з відповідно зміненим запасом вантажу на одній з баз (на тій базі, якою було задоволено замовник на даному кроці).
§ У другому випадку виключається рядок, що містить заповнюють клітину, і вважається, що таблиця звузилася на один рядок при незмінній кількості шпальт і при відповідній зміні потреби замовника, у стовпці якого знаходиться заповнювана клітина.
Починаючи зі спочатку даної таблиці і повторивши
Зауваження. Може статися, що вже на деякій (але не на останньому!) Кроці потреба чергового замовника виявиться рівною запасу вантажу на черговий базі. Тоді після заповнення черговий клітини обсяг таблиці як би одночасно зменшується на одні стовпець і на один рядок. Але і при цьому ми повинні вважати, що зменшення обсягу таблиці відбувається або на один стовпець, а на базі зберігається "залишок" рівний нулю, або на один рядок, а у замовника ще залишилася незадоволена "потреба" в кількості нуля одиниць вантажу, яка і задовольняється на одному з наступних кроків. Цей нуль ("запас" або "потребою" - байдуже) треба записати в чергову заповнюють клітину на одному з наступних кроків. Тому що при цьому виявляється рівною нулю одна з базисних невідомих, то ми маємо справу з виродженим випадком.
Різниця методів відшукання першого опорного плану полягає у відмінності способів набору заповнюваної клітини.
1.Діагональний метод, або метод північно-західного кута. При цьому методі на кожному кроці побудови першого опорного плану заповнюється ліва верхня клітина (північно-західний кут) залишилася, таблиці. При такому методі заповнення таблиці починається з клітини невідомого
Приклад.
Пункти Відправлення | Пункти призначення | Запаси | |||||||||
70 | 50 | 15 | 80 | 70 | 300 | ||||||
170 | 110 | 20 | |||||||||
80 | 90 | 40 | 60 | 85 | 150 | ||||||
80 | 70 | ||||||||||
50 | 10 | 90 | 11 | 25 | 250 | ||||||
50 | 200 | ||||||||||
Потреби | 170 | 110 | 100 | 120 | 200 | 700 |
Тепер переходимо до заповнення клітини для невідомого
Через шість кроків у нас залишиться одна база
Загальний обсяг перевезень в тонно-кілометрах для цього плану складе
2.Метод найменшої вартості. При цьому методі на кожному кроці побудови опорного плану першою заповнюється та клітина залишилася, таблиці, яка має найменший тариф. Якщо така клітина не єдина, то заповнюється кожна з них.
Приклад.
Пункти Відправлення | Пункти призначення | Запаси | |||||||||
70 | 50 | 15 | 80 | 70 | 300 | ||||||
20 | 100 | 180 | |||||||||
80 | 90 | 40 | 60 | 85 | 150 | ||||||
150 | |||||||||||
50 | 10 | 90 | 11 | 25 | 250 | ||||||
110 | 120 | 20 | |||||||||
Потреби | 170 | 110 | 100 | 120 | 200 | 700 |
На п'ятому кроці клітин з найменшими значеннями виявилося дві . Ми заповнили клітку для , Поклавши . Можна було вибрати для заповнення іншу клітку, поклавши , Що призведе в результаті до іншого опорному плану. Загальний обсяг перевезень в тонно-кілометрах для цього плану складе
Зауваження. У діагональному методі не враховуються величини тарифів, у методі ж найменшої вартості ці величини враховуються, і часто останній метод призводить до плану з меншими загальними витратами (що і має місце в нашому прикладі), хоча це й не обов'язково.
Крім розглянутих вище способів іноді використовується, так званий, метод Фогеля. Суть його полягає в наступному: У розподільній таблиці по рядках і стовпцях визначається різниця між двома найменшими тарифами. Відзначається найбільша різниця. Далі в рядку (стовпці) з найбільшою різницею заповнюється клітка з найменшим тарифом. Рядки (стовпці) з нульовим залишком вантажу надалі в розрахунок не приймаються. На кожному етапі завантажується тільки одна клітина. Розподіл вантажу провадиться, як і раніше.
4.Понятіе потенціалу і циклу.
Для переходу від одного базису до іншого при вирішенні транспортної задачі використовуються так звані цикли.
Циклом перерахунку або коротше, циклом в таблиці перевезень називається послідовність невідомих, що задовольняє таким умовам:
1. Одне з невідомих послідовності вільне, а всі інші - базисні.
2. Кожні дві сусідні в послідовності невідомих лежать або в одному стовпці, або в одному рядку.
3. Три послідовних невідомих не можуть перебувати в одному стовпці або в одному рядку.
4. Якщо, починаючи з будь-якого невідомого, ми будемо послідовно переходити від одного до наступного за ним невідомому те, через кілька кроків ми повернемося до вихідного невідомого.
Друга умова означає, що у двох сусідніх невідомих у циклі або перші, або другий індекси однакові.
Якщо кожні два сусідніх невідомих циклу з'єднати відрізком прямої, то буде отримано геометричне зображення циклу - замкнута ламана з чергуються горизонтальних і вертикальних ланок, одна з вершин якої знаходиться у вільній клітці, а інші - в базисних клітинах.
Можна довести, що для будь-якої вільної клітини таблиці перевезень існує один і тільки один цикл, у якому вільне невідоме з цієї клітини, і що число вершин у циклі завжди парне.
Так, наприклад, в таблиці перевезень, складеної за діагональному методу при вирішення завдання з попереднього пункту, невідомому
Нехай тепер ми маємо деяку вільну клітину з відповідним їй циклом. Якщо ми змінимо значення вільного невідомого, збільшивши його на деяке число
старі значення:
нові значення:
Очевидно, якщо забезпечити вершини циклу по черзі знаками "+" і "-", приписавши вершині у вільній клітці знак "+", то можна сказати, що у вершинах зі знаком "+" число
Зауваження. Оскільки число вершин у циклі завжди парне, то, повертаючись у вільну клітину, ми повинні будемо приписати їй знак "+", тобто той знак, який їй вже приписаний при виході з неї. Це дуже істотна обставина, бо інакше ми прийшли б до протиріччя. Байдуже також, у якому напрямку обходиться цикл при "означування" вершин.
Якщо в якості
Так, наприклад, у розглянутому вище циклі маємо негативні вершини
старі значення:
нові значення:
тобто замість колишнього базисного рішення отримуємо нове базисне рішення:
Пункти Відправлення | Пункти призначення | Запаси | |||||||||
70 | 50 | 15 | 80 | 70 | 300 | ||||||
90 | 110 | 100 | |||||||||
80 | 90 | 40 | 60 | 85 | 150 | ||||||
80 | 70 | ||||||||||
50 | 10 | 90 | 11 | 25 | 250 | ||||||
50 | 200 | ||||||||||
Потреби | 170 | 110 | 100 | 120 | 200 | 700 |
Якщо мінімальне значення серед базисних невідомих, які стоять у негативних вершинах циклу, приймається не в одній негативній вершині, то вільної залишають тільки одну з них, а в інших клітинах з тим же мінімальним значенням пишуть нулі. У цьому випадку нове базисне рішення буде виродженим.
Може статися, що й саме мінімальне значення серед чисел в негативних клітинах дорівнює нулю. Тоді перетворення таблиці перевезень зведеться до перестановки цього нуля в вільну клітину. Значення всіх невідомих при цьому залишаються незмінними, але рішення вважаються різними, тому що різні базиси. Обидва рішення виродилися.
Описане вище перетворення таблиці перевезень, в результаті якого перетвориться базис, називається перерахунком по циклу.
Зауважимо, що невідомі, що не входять до циклу, цим перетворенням не зачіпаються, їх значення залишаються незмінними і кожне з них залишається або в групі базисних, або в групі вільних невідомих, як і до перерахунку.
З'ясуємо тепер, як перерахунок по циклу впливає на загальний обсяг витрат на перевезення та при якій умові ці витрати стають менше.
Нехай
Складемо тарифи, відповідні позитивним вершин циклу, і віднімемо з цієї суми суму тарифів, відповідних негативним вершин циклу; отриману різницю
Тепер, очевидно, ми можемо, укласти, що в цілому при перерахунку але циклу, відповідному вільному невідомому
Так, наприклад, для циклу
Значить, перерахунок з цього циклу знижує витрати. І дійсно, здійснивши такий перерахунок, ми отримуємо план, за яким обсяг перевезень в тонно-кілометрах становить
тоді як по вихідному планом він склав
Обчислення алгебраїчної суми тарифів для кожного з вільних невідомих можна робити без побудови відповідного циклу, користуючись, так званими, потенціалами. Припишемо кожній базі
так що
|
де
Знаючи потенціали, легко вирахувати алгебраїчну суму тарифів. Дійсно, якщо в алгебраїчній сумі тарифів по циклу, відповідному вільному невідомому
Так, наприклад, для циклу
Для базисних клітин сума потенціалів рядка і стовпця, в яких знаходиться ця клітина, дорівнює тарифом, відповідному цій клітці; якщо ж клітина для невідомого
|
називають непрямим тарифом цієї клітини. Отже, алгебраїчна сума тарифів для вільної клітини
|
З (4.3) випливає, що якщо непрямий тариф для даної вільної клітини більше її справжнього тарифу, то алгебраїчна сума тарифів по циклу, відповідному цій клітці, буде негативна, якщо ж непрямий тариф менший істинного, то алгебраїчна сума тарифів позитивна, і, нарешті, якщо непрямий тариф дорівнює істинному, то алгебраїчна сума тарифів дорівнює нулю.
Потенціали можна знайти з системи рівностей (4.1), розглядаючи їх як систему
Наприклад, для плану, отриманого за діагональному методу в розглянутій вище задачі, маємо
Система містить сім рівнянь з вісьмома невідомими. Вибираючи довільно значення
Поклавши, наприклад,
Знайдемо тепер непрямі тарифи для вільних клітин і порівняємо їх з істинними тарифами:
Для клітин з невідомими
Значення
Зауваження 1. Підраховуючи непрямі тарифи як суми відповідних потенціалів, корисно не пропускати і клітини з базисними невідомими (заповнені клітини). Для цих клітин сума потенціалів дорівнює істинному тарифом; останнє може служити перевіркою правильності знайдених значенні потенціалів.
Зауваження 2. Можна показати, що якщо суму всіх витрат за цим планом перевезень виразити через вільні невідомі [для цього треба виключити базисні невідомі з виразу для S, див. формулу (2.4)], то коефіцієнт при кожному з таких невідомих буде дорівнює алгебраїчній сумі тарифів по циклу, відповідному їй в таблиці перевезень. Це ще раз підтверджує, що перерахунок за циклами є специфічною формою застосування симплекс-методу до вирішення транспортної задачі.
5. Критерій оптимальності базисного розв'язку транспортної задачі. Методи відшукання оптимального рішення.
Зі сказаного в попередньому пункті випливає наступний критерій оптимальності базисного рішення транспортної задачі: якщо для деякого базисного плану перевезень алгебраїчні суми тарифів за циклами для всіх вільних клітин ненегативні, то цей план оптимальний.
Звідси випливає спосіб відшукання оптимального рішення транспортної задачі, що полягає в тому, що, маючи деякий базисне рішення, обчислюють алгебраїчні суми тарифів для всіх вільних клітин. Якщо критерій оптимальності виконаний, то дане рішення є оптимальним, якщо ж є клітини з негативними алгебраїчними сумами тарифів, то переходять до нового базису, виробляючи перерахунок по циклу, відповідному однієї з таких клітин. Отримане таким чином нове базисне рішення буде краще вихідного - витрати на його реалізацію будуть меншими. Для нового рішення також перевіряють здійснимість критерію оптимальності та в разі потреби знову здійснюють перерахунок по циклу для однієї з кліток з негативною алгебраїчною сумою тарифів і т.д.
Через кінцеве число кроків приходять до шуканого оптимальному базисного рішення.
У разі якщо алгебраїчні суми тарифів для всіх вільних клітин позитивні, ми маємо єдину оптимальне рішення, якщо ж алгебраїчні суми тарифів для всіх вільних клітин ненегативні, але серед них є алгебраїчні суми тарифів, рівні нулю, то оптимальне рішення не єдина: при перерахунку за циклом для клітини з нульовою алгебраїчною сумою тарифів ми отримаємо оптимальне ж рішення, але відмінне від вихідного (витрати по обох планів будуть однаковими).
У залежності від методів підрахунку алгебраїчних сум тарифів для вільних клітин розрізняють два методи відшукання оптимального вирішення транспортної задачі:
1. Розподільний метод. При цьому методі для кожної порожній клітини будують цикл і для кожного циклу безпосередньо обчислюють алгебраїчну суму тарифів.
2. Метод потенціалів. При цьому методі попередньо знаходять потенціали баз і споживачів, а потім обчислюють для кожної порожній клітини алгебраїчну суму тарифів за допомогою потенціалів.
Переваги методу потенціалів в порівнянні з розподільним методом полягають у тому, що відпадає необхідність побудови циклів для кожної з порожніх клітин і спрощується обчислення алгебраїчних сум тарифів. Цикл будується тільки один - той, за яким здійснюється перерахунок.
Застосовуючи метод потенціалів, можна говорити не про знак алгебраїчних сум тарифів, а про порівняння непрямих тарифів з істинними. Вимога неотрицательности алгебраїчних сум тарифів замінюється умовою, що непрямі тарифи не перевершують істинних.
Слід мати на увазі, що потенціали (так само як і цикли) для кожного нового базисного плану визначаються заново.
Вище розглядалася закрита модель транспортної задачі, з правильним балансом, коли виконується умова (1.3). У разі виконання (1.4) (відкрита модель) баланс транспортної задачі може порушуватися в 2-ух напрямках:
1. Сума запасів у пунктах відправлення перевищує суму поданих заявок (транспортна задача з надлишком запасів):
å а i> å b j (де i = 1 ,..., m; j = 1 ,..., n);
2. Сума поданих заявок перевищує наявні запаси (транспортна задача з надлишком заявок):
å а i <å b j (де i = 1 ,..., m; j = 1 ,..., n);
Розглянемо послідовно ці два випадки:
Транспортна задача з надлишком запасів.
Зведемо її до раніше розглянутої транспортної задачі з правильним балансом. Для цього, понад наявні n пунктів призначення В 1, B 2, ... , B n, введемо ще один, фіктивний, пункт призначення B n +1, якому припишемо фіктивну заявку, рівну надлишку запасів над заявками
b n +1 = å а i - å b j (де i = 1 ,..., m; j = 1 ,..., n),
а вартість перевезень з усіх пунктів відправлення у фіктивний пункт призначення b n +1 будемо вважати рівною нулю. Введенням фіктивного пункту призначення B n +1 з його заявкою b n +1 ми зрівняли баланс транспортної задачі, і тепер її можна вирішувати, як звичайну транспортну задачу з правильним балансом.
Транспортна задача з надлишком заявок.
Це завдання можна звести до звичайної транспортної задачі з правильним балансом, якщо ввести фіктивний пункт відправлення A m +1 з запасом a m +1 рівним невистачаючому запасу, і вартість перевезень з фіктивного пункту відправлення в усі пункти призначення прийняти рівною нулю.
6. Завдання, двоїста до транспортної.
Побудуємо завдання, двоїсту до транспортної. З цією метою згадаємо, що кожному пункту відправлення
|
У той же час, кожному обмеження з (6.1) зіставляється певна невідома в двоїстої задачі. Тим самим встановлюється відповідність між усіма пунктами
Позначимо невідому в двоїстої задачі, що відповідає пункту відправлення
Кожному невідомому в транспортній завданню відповідає обмеження, що зв'язує невідомі в двоїстої задачі. Невідоме
|
Права частина нерівності (6.2) дорівнює
Оптимізується форма двоїстої задачі має вигляд
|
Таким чином, завдання двоїста до транспортної формулюється наступним чином. При обмеженнях (6.2) максимізувати формулу (6.3). Підкреслимо, що знак значень невідомих
Припустимо, що нам відомо деяке дозволене базисне рішення транспортної задачі, в якому всі базисні невідомі суворо позитивні. Це рішення оптимально лише в тому випадку, коли відповідна їй система виявляється спільної. Ця система виникає із системи (6.2), якщо в ній все нерівності, що відповідають базисним невідомим
У підсумку приходимо до співвідношення:
|
Тим самим ми переконуємося, що ознака оптимальності в роботі за методом потенціалів збігається з необхідним і достатнім умовою оптимальності.
7.Прімер рішення транспортної задачі.
У місті N є 4 склади А i, на яких зберігається тканину (в рулонах) і 5 магазинів B j, що займаються продажем тканини. Нижче, у таблиці, наведені дані щодо кількості рулонів на кожному складі, запити магазинів і вартість перевезення одного рулону з А i в B j. Необхідно скласти такий план перевезень, при якому запити магазинів будуть задоволені при мінімальної сумарної вартості перевезень.
Магазини Склад | B 1 (B 1 = 40) | B 2 (B 2 = 50) | B 3 (B 3 = 15) | B 4 (B 4 = 75) | B 5 (B 5 = 40) |
А 1 (а 1 = 50) | 1,0 | 2,0 | 3,0 | 2,5 | 3,5 |
А 2 (а 2 = 20) | 0,4 | 3,0 | 1,0 | 2,0 | 3,0 |
А 3 (а 3 = 75) | 0,7 | 1,0 | 1,0 | 0,8 | 1,5 |
А 4 (а 4 = 80) | 1,2 | 2,0 | 2,0 | 1,5 | 2,5 |
Магазини Склад | B 1 (B 1 = 40) | B 2 (B 2 = 50) | B 3 (B 3 = 15) | B 4 (B 4 = 75) | B 5 (B 5 = 40) | B 6 (B 6 = 5) |
А 1 (а 1 = 50) | 1,0 | 2,0 | 3,0 | 2,5 | 3,5 | 0 |
А 2 (а 2 = 20) | 0,4 | 3,0 | 1,0 | 2,0 | 3,0 | 0 |
А 3 (а 3 = 75) | 0,7 | 1,0 | 1,0 | 0,8 | 1,5 | 0 |
А 4 (а 4 = 80) | 1,2 | 2,0 | 2,0 | 1,5 | 2,5 | 0 |
x 11 x 12 x 13 x 14 x 15 x 16
x 21 x 22 x 23 x 24 x 25 x 26
X = x 31 x 32 x 33 x 34 x 35 x 36 - матриця перевезень.
x 41 x 42 x 43 x 44 x 45 x 46
min (x 11 +2 x 12 +3 x 13 +2,5 x 14 +3,5 x 15 +0,4 x 21 +3 x 22 + x 23 +2 x 24 +3 x 25 +0,7 x 31 + x 32 + x 33 +0 , 8x 34 +1,5 x 35 + +1,2 x 41 +2 x 42 +2 x 43 +1,5 x 44 +2,5 x 45) (1)
x 11 + x 12 + x 13 + x 14 + x 15 + x 16 = 50
x 21 + x 22 + x 23 + x 24 + x 25 + x 26 = 20
x 31 + x 32 + x 33 + x 34 + x 35 + x 36 = 75
x 41 + x 42 + x 43 + x 44 + x 45 + x 46 = 80
x 11 + x 21 + x 31 + x 41 = 40 (2)
x 12 + x 22 + x 32 + x 42 = 50
x 13 + x 23 + x 33 + x 43 = 15
x 14 + x 24 + x 34 + x 44 = 75
x 15 + x 25 + x 35 + x 45 = 40
x 16 + x 26 + x 36 + x 46 = 5
x ij ≥ 0 (i = 1,2,3,4; j = 1,2,3,4,5,6) (3)
Двоїста ЗЛП:
max (50u 1 +20 u 2 +75 u 3 +80 u 4 +40 v 1 +50 v два +15 v три +75 v 4 +40 v 5 +5 v 6) (1 *)
u 2 + v 1 ≤ 0,4 u 2 + v 2 ≤ 3 u 2 + v 3 ≤ 1 u 2 + v 4 ≤ 2 u 2 + v 5 ≤ 3 u 2 + v 6 ≤ 0 |
u 3 + v 1 ≤ 0,7 u 3 + v 2 ≤ 1 u 3 + v 3 ≤ 1 u 3 + v 4 ≤ 0,8 u 3 + v 5 ≤ 1,5 u 3 + v 6 ≤ 0 |
u 4 + v 1 ≤ 1,2 u 4 + v 2 ≤ 2 u 4 + v 3 ≤ 2 u 4 + v 4 ≤ 1,5 u 4 + v 5 ≤ 2,5 u 4 + v 6 ≤ 0 |
u 1 + v 1 ≤ 1
u 1 + v 2 ≤ 2
u 1 + v 3 ≤ 3 (2 *)
u 1 + v 4 ≤ 2,5
u 1 + v 5 ≤ 3,5
u 1 + v 6 ≤ 0
u i, v j - довільні (i = 1,2,3,4; j = 1,2,3,4,5,6) (3 *)
Будемо шукати початковий план за методом найменшої вартості:
1) x 21 = 20 і 2-й рядок ісключаем.2) x 31 = 20 і перший стовпець виключаємо.
3) x 34 = 55 і 3-й рядок ісключаем.4) x 44 = 20 і 4-ий стовпець виключаємо.
5) x 12 = 50 і 1-й рядок і 2-ий стовпець виключаємо і x 32 = 0. 6) x 43 = 150 і 3-ий стовпець ісключаем.7) x 45 = 40 і 5-ий стовпець ісключаем.x 46 = 5.Составім таблицю. Тут і далі в нижньому правому куті записуємо значення перевезення.
Магазини Склад | B 1 (B 1 = 40) | B 2 (B 2 = 50) | B 3 (B 3 = 15) | B 4 (B 4 = 75) | B 5 (B 5 = 40) | B 6 (B 6 = 5) | ||||||||
А 1 (а 1 = 50) | 1,0 |
| 3,0 | 2,5 | 3,5 | 0 | ||||||||
А 2 (а 2 = 20) | 0,4
| 3,0 | 1,0 | 2,0 | 3,0 | 0 | ||||||||
А 3 (а 3 = 75) | 0,7
|
| 1,0 |
| 1,5 | 0 | ||||||||
А 4 (а 4 = 80) | 1,2 | 2,0 |
|
|
|
|
D 1 = 2 • 50 +0,4 • 20 +0,7 • 20 +0,8 • 1955 +2 • 15 +1,5 • 20 +2,5 • 40 = 326.
Будемо покращувати цей план методом потенціалів: u i - потенціал А i, v j - потенціал B j. Тоді u 1 + v 2 = 2, u 2 + v 1 = 0,4, u 3 + v 1 = 0,7, u 3 + v 2 = 1, u 3 + v 4 = 0,8, u 4 + v 3 = 2, u 4 + v 4 = 1,5, u 4 + v 5 = 2,5, u 4 + v 6 = 0.Положім u 1 = 0, тоді v 2 = 2, u 3 =- 1 , v 1 = 1,7, v 4 = 1,8, u 2 =- 1,3, u 4 =- 0,3, v 3 = 2,3, v 5 = 2,8, v 6 = 0, 3.Составім таблицю:
Магазини Склад | B 1 (B 1 = 40) v 1 = 1,7 | B 2 (B 2 = 50) v 2 = 2 | B 3 (B 3 = 15) v 3 = 2,3 | B 4 (B 4 = 75) v 4 = 1,8 | B 5 (B 5 = 40) v 5 = 2,8 | B 6 (B 6 = 5) v 6 = 0,3 | ||||||||||||||||||||
А 1 (а 1 = 50) U 1 = 0 | 1,0 | 2,0 | 3,0 | 2,5 | 3,5 | 0 | ||||||||||||||||||||
А 2 (а 2 = 20) U 2 =- 1,3 | 0,4 | 3,0 | 1,0 | 2,0 | 3,0 | 0 | ||||||||||||||||||||
U 3 =- 1 |
|
|
|
|
| 0 | ||||||||||||||||||||
U 4 =- 0,3 |
|
|
|
|
|
|
u 4 + v 1-c 41 = 0,2> 0. => За критерієм оптимальності, перший план не оптимальний. Далі max (0,7, 0,3, 0,3, 0,3; 0,2) = 0,7. => Помістимо перевезення в клітку А 1 В 1, змістивши 20 = min (20,50) по циклу, вказаною в таблиці штрихом. Отримаємо нову таблицю. Знайдемо потенціали: u 1 + v 1 = 1, u 1 + v 2 = 2, u 2 + v 1 = 0,4, u 3 + v 2 = 1, u 3 + v 4 = 0,8, u 4 + v 3 = 2, u 4 + v 4 = 1,5, u 4 + v 5 = 2,5, u 4 + v 6 = 0. Покладемо u 1 = 0, тоді v 1 = 1, u 2 =- 0,6, v 2 = 2, v 4 = 1,8, u 3 =- 1, u 4 =- 0,3, v 3 = 2 , 3, v 5 = 2,8, v 6 = 0,3. Складемо таблицю:
Магазини Склад | B 1 (B 1 = 40) v 1 = 1 | B 2 (B 2 = 50) v 2 = 2 | B 3 (B 3 = 15) v 3 = 2,3 | B 4 (B 4 = 75) v 4 = 1,8 | B 5 (B 5 = 40) v 5 = 2,8 | B 6 (B 6 = 5) v 6 = 0,3 | ||||||||||||||||||||||
U 1 = 0 |
|
|
|
|
| 0 | ||||||||||||||||||||||
U 2 =- 0,6 |
|
|
|
|
| 0 | ||||||||||||||||||||||
U 3 =- 1 |
|
|
|
|
| 0 | ||||||||||||||||||||||
U 4 =- 0,3 |
|
|
|
|
|
|
D 2 = 1 • 20 +2 • 30 +0,4 • 20 +1 • 20 +0,8 • 1955 +2 • 15 +1,5 • 20 +2,5 • 40 = 312.
Маємо: u 1 + v 6-c 16 = 0,3> 0, u 2 + v 3-c 23 = 0,7> 0, u 3 + v 3-c 33 = 0,3> 0, u 3 + v 5-c 35 = 0,3> 0. => За критерієм оптимальності, другий план не оптимальний. Далі max (0,3; 0,7; 0,3; 0,3) = 0,7 => Помістимо перевезення в клітку А 2 В 3, змістивши 15 = min (20,30,55,15) по циклу, вказаною в таблиці штрихом. Отримаємо нову таблицю. Знайдемо потенціали: u 1 + v 1 = 1, u 1 + v 2 = 2, u 2 + v 1 = 0,4, u 3 + v 2 = 1, u 3 + v 4 = 0,8, u 2 + v 3 = 1, u 4 + v 4 = 1,5, u 4 + v 5 = 2,5, u 4 + v 6 = 0. Покладемо u 1 = 0, тоді v 1 = 1, u 2 =- 0,6, v 2 = 2, v 4 = 1,8, u 3 =- 1, u 4 =- 0,3, v 3 = 1 , 6, v 5 = 2,8, v 6 = 0,3. Складемо таблицю:
Магазини Склад | B 1 (B 1 = 40) v 1 = 1 | B 2 (B 2 = 50) v 2 = 2 | B 3 (B 3 = 15) v 3 = 1,6 | B 4 (B 4 = 75) v 4 = 1,8 | B 5 (B 5 = 40) v 5 = 2,8 | B 6 (B 6 = 5) v 6 = 0,3 | ||||||||||||||||||||
U 1 = 0 |
|
|
|
|
| 0 | ||||||||||||||||||||
U 2 =- 0,6 |
|
|
|
|
| 0 | ||||||||||||||||||||
U 3 =- 1 |
|
|
|
|
| 0 | ||||||||||||||||||||
U 4 =- 0,3 |
|
|
|
|
|
|
D 3 = 1 • 35 +2 • 15 +0,4 • 5 +1 • 15 +0,8 • 40 +1 • 35 +1,5 • 35 +2,5 • 40 = 301,5.
Маємо: u 1 + v 6-c 16 = 0,3> 0, u 3 + v 5-c 35 = 0,3> 0. => За критерієм оптимальності, третій план не оптимальний. Далі max (0,3, 0,3) = 0,3. => Помістимо перевезення в клітку А 3 В 5, змістивши 40 = min (40,40) по циклу, вказаною в таблиці штрихом. Отримаємо нову таблицю. Щоб четвертий план був невиродженим, залишимо в клітці А 4 В 5 нульову перевезення. Знайдемо потенціали: u 1 + v 1 = 1, u 1 + v 2 = 2, u 2 + v 1 = 0,4, u 3 + v 2 = 1, u 4 + v 5 = 2,5, u 2 + v 3 = 1, u 4 + v 4 = 1,5, u 3 + v 5 = 1,5, u 4 + v 6 = 0. Покладемо u 1 = 0, тоді v 1 = 1, u 2 =- 0,6, v 2 = 2, v 4 = 1,5, u 3 =- 1, u 4 = 0, v 3 = 1,6, v 5 = 2,5, v 6 = 0. Складемо таблицю:
Магазини Склад | B 1 (B 1 = 40) v 1 = 1 | B 2 (B 2 = 50) v 2 = 2 | B 3 (B 3 = 15) v 3 = 1,6 | B 4 (B 4 = 75) v 4 = 1,5 | B 5 (B 5 = 40) v 5 = 2,5 | B 6 (B 6 = 5) v 6 = 0 |
|
U 1 = 0
|
|
|
|
|
|
|
|
U 2 =- 0,6
|
|
|
|
|
|
|
|
U 3 =- 1
|
|
|
|
|
|
|
|
U 4 = 0
|
|
|
|
|
|
|
|
Для всіх клітин останньої таблиці виконані умови оптимальності:
1) u i + v j-с ij = 0 для клітин, зайнятих перевезеннями;
2) u i + v j-с ij ≤ 0 для вільних клітин.
Незмістовні відповіді:
Прямий ЗЛП:
35 15 0 0 0 0
5 0 15 0 0 0
X = 0 35 0 0 40 0
0 0 0 75 0 5
min = 289,5.
Двоїстої ЗЛП:
U 1 = 0; U 2 =- 0,6; U 3 =- 1; U 4 = 0; V 1 = 1; V 2 = 2; V 3 = 1,6; V 4 = 1,5; V 5 = 2,5; V 6 = 0.
max = 289,5.
Так як min = max, то за критерієм оптимальності знайдені оптимальні рішення прямої і двоїстої ЗЛП. Змістовну відповідь: Оптимально перевозити так:
З А 1 в B 1 - 35 рулонів полотна;
З А 1 в B 2 - 15 рулонів полотна;
З А 2 в B 1 - 5 рулонів полотна;
З А 2 в B 3 - 15 рулонів полотна;
З А 3 в B 2 - 35 рулонів полотна;
З А 3 в B 5 - 40 рулонів полотна;
З А 4 в B 4 - 75 рулонів полотна.
При цьому вартість мінімальна і складе D min = 289,5. 5 рулонів полотна необхідно залишити на складі А 4 для їх подальшого перевезення в інші магазини.
8.Виводи.
У курсовій роботі викладені основні підходи і методи вирішення транспортної задачі, що є однією з найбільш поширених завдань лінійного програмування. Рішення даної задачі дозволяє розробити найбільш раціональні шляхи і засоби транспортування товарів, усунути надмірно далекі, зустрічні, повторні перевезення. Все це скорочує час просування товарів, зменшує витрати підприємств і фірм, пов'язані із здійсненням процесів постачання сировиною, матеріалами, паливом, обладнанням і т.д.
Алгоритм і методи вирішення транспортної задачі можуть бути використані при вирішенні деяких економічних завдань, які не мають нічого спільного з транспортуванням вантажу. У цьому випадку величини тарифів c ij мають різний зміст в залежності від конкретної економічної задачі. До таких задач відносяться наступні:
- Оптимальне закріплення за верстатами операцій по обробці деталей. У них c ij є таким економічним показником, як продуктивність. Завдання дозволяє визначити, скільки часу і на який операції потрібно використовувати кожен з верстатів, щоб обробити максимальну кількість деталей. Так як транспортна задача вимагає знаходження мінімуму, то значення c ij беруться з негативним знаком;
- Оптимальні призначення, або проблема вибору. Є m механізмів, які можуть виконувати m різних робіт з продуктивністю c ij. Завдання дозволяє визначити, який механізм і на яку роботу треба призначити, щоб домогтися максимальної продуктивності;
- Завдання про скорочення виробництва з урахуванням сумарних витрат на виготовлення і транспортування продукції;
- Збільшення продуктивності автомобільного транспорту за рахунок мінімізації порожнього пробігу. Зменшення порожнього пробігу скоротить кількість автомобілів для перевезень, збільшивши їх продуктивність;
- Вирішення завдань з допомогою методу заборони перевезень. Використовується в тому випадку, якщо вантаж від деякого постачальника з якихось причин не може бути відправлений одному зі споживачів. Дане обмеження можна врахувати, присвоївши відповідній клітині досить велике значення вартості, тим самим у цю клітку не будуть проводитися перевезення.
Таким чином, важливість вирішення даного завдання для економіки безсумнівна. Приємно усвідомлювати, що біля витоків створення теорії лінійного програмування і рішення, в тому числі і транспортної задачі, стояв російський учений - Леонід Віталійович Канторович.
Список використовуваної літератури:
1. Кузнєцов А.В., Сакович В.А., Холод Н.І. "Вища математика. Математичне програмування ", Мінськ, Вишейшая школа, 2001р.
2. Красс М.С., Чуприна Б.П. "Основи математики і її застосування в економічній освіті", Видавництво "Дело", Москва 2001р.
3. В.І. Єрмаков "Загальний курс вищої математики для економістів", Москва, Інфра-М, 2000р.
Цей текст може містити помилки.
Математика | Курсова
Схожі роботи:
Розв язок задач лінійного програмування Задача планування виробництва
Транспортна задача
Транспортна задача з обмеженнями можливих транспортних засобів
Основні поняття математичного програмування Побудова моделі задачі лінійного програмування
Завдання лінійного програмування
Завдання лінійного програмування
Завдання лінійного програмування
Розвязок задачі лінійного програмування
Розвязання задач лінійного програмування