Опорний конспект лекцій з курсу Дослідження операцій Тема 6 Транспортні задачі лінійного програмування, НУДПСУ

Лекція №6. ТРАНСПОРТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

План

1. Транспортна задача. Загальні особливості транспортних задач.

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

3. Таблиця транспортної задачі.

4. Закриті та відкриті транспортні задачі.

5. Опорний план.

3. ТРАНСПОРТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

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

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

Перша строга постановка транспортної задачі (Т-задачі) належить Ф.Хичкоку, тому в зарубіжній літературі її називають проблемою Хичкока.

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

3.1. Постановка задачі

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

Найчастіше зустрічаються наступні задачі, що відносяться до транспортних:

• прикріплення споживачів ресурсу до виробників;

• прив'язка пунктів відправлення до пунктів призначення;

• взаємна прив'язка вантажопотоків прямого і зворотного напрямів;

• окремі задачі оптимального завантаження промислового устаткування;

• оптимальний розподіл об'ємів випуску промислової продукції між заводами-виготівниками і ін.

Розглянемо економіко-математичну модель прикріплення пунктів відправлення до пунктів призначення. Є m пунктів відправлення вантажу і об'єми відправлення по кожному пункту a₁, a₂,...,a_m. Відома потреба у вантажах b₁, b₂,...,b_n по кожному з n пунктів призначення. Задана матриця вартостей доставки по кожному варіанту c_ij, i = 1,…,m, j = 1,…,n. Необхідно розрахувати оптимальний план перевезень, тобто визначити, скільки вантажу повинно бути відправлено з кожного i-го пункту відправлення (від постачальника) в кожен j-й пункт призначення (до споживача) x_ij з мінімальними транспортними витратами.

У загальному вигляді початкові дані представлені в табл. 3.1. Рядки транспортної таблиці відповідають пунктам відправлення (у останній клітці кожного рядка вказаний об'єм запасу продукту a_i), а стовпці – пунктам призначення (остання клітка кожного стовпця містить значення потреби b_j). Всі клітки таблиці (окрім тих, які розташовані в нижньому рядку і правому стовпці) містять інформацію про перевезення з i-го пункту в j-й: у правому верхньому кутку знаходиться ціна перевезення одиниці продукту, а в лівому нижньому – значення об'єму вантажу, що перевозиться, для даних пунктів.

Таблиця 3.1. Початкові дані

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

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

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

Всі вантажі з i-х пунктів повинні бути відправлені, тобто.

Всі j-і пункти (споживачі) повинні бути забезпечені вантажами в плановому об'ємі.

Сумарні об'єми відправлення повинні дорівнювати сумарним об'ємам призначення (3.1).

Повинна виконуватися також умова позитивності змінних

х_ij ³ 0, i = 1,…,m, j = 1,…,n.

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

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

• потреби за пунктами призначення перевищують запаси пунктів відправлення, то вводиться фіктивний постачальник з бракуючим об'ємом відправлення;

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

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

Транспортним задачам властиві наступні особливості:

• розподілу підлягають однорідні ресурси;

• умови задачі описуються тільки рівняннями (нерівності відсутні);

• всі змінні виражаються в однакових одиницях вимірювання;

• у всіх рівняннях коефіцієнти при невідомих рівні одиниці;

• кожна невідома зустрічається тільки в двох рівняннях системи обмежень;

• невідомі змінні представляють собою не вектор, а матрицю.

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

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

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

Контрольні запитання

1. Що таке транспортна задача?

2. Наведіть загальні особливості транспортних задач.

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

4. Сформулюйте задачу прив'язки пунктів відправлення до пунктів призначення.

5. Сформулюйте задачу взаємної прив'язки вантажопотоків прямого і зворотного напрямів.

6. Сформулюйте задачу оптимального завантаження промислового устаткування.

7. Сформулюйте задачу оптимального розподілу об'ємів випуску промислової продукції між заводами-виготівниками.

8. Що таке таблиця транспортної задачі?

9. Що таке закриті та відкриті транспортні задачі?

10. Що таке опорний план?

З повагою ІЦ “KURSOVIKS”!