К главной странице 2 части

  1. Метод минимального элемента в транспортной задаче.
  2. Метод Фогеля.

Метод минимального элемента в транспортной задаче

 Четыре предприятия данного экономического района для производства продукции используют некоторое сырьё. Спрос на сырьё каждого предприятия составляет: 120, 50, 190 и 110 усл.ед. Сырьё сосредоточено в трёх местах. Предложения поставщиков сырья равны: 160, 140 и 170 усл.ед. На каждое предприятие сырьё может завозиться от любого поставщика. Тарифы перевозок известны и задаются матрицей
C= 7 8 1 2
4 5 9 8
9 2 3 6
 Требуется составит план перевозок, при котором общая стоимость перевозов минимальна.
 Эта цель может быть достигнута с помощью оптимальной организации перевозок сырья. Следовательно, за неизвестные можно принять количество сырья, перевозимого от каждого поставщика каждому потребителю.
 Пусть xij- количество сырья, перевозимого от i-го поставщика j-му потребителю. Параметры задачи - число поставщиков и потребителей, предложение и спрос сырья в каждом пункте, тарифы на перевозки. Ограничения задачи - это ограничения на предложение и спрос сырья. Предложение сырья всех поставщиков не должны быть меньше суммарного спроса на него во всех пунктах потребления. В данной задаче имеет место точное равенство между предложением и спросом: 120 + 50 + 190 + 110 = 160 + 140 + 170 = 470.
 Количество сырья, вывозимого от каждого поставщика, должно быть равно наличному количеству сырья. Количество сырья, доставленное каждому потребителю, должно равняться его спросу. Последнее ограничение – условие неотрицательности xij. Критерием эффективности (целевой функцией) является суммарные затраты S на перевозку, равные сумме произведений тарифов на перевозку на количество перевозимого сырья от каждого поставщика каждому потребителю.
 Окончательно математическая модель задачи имеет вид
S = 7 x11 + 8 x12 + x13 + 2 x14 + 4 x21 + 5 x22 + 9 x23 + 8 x24 + 9 x31 + 2 x32 + 3 x33 + 6 x34 -> min,
x11 + x12 + x13 + x14 = 160,
x21 + x22 + x23 + x24 = 140,
x31 + x32 + x33 + x34 = 170,
x11 + x21 + x31 = 120,
x12 + x22 + x32 = 50,
x13 + x23 + x33 = 190,
x14 + x24 + x34 = 110,
120 + 50 + 190 + 110 = 160 + 140 + 170,
xij ≥ 0, i = 1, 2, 3; j = 1, 2, 3, 4.
 Шаг 1. Составляем транспортную таблицу.
№

1

2

3

4

предложение

1

                7

                8

           1

         2

160

2

               4

                5

              9

         8

140

3

                9

               2

            3

          6

170

спрос

120    

50    

190  

110  

 

  Шаг 2. Выбирают клетку таблицы, которой соответствует минимальное значение тарифа, и переходят на шаг 3. Минимальный тариф с13 = 1, х13 = min(160, 190)= 160.

№

1

2

3

4

предложение

1

                7

                8

    160  1

         2

160

2

               4

                5

              9

         8

140

3

                9

               2

            3

          6

170

спрос

120    

50    

190  

110  

 
  Шаг 3. В выбранную клетку аналогично методу «северо-западного» угла помещают максимально возможное число единиц продукции, разрешённое ограничениями на предложение и спрос. После этого предложение производителя исчерпано, вычёркивают соответствующую строку; если спрос удовлетворён, вычёркивают соответствующий столбец.
№

1

2

3

4

предложение

1

                7

                8

    160  1

         2

160

2

               4

                5

              9

         8

140

3

                9

50     2

            3

          6

170

спрос

120    

50    

190  

110  

 
Минимальный тариф для оставшихся клеток с32 = 2, х32 = min(170, 50) = 50. Второй столбец вычёркивают.
№

1

2

3

4

предложение

