Оптимізація грузоперевезень за допомогою транспортної задачі

1.1 Загальна характеристика методів оптимізації для рішення економічних задач

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

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

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

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

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

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

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

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

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

Тут можливі два випадки:

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

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

В математичному програмуванні можна виділити два напрями.

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

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

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

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

Так, в лінійному програмуванні з'явився розділ транспортних задач.

Нелінійне програмування - цільова функція і обмеження нелінійна. Нелінійне програмування прийнято підрозділяти таким чином:

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

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

(1.1)

при умовах

(1.2)

(1.3)

(1.4)

де - постійні змінні й .

Визначення 2.

Функція (1.1) називається цільовою функцією (або лінійною формою) задачі (1.1) - (1.4), а умови (1.2) - (1.4) - обмеженнями даної задачі.

Визначення 3.

Стандартної (або симетричної} задачею лінійного програмування називається задача, яка полягає у визначенні максимального значення функції (2.1) при виконанні умов (1.2) і (1.4), де к = m і l = n.

Визначення 4.

Канонічною (або основний) задачею лінійного програмування називається задача, яка полягає у визначенні максимального значення функції (1.1) при виконанні умов (1.3) і (1.4), де до = 0 і l = п.

Визначення 5.

Сукупність чисел , що задовольняють обмеженням задачі (2.2) - (2.4), називається допустимим рішенням (або планом). Визначення

Визначення 6.

План , при якому цільова функція задачі (8) приймає своє максимальне (мінімальне) значення, називається оптимальним. Значення цільової функції (1.1) при плані Х позначатимемо через . Отже, X* - оптимальний план задачі, якщо для будь-кого Х виконується нерівність [відповідно ]. Вказані вище три форми задачі лінійного програмування еквівалентні в тому значенні, що кожна з них за допомогою нескладних перетворень може бути переписаний у формі іншої задачі. Це означає, що якщо є спосіб знаходження рішення одній з вказаних задач, то тим самим може бути визначений оптимальний план будь-якої з трьох задач. Щоб перейти від однієї форми запису задачі лінійного програмування до іншої, потрібно уміти, по-перше, зводити задачу мінімізації функції до задачі максимізації; по-друге, переходити від обмежень-нерівностей до обмежень-рівності і навпаки; по-третє, замінювати змінні, які не підлеглі умові позитивності. У тому випадку, коли вимагається знайти мінімум функції , можна перейти до знаходження максимуму функції , оскільки . Обмеження-нерівність початкової задачі лінійного програмування, що має вид “”, можна перетворити в обмеження-рівність додаванням до його лівої частини додаткової ненегативної змінної, а обмеження-нерівність виду “” - в обмеження-рівність відніманням з його лівої частини додаткової ненегативної змінної. Таким чином, обмеження-нерівність

перетвориться в обмеження

(1.5)

а обмежена нерівність

- в обмежену рівність

(1.6)

В той же час кожне рівняння системи обмежень

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

(1.7)

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

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

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

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

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

Векторний запис має вигляд

F=CX (1.7)

при умові

(1.8)

(1.9)

де , CX - скалярний додаток;

і- m-ні вектори-столбци

Визначення 7.

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

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

Визначення 8.

Опорний план називається невиродженим, якщо він містить рівно т позитивних компонент, в осоружному випадку він називається виродженим. Властивості основної задачі лінійного програмування (1.7) - (1.9) тісним чином пов'язані з властивостями опуклих множин.

Визначення 9.

Хай - точки простору . Випуклой комбінацієй цих точок є

де - невід'ємні числа, сума яких дорівнює 1:

Визначення 10.

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

Визначення 11.

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

Теорема 1.

Безліч планів основної задачі лінійного програмування є опуклою (якщо воно не порожнє).

Визначення 12.

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

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

Теорема 3.

Якщо система векторів в (2.8) лінійно незалежна і

(1.10)

де всі то точка є вершиною многограника рішень.

Теорема 4.

Якщо - вершина многограника рішень, то вектори , відповідають позитивним в рокладанні (1.8) та лінійно незалежні.

Сформульовані теореми дозволяють зробити наступні висновки.

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

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

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

(19)(1.11)

при умові

(1.12)

(1.13)

