<<
>>

Критерии оптимальности.

Выбор критерия зависит от: характера проблемы, наличной информации и требуемой точности нахождения оптимума.

Примерами локального критерия оптимальности транспортной задачи могут служить:

а) критерий минимума суммарного пробега (пригоден только для решения закрытых транспортных задач в пределах одного вида транспорта);

б) при оптимизации перевозок в пределах года обычным стоимостным критерием является сумма зависящих приведенных расходов:

C = Эзав + Эпер + Еп (К пс + C гр ),

где Эзав - зависящие от движения эксплуатационные расходы,

Кпс - капитальные вложения в подвижной состав,

Сгр - стоимость грузов, находящихся в процессе перевозки,

Эпер - издержки по перевалкам;

в) при составлении оптимальных схем перевозок на перспективу возможно усиление пропускной способности линий в зависимости от размещения на них оптимальных грузопотоков.

Поэтому в критерии оптимальности учитывается:

Кпост - затраты на необходимое развитие пропускной способности по по-стоянным устройствам,

Энез - независящие эксплуатационные расходы.

Тогда

C = Эзав + Энез + Еп(Кпс + Кпост + Cгр) ;

477

г) в некоторых случаях при решении открытых транспортных задач допускается использование в качестве критерия суммы издержек производства и та-рифных плат за перевозки;

д) в отдельных задачах по оптимизации срочных перевозок в качестве критерия выступает время: тонно-часы (вагоны-часы) пребывания груза в процессе перевозки или общее время завершения определенной перевозочной операции.

Из многих методов решения матричных задач наиболее распространенными являются: метод потенциалов (Л. А. Канторович и М.В. Говурин) и метод условно-оптимальных планов (А. Л. Лурье).

Метод условно-оптимальных планов относится к методам сокращения невязок:

в начальном варианте допускается нарушение основных ограничений транспортной задачи

X Xij = Bj (j = 1, 2, ...

л); X Xij = Ai (i = 1, 2, ... m);

i j

допущенные невязки и разбалансировки устраняются путем внесения ряда поправок.

Основные этапы метода условно-оптимальных планов можно рассмотреть на примере некоторой транспортной задачи (см. табл. 17.1), требующей увязать ресурсы трех поставщиков А1, А2, A3 (строки табл. 17.1) с потребностями че-тырех потребителей В1^В4 (столбцы табл. 17.1). В правых верхних углах клеток матрицы показаны стоимости перевозки Су единицы груза от поставщика и потребителя Вj - оптимальное решение будет получено за четыре этапа реше-ния, которые называют приближениями задачи и также показаны в табл. 17.1.

Пример решения матричной транспортной задачи методом условно-оптимальных планов Номер прибли-жения Поставщик и Потребитель и его потребность, Bj Сумма по-ставок Разба-лансы Л,- его ресурс, ЛІ B 7 B2 9 B3 9 B4 5 ^xij J J A1 10 10/12 7 12/14 9 9/11 15/17 5 21 -11 1 A2 10 1 14

Г 20 8 9 50 9 +1 A3 10 12 15 20 25 0 +10 Aj 12-10=2 15-12=3 - 25-15=10 A1 10 12/13 4/15 9 11/12 17/18 5 14 -4 2 A2 10 14 1 20 8 9 50 9 +1 A3 10 12 7 15 20 25 7 +3 Aj - 1 - 8 A1 10 і ^ 13/15 5/17 6 2/14 8/20 5 11 -1 3 A2 10 14 1 20 8 9 50 9 +1 A3 10 2/14 7 15/17

3 20/22 25/27 10 -0 Aj 14-12=2 20-15=5 - 50-18=32 Aj 10 15 17 5 14 20 5 10 +0 4 A2 10 14 1 20 8 9 50 10 +0 A3 10 14

6 17 4 22 27 10 +0

Каждый этап решения состоит из 9-ти шагов (пунктов). 1. Построение начального варианта.

В столбцах 3-6 матрицы (табл. 17.1) находится клетка с минимальной стоимостью:

Сkj = min Cjj.

В эту клетку заносится поставка, равная полной потребности столбца:

Xkj = BJ.

При наличии нескольких клеток с минимальной стоимостью поставка Bj распределяется между ними произвольно.

В табл. 17.1 для первого, второго и четвертого столбцов минимальные стоимости обнаружены в первой строке (10, 12, 15), для третьего столбца - во второй (8).

Определение сумм поставок и невязок.

Находятся суммы поставок по каждой строке Z Xij и разности между ре-

J

сурсами поставщиков и предусмотренными поставками:

RI = 4 -z XIJ.

j

Разности Rj называются невязками или разбалансами.

Так, в таблице, в приближении № 1 разбалансы показаны в последнем столбце и равны для трех поставщиков соответственно -11, +1, +10.

Проверка наличия отрицательных разбалансов.

Отсутствие отрицательных разбалансов говорит об оптимальности найденного варианта решения. В приближении № 1 табл. 17.1 первая строка имеет отрицательный разбаланс -11, поэтому поиск оптимального решения будет продолжен.

Классификация строк.

Строка i считается абсолютно недостаточной, если ее разбаланс отрицательный, и абсолютно избыточной, если разбаланс - положительный. При R = 0 строки классифицируются на относительно избыточные и относительно недостаточные согласно примечанию, которое будет указано ниже. В приближении № 1 (табл. 17.1) 1-я строка абсолютно недостаточная, 2-я и 3-я строки - абсолютно избыточные.

Преобразование матрицы стоимостей. Включает в себя следующие действия:

а) в каждом столбце, имеющем поставку в недостаточной строке, находится минимальная из стоимостей на пересечении с избыточными строками:

С rj = min Cj;

I gU ,

где U - множество абсолютно и относительно избыточных строк.

Например, в приближении № 1 в 1-м столбце наименьшая стоимость по избыточным строкам:

С r1 = min (14, 12) = 12.

Во 2-м столбце наименьшая стоимость по избыточным строкам Cr2 = min (20, 15), в 4-м - Cr4 = min (50, 25) = 25. В 3-м столбце Cr1 min по избыточным строкам не определяется, так как этот столбец не имеет поставки в единственной недостаточной 1-й строке;

б) в каждом столбце, имеющем поставку в недостаточной строке, определяется разность между минимальной стоимостью по избыточным строкам и минимальной стоимостью по столбцу в целом:

A j = C rj - C kj .

Значение Aj фиксируется во вспомогательной строке (строкаj в табл. 17.1).

Например, в приближении № 1 в 1-м столбце Aj = 12-10 = 2, во 2-м Aj = 15- = 12 = 3, в 4-м столбце Aj = 15-15 = 10. В 3-м столбце значение A3 не определено, так как поставка находится в избыточной строке;

в) находится наименьшее значение из всех Aj:

A = min Aj, которое прибавляется по всем стоимостям во всех недостаточных строках.

Так, для приближения № 1 получаем:

A = min (2, 3, 10) = 2.

Все стоимости в недостаточной 1-й строке увеличиваются на A = 2, в остальных не меняются.

Значения стоимостей на этом этапе решения показываются дробью в правом верхнем углу клеток в недостаточных строках, причем в числителе дроби - первоначальное значение стоимости, в знаменателе - обновленное в соответствии с шагом 5 алгоритма решения задачи.

6. Нахождение связей строк, возникших в результате преобразования стоимостей в пункте 5.

Строка S считается связанной со строкой t при соблюдении 2-х условий:

а) в каком-либо столбце d имеется совпадение стоимостей

С sd = Ctd ;

б) в клетке sd имеется поставка

Xsd > 0.

481

При этих условиях существует направленная связь клеток:

sd ^ td.

При ручном выполнении расчетов связи удобно показывать стрелками на матрице.

Смысл понятия связи строк следующий. В рассматриваемом методе допустимыми для поставок являются клетки матриц с минимальными по столбцу стоимостями. После изменения стоимостей в матрице появляется новая допустимая клетка (иногда несколько), в которую может быть перенесена часть поставки из недостаточной строки.

Связь строк указывает возможное направление переноса поставки. Так, в приближении № 1 после изменения стоимостей в 1-й строке клетка 3.1 стала допустимой. Это означает возможность переноса поставки из клетки 1.1 в клетку 3.1, т.е. наличие связи между этими строками.

Нахождение последовательности (цепи) связей между абсолютно недостаточной и любой избыточной строками.

Цепь может состоять из одной или несколько связей и возникает после исполнения пункта 6. В нее всегда входит вновь образованная в этом пункте связь, начиная от которой удобно вести поиск цепи.

Например, в приближении № 3 новая связь появилась между клетками 3.1 и 2.1; от прежнего цикла (приближения) осталась связь клеток 1.2 и 3.2. Цепь от абсолютно недостаточной 1-й строки до избыточной 2-й строки проходит по клеткам 1.2-3.2 и 3.1-2.1. В приближении № 1 цепь состоит лишь из одной связи 1.1-3.1, так как эта связь начинается в абсолютно недостаточной и кончается в избыточной строке.