1

                7

                8

    160  1

         2

160

2

               4

                5

              9

         8

140

3

                9

50     2

            3

          6

170

спрос

120    

50    

190  

110  

 
  Если все клетки заполнены или вычеркнуты, то план перевозок построен. В противном случае переходят к шагу 2 без учёта заполненных или вычеркнутых клеток.
  Для оставшихся клеток минимальный тариф: с33 = 3; х33 = min(170 - 50, 190 - 160) = 30.
№

1

2

3

4

предложение

1

                7

                8

    160  1

         2

160

2

120        4

                5

              9

         8

140

3

                9

50     2

30   3

          6

170

спрос

120    

50    

190  

110  

 
  Третий столбец вычёркивают.
  Для оставшихся клеток минимальный тариф с21 = 4; х21 = min(120, 140) = 120. Первый столбец вычёркивают.
№

1

2

3

4

предложение

1

                7

                8

    160  1

         2

160

2

120        4

                5

              9

         8

140

3

                9

50     2

30   3

          6

170

спрос

120    

50    

190  

110  

 
 Для оставшихся клеток минимальный тариф: с34 = 6; х34 = min(170 - 50 - 30, 110) = 90.
№

1

2

3

4

предложение

1

                7

                8

    160  1

         2

160

2

120        4

                5

              9

20      8

140

3

                9

50     2

30   3

90      6

170

спрос

120    

50    

190  

110  

 
 Для одной оставшейся клетки х24 = min(140 - 120,110 - 90) = 20.
 План перевозок, полученный по методу минимального элемента, имеет вид
№

1

2

3

4

предложение

1

                7

                8

    160  1

         2

160

2

120        4

                5

              9

20      8

140

3

                9

50     2

30   3

90      6

170

спрос

120    

50    

190  

110  

 
 План перевозок, полученный по методу минимального элемента, имеет вид
X = x11 = 0 x12 = 0 x13 = 160 x14 = 0
x21 = 120 x22 = 0 x23 = 0 x24 = 20
x31 = 0 x32 = 50 x33 = 30 x34 = 90
 Стоимость перевозок по этому плану составляет
S2 = 160·1 + 120·4 + 20·8 + 50·2 + 30·3 + 90·6 = 1530.
Стоимость перевозок, полученных по методу минимального элемента, обычно бывает меньше стоимости перевозок, полученных по методу «северо-западного» угла.

Метод Фогеля

 Шаг 1. Составляем транспортную таблицу.
 Шаг 2.Для каждой строки и каждого столбца транспортной таблицы составляют разность между наименьшим тарифом и ближайшим к нему значением. Переход к шагу 3.
Шаг 3. В строке или столбце, который соответствует наибольшая разность, выбирают клетку с наименьшим тарифом. Переход к шагу 4.
  Шаг 4. В выбранную клетку, аналогично предыдущим методам, записывают максимально возможное число единиц продукции, которое разрешается ограничениями на предложение и спрос. После этого вычёркивают либо строку, если предложение поставщика исчерпано, либо столбец, если спрос потребителя удовлетворён. Если все клетки таблицы заполнены или вычеркнуты, то план перевозок построен. В противном случае переходят к шагу 2 без учёта вычеркнутых и заполненных клеток. Разности по строкам будем записывать в правой части таблицы, разности по столбцам – внизу. Максимальную разность будем отмечать кружком или цветом.
 Наименьший тариф в первой строке равен 1. Ближайший к нему равен 2. Разность равна 1. Наименьший тариф во второй строке 4. Ближайшее к нему значение 5. В третьей строке 2 и 3, соответственно. Разности по всем строкам равны 1. В первом столбце наименьший тариф с21=7. Ближайшее значение с11=7, с11 - с21 = 7 - 4 = 3.
 Во втором столбце наименьшее значение с32 = 2. Ближайшее значение с22 = 5, с22 - с32 = 5 - 2 = 3.
 Третий столбец: с13 = 1, с33 = 3, с33 - с13 = 3 - 1 = 2.
 Четвёртый столбец: с14 = 2, с34 = 6, с34 - с14 = 6 - 2 = 4.
 Максимальная из всех разностей 4 находится в четвёртом столбце. В этом столбце клетка с наименьшим тарифом с14 = 2 находится в первой строке. В эту клетку помещают максимально возможное значение: х14 = min(110, 160) = 110. Четвёртый потребитель полностью удовлетворил свой спрос, и четвёртый столбец вычёркиваем.
 Повторяем предыдущие действия без учёта вычеркнутых и заполненных клеток.
 Первая строка: минимальный тариф с13 = 1. Ближайшее значение с11 = 7, с11 - с13 = 6.
