Пиши Дома Нужные Работы

Обратная связь

Методика решения транспортной задачи

Задачи имитационного моделирования решаются итерационными методами (методами приближений). Исследование и решение транспортной задачи, как правило, проводят в два этапа.

1. Построение опорного плана. Находят произвольное решение, хотя бы и неудачное.

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

 

Построение опорного плана

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

 

Алгоритм метода аппроксимации Фогеля

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

2. Поиск максимальной из всех разностей, как по строкам, так и по столбцам (максимальная разность обводится рамкой).

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

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

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



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

Вычисление целевой функции опорного плана

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

 
 

Рис. 3. Исходные данные транспортной задачи в форме графа

 

B a
B1 B2 B3 B4
A1 14
A A2 20
A3 26
A4 41
b 30 22 15 34

Рис. 4. Исходные данные транспортной задачи в форме матрицы

 

Построим опорный план методом Фогеля (рис. 5).

B a
B1 (v1) B2 (v2) B3 (v3) B4 (v4) Столбцы разностей по строкам
A1 (u1) * * * 14
A A2 (u2) * * * 20
A3 (u3) * 26
A4 (u4) * * 41
b 30 22 15 34
ШАГ1
ШАГ2
ШАГ3
ШАГ4
ШАГ5
x x ШАГ6
Строки разностей по столбцам

Рис. 5. Опорный план перевозок

 

В результате имеем следующий план перевозок:

Поставщик Потребитель Кол-во единиц груза
A1 B3
A2 B2
A3 B1
A3 B2
A3 B3
A4 B1
A4 B4

Вычисление целевой функции опорного плана.Суммарные приведенные затраты на перевозку всего груза составляют:

Y0 = c13x13+ c22x22+ c31x31+ c32x32+ c41x41+ c44x44 = 24×14 + 18×20 + 19×23 + 10×2 + 100×1 + 3×7 + 8×34 = 1546 (усл. ед.).

Здесь и далее Yi обозначает, что значение целевой функции относится к i-му шагу оптимизации. Опорный план ‑ Y0.

В настоящее время существует несколько методов последовательного улучшения опорного плана, например распределительный метод, метод потенциалов и т.д. Основой алгоритмов этих методов является критерий оптимальности dij = cij - zij > 0, где cij – затраты, связанные с доставкой одной единицы ресурса из i-го в j-й пункт; zij – расчетные затраты, связанные с доставкой одной единицы ресурса из i-го в j-й пункт, для тех клеток опорного плана, ресурсы в которые не распределены.

Если все δij > 0, то данный план является оптимальным, если нет, то требуется его улучшение.

 

Алгоритм метода потенциалов

Пусть имеется матрица перевозок, соответствующая начальному решению хij= (распределенные ресурсы), xij = 0 для свободных переменных (ресурсы не рас-пределены). Клетки, соответствующие свободным ресурсам, помечены звездочками.

В крайний правый столбец матрицы введем неизвестные ui, а в нижнюю строку – неизвестные vj. Эти n и m неизвестных должны для всех i, j, соответствующих базисным переменным, удовлетворять линейной системе уравнений

ui + vj = cij,(1)

Можно доказать, что эта система для всех базисных решений имеет треугольный вид. Её ранг равен n+m-1, и, следовательно, систему всегда можно решить следующим способом. На первом шаге полагают vn = 0. Если на k-м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения (1), так как значение другой неизвестной в этом уравнении уже известно. Это верно до тех пор, пока не найдены все неизвестные. То, какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб. Переменные ui и vj называются потенциалами.

 

1.Составим и решим систему уравнений (1).

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

2. Определим расчетные значения затрат zij для клеток, в которые ресурсы не распределены (со свободными переменными):

zij = ui + vj;

3. Вычислим разность заданных и расчетных затрат dij = cij - zij и проверим условие оптимальности dij > 0.

Если все di > 0, то исходный план является оптимальным, и переходят к пункту 5, в противном случае переходят к построению нового плана.

4. Построим новый план (уточним опорный план).

