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

Курсова робота:

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

Зміст:

1. Транспортна задача. Загальна постановка, мети, задачі. Основні типи, види моделей.

2. Методи складання початкового опорного плану.

3. Поняття потенціалу й циклу.

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

5. Задача, двоїста до транспортного.

6. Приклад рішення транспортної задачі.

Висновки.

Література

1. Транспортна задача. Загальна постановка, мети, задачі. Основні типи, види моделей

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

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

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

Позначимо кількість вантажу, наявного на кожній з баз (запаси), відповідно,а загальна кількість наявності, що є в наявності- :

;

замовлення кожного зі споживачів (потреби) позначимо відповідно, а загальна кількість потреб - :

,

Тоді за умови

ми маємо закриту модель, а за умови

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

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

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

План перевезень із вказівкою запасів і потреб зручно записувати у вигляді наступної таблиці, називаною таблицею перевезень:

Пункти Відправлення	Пункти призначення	Запаси
			…
			…
			…
…	…	…	…	…	…
			…
Потреби			…		або

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

Очевидно, змінні повинні задовольняти умовам:

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

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



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

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

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

або коротше



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

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

Отже, перетворення системи (2.1) звелося до заміни двох рівнянь (першим горизонтальним і першим вертикального) рівнянням (2.2). Інші рівняння залишаються незмінними. Система прийняла вид

У системі (2.3) виділений зазначений вище базис: базисні невідомі з перших т рівнянь утворять перший стовпець матриці перевезень, а базисних невідомі інших рівнянь утворять перший рядок матриці перевезень без першого невідомого [вона входить у перше рівняння системи (2.3)]. У системі (2.3) є рівнянь, виділений базис містить невідомих, а, отже, і ранг системи (2.1) .

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

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

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

Потрібно в області припустимих рішень системи рівнянь (2.1) і (2.1.1) знайти рішення, які мінімізують лінійну функцію (2.4).

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

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

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

Зауваження 2. Під величинами, мабуть, не обов'язково мати на увазі тільки тарифи. Можна також уважати їхніми величинами, пропорційними тарифам, наприклад, відстанями від баз до споживачів. Якщо, наприклад, виражені в тоннах, а в кілометрах, то величина , обумовлена формулою (2.4), є кількістю тонно-кілометрів, що становлять об'єм даного плану перевезень. Очевидно, що витрати на перевезення пропорційні кількості тонно-кілометрів і, отже, будуть мінімальними при мінімумі S. У цьому випадку замість матриці тарифів ми маємо матрицю відстаней.

2. Методи складання початкового опорного плану

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

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

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

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

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

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

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

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

Тепер переходимо до заповнення клітки для невідомого й т.д.

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

Загальний об'єм перевезень у тонно-кілометрах для цього плану складе

.

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

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

.

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

.

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

Крім розглянутих вище способів іноді використовується, так званий, метод Фогеля. Суть його полягає в наступному: У розподільній таблиці по рядках і стовпцям визначається різниця між двома найменшими тарифами. Відзначається найбільша різниця. Далі в рядку (стовпці) з найбільшою різницею заповнюється клітка з найменшим тарифом. Рядка (стовпці) з нульовою остачею вантажу надалі в розрахунок не приймаються. На кожному етапі завантажується тільки одна клітка. Розподіл вантажу виробляється, як і раніше.

3. Поняття потенціалу й циклу

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

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

Одне з невідомі послідовності вільне, а всі інші - базисні.

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

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

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

Друга умова означає, що у двох сусідніх невідомих у циклі або перші, або другі індекси однакові.

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

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

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

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

старі значення: ;

нові значення:

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

Зауваження. Тому що число вершин у циклі завжди парне, те, вертаючись у вільну клітку, ми повинні будемо приписати їй знак “+”, тобто той знак, що їй уже приписаний при виході з її. Це дуже істотна обставина, тому що інакше ми прийшли б до протиріччя. Байдуже також, у якому напрямку обходиться цикл при означені вершин.

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

Так, наприклад, у розглянутому вище циклі маємо негативні вершини й ; отже, вибравши , ми одержуємо:

старі значення: ;

нові значення:

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

Пункти Відправлення	Пункти призначення	Запаси
		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

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

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

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

Описане вище перетворення таблиці перевезень, у результаті якого перетвориться базис, називається перерахуванням по циклі.

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

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

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

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

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

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

.

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

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

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

,

так що

,

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

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

.

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

.

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

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

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

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

Наприклад, для плану, отриманого по діагональному методі в розглянутій вище задачі, маємо

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

