Вирішення транспортної задачі з використанням електроних таблиц Micrsoft Excel

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Міністерство освіти і науки, молоді та спорту України

ПОЛТАВСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

імені ЮРІЯ КОНДРАТЮКА

кафедра комп'ютерної інженерії

Розрахунково-графічна робота

з дисципліни «Методи оптимізації»

«Вирішення транспортної задачі з використанням електроних таблиц Micrsoft Excel»

Варіант № 12

Виконавець: студент(ка) навч. групи 2КСМв

Криворучко О.М.

Перевірив: : к.т.н., доцент Сомов С.В

Полтава 2015

Вихідні дані задачі:

вектор А = (a1, a2, a3) запасів постачальників:

- а1 = 200; - а2 = 150; - а3 = 180;

вектор B = (b1, b2, b3, b4, b5)

запитів споживачів: - b1 = 110; - b2 = 90; - b3 = 120; - b4 = 80; - b5 = 130;

матриці вартостей С:

6	9	11	15	12
5	8	10	3	7
16	10	8	2	4

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

Кожна людина щодня, не завжди усвідомлюючи це, вирішує проблему: як одержати найбільший ефект, володіючи обмеженими засобами. Наші засоби і ресурси завжди обмежені. Життя було б менш цікаве, якби це було не так. Не важко виграти бій, маючи армію в 10 разів більшу, ніж у супротивника. Щоб досягти найбільшого ефекту, маючи обмежені засоби, треба скласти план чи програму дій. Раніше план в таких випадках складався «на око». У середині XX століття був створений спеціальний математичний апарат, що допомагає це робити «по науці».

Відповідний розділ математики називається математичним програмуванням. Слово «програмування» тут і в аналогічних термінах («лінійне програмування», «динамічне програмування» і т.п.) зобов'язане почасти історичному непорозумінню, почасти неточному перекладу з англійської мови: mathematical programming, що означає розроблення на основі математичних розрахунків програми дій для досягнення обраної мети. З програмуванням для ЕОМ математичне програмування має лише те спільне, що більшість виникаючих на практиці задач математичного програмування занадто громіздкі для ручного розрахунку, тому розв'язати їх можна тільки за допомогою ЕОМ, попередньо склавши програму.

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

Справжнім початком математичного програмування в сучасному розумінні вважають 1939р., коли була надрукована брошура Леоніда Віталійовича Канторовича «Математичні методи організації і планування виробництва». Наприкінці 30-х років в Ленінградському університеті ним уперше були сформульовані та досліджувались основні задачі, критерії оптимальності, економічна інтерпретація, методи розв'язання та геометрична інтерпретація результатів розв'язання задач лінійного програмування. Але, оскільки методи, викладені Л.В.Канторовичем, були мало придатні для ручного рахунку, а швидкодіючих обчислювальних машин у той час не існувало, то роботи Л.В.Канторовича залишилася майже не поміченими.

В автобіографії, представленої в Нобелівський комітет, Леонід Віталійович Канторович розповідає про події, що трапилися в 1939 році. До нього, 26-літнього професора-математика, звернулися за консультацією співробітники лабораторії планерного тресту, яким потрібно було вирішити задачу про найбільш вигідний розподіл матеріалу між верстатами. Ця задача зводилася до відшукання максимуму лінійної функції, заданої на багатограннику. Максимум такої функції досягався у вершині, однак число вершин у цій задачі досягало мільярду. Тому простий перебір вершин не підходив. Леонід Віталійович писав: «Виявилось, що ця задача не є випадковою. Я знайшов велике число різноманітних по змісту задач, що мають аналогічний математичний характер: найкраще використання посівних площ, вибір завантаження устаткування, раціональний розкрій матеріалу, розподіл транспортних вантажопотоків... Це наполегливо спонукало мене до пошуку ефективного методу їхнього розв'язання». І вже влітку 1939 року була здана в набір книга Л.В.Канторовича «Математичні методи організації і планування виробництва», в якій закладалися основи того, що нині називається математичною економікою.

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

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

