Экономико-математическое моделирование как метод научного познания

План вычислений

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

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

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

 

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

в) отсутствие замкнутых контуров, Образованных базисными звеньями с потоками 0<Х

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

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

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

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

При потоке от вершины     присваивается потенциал     (где   длина звена). Если поток следует от, что потенциал определяется по следующей формуле

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

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

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

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

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

Если эти условия соблюдаются везде, то задача решена и план оптимален.

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

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

Условие 2.7 нарушено на звене А-Е:

       = 440- 220 = 220 > С = 200;

       = 220- 200=20.

Условие (2 8.) нарушено на звене Г-Д:

     = 330- 230 < С = 100;

     = 100-50 = 50.

На звене Е-Д условие оптимальности соблюдено. Выбираем звено с наибольшей невязкой Г-Д и переходим к пункту 4.

 

В                                                Д         А                                                                             Б                                       Г                         Е

 

Рисунок 2.3. Вырожденная схема потоков

 

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

Совокупность этого пути и звена с невязкой называется контуром.

Для начального варианта на рисунке 2.4. контур составляют звенья ГД, ДЖ, ЖБ и БГ. Для второго варианта (рисунок 2.5.) в контур входят звенья АЕ, ЕВ, ВЖ, ЖД, ДГ, ГА. для третьего варианта (рисунок 2.6.) контур состоит из звеньев БЖ, ЖБ, ВЕ, ЕА, АГ и ГБ.

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

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

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

б) Все другие потоки в контуре делятся на попутные и встречные этому потоку.

Так, для начального варианта (рисунок 2.4.) звенья ГД и БГ- попутные, а ДЖ и ЖБ- встречные, во втором варианте (рисунок 2.5.) звенья АЕ, ВЖ, ЖД попутные, а ЕБ, ДГ и ГА- встречные, в третьем варианте (рисунок 2.7.)- БЖ. ВЕ. АГ- попутные, а )КБ, БА, ГБ- встречные.

6. Определение изменение потоков  ΔХ.

Изменение потоков:

а) для пустого звена с невязкой ΔХ = min [minX; min(d-x)]  (2.9.)

где d-пропускная способность звена.

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

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

ΔХ = min [minХ; min(d-x)] (2.10.)

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

При использовании правил (2.9) и (2.10) звено с невязкой учитывается в числе попутных.

для начального варианта величина изменения потоков ΔХ1 определится как минимальное из следующих величин:

ΔХ1 =min [(20,8;(16-11), (10-6)]=4

 так как  звено с невязкой- пустое.

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

ΔХ2 =min [(15,16,22,30;(16-14),(16-15)]=1,

так как звено с невязко насыщенное.

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

ΔХ3 = min [(10,14,21;(16-15),(30-1),(30-4)]=1 ,

 так как  звено с невязки- насыщенное.

 

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

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

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

В расчете получается новый вариант плана, для которого заново определяются потенциалы, проверяется наличиё невязок и т.д. (те, от пункта 7 переходим к пункту 2).

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

Решение сетевой транспортной задачи непосредственно не содержит значений поставок по корреспонденциям, а дает лишь схему потоков по участкам

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

Такие равноценные оптимальные варианты называются альтернативными оптимумами.

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