![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Некоторые определения и понятия
В математической формулировке транспортную задачу можно сформулировать так: требуется минимизировать общую стоимость перевозок
![]() при условии, что на неизвестные
![]()
![]() Алгоритм решения транспортной задачи состоит из следующих шагов: 1. Составить исходный опорный план. 2. Найти оценки для каждой свободной клетки. 3. Проверить, будет ли найденный план оптимальным. 4. В случае, если найденный план не является оптимальным, то перейти к новому опорному плану, а затем к пункту 2. При построении начального опорного плана и дальнейшем решении задачи используются некоторые понятия и утверждения, которые приведены ниже. Невырожденный опорный план транспортной задачи содержит Определение 1. Клетки в таблице перевозок, в которых находятся отличные от нуля перевозки, называются занятыми или базисными, остальные (с Определение 2. Циклом называется замкнутая ломаная, звенья которой идут либо вдоль строки, либо вдоль столбца, причем в каждой вершине сходится точно одно звено, идущее вдоль строки, и точно одно звено, идущее вдоль столбца. Построение циклов начинают с какой-либо занятой клетки и переходят по строке (столбцу) к другой занятой клетке, делая повороты под прямым углом, пытаясь возвратиться к первоначальной клетке. Виды замкнутых циклов: Опорность плана транспортной задачи (1.6.1)-(1.6.3) заключается в его ацикличности, т.е. в таблице перевозок нельзя построить замкнутый цикл, все вершины которого лежат в базисных (занятых) клетках. Определение 3. Означенным циклом называется цикл, каждой вершине которого приписан знак “+” или “-”, причем соседним вершинам приписаны разные знаки (соседние вершины – вершины, лежащие на одном звене цикла). Определение 4. Сдвигом по циклу на Определение 5. Оценкой
Для нахождения начального опорного плана наиболее часто применяется метод северо-западного угла или метод минимального элемента. Для большей наглядности при решении транспортной задачи В методе северо-западного угла начинают заполнение исходного плана с левой верхней (северо-западной) клетки (1, 1), в которую записываем перевозку Если Часто исходный опорный план, составленный по методу северо-западного угла, далек от оптимального, Это объясняется тем, что при распределении груза не учитываются затраты В итоге распределения груз оказывается в клетках с большими тарифами Выбор клеток продолжается до тех пор, пока не распределится весь груз. Это правило называется правилом минимального элемента или методом наименьших стоимостей. Продемонстрируем метод северо-западного угла и минимального элемента на следующем примере.
Пример 1. Найти исходный опорный план транспортной задачи: Таблица 1.6.1
Составим исходный опорный план по методу северо-западного угла. Имеем: Таблица 1.6.2
Опорному плану, полученному в табл. 1.6.2, соответствуют Теперь составим исходный опорный план по методу минимального элемента. Вначале выбирают клетку с наименьшим тарифом и направляют в нее максимально возможный объем перевозок. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены (оставшиеся клетки прочеркиваем). Если одновременно исключаются и строка и столбец, то в ближайшую соседнюю свободную клетку с наименьшим тарифом добавляется нулевая фиктивная перевозка. Если клетка с минимальным тарифом не одна, то предпочтение отдается той, в которую можно направить больший объем перевозок. Таблица 1.6.4
Так, в табл. 1.6.4, в клетку После того, как груз будет распределен, можно рассчитать общую стоимость перевозок полученного первоначального опорного плана. Для этого умножим количество груза в каждой клетке на соответствующий тариф и полученные произведения сложим. Имеем Как видно, план, составленный по методу минимального элемента, оказался лучше. После нахождения начального опорного плана возникает вопрос, является ли найденный план оптимальным и, если нет, то как найти оптимальный план? Чаще всего для решения этих вопросов используют распределительный метод или метод потенциалов.
|