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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати



Міжнародний університет

Калінінградський філія
Заочне відділення

Спеціальність-менеджмент

Курсова робота
з дисципліни економіко-математичні методи
Транспортна задача
лінійного програмування
Виконав:
Перевірив (уч.степень, звання):


Курсова робота
з вищої математики
Тема:
  "Транспортна задача лінійного програмування"
Зміст:
1. Історія зародження та створення лінійного програмування.
2. Транспортна задача. Загальна постановка, цілі, завдання. Основні типи, види моделей.
3. Методи складання початкового опорного плану.
4. Поняття потенціалу і циклу.
5. Критерій оптимальності базисного розв'язку транспортної задачі. Методи відшукання оптимального рішення.
6. Завдання, двоїста до транспортної.
7. Приклад розв'язання транспортної задачі.
8. Висновки.
1.Історія зародження і створення лінійного програмування.
Кожна людина щодня, не завжди усвідомлюючи це, вирішує проблему: як отримати найбільший ефект, володіючи обмеженими засобами. Наші засоби і ресурси завжди обмежені. Життя було б менш цікавою, якщо б це було не так. Не важко виграти бій, маючи армію в 10 разів більшу, ніж у супротивника. Щоб досягти найбільшого ефекту, маючи обмежені кошти, треба скласти план, або програму дій. Раніше план у таких випадках складався "на око" (тепер, втім, часто теж). У середині XX століття було створено спеціальний математичний апарат, що допомагає це робити "по науці". Відповідний розділ математики називається математичним програмуванням. Слово "програмування" тут і в аналогічних термінах ("лінійне програмування, динамічне програмування" тощо) зобов'язана почасти історичного непорозуміння, почасти неточного перекладу з англійської. По-русски краще було б вжити слово "планування". З програмуванням для ЕОМ математичне програмування має лише те загальне, що більшість виникаючих на практиці завдань математичного програмування дуже громіздкі для ручного рахунку, вирішити їх можна лише за допомогою ЕОМ, попередньо склавши програму. Часом народження лінійного програмування прийнято вважати 1939р., Коли була надрукована брошура Леоніда Віталійовича Канторовича "Математичні методи організації і планування виробництва". Оскільки методи, викладені Л. В. Канторовичем, були мало придатні для ручного рахунку, а швидкодіючих обчислювальних машин у той час не існувало, робота Л. В. Канторовича залишилася майже не поміченою.
Своє друге народження лінійне програмування отримало на початку п'ятдесятих років з появою ЕОМ. Тоді почалося загальне захоплення лінійним програмуванням, що викликало в свою чергу розвиток інших розділів математичного програмування. У 1975 році академік Л. В. Канторович і американець професор Т. Купманс отримали Нобелівську премію з економічних наук за "внесок у розробку теорії і оптимального використання ресурсів в економіці".
В автобіографії, поданій до Нобелівського комітету, Леонід Віталійович Канторович розповідає про події, що трапилися в 1939 році. До нього, 26-річному професору-математику, звернулися за консультацією співробітники лабораторії планерного тресту, яким потрібно було вирішити задачу про найбільш вигідному розподіл матеріалу між верстатами. Ця задача зводилася до знаходження максимуму лінійної функції, заданої на многограннику. Максимум такої функції досягався у вершині, однак число вершин у цьому завданні досягало мільярда. Тому простий перебір вершин не годився. Леонід Віталійович писав: "виявилося, що це завдання не є випадковою. Я виявив велику кількість різноманітних за змістом завдань, що мають аналогічний математичний характер: найкраще використання посівних площ, вибір завантаження обладнання, раціональний розкрій матеріалу, розподіл транспортних вантажопотоків ... Це наполегливо спонукало мене до пошуку ефективного методу їх вирішення ". І вже влітку 1939 року була здана в набір книга Л. В. Канторовича "Математичні методи організації і планування виробництва", в якій закладалися підстави того, що нині називається математичної економікою.
Однак ідеї Л. В. Канторовича не зустріли розуміння в момент їх зародження, були оголошені єрессю, і його робота була перервана. Концепції Леоніда Віталійовича незабаром після війни були перевідкрили на заході. Американський економіст Т. Купманс протягом багатьох років привертав увагу математиків до низки завдань, пов'язаних з військовою тематикою. Він активно сприяв тому, щоб була організована математичний колектив для розробки цих проблем. У підсумку було усвідомлено, що треба навчитися вирішувати задачі про знаходження екстремумів лінійних функцій на багатогранника, що задаються лінійними нерівностями. За пропозицією Купманса цей розділ математики отримав назву лінійного програмування.
Американський математик А. Данциг в 1947 році розробив досить ефективний конкретний метод чисельного рішення задач лінійного програмування (він отримав назву симплекс методу). Ідеї ​​лінійного програмування протягом п'яти шести років отримали грандіозне поширення у світі, і імена Купманса і Данцига стали всюди широко відомі.
Приблизно в цей час Купманс дізнався, що ще до війни в далекій Росії вже було зроблено щось схоже на розробку почав лінійного програмування. Як легко було б Данцигу і Купманса проігнорувати цю інформацію! Маленька книжечка, видана нікчемним тиражем, звернена навіть не до економістів, а до організаторів виробництва, з мінімумом математики, без чітко описаних алгоритмів, без доказів теорем - словом, чи варто приймати таку книжку до уваги ... Але Купманс наполягає на переведенні та виданні на заході книги Канторовича. Його ім'я й ідеї стають відомі всім. Віддамо належне шляхетності американського вченого!
А самому Леоніду Віталійовичу - як природно було б йому, випробувавши перші грізні удари ретроградів, утриматися від "гріхів" молодості, забути про всю цю економіку і повернутися до математики. Але Л. В. Канторович продовжує писати математичні праці, навіяні економічними ідеями, бере участь і в конкретних розробках на виробництві. При цьому (одночасно з Данцигом, але, не знаючи його робіт) він розробляє метод, пізніше названий симплекс-методом. Як тільки в 50-ті роки утворюється маленький просвіт, і дещо з забороненого стає можливим, він організовує групу студентів на економічному факультеті ЛДУ для навчання методам оптимального планування. А, починаючи з 1960 року, Леонід Віталійович займається тільки економічної і пов'язаної з нею математичної проблемами. Його внесок у цій області був відзначений Ленінською премією в 1965 році (присуджена йому спільно з В. С. Немчинова і В. В. Новожиловим) і, як уже говорилося, Нобелівською премією в 1975 році.
2.Транспортно завдання. Загальна постановка, цілі, завдання. Основні типи, види моделей.
Під назвою "транспортна задача" об'єднується широке коло завдань з єдиною математичною моделлю. Дані завдання відносяться до завдань лінійного програмування і можуть бути вирішені симплексним методом. Однак матриця системи обмежень транспортної задачі настільки своєрідна, що для її рішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, поліпшуючи його, отримати оптимальне рішення.
У загальній постановці транспортна задача полягає у знаходженні оптимального плану перевезень деякого однорідного вантажу з баз споживачам .
Розрізняють два типи транспортних завдань: але критерієм вартості (план перевезень оптимальний, якщо досягнуть мінімум витрат на його реалізацію) і за критерієм часу (план оптимальний, якщо на його реалізацію витрачається мінімум часу).
(1.1)
Позначимо кількість вантажу, що є на кожній з баз (Запаси), відповідно , А загальна кількість наявного в наявності вантажу- :
;
(1.2)
замовлення кожного із споживачів (потреби) позначимо відповідно , А загальна кількість потреб - :
,