Приблизно в цей час Купманс довідався, що ще до війни в далекій Росії вже було зроблено щось схоже на розробку основ лінійного програмування. Як легко було б Данцигові і Купмансу проігнорувати цю інформацію! Маленька книжечка, видана незначним тиражем, звернена навіть не до економістів, а до організаторів виробництва, з мінімумом математики, без чітко описаних алгоритмів, без доведень теорем - словом, чи варто брати таку книжку до уваги. Але Купманс наполягає на перекладі і виданні на заході книги Канторовича. Його ім'я й ідеї стають відомі всім. У своїй монографії Дж.Данциг зазначає, що Л.В.Канторовича слід визнати першим, хто виявив, що широке коло важливих виробничих задач може бути подане у чіткому математичному формулюванні, яке уможливлює підхід до таких задач з кількісного боку та розв'язання їх чисельними методами.

Л.В.Канторович продовжує писати математичні роботи, навіяні економічними ідеями, бере участь і в конкретних розробках на виробництві. При цьому (одночасно з Данцигом, але, не знаючи його робіт) він розробляє метод, пізніше названий симплексним методом. Як тільки в 50-і роки утвориться маленький просвіт, і дещо з забороненого стає можливим, він організовує групу студентів на економічному факультеті Ленінградського університету для навчання методам оптимального планування. А починаючи з 1960 року, Леонід Віталійович займається тільки економікою і позв'язаними з нею математичними проблемами. Його внесок в цій області був відзначений Ленінською премією в 1965 році, а згодом, разом з Купмасом, Л.В.Канторович одержує Нобелівську премію в 1975 році за «внесок у розробку теорії й оптимального використання ресурсів в економіці».

Періодом найінтенсивнішого розвитку математичного програмування є п'ятдесяті роки. У цей час з'являються розробки нових алгоритмів, теоретичні дослідження з різних напрямків математичного програмування: 1951 року -- праця Г.Куна і А.Таккера, в якій наведено необхідні та достатні умови оптимальності нелінійних задач; 1954 року -- Чарнес і Лемке розглянули наближений метод розв'язання задач з сепарабельним опуклим функціоналом та лінійними обмеженнями; 1955 року -- ряд робіт, присвячених квадратичному програмуванню. У п'ятдесятих роках сформувався новий напрямок математичного програмування -- динамічне програмування, значний вклад у розвиток якого вніс американський математик Р.Белман.

На жаль, у період найбурхливішого розвитку математичного програмування за кордоном у Радянському Союзі не спостерігалося значних досягнень через штучні ідеологічні обмеження. Відродження досліджень з математичного моделювання економіки почалося в 60-80-тих роках і стосувалося опису «системи оптимального функціонування соціалістичної економіки». Серед радянських вчених того періоду слід виокремити праці В.С.Немчинова, В.В.Новожилова, Н.П.Федоренка, С.С.Шаталіна, В.М.Глушкова, В.С.Михалевича, Ю.М.Єрмольєва та ін.

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

Поняття задачі лінійного програмування та різні форми її задання

Лінійне програмування є однією з основних частин розділу сучасної математики, який називається «математичне програмування». В загальній постановці задачі цього розділу виглядають наступним чином. Існують деякі змінні і функція цих змінних ) , яка називається цільовою функцією. Ставиться задача: знайти екстремум (максимум або мінімум) цільової функції при умові що значення змінних належать деякій області G. В залежності від виду функції f (x) і області G виділяють різні розділи математичного програмування: квадратичне, опуклу, цілочисельне програмування тощо. Лінійне програмування характеризується тим, що а) функція м є лінійною; б) область G визначається системою лінійних рівнянь або нерівностей.

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

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

і перетворюють в екстремум (максимум або мінімум) лінійну функцію

.

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

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

З цього випливають три форми задач лінійного програмування:

1) загальна задача лінійного програмування;

2) стандартна ( симетрична);

3) канонічна.

Загальна задача лінійного програмування подається у вигляді:

(3.1)

за умов:

( 3.2)

…, . (3.3)

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

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

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

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

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

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

Стандартна (симетрична) задача лінійного програмування подається у вигляді: за умов:

, або .

…, .

Задачу (3.1)-(3.3) можна легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (3.2) всі невід'ємні, а всі обмеження є рівностями.

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

