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

Транспортна задача

Побудова опорного плану

1. Економічна постановка транспортної задачі (ТЗ)
2. Математична модель ТЗ
3. Побудова початкового опорного плану для закритої моделі ТЗ: метод північно-західного кута
4. Методи мінімальної вартості і подвійної переваги

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

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

2. Уведемо наступні позначення:

- постачальники, - обсяг (кількість) товару в кожного з них; .

- споживачі, - обсяг потреб кожного з них; .

- матриця цін (питомих витрат), де - ціна перевезення товару за маршрутом від до .

Позначимо через - кількість продукту (обсяг перевезень) за маршрутом від до .

Тоді загальні витрати за всіма маршрутами

Одержали наступну лінійну модель

цільова функція (5.1)

i = 1, 2, ...m (5.2)

j = 1, 2, ...n (5.3)

(5.4)

Економічний зміст обмежень:

(5.2) – весь товар постачальників вивезений

(5.3) – усі потреби споживачів задоволені

(5.4) – товар за кожним маршрутом або планується до перевезення (х_ij >0) або не планується (х_ij = 0).

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

Для викладення методів додамо умову:

(5.5)

Зміст умови (5.5); загальний обсяг запасів товару дорівнює загальному обсягу потреб.

Модель (5.1)-(5.4) з додатковою умовою (5.5) називається закритою, без неї – відкритою.

Теорема. Будь-яка закрита модель транспортної задачі має розв’язок.

3. Побудова початкового опорного плану для закритої моделі

Будемо заповнювати таблицю з m рядками і n стовпчиками. Клітину таблиці назвемо зайнятою, якщо в неї поміщене перевезення x_ij>0. Інші клітини називаються вільними, x_ij = 0 у них не ставляться.

У системі рівнянь (5.2), (5.3) і (5.5) усього m+n-1 незалежних рівнянь, тому опорний план задачі повинен містити не більш m+n-1 зайнятих клітин. Якщо N = m+n-1 - план називається не виродженим, якщо N<m+n-1 – виродженим.

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

Опорний план не повинен містити циклів.

4. Розглянемо кілька методів побудови опорного плану транспортної задачі.

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

1. Б. Задача
2. Взаємне положення площин. Перша позиційна задача
3. Взаємне положення прямої і площини. Друга позиційна задача.
4. Види транспорту в Україні. Єдина транспортна система України
5. Вторая задача анализа на чувствительность
6. Головна задача м/н фінансового менеджменту полягає у оцінці короткострокових і довгострокових активів і зобов’язань фірми у часовому і просторовому використанні м/н ринків.
7. Двоїста задача
8. Двухмерная задача Коши
9. Єдина транспортна мережа і єдиний транспортний процес.
10. З праці В. Леніна «О задачах пролетариата в данной революции»
11. Загальна задача лінійного програмування (ЗЛТ)
12. Задача # 12 (з тих, що вона скидувала)

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