Предложение Разность по строкам № 1 2 3 4 1 7 8 1 110 2 160 1 6 - - 2 4 5 9 8 140 1 1 1 1 3 9 2 3 6 170 1 1 1 7 Спрос 120 50 190 110 Разность по столбцам

3 3 2 4
3 3 2 -
5 3 6 -
5 3 - -

Вторая строка: минимальный тариф с21 = 4. Ближайшее значение с22 = 5, с22 - с21 = 5 - 4 = 1.
Третья строка: с32 = 2, с33 = 3, с33 - с32 = 3 - 2 = 1. Первый столбец: минимальный тариф с21 = 4. Ближайшее значение с11 = 7, с11 - с21 = 7 - 4 = 3. Второй столбец: с32 = 2, с22 = 5, с22 - с32 = 5 - 2 = 3.
Максимальная разность равна 6 и стоит в первой строке. Минимальный тариф в первой строке с13 = 1. В эту клетку помещаем х13 = min(160 - 110, 190) = 50. Вычёркиваем эту строку.
Повторяем все действия без учёта первой строки и четвёртого столбца.
Вторая строка: с21 = 4, с22 = 5, с22 - с21 = 5 - 4 = 1.
Третья строка: с32 = 2, с33 = 3, с33 - с32 = 3 - 2 = 1.
Первый столбец: с21 = 4, с31 = 9, с31 - с21 = 9 - 4 = 5.
Второй столбец: с32 = 2, с22 = 5, с22 - с32 = 5 - 2 =3 .
Третий столбец: с33=3, с23=9, с23 - с33 = 9 - 3 = 6.
Максимальная разность равна 6 и стоит в третьем столбце. Минимальный из оставшихся тарифов в этом столбце с33 = 3, х33 = min(170, 190 - 50) = 140. Спрос третьего потребителя удовлетворён, третий столбец вычёркиваем.
Вновь составляем разности для не вычеркнутых столбцов.
Вторая строка: с21 = 4, с22 = 5, с22 - с21 = 5 - 4 = 1. Третья строка: с32 = 2, с31 = 9, с31 - с32 = 9 - 2 = 7. Первый столбец: с21 = 4, с31 = 9, с31 - с21 = 9 - 4 = 5. Второй столбец: с32 = 2, с22 = 5, с22 - с32 = 5 - 2 = 3. Максимальная разность стоит в третьей строке. Минимальный тариф в этой строке с32 = 2, х32 = min(170 - 140, 50) = 30. Предложение поставщика исчерпано, и третью строку вычёркиваем. Осталась одна строка транспортной таблицы. Это вторая строка. В этой строке сначала заполняем клетку с наименьшим тарифом с21 = 4, х21 = min(140, 120) = 120. Оставшееся предложение второго поставщика записываем в единственную свободную клетку х22 = min(140 - 120, 50 - 30) = 20. Полученный по методу Фогеля план перевозок имеет вид Затраты на перевозку по этому плану составляют
S3 = 50·1 + 110·2 + 120·4 + 20·5 + 30·2 + 140·3 = 1430. S3 < S2 < S1.
Таким образом, для одной и той же транспортной задачи получены различные начальные планы перевозок, построенные с использованием разных методов.