(1.3)
Тоді за умови


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

- Відкриту модель транспортної задачі.
Очевидно, у випадку закритої моделі весь наявний вантаж розвозиться повністю, і всі потреби замовників повністю задоволені; у разі ж відкритої моделі або всі замовники задоволені і при цьому на деяких базах залишаються надлишки вантажу , Або весь вантаж виявляється витраченим, хоча потреби повністю не задоволені .
Так само існують одноетапні моделі задач, де перевезення здійснюється безпосередньо від, наприклад, бази або заводу виробника до споживача, і двохетапні, де між ними є "перевалочний пункт", наприклад - склад.
План перевезень із зазначенням запасів і потреб зручно записувати у вигляді такої таблиці, званої таблицею перевезень:
Пункти
Відправлення
Пункти призначення
Запаси


...




...





...


...
...
...
...
...
...



...


Потреби


...


або

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


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

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

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

або коротше
(2.2)


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

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

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


...




...








...





...
...
...
...
...
...



...





Потреби


...


або

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

Необхідно в області допустимих рішень системи рівнянь (2.1) та (2.1.1) знайти рішення, яке мінімізує лінійну функцію (2.4).
Таким чином, ми бачимо, що транспортна задача є задачею лінійного програмування. Для її вирішення застосовують також симплекс-метод, але в силу специфіки завдання тут можна обійтися без симплекс-таблиць. Рішення можна отримати шляхом деяких перетворень таблиці перевезень. Ці перетворення відповідають переходу від одного плану перевезень до іншого. Але, як і в загальному випадку, оптимальне рішення шукається серед базисних рішень. Отже, ми будемо мати справу тільки з базисними (або опорними) планами. Так як в даному випадку ранг системи обмежень-рівнянь дорівнює то серед всіх невідомих виділяється базисних невідомих, а решта ·
невідомих є вільними. У базисному рішенні вільні невідомі рівні нулю. Зазвичай ці нулі в таблицю не вписують, залишаючи відповідні клітини порожніми. Таким чином, в таблиці перевезень, що представляє опорний план, ми маємо заповнених і · порожніх клітин.
Для контролю треба перевіряти, дорівнює чи сума чисел в заповнених клітках кожного рядка таблиці перевезень запасу вантажу на відповідній базі, а в кожному стовпці - потреби замовника [цим підтверджується, що цей план є рішенням системи (2.1)].
Зауваження 1. Не виключаються тут і вироджені випадки, тобто можливість звернення до нуль однієї або кількох базисних невідомих. Але ці нулі на відміну від нулів вільних невідомих вписуються у відповідну клітину, і ця клітина вважається заповненою.
Зауваження 2. Під величинами , Очевидно, не обов'язково мати на увазі тільки тарифи. Можна також вважати їх величинами, пропорційними тарифами, наприклад, відстанями від баз до споживачів. Якщо, наприклад, виражені в тоннах, а в кілометрах, то величина , Яка визначається формулою (2.4), є кількістю тонно-кілометрів, що складають обсяг даного плану перевезень. Очевидно, що витрати на перевезення пропорційні кількості тонно-кілометрів і, отже, будуть мінімальними при мінімумі S. У цьому випадку замість матриці тарифів ми маємо матрицю відстаней.
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
Вибір в якості х мінімального серед чисел, що стоять в негативних вершинах циклу, забезпечує допустимість нового базису.
Якщо мінімальне значення серед базисних невідомих, які стоять у негативних вершинах циклу, приймається не в одній негативній вершині, то вільної залишають тільки одну з них, а в інших клітинах з тим же мінімальним значенням пишуть нулі. У цьому випадку нове базисне рішення буде виродженим.
Може статися, що й саме мінімальне значення серед чисел в негативних клітинах дорівнює нулю. Тоді перетворення таблиці перевезень зведеться до перестановки цього нуля в вільну клітину. Значення всіх невідомих при цьому залишаються незмінними, але рішення вважаються різними, тому що різні базиси. Обидва рішення виродилися.
Описане вище перетворення таблиці перевезень, в результаті якого перетвориться базис, називається перерахунком по циклу.
Зауважимо, що невідомі, що не входять до циклу, цим перетворенням не зачіпаються, їх значення залишаються незмінними і кожне з них залишається або в групі базисних, або в групі вільних невідомих, як і до перерахунку.
З'ясуємо тепер, як перерахунок по циклу впливає на загальний обсяг витрат на перевезення та при якій умові ці витрати стають менше.
Нехай - Деякий вільний невідоме, для якого ми побудували цикл і здійснили перерахунок по циклу з деяким числом . Якщо вершині циклу, що знаходиться в рядку і стовпці таблиці перевезень, приписаний знак "+", то значення невідомого , Що знаходиться в цій вершині, збільшується на , Що в свою чергу викликає збільшення витрат на . Де - Тариф, що відповідає цій клітці, коли ж зазначеної вершині приписаний знак "-", то значення невідомого зменшується на , Що викликає зменшення витрат на .
Складемо тарифи, відповідні позитивним вершин циклу, і віднімемо з цієї суми суму тарифів, відповідних негативним вершин циклу; отриману різницю назвемо алгебраїчною сумою тарифів для даного вільного невідомого . Підрахунок алгебраїчної суми тарифів можна витлумачити і так: припишемо тарифами ті ж знаки, які приписані відповідним вершин циклу, тоді алгебраїчна сума тарифів дорівнює сумі таких тарифів зі знаком ("відносних тарифів").
Тепер, очевидно, ми можемо, укласти, що в цілому при перерахунку але циклу, відповідному вільному невідомому загальний обсяг витрат на перевезення зміниться на твір алгебраїчної суми тарифів на , Тобто на величину . Отже, якщо алгебраїчна сума тарифів для деякого вільного невідомого негативна , То перерахунок по циклу, відповідному цього невідомого, призводить до зменшення загальної суми витрат на реалізацію плану перевезень. Якщо ж алгебраїчна сума тарифів позитивна , То перерахунок за відповідним циклу призведе до збільшення загальної суми витрат. І, нарешті, якщо алгебраїчна сума тарифів дорівнює нулю , То перерахунок за відповідним циклу не змінить загальну суму витрат (два різних базисних плану вимагають однакових витрат на їх реалізацію).
Так, наприклад, для циклу у розглянутій задачі алгебраїчна сума тарифів
.
Значить, перерахунок з цього циклу знижує витрати. І дійсно, здійснивши такий перерахунок, ми отримуємо план, за яким обсяг перевезень в тонно-кілометрах становить

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

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

