![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Б) Метод наименьшей стоимости (наименьших затрат (тарифов), минимального элемента)
Сущность метода состоит в том, что на каждом шаге заполняется клетка с наименьшей величиной cij. Если такая клетка не единственная, то лучше заполнять ту, по вертикали и горизонтали которой встречаются бό льшие значения cij, а в принципе заполняется любая из них. Таблица начинает заполняться с той клетки, в которой наименьший тариф cij. Пусть это будет клетка (i, j). В эту клетку записывается максимально возможная поставка с учетом ограничений i- й строки и j- го столбца, т.е. значение Процесс повторяется до тех пор, пока не будут зачеркнуты все столбцы и строки. Если ТЗ открытая, и введены фиктивный поставщик или потребитель, то сначала заполняются клетки для действительных поставщиков и потребителей, и в последнюю очередь – для фиктивных. На последнем шаге строка и столбец заполняются одновременно, следовательно, в благоприятном случае должно быть (m + n -1) заполненных клеток. Такой план является невырожденным. Вырожденный план появляется при одновременном зачеркивании строки и столбца (кроме последнего шага), когда число заполненных клеток будет меньше, чем r = m + n -1. Для дальнейших расчетов его надо дополнить до невырожденного плана нулями, записав их в клетки, расположенные в строке или в столбце, которые одновременно исключены из рассмотрения, т.е. имеют один номер шага. При этом клетки, заполненные нулями, не должны составлять цикл (контур) с прочими заполненными клетками и, кроме того, на момент одновременного зачеркивания строки и столбца принадлежат столбцам, для которых сохраняется потребность в грузе. Необходимо отметить, что при наличии в таблице клеток с одинаковыми тарифами, планы, полученные с помощью этого метода, могут быть разными. Пример 2. Построить начальный опорный план методом наименьшей стоимости и найти транспортные расходы для ТЗ. Исходные данные такие же, как в примере 1. Решение. Задача закрытая, так как Строим распределительную таблицу и начинаем ее заполнять с клетки (1; 1), т. к. в ней наименьший тариф (с 11 = 1): х 11 = min(90; 70) = 70. Из дальнейшего рассмотрения исключаем 1-й столбец, отметив его номером 1).
Затем заполняем клетку (1; 4) с наименьшим тарифом с 14 = 1: х 14 = min(а 1 – х 11; b 4) = min(90-70; 70) = min(20; 70) = 20. Из дальнейшего рассмотрения исключаем 1-ю строку, отметив ее номером 2). Далее (с 22 = 1): х 22 = min(100; 60) = 60; (с 24 = 3): х 24 = min(а 2 – х 22; b 4 – х 14) = min(100-60; 70-20) = min(40; 50) = 40; (с 34 = 4): х 34 = min(а 3; b 4 – х 14 – х 24) = min(90; 70-20-40) = min(90; 10) = 10; (с 33 = 5): х 33 = min(а 3 – х 34; b 3) = min(90-10; 80) = min(80; 80) = 80. Стоимость перевозок: Ранг матрицы системы Сравнивая значения Z в примерах 1 и 2, видим, что затраты при 2-м методе (с учетом стоимости перевозок) значительно меньше. Рассмотрим пример невырожденного плана: Пример 3. Построить начальный опорный план методом наименьшей стоимости. Решение: Задача закрытая, так как Ранг матрицы При заполнении таблицы на 4-м шаге одновременно зачеркнуты 2-я строка и 4-й столбец. Отмеченная уголком и звездочкой клетка (2, 3) заполняется нулем. В клетку (2, 1) нуль не пишем, так как она составляет цикл с заполненными клетками (70), (50) и (20). В клетку (3, 4) нуль не пишем, так как на момент зачеркивания на 4-м шаге линий i =2 и j =4 потребность в 70 ед. для столбца j =4 не остается. После построения начального опорного плана он проверяется на оптимальность методом потенциалов. Проверка опорного плана на оптимальность методом потенциалов Потенциалы – это набор из m + n чисел α i и β j, которые удовлетворяют условиям: - при решении задачи на минимум (Z → min): I. II. - при решении задачи на максимум (Z → max): I. II. Так как число переменных (потенциалов) m + n этой системы больше числа уравнений m + n -1, то система данных уравнений не определена и имеет ∞ множество решений. Поэтому для однозначного определения потенциалов один из них берут произвольно, например, α 1=0. Остальные потенциалы находятся последовательно с использованием условия I. Для занятых клеток значения оценок будут нулевыми ( Потенциалы записываются в дополнительных столбце и строке таблицы. Далее, используя полученные потенциалы и известные тарифы, для пустых клеток определяются оценки Условие оптимальности плана для задачи на max: оценки всех свободных клеток Замечание. Потенциалы могут быть рассчитаны только для невырожденного плана. Если план вырожденный (число заполненных клеток меньше, чем m + n -1), то вносятся нули в свободные клетки так, чтобы общее число занятых клеток стало равным m + n -1. Нуль вводят в клетку, расположенную в столбце или строке, вычеркиваемых одновременно при составлении начального плана.
5.4 Переход к не худшему опорному плану. Построение цикла Переход к не худшему опорному плану осуществляется при помощи построения цикла перераспределения груза. Цикл – это замкнутая ломаная, звенья которой взаимно перпендикулярны, а вершины цикла находятся в занятых клетках, кроме одной – начала цикла. Начало цикла находится в той свободной клетке, которая имеет наибольшую величину нарушения условия оптимальности II, т.е. наименьшую отрицательную (максимальную по модулю) оценку Цикл перераспределения груза обладает свойствами: - все его вершины, кроме начальной, расположены в занятых клетках; - звенья (стороны) расположены в строках и столбцах, т.е. две соседние вершины расположены либо в одной строке, либо в одном столбце; - в каждой вершине встречаются ровно два звена под прямым углом (одно звено находится в строке, другое – в столбце); - на звеньях могут быть занятые клетки, но они не являются вершинами; - точки пересечения ломаной линии цикла не являются вершинами. Два последних свойства обеспечивают некоторую минимальность цикла: он не должен распадаться на объединение двух или более меньших циклов. На рис.1 изображено несколько циклов с началом в незанятой клетке. Обозначения: О – незанятая клетка (начало цикла), * – занятая клетка; возможные места расположения занятых клеток отмечены черным кружком на звеньях. Рис.1 На рис.2 изображено несколько замкнутых ломаных, не являющихся циклами: «так нельзя». Штриховыми линиями обозначены возможности сокращения цикла или распада цикла на объединение (сумму) нескольких циклов. Рис.2
Построение циклов и перераспределение поставок груза будем выносить за пределы таблицы и рассматривать отдельно. После построения цикла клетке начала цикла присваивают знак «+», начиная с неё, остальным вершинам цикла знаки присваиваются поочередно: «–», «+» и т.д. Из всех клеток цикла (объемов груза, величин поставок) со знаком «–» выбирают ту, в которой находится минимальный груз (обозначим Θ). Это количество груза Θ перераспределяется (сдвигается) по циклу, т.е. в клетках со знаком «+» величина Θ прибавляется, а в клетках со знаком «–» – вычитается. Клетка в начале цикла, которая ранее была свободной, становится занятой (базисной), а одна из занятых «–» клеток (с меньшим значением Θ) становится пустой (свободной). Если наименьшее значение Θ появляется сразу в нескольких «–» клетках, то для перераспределения величины Θ выбирается любая из них. При перераспределении поставок эти клетки с одинаковыми значениями Θ будут освобождаться, и план станет вырожденным (число заполненных клеток будет меньше m + n -1). Поэтому для продолжения решения необходимо в эти одновременно освобождающиеся клетки (кроме той, которая станет свободной) поставить значение «0», причем предпочтение отдается клеткам с наименьшим тарифом. Нулей вводим столько, чтобы во вновь полученном плане число заполненных клеток стало равно m + n -1. Клетки, которые не задействованы в цикле, остаются неизменными. В результате получается новый опорный план, который заносится в таблицу. Подсчитываются транспортные расходы Z, которые должны быть не более предыдущих. В противном случае где-то допущена ошибка. Новый план опять проверяется на оптимальность методом потенциалов. Улучшение планов проводят до тех пор, пока на очередном шаге все оценки в незаполненных клетках будут неотрицательными ( При заполнении клеток тарифами, поставками, оценками для контраста используют разные цвета, выделяют рамками, цикл в таблице или выносят отдельно, или выделяют отдельным цветом или штриховой линией. Рассмотрим пример проверки оптимальности плана методом потенциалов и построения цикла. Пример 4. Условия и таблица взяты из последнего примера 3:
Решение. Задача закрытая, План вырожденный (базисных клеток 5< rang= m + n -1=4+3-1=6). Метод потенциалов применим только для невырожденного плана, т.е. для определения потенциалов нужна еще одна занятая клетка. Такой клеткой будет (2, 3), ее заполняем нулем (так как находится во 2-й строке, вычеркнутой одновременно с 4-м столбцом на 4-м шаге, не является вершиной цикла и на момент зачеркивания на 4-м шаге линий i =2 и j =4 для столбца j =3 сохранилась потребность в 80 ед.). В уме определяем потенциалы из системы для всех базисных клеток α 1=0, α 1 + β 4 =1 => β 4 = 1, α 2 + β 4 =3 => α 2 = 2, α 2 + β 2 =1 => β 2 = -1, α 1 + β 1 =1 => β 1 = 1, α 2 + β 3 =4 => β 3 = 2, α 3 + β 3 =5 => α 3 = 3. Вычислим оценки для всех свободных клеток, используя 2-е условие оптимальности Δ 12=5-0+1=6, Δ 13=6-0-2=4, Δ 21=4-2-1=1, Δ 31=3-3-1=-1, Δ 32=3-3+1=1, Δ 34=6-3-1=2. Подчеркнем, что для занятых клеток Матрица оценок будет иметь вид: Стоимость этого плана (стоимость перевозок): Z (X 1)=70·1+20·1+60·1+50·3+80·5=700. Для перераспределения груза строим цикл с началом в клетке (3, 1) с отрицательной оценкой Δ 31 = -1. Для его пересчета выносим цикл отдельно. Минимальную поставку (объем перепоставки) груза определяем по вершинам с «–» знаками: Θ =min(70, 50, 80)=50. Эту величину вычтем из вершин c «–» знаками и прибавим к вершинам с «+» знаками. Старые поставки запишем вне цикла, а новые – внутри него. Клетка (3, 1) была свободной, после перераспределения свободной стала клетка (2, 4). Строим новую таблицу, в которую заносим новый план, состоящий из старых поставок, не вовлеченных в цикл, и новых – в вершинах рассмотренного цикла. Получили невырожденный план, в нем 6 отличных от нуля компонент, тогда как в первом вырожденном плане было 5 отличных от нуля компонент. Методом потенциалов определяем оценки клеток. Отрицательных оценок нет ( Z (X 2)=20·1+70·1+60·1+50·4+50·3+30·5=650. Ответ: Оптимальный план перевозок Стоимость плана Z (X 2) = 650.
|