Кожна з нерівностей (1.12), (1.13) системи обмежень задачі геометрично визначає напівплощина відповідно з граничними прямими и . В тому випадку, якщо система нерівностей (1.12), (1.13) сумісна, область її рішень є безліч крапок, що належать всім вказаним напівплощинам. Оскільки безліч точок перетину даних напівплощин - опукла, то областю допустимих рішень задачі (1.11) - (1.13) є опукла множина, яка називається багатокутником рішень (введений раніше термін “многогранник рішень” звичайно використовується, якщо ). Сторони цього багатокутника лежать на прямих, рівняння яких виходять з початкової системи обмежень заміною знаків нерівностей на знаки точної рівності. Таким чином, початкова задача лінійного програмування полягає в знаходженні такої точки багатокутника рішень, в якій цільова функція F приймає максимальне значення. Ця крапка існує тоді, коли багатокутник рішень не порожній і на ньому цільова функція обмежена зверху. За вказаних умов в одній з вершин багатокутника рішень цільова функція приймає максимальне значення. Для визначення даної вершини побудуємо лінію рівня (де h - деяка постійна), що проходить через багатокутник рішень, і пересуватимемо її у напрямі вектора до тих пір, поки вона не пройде через її останню загальну крапку з багатокутником рішень. Координати вказаної крапки і визначають оптимальний план даної задачі.

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

Рисунок 1.1 - Перший і другий випадки знаходження рішення

Рисунок 1.2 - Третій і четвертий випадки знаходження рішення

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

Отже, знаходження рішення задачі лінійного програмування (1.11) - (1.13) на основі її геометричної інтерпретації включає наступні етапи:

1 Будують прямі, рівняння яких виходять в результаті заміни в обмеженнях (1.12) і (1.13) знаків нерівностей на знаки точної рівності.

2 Знаходять напівплощини, визначувані кожним з обмежень задачі.

3 Знаходять багатокутник рішень.

4 Будують вектор .

5 Будують пряму, що проходить через багатокутник рішень.

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

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

1.2 Оптимізація грузоперевезень за допомогою транспортної задачі

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

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

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

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

F (X) > max (1.14)

X Є A

де Х - параметр, який менеджер може вибирати (управляючий параметр). Він може мати різну природу - число, вектор, множина і т.п. Мета менеджера - максимізувати цільову функцію F (X), вибравши відповідний Х. При цьому він повинен враховувати обмеження X Є А на можливі значення управляючого параметра Х - він повинен лежати в безлічі А. Ряд прикладів оптимізаційних задач менеджменту приведений нижче.

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

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

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

(1.15)

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

(1.16)

При цьому транспортну задачу називають збалансованою.

Можна переконатися, наприклад, що в збалансованій транспортній задачі

(1.17)

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

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

(1.18)

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

Таблиця 1.1 - Матриця обсягів перевезень

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

Таблиця 1.2 - Матриця обмежень транспортної задачі

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

велика частина її елементів рівна нулю.

серед ненульових елементів багатьох однакових.

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

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

Таблиця 1.3 - Список транспортних зв'язків

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

Даний метод заснований на теорії графів і вимагає представлення транспортної задачі у вигляді графа (рис. 1.3).

Рисунок 1.3 - Мережний метод рішення транспортної задачи

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

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

Розглянемо алгоритм рішення

Крок 1. Нумерація вершин сіті.

Нумерація вершин здійснюється довільним чином.

Крок 2. Побудова первинного плану перевезень.

Первинний план перевезень повинен відповідати двом критеріям:

- кількість перевезень повинна бути на одну менше ніж кількість вершин в графі, тобто:

(1.19)

де - кількість перевезень;

- кількість постачальників;

- кількість споживачів.

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

Крок 3. Розрахунок загальної вартості перевезень.

Загальна вартість перевезень розраховується по наступній формулі:

(1.20)

де - вартість перевезення від вершини i до вершини j.

- об'їм перевезення від вершини i до вершини j.

Крок 4. Визначення потенціалів в кожній вершині.

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

(1.21)

Крок 5. Розрахунок різниці потенціалів

Різниця потенціалів між вершинами i і j розраховується тільки для зв'язків, на яких немає поставок. Вона розраховується по наступній формулі:

(1.22)

Крок 6. Перевірка умови оптимальності.

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

(1.23)

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

Крок 7. Введення нового перевезення.

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

Крок 8. Розрахунок об'єму перевезення.

Для розрахунку об'єму перевезення необхідно знайти замкнутий контур, який формує перевезення. В отриманому замкнутому контурі необхідно відшукати мінімальне протилежну за об'ємом перевезення. Об'єм даного перевезення буде рівний об'єм нового перевезення.

Крок 9. Перерахунок перевезень.

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

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

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

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

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

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

3 Ряд транспортних маршрутів, по яких необхідно доставити вантажі, мають обмеження по пропускній спроможності. Якщо, наприклад, по маршруту AiBj можна провести не більш q одиниць вантажу, то Bj-й стовпець матриці розбивається на два стовпці - і . В першому стовпці попит приймається рівним різниці між дійсним попитом і обмеженням q: , в другому - рівним обмеженню q, тобто . Витрати cij в обох стовпцях однакові і рівні даним, але в першому стовпці , в клітці, відповідній обмеженню i, замість істинного тарифу cij ставиться штучно завишений тариф M (клітка блокується). Потім задача розв'язується звичайним способом.

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

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

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

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

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