Задачи линейного программирования транспортного типа. Горячев Л.В. - 10 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

Составители: 

Рубрика: 

10
Примерами построения опорных планов методом северо-западного угла могул служить планы в
следующих Т.З.:
Пример 1 Пример 2
32422
2 20000
4
12100
7
00322
13325
3 12000
7
01321
4
00004
Число итераций, необходимых для решения Т.З. методом потенциалов, существенно зависит от
вида первоначального плана. Удачны выбор исходного плана может существенно сократить коли-
чество итераций и тем самым ускорить решение задачи. Опорный план, построенный по методу
северо-западного угла, учитывает лишь объемы производства и потребления пунктов и совершенно
не связан с матрицей транспортных издержек. Поэтому можно модифицировать метод, увязав алго-
ритм построения опорного плана со стоимостью перевозок. Эта модификация называется методом
минимального элемента.
2. Метод минимального элемента. Этот метод состоит из последовательных шагов.
Шаг 1. Определим минимальный элемент матрицы транспортных издержек C = c
ij
m·n
.Если
им оказался c
ij
, то полагаем x
ij
= min(a
i
,b
j
) и поступаем так же, как в методе северо-западного
угла.
Шаг 2. После вычеркивания i – ой строки (a
i
1
<b
j
1
) или j
1
– го столбца (a
i
1
≥ b
j
1
) получим
сокращенную матрицу C
1
.
Второй шаг состоит в проведении уже описанных операций применительно к C
1
. В результа-
те заполняется еще одна перевозка и вычеркивается строка или столбец матриц X и C. Процесс
продолжается до полного распределения продукции между потребителями. Очевидно, что метод
минимального элемента сводится к методу северо-западного угла, если перенумеровать пункты
производства и потребления в соответствии с порядком вычеркивания строк и столбцов матрицы
C. Отсюда следует, что модифицированный метод также приводит к опорному плану за m + n − 1
шагов. В таблице 1 приведен опорный план , построенный методом минимального элемента (в левом
углу клеток — элементы матрицы затрат c
ij
).
5 9 9 7
II
7 8
3
5
1
3
7
II
2
5
4
6
5 9
8
6 3 1
8
2
Таблица 1
Из других методов построения опорных планов можно отметить метод аппроксимации Фогеля.
Задача. Решить Т.З. с тремя поставщиками с объемами продукции, равными 10, 8 и 12 единиц и
четырьмя потребителями с потребностями 8, 5, 7 и 10 единиц соответственно. Матрица транспорт-
ных затрат имеет вид
C =
2357
4132
6325
Решение. Условие баланса выполняется: 10+8+12=8+5+7+10. Начальный опорный план X
0
10

   Примерами построения опорных планов методом северо-западного угла могул служить планы в
следующих Т.З.:

                                   Пример 1                       Пример 2
                                   3 2 4 2          2             1 3 3 2               5
                                 2 2 0 0 0          0           3 1 2 0 0               0
                                 4 1 2 1 0          0           7 0 1 3 2               1
                                 7 0 0 3 2          2           4 0 0 0 0               4


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

     2. Метод минимального элемента. Этот метод состоит из последовательных шагов.
   Шаг 1. Определим минимальный элемент матрицы транспортных издержек C = cij m·n . Если
им оказался cij , то полагаем xij = min(ai , bj ) и поступаем так же, как в методе северо-западного
угла.
   Шаг 2. После вычеркивания i – ой строки (ai1 < bj1 ) или j1 – го столбца (ai1 ≥ bj1 ) получим
сокращенную матрицу C1 .
   Второй шаг состоит в проведении уже описанных операций применительно к C1 . В результа-
те заполняется еще одна перевозка и вычеркивается строка или столбец матриц X и C. Процесс
продолжается до полного распределения продукции между потребителями. Очевидно, что метод
минимального элемента сводится к методу северо-западного угла, если перенумеровать пункты
производства и потребления в соответствии с порядком вычеркивания строк и столбцов матрицы
C. Отсюда следует, что модифицированный метод также приводит к опорному плану за m + n − 1
шагов. В таблице 1 приведен опорный план , построенный методом минимального элемента (в левом
углу клеток — элементы матрицы затрат cij ).

                                           5            9           9           7
                                          7         8           5           3
                                     II
                                                            3           1           7
                                          2         4           5           9
                                     II
                                               5            6
                                          6         3           1           2
                                      8
                                                            8
                                                   Таблица 1


     Из других методов построения опорных планов можно отметить метод аппроксимации Фогеля.
   Задача. Решить Т.З. с тремя поставщиками с объемами продукции, равными 10, 8 и 12 единиц и
четырьмя потребителями с потребностями 8, 5, 7 и 10 единиц соответственно. Матрица транспорт-
ных затрат имеет вид
                                                      
                                           2 3 5 7
                                     C= 4 1 3 2 
                                           6 3 2 5


     Решение. Условие баланса выполняется: 10+8+12=8+5+7+10. Начальный опорный план X 0

Страницы