Оценка возможности практической реализации разработанной ЭММ

Решение такой модели крайне трудно, поскольку размеры практической задачи для завоза грузов в регион определяются следующими параметрами:

А - число переменных, решаемой задачи , определяется:

A=Q*i*k*m*s*n

Где численные значения параметров по минимальным значе­ниям равны:

Q - род груза - 11;

i - пункты производства - 20; .

к - порты назначения (базовые без развоза) -7;

s - альтернативные пункты перевалки - 3;

m - виды транспорта - 5;

п - альтернативные пункты вторичной перевалки - 2.

Тариф за перевозку в целом по схеме. И то, и другое дифференцировано.

Таким образом, минимальное число переменных составит:

А=11*20*7*5*3*2=46200

При этом число уравнений равно:

Б=11+20+7+5+3+2=48

Число элементов матрицы решаемой модели есть произведение А*Б=46200*48=2217600

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

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

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

2. ЭММ логистической транспортной задачи в упрощенной постановке:

2.1. Все грузы из пунктов производства должны быть отправлены:

Оценка возможности практической реализации разработанной ЭММ - student2.ru

2.2. Все грузы в пункты потребления должны быть доставлены:

Оценка возможности практической реализации разработанной ЭММ - student2.ru

2.3. Искомые переменные не должны быть отрицательными:

Xij ≥0

2.4. Затраты по доставке груза должны быть минимизированы:

Оценка возможности практической реализации разработанной ЭММ - student2.ru Оценка возможности практической реализации разработанной ЭММ - student2.ru

В такой постановке ЭММ может быть решена распределительным методом линейного программирования. Матрица решаемой задачи приведена ниже для случая когда три пункта отправления и четыре – потребления. В матрице каждый Х – это клетка (см. табл.3.1.)

Таблица 3.1

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

I J G1 G2 G3 G4
G1 G11 X11 G12 X12 G13 X13 G14 X14
G2 G21 X21 G22 X22 G23 X23 G24 X24
G3 G31 X31 G32 X32 G33 X33 G34 X34

Но это частный случай, который в жизни встречается редко. Кроме того, этот метод не является универсальным и пригоден только для двухиндексных ЭММ, но практика намного сложнее, как видно из постановки 1, где оптимизируемых параметров ЭММ – индексов 7.

Ясно, что в распределительную матрицу приведенная выше задача (1) не вписывается. Как быть? Свести в симплексную матрицу, где каждый Х вектор – столбец, каждое уравнение – вектор – строка.

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

Таблица 3.2

Симплексная матрица двухиндексной транспортной задачи

  Хij Х11 Х12 Х13 Х14 Х21 Х22 Х23 Х24 Х31 Х32 Х33 Х34
Р  
Gi=1                
Gi=2                
Gi=3                
Gj=1                  
Gj=2                  
Gj=3                  
Gj=4                  
Зij З11 З12 З13 З14 З21 З22 З23 З24 З31 З32 З33 З34

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

3.1. Постановка задачи

 
  Оценка возможности практической реализации разработанной ЭММ - student2.ru

Рис.3.3. Диаграмма грузопотоков

γ – прямой грузопоток (3);

к – обратный грузопоток (3);

i – тип флота (2);

j – круговой рейс;

ГТ – 2000 т. состав – 3600 т.(2б*1800)

Xijtk – число отправлений i-го типа флота на j круговом рейсе при сочетании γ и к грузопотоков;

Эij yk – соответственно эксплуатационные расходы.

3.4. ЭММ

Функция цели – затраты на перевозки должны быть минимальными:

Оценка возможности практической реализации разработанной ЭММ - student2.ru

1) В прямом направлении перевозки должны быть выполнены.

Оценка возможности практической реализации разработанной ЭММ - student2.ru

2) В обратном направлении перевозки должны быть выполнены.

Оценка возможности практической реализации разработанной ЭММ - student2.ru Оценка возможности практической реализации разработанной ЭММ - student2.ru =Gk k=1-3;

3) Перевозки должны быть выполнены имеющимися ресурсами флота.

∑ tijyk * Xijtk Оценка возможности практической реализации разработанной ЭММ - student2.ru Фm*Tom i=1-2

j=1

4) Искомые переменные не должны быть отрицательными

Xijtk Оценка возможности практической реализации разработанной ЭММ - student2.ru 0 i=1; jyk =1…15;

Qiλ, Qik - соответственно эксплуатационная загрузка i-го типа флота на ук грузопотоках;
Фi – ресурсы i-го типа флота;

Э ijyk - расходы i–го типа на jyk круговом рейсе.

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

Ниже приводится симплексная матрица ЭММ на условия изложенные в 3.1. (табл.З.3).

Решение ЭММ

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

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

Таблица 3.3

Симплексная матрица ЭММ разработки плана использования флота. I=1 i=2
    110.1.0 1.11.20 1.12.30 1.13.01 1.14.02 1.15.03 2.16.11 2.17.12 2.18.13 2.19.21 2.20.22 2.21.23 2.22.31 2.23.32 2.24.33 2.25.10 2.26.20 2.27.30 2.28.01
р  
200 Gy=1                                        
150 Gy=2                                        
100 Gy=3                                        
100 Gk=1                                        
80 Gk=2                                          
70 Gk=3                                          
2000 Фi=11                          
3000 Фi=1                              
Sijyk 2.1 2.2 2.1 2.15 2.22 2.2 2.25 2.3 3.5 3.5 3.6 3.7 1.9 2.15 2.25 2.15 2.2 2.3 2.4 2.3 2.5 3.5 4.5 4.0 4.0

Алгоритм метода абсолютного приоритета 1-я итерация

Выбирается вектор столбец по критерию.

1) min по Sijyk

Рассчитывается искомая переменная

Оценка возможности практической реализации разработанной ЭММ - student2.ru

2) …

3) Корректировка вектора условий GГ;Gk',Ф,ТОТ

4) вычеркивание уравнений и переменных из матрицы, которые уже отработали

2-я'итерация

Из оставшихся переменных и уравнений все повторяем (1, 2, 3, 4)
до выполнения ограничений по перевозкам. Приведенная ЭММ - это ча­
стный случай, который в жизни не существует (только для учебных це­
лей).
Фактические параметры реальных задач:

1) y,k- сотни;

2) i – десятки;

3) базы отстоя до десяти;

4) три периода навигации;

5) равенство судопотоков вверх вниз по каждому судну;

6) ввод и вывод из эксплуатации в одни и те же пункты;

7) равенство входа и выхода по каждому судну в каждый порт, то есть на каждом j-ом круговом рейсе, для каждого i-го тала судна до 7-10 параметров, то есть М=А*Б.

А находится перемножением 7- 10 параметров по вариантам.

Б - находится сложением всех параметров варьирования по группам – уравнения. Такие задачи даже на мощных сетевых ЭВМ часами.

Поэтому и рекомендуются приближенные методы.

Какие еще существуют ЭММ (перечень не полный):

- линейные;

- нелинейные (обоснование параметров систем обслуживания, средств производства и т.д. идут в комплексе с теорией массового обслуживания);

- теория массового обслуживания (теория очередей);

- целочисленные задачи и соответствующие методы;

- имитационное моделирование;

- параметрические и стохастические модели;

- теория игр и т.д.

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

Наши рекомендации