|
Поиск оптимального решения методом потенциалов.Как отмечалось выше, поиск оптимального решения методом потенциалов состоит из двух этапов. Этап 2. Проверка оптимальности полученного плана перевозок. Введем специальные показатели ui для каждой строки матрицы перевозок (каждого поставщика), где 1=1,2,..., m, и показатели vj для каждого столбца (каждого потребителя), где j = 1,2,..., n. Эти показатели называются потенциалами поставщиков и потребителей, их удобно интерпретировать как цены продукта в соответствующих пунктах поставщиков и потребителей. Потенциалы подбираются таким образом, чтобы для заполненной клетки (i;j) выполнялось равенство (5.5.5). Совокупность уравнений вида (5.5.5), составленных для всех заполненных клеток (всех базисных неизвестных), образует систему m + n – 1 линейных уравнений с m + n неизвестными ui и vj. Эта система всегда совместна, причем значение одного из неизвестных i можно задавать произвольно (например, ui = 0), тогда значения остальных неизвестных находятся из системы однозначно. Рассмотрим процесс нахождения потенциалов для базисного начального распределения, представленного в таблице 5.5.6. Суммарные затраты на реализацию данного плана составят .
Таблица 5.5.6
Задав u1 = 0 и используя формулу (5.5.5) для заполненных клеток (1;1) и (1;2), находим v1= 4 и v2 = 5. Зная v2, по заполненной клетке (2;2) находим u2 = 2, а зная u2, по заполненной клетке (2;3) находим v3 = 8. Зная v3, по заполненной клетке (3;3) находим u3 = 1, а затем по заполненной клетке (3;4) находим v4 = 5. Результаты представлены в таблице 5.5.7, где потенциалы поставщиков приведены в последнем столбце, а потенциалы потребителей - в последней строке. Таблица 5.5.7
Смысл прямоугольного контура, проведенного пунктиром в таблице 5.5.7, и знаков при его вершинах будет пояснен далее при описании этапа третьего метода потенциалов. Чтобы оценить оптимальность распределения, для всех клеток (i,j) матрицы перевозок определяются их оценки, которые обозначим через dij по формуле . (5.5.6) Используя ранее принятую интерпретацию, выражение (ui + сij) можно трактовать как сумму цены продукта у поставщика и стоимости перевозки; эта сумма путем вычитания сравнивается с ценой продукта у соответствующего потребителя vj. Очевидно, оценки заполненных клеток равны нулю (цена потребителя покрывает цену поставщика и стоимость перевозок). Таким образом, об оптимальности распределения можно судить по величинам оценок свободных клеток. Если оценка некоторой свободной клетки отрицательна, это можно интерпретировать так: цена, предлагаемая соответствующим потребителем, больше суммы цены поставщика и стоимости перевозки, т.е. если бы эта клетка была занята, то можно было бы получить дополнительный экономический эффект. Следовательно, условием оптимальности распределения служит условие неотрицательности оценок свободных клеток матрицы перевозок. Оценки клеток по формуле (5.5.6) удобно представить в виде матрицы оценок. Для ранее рассматриваемого распределения (табл. 5.5.7) матрица оценок клеток имеет вид . (5.5.1) Наличие большего числа отрицательных оценок свободных клеток свидетельствует о том, что данный план перевозок далёк от оптимального (напомним, что суммарные затраты на перевозку по этому плану равны 1170). Этап 3. Улучшение неоптимального плана перевозок (циклы перераспределения). Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с отрицательной оценкой; если таких клеток несколько, то обычно (но необязательно) выбирается клетка с наибольшей по абсолютной величине отрицательной оценкой. Например, для распределения, представленного в таблице 5.6, такой клеткой может служить клетка (1;3) [см. матрицу оценок (5.5.1)]. Для выбранной клетки строится замкнутая линия (контур), начальная вершина которой лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках; при этом направления отдельных отрезков контура могут быть только горизонтальными и вертикальными. Вершиной контура, кроме первой, является занятая клетка, где отрезки контура образуют один прямой угол (нельзя рассматривать как вершины клетки, в которых горизонтальные и вертикальные отрезки контура пересекаются). Очевидно, число отрезков контура, как и его вершин, будет четным. В вершинах контура расставляются поочередно знаки "+" и "-", начиная со знака "+" в выбранной свободной клетке. Пример простого контура показан пунктиром в таблице 5.5.7, хотя вид контура может быть самым разнообразным. Величина перераспределяемой поставки определяется как наименьшая из величин поставок в вершинах контура со знаком "-", и на эту величину увеличиваются поставки в вершинах со знаком "+" и уменьшаются поставки в вершинах со знаком "-". Это правило гарантирует, что в вершинах контура не появится отрицательных поставок. Начальная выбранная клетка окажется занятой, в то время как одна из занятых клеток при этом обязательно освободится. Если величина перераспределяемой поставки не в одной, а в контуре перераспределения (табл. 5.7), то освобождается только одна клетка, обычно с наибольшей стоимостью перевозки, а все другие такие клетки остаются занятыми с нулевой поставкой. Результат указанных операций для представленной в таблице 5.7 распределения поставок показан в таблице 5.8. Суммарные затраты на перевозки по этому плану составляют F = 4 × 30 + 5 × 0 + 2 × 30 + 3 × 100 + 7 × 10 + 4 × 110 = = 990, что то значительно меньше предыдущей суммы затрат 1170, хотя план перевозок в таблице 5.7 ещё не является оптимальным. Об этом свидетельствует наличие отрицательных значений в матрице оценок клеток этого плана (соответствующие потенциалы ui и vj найдены способом, изложенным при описании этапа 2):
.
Транспортные задачи, в базисном плане перевозок которых имеют место занятия клетки с нулевой поставкой (или в первоначальном распределении, или в процессе итераций), называются вырожденными; пример такой задачи представлен в таблице 5.8. В случае вырожденной транспортной задачи существует опасность зацикливания, т.е. бесконечного повторения итераций (бесконечного перебора одних и тех же базисных комбинаций занятых клеток). Как правило, в практических задачах транспортного типа зацикливание не встречается; тем не менее, следует знать, что существуют специальные правила, позволяющие выйти из цикла, если зацикливание всё же произойдёт. При отсутствии вырождения метод потенциалов конечен и приводит к оптимальному плану перевозок за конечное число шагов.
Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|