Выберем dab< 0,равное максимальному по модулю dij из состава отрицательных dij, т.е.

dab = - max êdi ê, dij > 0.

Индексом a, bпомечена свободная переменная xab, которая соответствует dab. Соответствующую клетку транспортной таблицы отметим знаком “+”.

Кроме клетки a, bтранспортной таблицы, пометим знаками «–» и «+» другие клетки, в которые ресурсы распределены таким образом, что в каждой строке и столбце транспортной таблицы число знаков «+» будет равно числу знаков «–». Это всегда можно сделать единственным образом, причем в каждой строке и в каждом столбце содержится максимум по одному «+» и «–».

Проставленные в таблице знаки «+» и «–» образуют прямоугольник, в углах которого расположены соответствующие знаки. Указанный прямоугольник далее представляется в виде фрагмента матрицы, который состоит из четырех клеток. В этих клетках производят перераспределение ресурсов (рис. 6).

b
- a + dab<0
+ -

 

Рис. 6. Фрагмент матрицы

 

Затем определяем минимум M из всех элементов, помеченных знаками «–», и выбираем одну клетку g,d где этот минимум достигается. При этом g,d обозначает клетку, в которую ресурсы далее распределяться не будут, а все ее содержимое будет распределено между остальными тремя клетками по следующему правилу:

а) в клетку, соседнюю клетке g,d новой таблицы записывается число M;

б) клетка g,d остается пустой;

г) в остальных клетках, помеченных знаками «+» и «–», число M вычитается из стоящего в клетке числа или складывается с ним, в соответствии со знаками;

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

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

5. Определим значение целевой функции, с учетом перераспределения в мат-рице (уточнение матрицы проводится до тех пор, пока хотя бы одно значение di <0).

Улучшим опорный план, который был получен ранее.

1. Составим и решим систему уравнений (1).

 

u1 + v3 = 24 = c13;

u2 + v2 = 18 = c22;

u3 + v1 = 19 = c31;

u3 + v2 = 10 = c32;

u3 + v3 = 100 = c33;

u4 + v1 = 3 = c41;

u4 + v4 = 8 = c44.

Таким образом, имеется семь уравнений и восемь неизвестных, поэтому одному из неизвестных дается произвольное значение, как правило, для облегчения расчетов рекомендуется задаваться нулевым значением. Например u3 = 0, тогда, решая последовательно соответствующие уравнения, получаем v1=19; v2=10; v3=100; v4=24; u1=-76; u2=8; u3=0; u4=-16.

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

z11 = u1 + v1 = –76 + 19 = –57;

z12 = u1 + v2 = –76 + 10 = –66;

z14 = u1 + v4 = –76 + 24 = –52;

z21 = u2 + v1 = 8 + 19 = 27;

z23 = u2 + v3 = 8 + 100 = 108;

z24 = u2 + v4 = 8 + 24 = 32;

z34 = u3 + v4 = 0 + 24 = 24;

z42 = u4 + v2 = –16 + 10 = –6;

z43 = u4 + v3 = –16 + 100 = 84.

Определим значения dij и проверим условия оптимальности dαβ> 0

δ11 = с11z11 = 70 – (–57) = 127 > 0;

δ12 = с12z12 = 38 – (–66) = 104 > 0;

δ14 = с14z14 = 92 – (–52) = 144 > 0;

δ23 = с23z23 = 56 – 108 = –52 < 0;

δ24 = с24z24 = 72 – 32 = 40 > 0;

δ34 = с34z34 = 30 – 24 = 6 > 0;

δ42 = с42z42 = 36 – (–6) = 42 > 0;

δ43 = с43z43 = 121 – 84 = 37 > 0.

Так как d23 < 0, то переходим к формированию нового плана.

3.Построим новый опорный план.

Для его построения строится фрагмент опорного плана (рис. 7) относительно клетки 2, 3 = α, β, т.к. потенциал в ней отрицательный δ23 = δαβ < 0.

 

b b
B2 B3 B2 B3
- a A2 * + d23<0 - a A2 +
+ A3 - + A3 * -
а   б
                             

Рис. 7. Фрагменты плана:

а – фрагмент опорного плана; б – фрагмент нового плана

 

4. Определим значение целевой функции по новому плану (рис. 8).

 

B a
B1 B2 B3 B4
A1 * * * 14
A A2 * * 20
A3 * * 26
A4 * * 41
b 30 22 15 34

 

Рис. 8. Представление нового плана в форме матрицы

 

Суммарные затраты по новому плану:

Y1 = 14·24+19·18+1·56+23·19+3·10+7·3+34·8=1494 (усл. ед.).

Прежнее значение суммарных затрат составляло 1546 (усл. ед.).

Рассчитаем процент улучшения опорного плана:

D = 100%= 100 % = 3,36 %.

Проведем второй шаг оптимизации.

1. Составим и решим систему уравнений (1)

u1 + v3 = 24 = c13;

u2 + v2 = 18 = c22;

u2 + v3 = 56 = c23;

u3 + v1 = 19 = c31;

u3 + v2 = 10 = c32;

u4 + v1 = 3 = c41;

u4 + v4 = 8 = c44.

При u2 = 0, получим решение v1= 27; v2= 18; v3= 57; v4= 32; u1= –32; u2 = 0; u3 = –8; u4= –24.

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

z11 = u1 + v1 = –32 + 27 = –5;

z12 = u1 + v2 = –32 + 18 = –14;

z14 = u1 + v4 = –32 + 32 = 0;

z21 = u2 + v1 = 0 + 27 = 27;

z24 = u2 + v4 = 0 + 32 = 32;

z33 = u3 + v3 = –8 + 56 = 48;

z34 = u3 + v4 = –8 + 32 = 24;

z42 = u4 + v2 = –24 + 18 = –6;

z43 = u4 + v3 = –24 + 56 = 32.

 

3. Определим значения dij и проверим условие оптимальности dij> 0.

δ11 = с11z11 = 70 – (–5) = 75 > 0;

δ12 = с12z12 = 38 – (–14) = 52 > 0;

δ14 = с14z14 = 92 – 0 = 92 > 0;

δ21 = с21z21 = 58 – 27 = 31 > 0;

δ24 = с24z24 = 72 – 32 = 40 > 0;

δ33 = с33z33 = 100 – 48 = 52 > 0;

δ34 = с34z34 = 30 – 24 = 6 > 0;

δ42 = с42z42 = 36 – (–6) = 42 > 0;

δ43 = с43z43 = 121 – 32 = 89 > 0.

Так как все dij > 0, то данный план является оптимальным.

 

Окончательно представим оптимальный план перевозок (рис. 9, 10).

 

 

 

Рис. 9. Оптимальный план перевозок в форме графа

 

B a
B1 B2 B3 B4
A1 * * * 14
A A2 * * 20
A3 * * 26
A4 * * 41
b 30 22 15 34

 

Рис. 10. Оптимальный план перевозок в форме матрицы

 

 

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

1. УСЛОВИЕ ЗАДАЧИ

1.1. Проверка на сбалансированность

1.2. Исходные данные транспортной задачи в форме графа

1.3. Исходные данные транспортной задачи в матричной форме

2. ПОСТРОЕНИЕ ОПОРНОГО ПЛАНА

2.1. Построение опорного плана методом аппроксимации Фогеля

2.2. Расчет приведенных затрат

3. ПРОВЕРКА ОПОРНОГО ПЛАНА НА ОПТИМАЛЬНОСТЬ

3.1. Решение системы уравнений

3.2. Определение значений потенциалов dij.

4. ПОСТРОЕНИЕ УЛУЧШЕННОГО ПЛАНА

4.1. Перераспределение ресурсов методом потенциалов

4.2. Расчет приведенных затрат

4.3. Второй шаг оптимизации

4.n. n-ый шаг оптимизации

5. ПРЕДСТАВЛЕНИЕ ОПТИМАЛЬНОГО ПЛАНА В ФОРМЕ МАТРИЦЫ И ГРАФА

 

 






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2024 pdnr.ru Все права принадлежат авторам размещенных материалов.