Методическое пособие для выполнения контрольной работы по дисциплине
Транспортная задача. Общие понятия
жүктеу/скачать 0.49 Mb.
|
- Бұл бет үшін навигация:
- Математическая постановка транспортной задачи
| Транспортная задача. Общие понятия
Одним из основных понятий в прикладной математике является понятие «сеть». Раздел прикладной математики, изучающий сетевые модели, называется сетевым планированием. Основными примерами сетевых задач можно назвать следующие: - транспортная задача (система «производители-потребители»); - задача назначений («работы-исполнители»); - задача о кратчайшем пути (с выбором промежуточных пунктов); - задача коммивояжера (агент по сбыту должен посетить n городов по одному разу). Сеть представляет собой линейный граф, состоящий из узлов (вершин, точек) и множества дуг (ребер, звеньев), соединяющих различные пары узлов. На каждой дуге задана ориентация (направление). Таким образом, сеть является ориентированным графом. Последовательность дуг без учета ориентации из узла i в узел j называется путем между узлами. Если i=j, то путь называется контуром. Сеть называется связной, если между любой парой узлов существует хотя бы один путь. Путь с учетом ориентации называется ориентированной цепью. Ориентированная цепь, начинающаяся и заканчивающаяся в одном и том же узле, называется ориентированным циклом. Ациклическая сеть не содержит ни одного ориентированного цикла. Дерево – это связная сеть, содержащая p узлов, p-1 дугу и ни одного контура. Математическая постановка транспортной задачи Транспортная задача является типовой задачей для промышленных фирм, имеющих несколько предприятий, складов, рынков сбыта и оптовых баз. В основе транспортной задачи лежит двудольная сеть. Для двудольной сети характерно наличие двух непересекающихся множеств узлов G1 (предприятия, поставщики) и при этом каждая дуга начинается в узле множества G1 и заканчивается в узле множества G2 (потребители, оптовые базы). Введем следующие обозначения: ai– запас груза в i-ом пункте отправления; bj – потребность в j-ом пункте назначения; cij – тариф перевозки единицы груза из i-го пункта отправления в j-ый пункт назначения; xij – количество единиц груза, перевезенного из i-го пункта отправления в j-ый пункт назначения; Q – целевая функция (затраты на перевозку всех грузов). Тогда транспортная задача математически будет записана в следующем виде: – план ТЗ является оптимальным планом ТЗ с минимальным значением целевой функции Q. Транспортную задачу легко представить в виде таблицы, в основных ячейках которой записываются два числа тариф cij и количество перевозимого груза xij. В последнем столбце таблицы записываются суммы перевозимых грузов для данного пункта отправления (запасы), в последней строке записываются суммы перевозимых грузов для данного пункта назначения (потребности). Таблица. Табличное представление транспортной задачи
Общее наличие груза у поставщиков составляет , а общая потребность в грузе у потребителей равна . Если выполняется условие , то такая транспортная задача называется закрытой, в противном случае – открытой. Необходимым и достаточным условием разрешимости транспортной задачи является ее закрытость. Открытую транспортную задачу легко свести к закрытой. Так, если , то вводят -й пункт назначения (склад) с потребностью . Если , то вводят фиктивный -й пункт отправления (конкурент) с запасом груза . Мы будем рассматривать только закрытые Т3. При этом число переменных равно n*m, а число уравненийравно n+m-1 (число столбцов плюс число строк минус условие закрытости транспортной задачи). План называется невырожденным, если число отличных от нуля переменных равно в точности n+m-1, в противном случае вырожденным, когда число отличных от нуля переменных меньше, чем n+m-1. Решение транспортной задачи обычно осуществляется в две стадии: - сначала нужно определить опорный план (метод северо-западного угла, метод минимального элемента, метод аппроксимации Фогеля); - затем оптимизировать полученный план (метод потенциалов). Существуют методы, которые совмещают процессы составления и оптимизации плана транспортной задачи (метод дифференциальных рент). 1. Постановка транспортной задачи. 2. Табличное представление транспортной задачи. Этапы решения транспортной задачи. 3. Открытые и закрытые транспортные задачи. Число уравнений и число переменных в транспортной задаче. Вырожденный и невырожденный планы транспортной задачи. 4. Классификация методов решения транспортной задачи. Устранение неоднозначности при условии одинаковых тарифов. жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|