Определение величины переноса поставок AX, выполняемого одновременно по всем связям найденной цепи.

Эта величина равняется наименьшему из следующих чисел:

абсолютному значению разбаланса в недостаточной строке, где цепь начинается;

разбалансу в избыточной строке, где цепь кончается;

значению поставок во всех клетках, где начинаются связи, входящие в цепь:

нч

X

AX = min

/R /. R

нач кон

нч

где Xij - поставки в нечетных клетках цепи, если переписать их в порядке от недостающей строки к избыточной,

^нач, ^кон, - невязки в строках, где начинается и кончается цепь переноса поставок.

Например, величина переноса по цепи, найденной в приближении № 1, равна

AX = min (11, 10, 7) = 7, а по цепи, найденной в приближении № 3 -

AX = min (1,1,6,7) = 1.

9. Перенос поставок.

Найденное значение AX вычитается из поставок во всех нечетных по порядку клетках цепи и добавляется к поставкам во всех четных. В результате получается новый вариант плана, либо оптимальный, либо с меньшей по модулю суммой отрицательных разбалансов, чем предыдущий вариант. Далее метод условно-оптимальных планов предполагает переход к шагу 2 и циклическое продолжение шагов алгоритма до тех пор, пока в пункте не обнаружится, что отрицательных разбалансов больше нет и найденное решение оптимально.

Так, в приближении № 1 переносится 7 единиц поставок из клетки 1.1 в клетку 3.1 и происходит переход к приближению № 2.

При выполнении пункта 9 в приближении № 2 переносятся 3 единицы поставок из клетки 1.2 в клетку 3.2, и происходит переход к приближению № 3. В приближении № 3 единицы поставок переносятся из клетки 1.2 в клетку 3.2 и из клетки 3.1 - в клетку 2.1. Полученное в результате приближение № 4 после проверки на шаге 3 алгоритма решения оказывается оптимальным.

Решение матричной транспортной задачи с применением компьютеров позволяет использовать иной вариант метода условно-оптимальных планов - алгоритм дифференциальных рент, при котором переносы поставок по связям не делаются, а вместо этого на каждом цикле расчета все поставки распределяются заново по допустимым клеткам (с наименьшими по столбцу стоимостями, учитывая ранее выполненные изменения стоимости).

Для решения сетевых транспортных задач широко применяется метод потенциалов, который основан на свойстве потенциальности оптимального плана.

Пусть имеется некоторая схема потоков однородного ресурса (груза, порожних вагонов) по транспортной сети с ограниченной пропускной способностью звеньев. Пропускную способность звена r-s в направлении к s обозначим drs. Все звенья в зависимости от наличия потока х^ данного груза делятся на три категории:

базисные с потоками

пустые без потока данного груза xrs=0;

насыщенные xrs=drs.

Рассматривается однопродуктовая задача.

В многопродуктовой задаче насыщенными являются звенья с суммой потоков всех грузов, равной пропускной способности.

Если схема потоков оптимальна, всем вершинам сети могут быть присвоены потенциалы U, удовлетворяющие следующим условиям:

для базисных звеньев Us - Ur = Crs, (17.7)

где Crs - расстояние или издержки (в зависимости от используемого критерия) перевозки единицы груза от r до s;

для пустых звеньев Us - Ur < Crs; (17.8)

для насыщенных звеньев Us - Ur > Crs.

Равенство Us - Ur = Crs во всех случаях допустимо и не противоречит оптимальности схемы. Нарушение условий (17.7) и (17.8), т.е. Us - Ur> Crs для пустого звена и Us - Ur< Crs - для насыщенного говорит о неоптимальности плана и указывает путь к его улучшению.

При решении сетевой задачи вначале разрабатывается исходная схема потоков. Затем ведется циклический расчет по улучшению плана. Каждый цикл включает в себя присвоение потенциалов вершинам, проверку условий (17.7) и (17.8) и замещение схемы потоков.

1. Построение начального плана.

Начальная схема потоков должна удовлетворять следующим требованиям:

а) соблюдение условия баланса для всех вершин сети:

Z Xks -Z Xrk = Rk ;

(сдача) (прием) +погрузка выгрузка

б) непревышение пропускной способности звеньев, поток Xrs < drs на всех дугах сети;

в) отсутствие замкнутых контуров, образованных базисными звеньями с потоками 0Желательно построить начальную схему без явных нерациональностей (встречностей, кружностей), что позволит сократить число вводимых впоследствии поправок.

2. Присвоение потенциалов всем вершинам сети.

