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

Каждый этап решения состоит из следующих девяти шагов (пунктов):

Порядок вычислений

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

В каждом столбце матрицы (2.1) находится клетка с минимальной стоимостью:

Сkj = min Сij

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

Xki = Bij

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

В таблице 2.1 для первого, второго и третьего столбца минимальные стоимости обнаружены в первой строке (390, 220, 130), для четвертого, пятого и шестого столбца – во второй строке (160, 430, 420).

 

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

Находятся суммы поставок по каждой строке ΣХij и разности между ресурсами поставщиков и предусмотренными поставками

Ri = Ai – Σ Xij

Разности R называются невязками или разбалансами Так, в таблице, в приближение № 1 разбалансы показаны в последнем столбце и равны для четырёх поставщиков соответственно -183, -67, +100, +150.

Приближение № 2 (-83, -67, -0, +150)

Приближение № 3 (-56, -67, -0, +123)

Приближение № 4 ( -56, -25, -0, +81)

Приближение № 5 ( 0, -25, -0, +25)

Приближение № 6 ( 0, 0, 0, 0)

 

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

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

 

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

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

Приближение № 2 - 1-я, 2-я  строки абсолютно недостаточные, 3-я, 4-я строки абсолютно избыточные.

Приближение № 3 - 1-я, 2-я и 3-я  строки абсолютно недостаточные,  4-я строка абсолютно избыточна.

Приближение № 4 - 1-я, 2-я и 3-я  строки абсолютно недостаточные,  4-я строка абсолютно избыточна.

Приближение № 5 - 1-я строка абсолютно достаточна; 2-я и 3-я  строки абсолютно недостаточные,  4-я строка абсолютно избыточна.

Приложение № 6 – все строки достаточны.

 

5. Преобразование матрицы стоимостей.

- включает в  себя следующие действия:

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

Сrj = min Сij

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

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

Сr1 = min (970, 1090)=970.

Во втором столбце наименьшая стоимость по избыточным строкам С r2 (1120,1260) = 1120, в третьем Сr3, (1090, 1190)=1090. В четвертом, пятом, шестом столбцах Сrj min по избыточным строкам не определяется, т.к. эти столбцы не имеют поставки в единственной недостаточной первой строке.

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

Сr1 = min (1090)=1090.

Во втором столбце наименьшая стоимость по избыточным строкам С r2 (1260) = 1260, в третьем Сr3, (1190)=1190.

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

Сr3 = min (940)=940.

В четвертом столбце наименьшая стоимость по избыточным строкам С r4 (1210) = 1210, в пятом Сr5, (1160)=1160.

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

Сr2 = min (1260)=1260.

В третьем столбце наименьшая стоимость по избыточным строкам С r3 (1190) = 1190.

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

Сr4 = min (1760, 940)=940.

В пятом столбце наименьшая стоимость по избыточным строкам С r5 (1480, 1210) = 1210.

 

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

Δj = Crj – Ckj

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

Например, в приближение № 1 в первом столбце Δj = 970-390 = 580,  во втором стелбце Δj = 1120-220 = 900, в третьем столбце Δj = 1090-130 =960. В четвертом, пятом, шестом столбцах значение Δ  не определяется т.к. поставка находится в избыточной строке.

Приложение № 2 в первом столбце Δj = 1090-970 = 120,  во втором столбце Δj = 1260-800 = 460, в третьем столбце Δj = 1190-710 = 480. В четвертом, пятом, шестом столбцах значение Δ  не определяется.

Приложение № 3 в четвертом столбце Δj = 940-860 = 80,  в пятом столбце Δj = 1210-1130 = 80, в шестом столбце Δj = 1160-1120 = 40. В первом, втором, третьем столбцах значение Δ  не определяется.

Приложение № 4 во втором столбце Δj = 1260-960 = 300, в третьем столбце Δj = 1190-870 = 320. В первом, четвертом, пятом, шестом столбцах значение Δ  не определяется.

Приложение № 5 в четвертом столбце Δj = 1760-1200 = 560,  в пятом столбце Δj = 1480-1470 = 10. В первом, втором, третьем, шестом столбцах значение Δ  не определяется.

Приложение № 6 – значение Δ  не определяется.

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

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

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

Δ = min (580, 900, 960) = 580

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

Для приближения № 2 - Δ = min (120, 460, 480) = 120

Для приближения № 3 - Δ = min (80, 80, 40) = 40

Для приближения № 4 - Δ = min (300, 320) = 300

Для приближения № 5 - Δ = min (560, 10) = 10

Для приближения № 6 – не определяется

 

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

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

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

Сsd = Ctd

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

Xsd > 0

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

sd → td

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

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

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

Приложение № 2 – из клетки 1.1 в клетку 4.1

Приложение № 3 – из клетки 2.6 в клетку 4.6

Приложение № 4 – из клетки 1.2 в клетку 4.2

Приложение № 5 – из клетки 2.5 в клетку 1.5 и из клетки 1.2 в клетку 4.2

Приложение № 6 – не определяется.

 

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

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

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

Приложение № 2 – цепь между клетками 1.1 – 4.1

Приложение № 3 – цепь между клетками 2.6 – 4.6

Приложение № 4 – цепь между клетками 1.2 – 4.2

Приложение № 6 – не определяется.

 

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

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

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

ΔХ = min [ │Rнач │; │Rкон │; Xij ]

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

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

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

ΔХ = min  (183, 100, 127) = 100,

а по цепи, найденной в приближение № 5:

ΔХ = min (25, 25, 35) = 25.

Приближение № 2 –  ΔХ = min (83, 150, 27) = 27.

Приближение № 3 –  ΔХ = min (67, 123, 42) = 42.

Приближение № 4 –  ΔХ = min (56, 81, 99) = 56.

Приближение № 6 – не определяется.

 

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

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

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

При выполнении пункта 9 во втором приближение 27 единиц поставок переносятся из клетки 1.1 в клетку 4.1 и происходит переход к приближению 3. В третьем приближение 42 единицы поставок переносится из клетки 2.6 в клетку 4.6; в четвертом приближении 56 единиц поставок переносятся из клетки 1.2 в 4.2; в пятом приближении 25 единиц поставок переносятся из клетки 5.2 в 2.4 (цепь 2.5-1.5 – 1.2-4.2). Полученное в результате шестого приближение после проверки на шаге 3 алгоритма решения оказывается оптимальным.

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

 

2.3. Решение сетевых транспортных  задач методом потенциалов

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

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

делятся на три категории:

• базисные с потоками 0<Xrs<drs
• пустые без потока данного груза Xrs = 0
• насыщенные Xrs = drs

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

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

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

• для базисных звеньев Us – Ur = Сгs, (2.6)

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

• для пустых звеньев   Us - Ur ≤ Crs    (2.7)
• для насыщенных звеньев   Us - Ur ≥ Crs    (2.8)

Равенство во всех случаях допустимо и не противоречит оптимальности схемы. Нарушение условий (2.7) и (2.8), т.е.  Us - Ur ≤ Crs – для пустого звена и Us - Ur ≥ Crs – для насыщенного говорит о неоптимальности плана и указывает путь к его улучшению.

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