3. Дайте визначення поняттям: підмножина маршрутів, нижня оцінка вартості маршруту, константа приведення, наведена матриця витрат, штраф «за невикористання», оптимальний маршрут.
4. У якому випадку при вирішенні задачі про комівояжера методом гілок і меж виконується повернення на попередній крок рішення, повернення по дереву?
5. Чому метод гілок і меж називають «ефективним методом перебору»?
Транспортна задача (ТЗ) відноситься до особливого класу задач лінійного програмування. Специфіка математичної моделі ТЗ дозволяє поряд із загальними методами вирішення завдань ЛЗ застосовувати спеціальні методи, що дозволяють скоротити обчислення. Постановка ТЗ належить Хичкоку.
Постановка задачі. Є m пунктів виробництва (складів) деякого одного продукту, заданий ai - обсяг виробництва в i-му пункті виробництва,. Є n пунктів споживання цього продукту, заданий bj - обсяг споживання (подані заявки на поставку товару) в j-му пункті споживання,.
Пункти виробництва пов'язані з пунктами споживання мережею доріг з певними тарифами на перевезення. Вартість перевезення однієї одиниці продукту (вантажу) з i -го пункту виробництва в j- ий пункт споживання дорівнює сij. Необхідно знайти оптимальний план перевезень продукції, при якому транспортні витрати мінімальні, продукція повністю вивозиться з пунктів виробництва і повністю задовольняється потреба в продукції.
Математична модель задачі. В якості змінних вибираються елементи матриці перевезень:.
Нехай - кількість одиниць продукції, що вивозяться з i -го пункту виробництва в j -й пункт споживання.
Перші m обмежень задають умова: з кожного i -го пункту виробництва вивезений весь продукт. Наприклад (рис. 1), з першого пункту виробництва з об'ємом виробництва a1 продукт може бути перевезений в 1-n-ий пункти споживання. Обсяги перевезень невідомі і складають: - кількість одиниць продукції, перевезених з першого пункту виробництва в перший пукнт потебленія; - кількість одиниць продукції, перевезених з першого пункту виробництва в другій пункт споживання; - кількість одиниць продукції, перевезених з першого пункту виробництва в n-ий пункт споживання. Сума всіх перевезених одиниць продукції повинна бути дорівнює a1. .
Наступні n обмежень задають умова: в кожен j -й пункт споживання завезений весь необхідний продукт.
Розмірність завдання:. Транспортна задача - окремий випадок завдання лінійного програмування, в якій всі обмеження типу рівності. На відміну від загального випадку рішення задачі ЛП оптимальне рішення транспортної задачі завжди існує
Методи рішення. Як завдання лінійного програмування ТЗ може бути вирішена симплекс методом []. Також розроблені спеціальні (більш ефективні) методи вирішення транспортної задачі: узагальнений угорський метод []; метод північно-західного кута, метод мінімального елемента для знаходження опорного плану; метод потенціалів для знаходження оптимального плану [].
Відкрита і закрита транспортні завдання. Існує два типи ТЗ: відкрита ТЗ і закрита ТЗ.
Транспортна задача називається закритою, якщо виконується умова балансу. сумарний обсяг виробництва дорівнює сумарному обсягу споживання:
Зверніть увагу, математична модель () задає закриту транспортну задачу.
Відкрита ТЗ може бути задана в двох варіантах.
Перший варіант. Сумарний обсяг виробництва менше сумарного обсягу споживання:
Для вирішення транспортної задачі необхідно звести відкриту транспортну задачу до закритої, для чого вводиться фіктивний пункт виробництва m + 1 з об'ємом произвоства:
Другий варіант. Сумарний обсяг виробництва більше сумарного обсягу споживання:
Для відомості до закритого типу вводять фіктивний пункт споживання n + 1 з об'ємом споживання:
Умова транспортної задачі задають у вигляді транспортної таблиці (табл. 1) виду:
Елементи матриці плану перевезень (осередки, клітини таблиці) називають базисними. якщо вони відмінні від нуля; нульові клітини таблиці називають вільними.
План перевезень - допустимий. якщо він задовольняє балансовим умов (): все заявки задоволені, всі запаси вичерпані.
Допустимий план - опорний. якщо в ньому відмінні від нуля не більше ніж r = m + n-1 базисних перевезень, а решта перевезення дорівнюють нулю. Якщо відмінних від нуля перевезень менш ніж r = m + n-1. то такий план називають виродженим опорним планом.
Оптимальний план перевезень - план з найменшою вартістю з усіх допустимих планів перевезень.
Метод північно-західного кута.
Крок 0. Умова транспортної задачі задають у вигляді транспортної таблиці (табл. 1).
Крок 1. Перевіряють виконання умови балансу (). Якщо умова балансу не виконується, т. Е. Завдання відкрита, то її зводять до закритого типу.
Крок 2. Створюють таблицю плану перевезень (табл. 2), в якій заповнені тільки обсяги виробництва та обсяги споживання. Далі починають заповнювати таблицю перевезень з лівого верхнього (північно-західного) кута. При заповненні рухаються по рядку вправо і по стовпцю вниз. У клітку, що знаходиться на пе-ресеченіі першого рядка і першого стовпця, поміщають мак-симально можливу кількість одиниць продукції, дозволене ог-зпечних на пропозицію і попит:.
Нехай, наприклад,, тоді і пропозиція першого виробника (постав-ника) повністю вичерпано. Решта клітини першого рядка заповнюють нулями, і дві-гаются по на одну вниз. У клітку, що знаходиться на перетині першого стовпця і другого рядка, поміщають максимально мож-ли-число одиниць продукції, дозволене обмеженнями на пропозицію і попит:. Якщо, наприклад,, то. Попит першого споживача удовлет-Ворен. Решта клітини першого шпальти заповнюють нулями і рухаються по другому рядку вправо. Заповнивши клітку, що стоїть на перетині другого рядка і другого шпальти, переходять до заповнення наступної тре-тьей клітини другого рядка, або другого шпальти. Процес про-довжують до тих пір, поки не вичерпаються пропозиції і повністю не задовольниться попит. Остання заповнена клітина знаходиться в n-му стовпці і m -му рядку.
Приклад 1. Визначити опорний план за методом північно-західного кута для транспортної задачі, заданої в табл. 3
обсяг споживання виробництва
На першому кроці перевіряють виконання балансових умов. Сумарний обсяг виробництва становить: 200 + 40 + 110 = 350 умовних одиниць; сумарний обсяг споживання дорівнює: 120 + 50 + 190 + 110 = 470. Отже, ТЗ - відкрита. Для її відомості до закритого типу необхідно ввести четвертий пункт виробництва з об'ємом виробництва рівним: = 470-350 = 120 умовних одиниць. Так як пункт виробництва фіктівен, то вартості перевезень продукції з цього пункту в пункти споживання нульові (табл. 4).
обсяг споживання виробництва
На другому кроці створюють порожню таблицю плану перевезень і починають її заповнення (табл. 5).
обсяг споживання виробництва
В першу клітку поміщають: (табл. 5). Заявки першого споживача повністю задоволені, решта клітини першого шпальти заповнюють нулями. Залишок продукції в першому пункті становить: 200-120 = 80 умовних одиниць вантажу.
Далі дві-гаются по першому рядку вправо і заповнюють клітину (1,2):. Заявки другого споживача повністю задоволені, що залишилися клітини другого шпальти заповнюють нулями. Залишок продукції в першому пункті дорівнює: 80-50 = 30 умовних одиниць вантажу.
З через великий обсяг цей матеріал розміщений на декількох сторінках:
1 2 3 4 5 6 7
Підпишіться на розсилку:
Цікаві новини
важливі теми
Огляди сервісів Pandia.ru