Електронна бібліотека »Інформатика» Постановка транспортної задачі лінійного програмування
Симплекс-метод розв'язання задачі лінійного програмування є універсальним і застосуємо для вирішення будь-яких таких завдань. Однак існують деякі приватні типи завдань лінійного програмування, які, в силу деяких особливостей своєї структури, допускають рішення більш простими методами. До них відноситься, зокрема, так звана транспортна задача.
Класична транспортна задача лінійного програмування формулюється в такий спосіб.
Є m пунктів відправлення: А1. А2. Am. в яких зосереджені запаси якогось однорідного товару (вантажу) в кількості відповідно a1. a2. am одиниць. Крім того, є n пунктів призначення: B1. B2. Bn. які подали заявки відповідно на b1. b2. bn одиниць товару.
Передбачається, що сума всіх заявок дорівнює сумі всіх запасів:
Відома вартість cij перевезення одиниці товару від кожного пункту відправлення Ai до кожного пункту призначення Bj. Таблиця (матриця) вартостей перевезення сij задана:
Потрібно скласти такий план перевезень, при якому всі заявки були б виконані, і при цьому загальна вартість всіх перевезень була мінімальна.
При такій постановці завдання показником ефективності плану перевезень є вартість; тому поставлене завдання точніше називаюттранспортной завданням за критерієм вартості.
Дамо цьому завданні математичну формулювання. Позначимо xij - кількість вантажу, що відправляється з i -го пункту відправлення Аi в j -й пункт призначення В j (i = 1. m; j = 1. n). Невід'ємні змінні x11. x12. xmn (число яких, очевидно, так само m xn) повинні відповідати таким вимогам:
1. Сумарна кількість вантажу, що направляється з кожного пункту відправлення в усі пункти призначення, має дорівнювати запасу вантажу в даному пункті. Це дасть нам m умов-рівностей:
де знак подвійної суми означає, що підсумовування проводиться по всіх комбінацій індексів (i = 1. m; j = 1. n), тобто по всіх комбінацій пунктів відправлення до пунктів призначення.
Функція (3.31) лінійна, обмеження - рівності (3.29), (3.30) також лінійні. Перед нами - типова задача лінійного програмування з обмеженнями-рівностями (ОЗЛП).
Як і будь-яку іншу задачу лінійного програмування, її можна було б вирішити симплекс-методом, але дана задача має деякі особливості, що дозволяють розв'язати цю проблему простіше. Причиною є те, чтовсе коефіцієнти при змінних в рівняннях (3.29), (3.30) дорівнюють одиниці. Крім того, має значення структура зв'язків між умовами. Неважко переконатися, що не всі m + n рівнянь нашої задачі є незалежними. Дійсно, складаючи між собою всі рівняння (3.29) і все рівняння (3.30), ми повинні отримати один і той же, в силу умови (3.28). Таким чином, умови (2), (3) пов'язані однією лінійною залежністю, і фактично з цих рівнянь тільки m + n -1, а не m + n є лінійно незалежними. Значить, ранг системи рівнянь (3.29), (3.30) дорівнює
а, отже, можна вирішити ці рівняння щодо m + n -1 базисних змінних, висловивши їх через інші, вільні.
Підрахуємо кількість вільних змінних. Воно дорівнює:
Ми знаємо, що в задачі лінійного програмування оптимальне рішення досягається в одній з вершин ОДР, де принаймні (m -1) (n -1) значень xij повинні бути рівні нулю.
Домовимося про термінологію. Значення xij кількості одиниць вантажу, що направляються з пункту Ai в пункт Bj ми будемо називати перевезеннями.
Будь-яку сукупність значень (xij) (i = 1. m; j = 1. n) будемо називати планом перевезень. або просто планом.
План (xij) будемо називати допустимим. якщо він задовольняє умовам (3.29), (3.30) (так званим «балансовим умов»): все заявки задоволені, всі запаси вичерпані.
Допустимий план будемо називати опорним. якщо в ньому відмінні від нуля не більше r = m + n -1 базисних перевезень xij. а решта перевезення дорівнюють нулю.
План (xij) будемо називати оптимальним. якщо він, серед усіх допустимих планів, призводить до найменшої вартості всіх перевезень.
Перейдемо до викладу методів вирішення транспортної задачі (ТЗ). Ці методи не вимагають маніпуляцій з симплекс-таблицями, а зводяться до більш простих операцій безпосередньо з таблицею, де в певному порядку записані всі умови ТЗ. Таку таблицю ми будемо називати транспортної таблицею.
У транспортній таблиці записуються
- пункти відправлення та призначення,
- запаси, наявні в пунктах відправлення,
- заявки, подані пунктами призначення,
- вартості перевезень з кожного пункту відправлення в кожний пункт призначення.
Вартості перевезень ми будемо розміщувати в правому верхньому куті кожної клітинки, з тим щоб в самій комірці при складанні плану поміщати перевезення xij.
Зразок транспортної таблиці дано в табл.3.8.
Для стислості надалі будемо позначати пункти відправлення - ПО, пункти призначення - пн. У правому верхньому куті кожної клітини проставлені вартості перевезення одиниці товару (вантажу) з ПО Аi в ПН Bj. У правій колонці поміщені запаси товару в кожному ПО, в нижньому рядку - заявки, подані кожним ПН. Для ТЗ сума запасів дорівнює сумі заявок; загальне значення цієї суми записується в правій нижній комірці таблиці.
Вище ми показали, що ранг системи рівнянь-обмежень ТЗ дорівнює r = m + n -1, де m - число рядків, а n - число стовпців транспортної таблиці. Значить, в кожному опорному плані, включаючи оптимальний, будуть відмінні від нуля не більше, ніж m + n -1 перевезень.
Осередки (клітини) таблиці, в яких ми будемо записувати ці відмінні від нуля перевезення, домовимося називати базисними. а решта (порожні) вільними.
Таким чином, рішення ТЗ звелося до наступного. Знайти такі значення позитивних перевезень, які, будучи проставлені в базисних клітинах транспортної таблиці, задовольняли б наступним умовам:
- сума перевезень в кожному рядку таблиці має дорівнювати запасу даного ПЗ;
- сума перевезень в кожному стовпці повинна бути дорівнює заявці даного ПН;
- загальна вартість перевезень - мінімальна.
Надалі всі дії по знаходженню рішення ТЗ будуть зводитися до перетворення транспортної таблиці 3.8.
При описі цих перетворень нам зручно буде користуватися нумерацією клітин таблиці (подібної нумерації клітин шахової дошки). Кліткою (Аi, Bj) або, коротше, кліткою (i, j) ми будемо називати клітку, що стоїть в i -му рядку і j -м стовпці транспортної таблиці. Наприклад, сама верхня ліва клітка буде позначатися (1,1), що стоїть під нею (2,1) і т.д.
3.5.2. Знаходження опорного плану
Рішення транспортної задачі, як і будь-якої задачі лінійного програмування, починається з знаходження опорного рішення, або, як ми будемо говорити, опорного плану. На відміну від загального випадку ОЗЛП з довільними обмеженнями і мінімізується функцією, рішення ТЗ завжди існує.
Побудова опорного плану.
Скористаємося так званим «способом північно-західного кута». Пояснити його простіше за все буде на конкретному прикладі.
Приклад 1. Умови ТЗ задані транспортної таблицею (див. Табл.3.9)