то останню завжди можна звести до рівності , увівши додаткову змінну :

.

Аналогічно обмеження виду

зводиться до рівності, віднімаючи від лівої частини додаткову змінну :

,

Така заміна нерівностей рівняннями за допомогою введення додаткових змінних не змінить розв'язку початкової задачі.

Задачі лінійного програмування можна розв'язувати графічно і аналітично.

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

Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості змінних необхідно застосовувати інший метод. З властивостей розв'язків задачі лінійного програмування відомо: оптимальний розв'язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв'язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (допустимих планів задачі, які ще називають опорними). Порівняння вершин багатогранника можна здійснювати тільки після відшукання якоїсь однієї з них, тобто знайшовши початковий опорний план. Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів . Отже, загальна кількість опорних планів визначається кількістю комбінацій . Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Тому необхідне використання методу, який уможливлював би скорочення кількості обчислень. 1949 року такий метод був запропонований американським вченим Дж.Данцігом -- так званий симплексний метод, або симплекс-метод.

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

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

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

Правило побудови двоїстої задачі

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

Якщо пряма задача лінійного програмування подана у стандартному вигляді, то двоїста задача утворюється за такими правилами:

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

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

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

4. Коефіцієнтами при змінних цільової функції двоїстої задачі є вільні члени системи обмежень прямої задачі.

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

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

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

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

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

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

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

Економічна і математична постановки транспортної задачі

Класична транспортна задача лінійного програмування формулюється так: деякий однорідний продукт, що знаходиться у m постачальників А в обсягах ,,…, одиниць відповідно необхідно перевезти n споживачам в обсягах ,,…, одиниць. При цьому виконується умова, що загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі вартості перевезень одиниці продукції від кожного -го постачальника до кожного -го споживача, що подані як елементи матриці виду: = .

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

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

Запишемо її математичну модель. Позначимо через обсяг продукції, що перевозиться від постачальника до споживача (;). Тоді умови задачі зручно подати у вигляді такої таблиці:

Таблиця 7.1.

Споживачі Постачальники			…
			…
				…
				…
…	…	…	…	…	…
				…

Мають виконуватися такі умови:

1) сумарний обсяг продукції, що вивозиться з кожного -го пункту, має дорівнювати запасу продукції в даному пункті:

2) сумарний обсяг продукції, що ввезений кожному -му споживачеві, має дорівнювати його потребам:

3) сумарна вартість всіх перевезень повинна бути мінімальною:

Очевидно, що .

У скороченій формі запису математична модель транспортної задачі за критерієм вартості перевезень має такий вигляд:

(7.1)

за обмежень:

; (7.2)

; (7.3)

( ; ). (7.4)

У розглянутій задачі має виконуватися умова:

. (7.5)

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

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

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