Поклавши, наприклад, , одержуємо значення потенціалів:

Знайдемо тепер непрямі тарифи для вільних кліток і зрівняємо їх із щирими тарифами:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вище розглядалася закрита модель транспортної задачі, із правильним балансом, коли виконується умова (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 пункти призначення В₁, B₂, ... , 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 рівним відсутньому запасу, і вартість перевезень із фіктивного пункту відправлення в усі пункти призначення прийняти рівної нулю.

5. Задача, двоїста до транспортного

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

У той же час кожному обмеженню з (6.1) зіставляється певна невідома у двоїстій задачі. Тим самим установлюється відповідність між всіма пунктами й і всієї невідомими двоїстої задачі.

Позначимо невідому у двоїстій задачі, що відповідає пункту відправлення , через , а пункту призначення - через .

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

.

Права частина нерівності (6.2) дорівнює , тому що саме із цим коефіцієнтом невідома входить у формулу (2.4).

Форма двоїстої задачі має вигляд

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

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

У підсумку приходимо до співвідношення:

(для всіх вільних невідомих )

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

6. Приклад рішення транспортної задачі

У місті N є 4 склади А_i, на яких зберігається тканина (у рулонах) і 5 магазинів B_j, що займаються продажем тканини. Нижче, у таблиці, наведені дані по кількості рулонів на кожному складі, запити магазинів і вартість перевезення одного рулону з А_i в B_j. Необхідно скласти такий план перевезень, при якому запити магазинів будуть задоволені при мінімальній сумарній вартості перевезень.

Магазини Склад	B1 (b1=40)	B2 (b2=50)	B3 (b3=15)	B4 (b4=75)	B5 (b5=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

У цьому випадку Уa_i=225 >Уb_j=220 => маємо справа з відкритою моделлю транспортної задачі. Зведемо її до закритого введенням фіктивного магазина B₆ з потребою b₅=225-220=5 і вартістю перевезень с_i6=0. Маємо таблицю:

Магазини Склад	B1 (b1=40)	B2 (b2=50)	B3 (b3=15)	B4 (b4=75)	B5 (b5=40)	B6 (b6=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_ij - кількість товару, перевезеного з А_i в B_j. Тоді

x₁₁ x₁₂ x₁₃ x₁₄ x₁₅ x₁₆

x₂₁ x₂₂ x₂₃ x₂₄ x₂₅ x₂₆

X = x₃₁ x₃₂ x₃₃ x₃₄ x₃₅ x₃₆ - матриця перевезень.

x₄₁ x₄₂ x₄₃ x₄₄ x₄₅ x₄₆

min(x₁₁+2x₁₂+3x₁₃+2,5x₁₄+3,5x₁₅+0,4x₂₁+3x₂₂+x₂₃+2x₂₄+3x₂₅+0,7x₃₁+x₃₂+x₃₃+0,8x₃₄+1,5x₃₅++1,2x₄₁+2x₄₂+2x₄₃+1,5x₄₄+2,5x₄₅) (1)

x₁₁+x₁₂+x₁₃+x₁₄+x₁₅+x₁₆=50

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅+x₂₆=20

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅+x₃₆=75

x₄₁+x₄₂+x₄₃+x₄₄+x₄₅+x₄₆=80

x₁₁+x₂₁+x₃₁+x₄₁=40 (2)

x₁₂+x₂₂+x₃₂+x₄₂=50

x₁₃+x₂₃+x₃₃+x₄₃=15

x₁₄+x₂₄+x₃₄+x₄₄=75

x₁₅+x₂₅+x₃₅+x₄₅=40

x₁₆+x₂₆+x₃₆+x₄₆=5

x_ij?0 (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3)

Двоїста ЗЛП:

max(50u₁+20u₂+75u₃+80u₄+40v₁+50v₂+15v₃+75v₄+40v₅+5v₆) (1*)

u₁+v₁?1

u₁+v₂?2

u₁+v₃?3 (2*)

u₁+v₄?2,5

u₁+v₅?3,5

u₁+v₆?0

u_i,v_j - довільні (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3*)

Будемо шукати первісний план по методу найменшої вартості:

1) x₂₁=20 і 2-й рядок виключаємо.

2) x₃₁=20 і 1-й стовпець виключаємо.

3) x₃₄=55 і 3-й рядок виключаємо.

4) x₄₄=20 і 4-й стовпець виключаємо.

5) x₁₂=50 і 1й рядок і 2-ой стовпець виключаємо й x₃₂=0.6) x₄₃=150 і 3-й стовпець виключаємо.