З (4.3) випливає, що якщо непрямий тариф для даної вільної клітини більше її справжнього тарифу, то алгебраїчна сума тарифів по циклу, відповідному цій клітці, буде негативна, якщо ж непрямий тариф менший істинного, то алгебраїчна сума тарифів позитивна, і, нарешті, якщо непрямий тариф дорівнює істинному, то алгебраїчна сума тарифів дорівнює нулю.
Потенціали можна знайти з системи рівностей (4.1), розглядаючи їх як систему рівнянь з невідомими. Так як невідомих тут на одиницю більше, ніж рівнянь, то, принаймні, один з потенціалів ми можемо вибрати довільно, поклавши, наприклад, ; Тоді інші потенціали легко визначаються з рівнянь (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.1) зіставляється певна невідома в двоїстої задачі. Тим самим встановлюється відповідність між усіма пунктами і і усіма невідомими двоїстої задачі.
Позначимо невідому в двоїстої задачі, що відповідає пункту відправлення , Через , А пунктом призначення - Через .
Кожному невідомому в транспортній завданню відповідає обмеження, що зв'язує невідомі в двоїстої задачі. Невідоме входить рівно в два обмеження системи (6.1): одне з них відповідає пункту , А інше - пункту . В обох цих рівняннях коефіцієнт при дорівнює 1. Тому відповідне обмеження в двоїстої задачі має вигляд
(6.2)


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

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

