• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Математична модель транспортної задачі

Побудуємо загальну математичну модель транспортної задачі закритого типу за критерієм вартості:

Отже, сума ресурсу дорівнює сумі потреб (1):

Далі задається матриця вартості:

(2)

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

(3)

де - кількість одиниць продукту, який перевозиться з до .

План перевезень буде допустимий, якщо елементи матриці задовольняють таким умовам – обмеженням (умовам ввезення і вивезення продуктів):

1).Сумарна кількість продуктів, які направляються з кожного ПВ до всіх ПП повинна дорівнювати запасу продуктів в даному пункті, або така трактовка: з кожного ПВ повинен бути вивезений увесь наявний там продукт. Це дасть нам m умов-рівностей:

,

або

(4)

2). У кожному ПП має задовольнятися потреба в продукті. Це дасть нам n умов-рівностей:

,

або

(5)

Крім того, усі числа ; для всіх

3). Сумарна вартість перевезень по всіх маршрутах повинна бути мінімальною:

(6)

де подвійна сума означає, що підсумовування утворюється по всім комбінаціям індексів та , тобто по всім парам ПВ-ПП.

Таким чином, перед нами задача лінійного програмування з умовами-рівностями (4), (5) і мінімізуємого лінійною функцією (6). Особливістю цієї задачі є те, що усі коефіцієнти в умовах (4), (5) дорівнюють одиниці – це дозволяє розв’язувати задачу відносно просто. Крім цього, із структури моделі задачі видно, що умови-рівноваги (4). (5) лінійно залежні, бо їх праві частини зв’язані умовою (1). Лінійно-незалежних рівнянь буде m + n ─ 1, і базисний розв’язок матиме не більш як m + n ─ 1 невідомих, які не дорівнюють нулю, а число вільних змінних (які дорівнюють нулю)

де - загальна кількість змінних .

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

Таким чином, допустимий план перевезень повинен задовольняти умовам (4), (5), тобто всі потреби задовільнені, всі запаси використані. Опорним назвемо план, для якого всі базисні m + n ─ 1 змінні будуть більше за нуль, а вільні дорівнюватимуть нулю. План буде оптимальним, якщо він приводить до мінімальної сумарної вартості перевезень ().

В силу особливої структури транспортної задачі при її розв’язуванні зручніше представити початкові дані у вигляді таблиці 1.

Таблиця 1

ПП ПВ			…		ресурс (наявність)
			…
			…
. . .		. . .	…		. . .
			…
потреба в			…

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

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

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

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

Ця ідея лежить в основі, так званого, «угорського» метода розв’язування транспортної задачі. Цей метод особливо добре пристосований до вирішення проблеми вибору.

На лекції ми розглянемо методику розв’язання транспортної задачі методом потенціалів, запропонованого Л.В. Канторовичем та М.К. Гавуріним і, дещо пізніше й незалежно від них, Данцигом.

Читайте також:

1. G2G-модель електронного уряду
2. OSI - Базова Еталонна модель взаємодії відкритих систем
3. Абстрактна модель
4. Абстрактна модель
5. Абстрактна модель оптимального планування виробництва
6. Автомобільний пасажирський транспорт – важлива складова єдиної транспортної системи держави
7. Алгоритм розв’язання задачі
8. Алгоритм розв’язання розподільної задачі
9. Алгоритм розв’язування задачі
10. Алгоритм розв’язування задачі
11. Алгоритм розв’язування задачі
12. Алгоритм розв’язування задачі

Переглядів: 1059