7) x₄₅=40 і 5-ый стовпець виключаємо.

x₄₆=5. Складемо таблицю. Тут і далі в нижньому правому куті записуємо значення перевезення.

Магазини Склад	B1 (b1=40)	B2 (b2=50)	B3 (b3=15)	B4 (b4=75)	B5 (b5=40)	B6 (b6=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

Вартість 1-ого плану:

D₁=2* 50+0,4* 20+0,7* 20+0,8* 55+2* 15+1,5* 20+2,5* 40=326.

Будемо поліпшувати цей план методом потенціалів: u_i- потенціал А_i ,v_j- потенціал B_j. Тоді u₁+v₂=2,u₂+v₁=0,4, u₃+v₁=0,7, u₃+v₂=1, u₃+v₄=0,8, u₄+v₃=2, u₄+v₄=1,5, u₄+v₅=2,5 ,u₄+v₆=0.Покладемо u₁=0,тоді v₂=2,u₃=-1,v₁=1,7,v₄=1,8, u₂=-1,3,u₄=-0,3, v₃=2,3,v₅=2,8,v₆=0,3.

Складемо таблицю:

Магазини Склад	B1 (b1=40) v1=1,7	B2 (b2=50) v2=2	B3 (b3=15) v3=2,3	B4 (b4=75) v4=1,8	B5 (b5=40) v5=2,8	B6 (b6=5) v6=0,3
А1 (а1=50) U1=0	1,0	2,0	3,0	2,5	3,5	0
А2(а2=20) U2=-1,3	0,4	3,0	1,0	2,0	3,0	0
А3(а3=75) U3=-1	0,7	1,0	1,0	0,8	1,5	0
А4(а4=80) U4=-0,3	1,2	2,0	2,0	1,5	2,5	0

У верхньому лівому куті тут і далі записуємо значення u_i+v_j-c_ij. Маємо: u₁+v₁--c₁₁ =0,7>0, u₁+v₆-c₁₆ =0,3>0, u₃+v₃-c₃₃ =0,3>0, u₃+v₅-c₃₅ =0,3>0,

u₄+v₁-c₄₁ =0,2>0. => За критерієм оптимальності, перший план не оптимальний. Далі max(0,7;0,3;0,3;0,3;0,2)=0,7. => Помістимо перевезення в клітку А₁У₁, змістивши 20=min(20,50) по циклі, зазначеному в таблиці штрихом. Одержимо нову таблицю. Знайдемо потенціали: u₁+v₁=1,u₁+v₂=2,u₂+v₁=0,4,u₃+v₂=1, u₃+v₄=0,8, u₄+v₃=2, u₄+v₄=1,5, u₄+v₅=2,5 , u₄+v₆=0. Покладемо u₁=0,тоді v₁=1,u₂=-0,6,v₂=2,v₄=1,8, u₃=-1, u₄=-0,3,v₃=2,3,v₅=2,8,v₆=0,3. Складемо таблицю:

Магазини Склад	B1 (b1=40) v1=1	B2 (b2=50) v2=2	B3 (b3=15) v3=2,3	B4 (b4=75) v4=1,8	B5 (b5=40) v5=2,8	B6 (b6=5) v6=0,3
А1 (а1=50) U1=0	1,0	2,0	3,0	2,5	3,5	0
А2(а2=20) U2=-0,6	0,4	3,0	1,0	2,0	3,0	0
А3(а3=75) U3=-1	0,7	1,0	1,0	0,8	1,5	0
А4(а4=80) U4=-0,3	1,2	2,0	2,0	1,5	2,5	0

Вартість 2-ого плани:

D₂=1* 20+2* 30+0,4* 20+1* 20+0,8* 55+2* 15+1,5* 20+2,5* 40=312.

Маємо:u₁+v₆-c₁₆ =0,3>0, u₂+v₃-c₂₃ =0,7>0, u₃+v₃-c₃₃ =0,3>0, u₃+v₅-c₃₅ =0,3>0. => За критерієм оптимальності, другий план не оптимальний. Далі max(0,3;0,7;0,3;0,3)=0,7 => Помістимо перевезення в клітку А₂У₃, змістивши 15=min(20,30,55,15) по циклі, зазначеному в таблиці штрихом. Одержимо нову таблицю. Знайдемо потенціали: u₁+v₁=1,u₁+v₂=2,u₂+v₁=0,4,u₃+v₂=1, u₃+v₄=0,8, u₂+v₃=1, u₄+v₄=1,5, u₄+v₅=2,5 , u₄+v₆=0. Покладемо u₁=0,тоді v₁=1,u₂=-0,6,v₂=2,v₄=1,8, u₃=-1, u₄=-0,3,v₃=1,6, v₅=2,8, v₆=0,3. Складемо таблицю:

Магазини Склад	B1 (b1=40) v1=1	B2 (b2=50) v2=2	B3 (b3=15) v3=1,6	B4 (b4=75) v4=1,8	B5 (b5=40) v5=2,8	B6 (b6=5) v6=0,3
А1 (а1=50) U1=0	1,0	2,0	3,0	2,5	3,5	0
А2(а2=20) U2=-0,6	0,4	3,0	1,0	2,0	3,0	0
А3(а3=75) U3=-1	0,7	1,0	1,0	0,8	1,5	0
А4(а4=80) U4=-0,3	1,2	2,0	2,0	1,5	2,5	0

Вартість 3-його плани:

D₃=1* 35+2* 15+0,4* 5+1* 15+0,8* 40+1* 35+1,5* 35+2,5* 40=301,5.

Маємо:u₁+v₆-c₁₆ =0,3>0,u₃+v₅-c₃₅ =0,3>0. => За критерієм оптимальності, третій план не оптимальний. Далі max(0,3;0,3)=0,3. => Помістимо перевезення в клітку А₃У₅, змістивши 40=min (40,40) по циклі, зазначеному в таблиці штрихом. Одержимо нову таблицю. Щоб 4-й план був не виродженим, залишимо в клітці А₄У₅ нульове перевезення. Знайдемо потенціали: u₁+v₁=1,u₁+v₂=2,u₂+v₁=0,4,u₃+v₂=1, u₄+v₅=2,5, u₂+v₃=1, u₄+v₄=1,5, u₃+v₅=1,5 , u₄+v₆=0. Покладемо u₁=0,тоді v₁=1,u₂=-0,6,v₂=2,v₄=1,5, u₃=-1,u₄=0, v₃=1,6, v₅=2,5, v₆=0. Складемо таблицю:

Магазини Склад	B1 (b1=40) v1=1	B2 (b2=50) v2=2	B3 (b3=15) v3=1,6	B4 (b4=75) v4=1,5	B5 (b5=40) v5=2,5	B6 (b6=5) v6=0
А1 (а1=50) U1=0	1,0	2,0	3,0	2,5	3,5	0
А2(а2=20) U2=-0,6	0,4	3,0	1,0	2,0	3,0	0
А3(а3=75) U3=-1	0,7	1,0	1,0	0,8	1,5	0
А4(а4=80) U4=0	1,2	2,0	2,0	1,5	2,5	0

Вартість 4-ого плани: D₄=1* 35+2* 15+0,4* 5+1* 15+1* 35+1,5* 40+1,5* 75=289,5.

Для всіх кліток останньої таблиці виконані умови оптимальності:

1)u_i+ vj-сij=0 для кліток, зайнятих перевезеннями;