(6.3)

Таким чином, завдання двоїста до транспортної формулюється наступним чином. При обмеженнях (6.2) максимізувати формулу (6.3). Підкреслимо, що знак значень невідомих і може бути довільним.
Припустимо, що нам відомо деяке дозволене базисне рішення транспортної задачі, в якому всі базисні невідомі суворо позитивні. Це рішення оптимально лише в тому випадку, коли відповідна їй система виявляється спільної. Ця система виникає із системи (6.2), якщо в ній все нерівності, що відповідають базисним невідомим   замінити точними равенствами.
У підсумку приходимо до співвідношення:
(6.4)
(Для всіх вільних невідомих )
Тим самим ми переконуємося, що ознака оптимальності в роботі за методом потенціалів збігається з необхідним і достатнім умовою оптимальності.
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)
А 11 = 50)
1,0
2,0
3,0
2,5
3,5
А 22 = 20)
0,4
3,0
1,0
2,0
3,0
А 33 = 75)
0,7
1,0
1,0
0,8
1,5
А 44 = 80)
1,2
2,0
2,0
1,5
2,5
У даному випадку Σa i = 225> Σb j = 220 => маємо справу з відкритою моделлю транспортної задачі. Зведемо її до закритої введенням фіктивного магазину B 6 з потребою b 5 = 225-220 = 5 і вартістю перевезень з i 6 = 0.Імеем таблицю:
Магазини
Склад
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)
А 11 = 50)
1,0
2,0
3,0
2,5
3,5
0
А 22 = 20)
0,4
3,0
1,0
2,0
3,0
0
А 33 = 75)
0,7
1,0
1,0
0,8
1,5
0
А 44 = 80)
1,2
2,0
2,0
1,5
2,5
0
Математична модель: позначимо x ij - кількість товару, що перевозиться з А i в B j.   Тоді
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)
А 11 = 50)
1,0