Теорема (умова існування розв'язку транспортної задачі): необхідною і достатньою умовою існування розв'язку транспортної задачі(7.1)--(7.4) є її збалансованість: .

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

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

Як згадувалося вище, транспортна задача (7.1)-(7.4) є звичайною задачею лінійного програмування і може бути розв'язана симплексним методом, однак особливості побудови математичної моделі транспортної задачі дають змогу розв'язати її простіше. Легко помітити, що всі коефіцієнти при змінних у рівняннях (7.2), (7.3) дорівнюють одиниці, а сама система обмежень (7.2), (7..3) задана в канонічній формі. Крім того, система обмежень (7.2), (7.3) складається з mn невідомих та m+n рівнянь, які пов'язані між собою співвідношенням (7.8). Якщо додати відповідно праві та ліві частини систем рівнянь (7.2) та (7.3), то отримаємо два однакових рівняння:

;

.

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

Методи побудови опорного плану транспортної задачі

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

Існують такі методи:

· північно-західного кута,

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

	Постачальники
Споживачі	B1	B2	B3	B4	B5	Потреби	V
A1	110	6	90	9		11		15		12
											200
A2		5		8	120	10	30	3		7
											150
A3		16		10		8	50	2	130	4
						7					180
Запаси	110	90	120	80	130	530
U

Цільова функція Fцільова= 110*6 +90*9+120*10+30*3+50*2+130*4=3380 у.о.

Одержаний результат оптимальний?

Перевіремо

Кожному поставщику В _i ставимо у відповідність число - u _i , назвимо потенціалом поставщика.

Кожному споживачу А _j ставимо у відповідність деяке число - v _j , ставимо у відповідність споживача.

2	Постачальники
Споживачі	B1	B2	B3	B4	B5	Потреби	V
A1	110	6	90	9	1	11	3	15	7	12		0
											200
A2	-1	5	-1	8	120	10	30	3	2	7		0
											150
A3	11	16	2	10	-1	8	50	2	130	4		-1
						7					180
Запаси	110	90	120	80	130	530
U	6	9	10	3	5

Для задіяного маршруту, сума потенціалів поставщика и споживача рівна тарифу задіянного Значення одного потенціалу необхідно задати. Пусть v₁ = 0. Послідовно знайдемо значення потенціалов.

A1B1	v1+u1=6	u1=6-v1=6
A1B2	v1+u2=9	u2=9-v1=9
v2=0
A2B3	v2+u3=10	u3=10
A2B4	v2+u4=3	u4=3
A3B4	v3+u4=2	v3=-1
A3B5	v3+u5=4	u5=5
Знайдемо оцінки незадіяних маршрутів, на таблиці я їх позначу курсивом та підчеркуванням( наприклад 6). A2B1 : Д21 = 5-6=-1 A3B1 : Д31 =16- 5=11 A2B2 : Д22 = 8-9=-1 A3B2 : Д32 =10- 8=2 A1B3 : Д13 = 11-10=1 A3B3 : Д33 =8-9=-1 A1B5 : Д15 =12-5=7 A2B5 : Д25 =7-5=2

Є від'ємні результати,тому можна одержати результат, як мінімум не гірше, за попередій

Крок 2.

Поетапно виберемо ті ячейки, Д_ij від`ємні, відмітивши всі рядом стоячі заповнені ячейки.

4	Постачальники
Споживачі	B1	B2	B3	B4	B5	Потреби	V
A1	110	6	90	9		11		15		12
						1		3		7	200
A2		5		8	120-50	10	30+50	3		7
		-1		-1							150
A3		16		10	0+50	8	50-50	2	130	4
		11		2		-1				2	180
Запаси	110	90	120	80	130	530
U

Одержимо:

5	Постачальники
Споживачі	B1	B2	B3	B4	B5	Потреби	V
A1	110	6	90-70	9	0+70	11		15		12
						1		3		7	200
A2		5	0+70	8	70-70	10	80	3		7
		-1		-1							150
A3		16		10	50	8	0	2	130	4
		11		2		-1				2	180
Запаси	110	90	120	80	130	530
U

Одержимо

4	Постачальники
Споживачі	B1	B2	B3	B4	B5	Потреби	V
A1	110-70	6	20+70	9	70	11		15		12
						1		3		7	200
A2	0+70	5	70-70	8	0	10	80	3		7
		-1		-1							150
A3		16		10	50	8	0	2	130	4
		11		2		-1				2	180
Запаси	110	90	120	80	130	530
U

Одержимо:

4	Постачальники
Споживачі	B1	B2	B3	B4	B5	Потреби	V
A1	40	6	90	9	70	11	11	15	4	12		0
											200
A2	70	5	0	8	0	10	80	3	0	7		-1
											150
A3	13	16		10	50	8	1	2	130	4		-3
											180
Запаси	110	90	120	80	130	530
U	6	9	11	4	8

Підрахуємо цільову функцію:

Fцільова=40*6+70*5+90*9+70*11+50*8+80*3+130*4=3330

Аналогічно до попереднього разу визначимо потенціали та їх різницю в пустих клітинках, прийнявши v₁=0

З таблиці видно, що немає від»ємних значень Д_ij, тому данне значення цільової функції є мінімальне.

3	Постачальники
Споживачі	B1	B2	B3	B4	B5	Потреби
A1	40	6	90	9	70	11		15		12
						1		3		7	200
A2	70	5		8		10	80	3		7
											150
A3		16		10	50	8		2	130	4
		11		2		-1				2	180
Запаси	110	90	120	80	130	530

F_min = 3330 у.о.

· мінімальної вартості,

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

· подвійної переваги

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

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

· метод апроксимації Фотеля.

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

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

Метод апроксимації Фогеля дає змогу особливо для задач великих розмірностей скласти найкращий опорний план.

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

Метод потенціалів розв'язування транспортної задач

Задача, двоїста до транспортної. Один із способів розв'язування транспортної задачі ґрунтується на розгляді двоїстої задачі.

Розглянемо транспортну задачу (7.1-7.4).

Позначимо змінні двоїстої задачі, які відповідають рівнянням (7.2), через , а для рівнянь (7.3) -- через . Оскільки всі обмеження транспортної задачі є рівняннями, то пара спряжених задач є несиметричною і ніякі обмеження на знаки змінних двоїстої задачі та не накладаються.

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

(7.3.1)

(7.3.2)

Згідно з загальними правилами побудови двоїстих задач маємо:

(7.3.3)

за умов

(7.3.4)

Змінні та задачі (7.3.3), (7.3.4) двоїстої до транспортної мають назву потенціалів.

Сформулюємо другу теорему двоїстості для задач (7.1-7.4) та (7.3.3)-(7.3.4).

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

1) (7.3.5)

2) (7.3.6)

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

Перша умова виконується у двох випадках:

а) якщо . Другий співмножник бо за умовою ();

б) якщо , то за умовою транспортної задачі , тоді ().

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

Теорема (умова оптимальності опорного плану транспортної задачі). Якщо для деякого опорного існують числа та , для яких виконуються умови:

1) , ;

2) ,

для всіх , то він є оптимальним планом транспортної задачі.

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

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

1. Визначення типу транспортної задачі (відкрита чи закрита). За необхідності слід звести задачу до закритого типу.

2. Побудова першого опорного плану транспортної задачі одним з відомих методів.

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

4. Перевірка плану транспортної задачі на оптимальність.

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

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

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

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

4.4. Побудова циклу і перехід до наступного опорного плану. Вибрана порожня клітина разом з іншими заповненими становить , отже, з цих клітин обов'язково утвориться цикл. У межах даного циклу здійснюють перерахування, які приводять до перерозподілу постачань продукції. Кожній вершині циклу приписують певний знак, причому вільній клітинці - знак «+», а всім іншим -- за черговістю знаки «-» та «+». У клітинках зі знаком «-» вибирають значення і переносять його у порожню клітинку. Одночасно це число додають до відповідних чисел, які містяться в клітинках зі знаком «+», та віднімають від чисел, що позначені знаком «-». Якщо значенню відповідає кіль-ка однакових перевезень, то при відніманні залишаємо у відповідних клітинках нульові величини перевезень у такій кількості, що дає змогу зберегти невиродженість опорного плану.

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

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

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

5. Перевірка умови оптимальності наступного опорного плану. Якщо умова оптимальності виконується -- маємо оптимальний план задачі, інакше необхідно перейти до наступного опорного плану (тобто повернутися до пункту 3 даного алгоритму).

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

1. Вирішення транспортної задачі засобами EXCEL

Створюємо таблицю з формулами, які зв'язують план, обмеження і цільову функцію :

Діапазон G26:G28 заповнюємо формулою: =СУМ ( );

Діапазон B26:F26 заповнюємо формулою: =СУМ ( );

У цільову комірку G30 вводимо формулу: ==СУММПРОИЗВ(B18:F20;B26:F28

Виділивши діапазон B26:F28, робимо формат чисел 0 знаків після коми.

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

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

Натискаємо кнопку Виконати і у вікні, що з'явилося. Результати пошуку рішення виводимо звіт:

Аналіз результатів

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

Мінімальні витрати на транспортування дорівнюють 3330 гр. од.

Висновки

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

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

3. Транспортна задача може бути узагальнена на випадок "некла-сичної" постановки: трьохіндексна транспортна задача, трьохіндексна транспортна задача з різними видами вантажу, чотирьохіндексна транспортна задача тощо.

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

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

Размещено на Allbest.ru