Какой-либо вершине, к которой примыкает хотя бы одно базисное звено, присваивается произвольный потенциал (число одного порядка с наибольшей дальностью перевозок). Затем присваиваются потенциалы остальным вершинам сети, следуя по всем базисным звеньям и используя равенство Us—Ur = Crs. При потоке от R^S вершине S присваивается потенциал Us=Ur+Crs (где Crs - длина звена). Если поток следует от S к R, то потенциал определяется по следующей формуле: Us=Ur - Crs.

Е -6

В этом случае имеющихся базисных звеньев недостаточно для присвоения потенциалов всем вершинам. Тогда вводятся n-1 нулевые потоки, связывающие между собой отдельные системы базисных звеньев. Звенья с нулевыми потоками считаются базисными и используются для присвоения потенциалов.

485

В процессе присвоения потенциалов может обнаружиться так называемый случай вырождения: совокупность (граф) базисных звеньев распадается на n несвязанных между собой систем. На рис. 17.10 показаны две такие системы: В-А-Г и Д-Б-Е.

В задаче с ограничениями пропускной способности компоненты базисного графа могут быть отделены друг от друга не только пустыми, но и насыщенными звеньями. Тогда вводятся условные нулевые резервы пропускной способности на некоторых насыщенных звеньях, которые далее считаются базисными.

3. Проверка соблюдения условий (17.7 и 17.8) на всех пустых и насыщенных звеньях сети.

280

200

+29

Если эти условия соблюдаются везде, то задача решена и план оптимален. При наличии нарушений-невязок Ну выбираем участок с наибольшей невязкой и переходим к пункту 4. На рис.17.11 показан начальный вариант плана сетевой транспортной задачи с ограничениями пропускной способности звеньев. Вершинам сети присвоены потенциалы. Проверка нужна для пустых звеньев А-Е, Е-Д и насыщенного звена Г-Д. Остальные звенья - базисные. Длины звеньев в направлении «туда» и «обратно» совпадают.

Условие 17.7 нарушено на звене А-Е: Ve - Ua = 440 - 220 = 220 > Cae = 200; Нае = 220 - 200 = 20. Условие (17.8) нарушено на звене Г-Д: Ud - Ur = 330 - 280 = 50 < Crd = 100; Hrd = 100 - 50 = 50. На звене Е-Д условие оптимальности соблюдено. Выбираем звено с наибольшей невязкой Г-Д и переходим к пункту 4.

4. Поиск пути по базисным звеньям между вершинами-концами звена с невязкой.

Совокупность этого пути и звена с невязкой называется контуром. Для начального варианта на рисунке 17.11 контур составляют звенья Г-Д, Д-Ж, Ж-Б и Б-Г. Для второго варианта (см. рис. 17.12) в контур входят звенья А-Е, Е-В, В-Ж, Ж-Д, Д-Г, Г-А, для третьего варианта (см. рис. 17.13) контур состоит из звеньев Б-Ж, Ж-Б, В-Е, Е-А, А-Г и Г-Б.

280

200

+29 240

280

200

Дальнейшее действие зависит от того, является ли звено с невязкой пустым или насыщенным.

Классификация потоков контура.

а) Устанавливается направление потока на звене с невязкой от меньшего потенциала к большему;

б) все другие потоки в контуре делятся на попутные и встречные этому потоку. Так, для начального варианта (рис. 17.11) звенья Г-Д и Б-Г - попутные, а

Д-Ж и Ж-Б - встречные, во втором варианте (рис. 17.12) звенья А-Е, В-Ж, Ж-Д - попутные, а Е-В, Д-Г и Г-А - встречные, в третьем варианте (рис. 17.13) Б-Ж, В-Е, А-Г - попутные, а ЖБ, БА, ГБ - встречные.

Определение изменения потоков АХ. Изменение потоков:

а) для пустого звена с невязкой:

< >

АХ = min[ min X; min(d - x)], где d - пропускная способность звена.

Следовательно, поправка равна меньшей из двух величин: наименьшего встречного потока и наименьшего свободного остатка пропускной способности для попутных потоков;

б) для насыщенного звена с невязкой (в точности обратное правило):

> <

AX = min[ min X; min(d - x)], т.е. берутся наименьший попутный поток и наименьший из резервов пропускной способности для встречных потоков. При использовании правил (17.9) и (17.10) звено с невязкой учитывается в числе попутных. Для начального варианта величина изменения потоков АХ1 определится как минимальное из следующих величин:

AX1 = min[(20,8, (16 -11), (10 - 6)] = 4, так как звено с невязкой - пустое.

Для второго варианта величина изменения потоков АХ2 определится следующим образом:

AX2 = min[(15,16,22, 30, (16 -14), (16 -15)] = 1, так как звено с невязкой - насыщенное.

Для третьего варианта величина изменения потоков АХ3 определится так:

AX3 = min[(10,14,21, (16 -15), (30 -1)(30 - 4)] = 1, так как звено с невязкой - насыщенное.

7. Исправление плана.

а) при исправлении невязки на пустом звене потоки по всем попутным звеньям контура (включая звенья с невязкой) увеличиваются на АХ, а по встречным - уменьшаются на АХ;

б) при исправлении невязки на насыщенном звене, наоборот, потоки на всех попутных звеньях контура уменьшаются, а на встречных увеличиваются на АХ.

В расчете получается новый вариант плана, для которого заново определяются потенциалы, проверяется наличие невязок и т.д. (т.е. от пункта 7 переходим к пункту 2). Расчет заканчивается, когда в пункте 3 не будет обнаружено ни одной невязки, что и происходит в 4-м варианте решения, которое является оптимальным и показано на рис. 17.14.

200

Решение сетевой транспортной задачи непосредственно не содержит значений поставок по корреспонденциям, а дает лишь схему потоков по участкам. Поставки по корреспонденциям должны быть получены исходя из этой схемы, причем одной и той же оптимальной схеме потоков часто соответствует много вариантов поставок, равноценных по значению критерия оптимальности.

Такие равноценные оптимальные варианты называются альтернативными оптимумами. Например, в варианте на рис. 17.13 груз, прибывший от Б к Г, может быть выгружен в Г или направлен далее к Д в составе потока 15 единиц по участку Г-Д. При наличии альтернативных оптимумов из них можно выбрать более удобный или выгодный по соображениям, не учтенным в критерии оптимальности. Простота и наглядность нахождения большого числа альтернативных оптимумов является одним из преимуществ сетевой постановки транспортной задачи.

<< | >>
Источник: Н.П. Терёшина, В.Г. Галабурда, М.Ф. Трихунков и др.. Экономика железнодорожного транспорта: Учеб. для вузов ж.-д. транспорта Н.П. Терёшина, В.Г. Галабурда, М.Ф. Трихунков и др. ; Под ред. Н.П. Терёшиной, Б.М. Лапидуса, М.Ф. Трихункова. - М.: УМЦ ЖДТ.. 2006

Еще по теме Критерии оптимальности.:

  1. 1.4. МЕТОДЫ ОЦЕНКИ ОПТИМАЛЬНОСТИ ТОВАРНЫХ ЗАПАСОВ
  2. 2.2. РАСЧЕТ ОПТИМАЛЬНОГО РАЗМЕРА ЗАКАЗЫВАЕМОЙ ПАРТИИ
  3. 1.2 Технологические цели и критерии их достижения. Постановка технологической задачи ректификации нефти
  4. 5.3. Формирование максимальных по объему подмножеств оптимальных последовательностей
  5. 2.2.2 ПРОВЕРКА НА ОПТИМАЛЬНОСТЬ
  6. 2.2.2П ПРОВЕРКА НА ОПТИМАЛЬНОСТЬ
  7. Вопросы синтеза оптимальных ЛДС
  8. 7.9. Экономико-математический анализ полученных оптимальных решений
  9. Критерии оптимальности.
  10. § 4. КРИТЕРИЙ КАЧЕСТВА РЕГУЛИРОВАНИЯ И НАДЕЖНОСТЬ ДЕЙСТВИЯ СИСТЕМЫ
  11. 5.7. Критерии стабильности правовой системы
  12. Принцип оптимальности
  13. Глава 5.НАСТАИВАЙТЕ НА ИСПОЛЬЗОВАНИИ ОБЪЕКТИВНЫХ КРИТЕРИЕВ
  14. §1. Критерий ожидаемого значения.
  15. Критерии, основанные на известных вероятностях стратегий природы.
  16. Система критериев оценки эффективности техникокриминалистического обеспечения осмотра места происшествия
  17. ТЕМПЕРАТУРНЫЕ КРИТЕРИИ ДЛЯ ПРЕСНОВОДНЫХ РЫБ СЕВЕРО-ЗАПАДА РОССИИ
  18. 87. ОСНОВНЫЕ КРИТЕРИИ ЯЗЫКОВОГО КАЧЕСТВА РЕЧИ
  19. Критерии оценки эффективности формирования профессиональной языковой культуры студентов с применением мульти мед ий ного учебно-методического комплекса
  20. §2. Критерии эффективности муниципального правотворческого процесса.