50
2,0
3,0
2,5
3,5
0
А 22 = 20)
0,4
20

3,0
1,0
2,0
3,0
0
А 33 = 75)
0,7
20

0
1,0
1,0
55
0,8
1,5
0
А 44 = 80)
1,2
2,0
15
2,0
20
1,5
40
2,5
5
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
А 11 = 50)
U 1 = 0
1,0
2,0
3,0
2,5
3,5
0
А 22 = 20)
U 2 =- 1,3
0,4
3,0
1,0
2,0
3,0
0
0
А 33 = 75)
U 3 =- 1
-
Овал: -
0
0,7
20

+
Овал: +
0, 3
0
1,0
0
1,0
0, 3
55
0,8
- 0,7
1,5
0
0, 2
А 44 = 80)
U 4 =- 0,3
- 0,3
1,2
0
2,0
0
15
2,0
0
20
1,5
0
40
2,5
5
0
У верхньому лівому кутку тут і далі записуємо значення u i + v j-c ij. Маємо: u 1 + v 1 - c 11 = 0,7> 0, u 1 + v 6-c 16 = 0,3> 0, u 3 + v 3-c 33 = 0,3> 0, u 3 + v 5-c 35 = 0,3> 0,
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
0
А 11 = 50)
U 1 = 0
+
Овал: +
0
1,0
20

-
Овал: -
- 0,7
30
2,0
- 0,7
3,0
- 0,7
2,5
0, 3
3,5
0
0
А 22 = 20)
U 2 =- 0,6
-
Овал: -
- 1,6
20
0,4

0, 7
3,0
+
Овал: +
- 0,8
1,0
- 0,8
2,0
- 0,3
3,0
0
-0,7
А 33 = 75)
U 3 =- 1
0
0,7
+
Овал: +
0, 3
20
1,0
0
1,0
-
Овал: -
0, 3
55
0,8
- 0,7
1,5
0
-0,5
А 44 = 80)
U 4 =- 0,3
- 0,3
1,2
0
2,0
-
Овал: -
0
15
2,0
+
Овал: +
0
20
1,5
0
40
2,5
5
0
Вартість другого плану:
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
0
А 11 = 50)
U 1 = 0
0
1,0
35

-1,4
15
2,0
- 0,7
3,0
- 0,7
2,5
0, 3
3,5
0
0
А 22 = 20)
U 2 =- 0,6
- 1,6
5
0,4
0
3,0
15
- 0,8
1,0
- 0,8
2,0
- 0,3
3,0
0
-0,7
А 33 = 75)
U 3 =- 1
0
0,7
-0,4
35
1,0
0
1,0
-
Овал: -
0, 3
40
0,8
+
Овал: +
- 0,7
1,5
0
-0,5
А 44 = 80)
U 4 =- 0,3
- 0,3
1,2
-0,7
2,0
0
2,0
+
Овал: +
0
35
1,5
-
Овал: -
0
40
2,5
5
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
0
А 11 = 50)
U 1 = 0
0
1,0
35

- 1,4
15
2,0
- 1
3,0
- 1
2,5
0
3,5
0
0
А 22 = 20)
U 2 =- 0,6
- 1,6
5
0,4
0
3,0
15
- 1,1
1,0
- 1,1
2,0
- 0,6
3,0
0
-0,7
А 33 = 75)
U 3 =- 1
0
0,7
-0,4
35
1,0
-0,3
1,0
0
0,8
40
- 1
1,5
0
-0,2
А 44 = 80)
U 4 = 0
0
1,2
-0,4
2,0
0
2,0
0
75
1,5
0
0
2,5
5
0
Вартість четвертого плану: D 4 = 1 • 35 +2 • 15 +0,4 • 5 +1 • 15 +1 • 35 +1,5 • 40 +1,5 • 75 = 289,5.
Для всіх клітин останньої таблиці виконані умови оптимальності:
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р.
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Курсова
374.1кб. | скачати


Схожі роботи:
Розв язок задач лінійного програмування Задача планування виробництва
Транспортна задача
Транспортна задача з обмеженнями можливих транспортних засобів
Основні поняття математичного програмування Побудова моделі задачі лінійного програмування
Завдання лінійного програмування
Завдання лінійного програмування
Завдання лінійного програмування
Розвязок задачі лінійного програмування
Розвязання задач лінійного програмування
© Усі права захищені
написати до нас