План реферату
Введення
1. Формулювання транспортної завдання
2. Математична модель транспортної задачі
3. Необхідна і достатня умови розв'язності транспортної задачі
4. Властивість системи обмежень транспортної задачі
5. Опорне рішення транспортної задачі
6. Методи побудови початкового опорного рішення
6.1 Побудова початкового плану за способом північно-західного кута
6.2 Побудова початкового плану за способом мінімального елемента
7. Перехід від одного опорного рішення до іншого
8. Розподільчий метод
9. Метод потенціалів
10. Особливості вирішення транспортних завдань з неправильним балансом
11. Алгоритм вирішення транспортної задачі методом потенціалів
11.1 Попередній крок
11.2 Загальний повторюваний крок
12. Транспортна задача з обмеженнями на пропускну спроможність
13. Транспортна задача за критерієм часу
14. Застосування транспортної задачі для вирішення економічних задач
Висновок
Список використаної літератури
Введення
Методи лінійного програмування застосовуються для вирішення багатьох екстремальних задач, з якими досить часто доводиться мати справу в економіці. Вирішення таких завдань зводиться до знаходження крайніх значень (Максимуму і мінімуму) деяких функцій змінних величин.
Лінійне програмування засноване на вирішенні системи лінійних рівнянь (з перетворенням в рівняння і нерівності), коли залежність між досліджуваними явищами суворо функціональна. Для нього характерні математичний вираз змінних величин, певний порядок, послідовність розрахунків (алгоритм), логічний аналіз. Застосовувати його можна тільки в тих випадках, коли досліджувані змінні величини і фактори мають математичну визначеність і кількісну обмеженість, коли в результаті відомої послідовності розрахунків відбувається взаємозамінність факторів, коли логіка в розрахунках, математична логіка поєднуються з логічно обгрунтованим розумінням сутності досліджуваного явища.
За допомогою цього методу в промисловому виробництві, наприклад, обчислюється оптимальна загальна продуктивність машин, агрегатів, потокових ліній (при заданому асортименті продукції та інших заданих величинах), вирішується завдання раціонального розкрою матеріалів (з оптимальним виходом заготовок). У сільському господарстві він використовується для визначення мінімальної вартості кормових раціонів при заданій кількості кормів (за видами і що містяться в них поживним речовинам). Задача про сумішах може знайти застосування і в ливарному виробництві (склад металургійної шихти). Цим же методом вирішуються транспортна задача, задача раціонального прикріплення підприємств-споживачів до підприємствам-виробникам.
Всі економічні завдання, які вирішуються із застосуванням лінійного програмування, відрізняються альтернативністю рішення і певними обмежуючими умовами. Вирішити таке завдання - значить вибрати з всіх допустимо можливих (альтернативних) варіантів кращий, оптимальний. Важливість і цінність використання в економіці методу лінійного програмування полягають у тому, що оптимальний варіант вибирається з вельми значної кількості альтернативних варіантів. За допомогою інших способів вирішувати такі завдання практично неможливо.
Вельми типовою задачею, розв'язуваної за допомогою лінійного програмування, є транспортна задача. [1]
Транспортна задача (transportation problem) - одна з найбільш поширених задач математичного програмування (Зазвичай - лінійного). У загальному вигляді її можна представити так: потрібно знайти такий план доставки вантажів від постачальників до споживачів, щоб вартість перевезення (або сумарна дальність, або обсяг транспортної роботи в тонно-кілометрах) була найменшою. Отже, справа зводиться до найбільш раціонального прикріплення виробників до споживачів і навпаки. [2]
1. Формулювання транспортної задачі
У найпростішому вигляді, коли розподіляється один вид продукту і споживачам все одно, від кого з постачальників його отримувати, задача формулюється наступним чином.
Вихідна інформація:
M i - кількість одиниць вантажу в i -м пункті відправлення ( i = 1, 2, ..., k );
N j - потреба в j -м пункті призначення ( j = 1, 2, ..., l ) (в одиницях вантажу);
a ij - вартість перевезення одиниці вантажу з i -гo пункту в j -й.
Позначимо через x ij плановане кількість одиниць вантажу для перевезення з i -ro пункту в j -й.
У прийнятих позначеннях:
- загальна (Сумарна) вартість перевезень;
- кількість вантажу, що вивозиться з i -ro пункту;
- кількість вантажу, що доставляється в j -і пункт.
У найпростішому випадку повинні виконуватися наступні очевидні умови:
Таким чином, математичної формулюванням транспортної задачі буде:
знайти
при умовах
;
;
Ця задача носить назву замкнутої (Закритою, збалансованою) транспортної моделі.
Зауважимо, що умова є природною умовою разрешимости замкнутої транспортної задачі.
Більш спільної транспортної завданням є так звана відкрита (незбалансована) транспортна модель:
знайти
при умовах
Ясно, що в цьому завданні не передбачається, що весь вантаж, накопичений в i -му пункті, повинен бути вивезений. [3]
2. Математична модель транспортної задачі
Найпростішими транспортними завданнями є завдання про перевезеннях деякого однорідного вантажу з пунктів відправлення (Від постачальників) в пункти призначення (до споживачів) при забезпеченні мінімальних витрат на перевезення.
Зазвичай початкові умови таких завдань записують у таблицю. Наприклад, для k постачальників і l споживачів така задача має наступний вигляд:
Тут показники a ij означають витрати на перевезення одиниці вантажу від i -го постачальника ( i = 1,2, ..., k ) до j -тому споживачеві ( j = 1,2, ..., l ), M i - потужність i -того постачальника в планований період, N j - попит j -того споживача на цей же період. Позначимо через x ij поставку (кількість вантажу), яка планується до перевезення від i -того постачальника до j -тому споживачеві. Математично задача зводиться до знаходження мінімуму цільової функції, виражає сумарні витрати на перевезення вантажу, тобто функції
при обмеженнях
(1)
Якщо до цих обмежень додати ще одне:
, (2)
тобто сумарна потужність постачальників дорівнює сумарному попиту споживачів, то відповідна модель задачі називається закритою.
Завданням, в яких обмеження (2) відсутня, тобто
,
спочатку відповідає відкрита модель.
Відзначимо деякі особливості економіко-математичної моделі транспортної задачі.
Система обмежень (1) одразу має вид рівнянь, тому відпадає необхідність вводити додаткові змінні.
Матриця коефіцієнтів при змінних в системі (1) складається тільки з одиниць і нулів.
Система обмежень (1) включає k рівнянь, що зв'язують поставки i -того постачальника з потужністю M i (I = 1,2, ..., k ) цього постачальника, і l рівнянь, що зв'язують поставки j -тому споживачеві з попитом N j ( j = 1,2, ..., l ) цього споживача. Зауважимо, ...