2)u_i+ vj-с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₁=0 ; U₂=-0,6 ; U₃=-1 ; U₄=0 ; V₁=1 ; V₂=2 ; V₃=1,6 ; V₄=1,5 ; V₅=2,5 ; V₆=0.

max=289,5.

Тому що min=max, те за критерієм оптимальності знайдені оптимальні рішення прямої й двоїстої ЗЛП. Змістовна відповідь: Оптимально перевозити так:

З А₁ в B₁ - 35 рулонів полотна;

З А₁ в B₂ - 15 рулонів полотна;

З А₂ в B₁ - 5 рулонів полотна;

З А₂ в B₃ - 15 рулонів полотна;

З А₃ в B₂ - 35 рулонів полотна;

З А₃ в B₅ - 40 рулонів полотна;

З А₄ в B₄ - 75 рулонів полотна.

При цьому вартість мінімальна й складе D_min=289,5.5 рулонів полотна необхідно залишити на складі А₄ для їхнього наступного перевезення в інші магазини.

7. Висновки

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

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

Література

1. Ковальов А.В., Сакович В.А., Холод Н.І. Вища математика. Математичне програмування. - К., 2001

2. Красс М.С., Чупринов Б.П. Основи математики. - К., 2001

3. Єрмаков В.І. Загальний курс вищої математики для економістів - К., 2006

4. Акулич І.Л. Математичне програмування в прикладах і задачах. - К., 1993.

5.Воробйов Н.Н. Основи теорії ігор. - К., 1984.

6.Прохоров Г.В., Колбєєв В.В., Желнов К.І., Леденев М.О..Математичний пакет Maple V Release 4. - К., 1998