WWW.RESHMAT.RU

Решение задач по математике онлайн
ГЛАВНАЯ ЗАКАЗАТЬ РЕШЕНИЕ КНИГИ ССЫЛКИ
  Главная   >>   Пример №2. Транспортная задача. Метод минимального элемента. (с введением фиктивного потребителя)

Транспортная задача.
Пример №1. Транспортная задача. Метод минимального элемента.
Пример №2. Транспортная задача. Метод минимального элемента. (с введением фиктивного потребителя)
Пример №3. Транспортная задача. Метод минимального элемента. (с введением фиктивного поставщика)
Пример №4. Транспортная задача. Метод северо-западного угла.
Пример №5. Транспортная задача. Метод северо-западного угла. (с введением фиктивного потребителя)
Пример №6. Транспортная задача. Метод северо-западного угла. (с введением фиктивного поставщика)
Пример №7. Транспортная задача. Метод Фогеля.

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

перейти к решению своей задачи

Задача :
У поставщиков A1 , A2 , A3 , A4 , находится соответственно 500 , 300 , 200 , 100 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4 , B5 в количествах 50 , 150 , 250 , 150 , 250 единиц соответственно.
Стоимость доставки единицы продукции от поставщика A1 к указанным потребителям равна 11 , 6 , 8 , 12 , 16 ден.ед.
Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 16 , 10 , 8 , 16 , 15 ден.ед.
Стоимость доставки единицы продукции от поставщика A3 к указанным потребителям равна 14 , 17 , 9 , 11 , 13 ден.ед.
Стоимость доставки единицы продукции от поставщика A4 к указанным потребителям равна 13 , 12 , 7 , 8 , 15 ден.ед.
Требуется найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость доставки.
Решение :
Что мы будем делать?
Найдем начальное решение методом минимального элемента. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.
Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. Проверим это условие.
В нашем случае, запасы поставщиков - 1100 единиц продукции больше, чем потребность потребителей - 850 на 250 единиц. Введем в рассмотрение фиктивного потребителя B6, с потребностью в продукции равной 250. Стоимость доставки единицы продукции от всех поставщиков к данному потребителю примем равной нулю.
Маршруты доставки продукции от поставщиков к фиктивному потребителю B6 мы будем рассматривать в последнюю очередь. Не факт, но, скорее всего, это позволит получить более рентабельное начальное решение.
1)
Согласно условию задачи составим таблицу. (тарифы cij располагаются в нижнем правом углу ячейки)
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4 B 5 B 6
A 1
-
   11  
-
   6  
-
   8  
-
   12  
-
   16  
-
   0  
500
A 2
-
   16  
-
   10  
-
   8  
-
   16  
-
   15  
-
   0  
300
A 3
-
   14  
-
   17  
-
   9  
-
   11  
-
   13  
-
   0  
200
A 4
-
   13  
-
   12  
-
   7  
-
   8  
-
   15  
-
   0  
100
Потребность 50 150 250 150 250 250

2)
Минимальный элемент матрицы тарифов находится в ячейке A1B2 и равен 6, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B2 наиболее рентабельный.
Запасы поставщика A1 составляют 500 единиц продукции. Потребность потребителя B2 составляет 150 единиц продукции. (см. таблицу пункта 1)
От поставщика A1 к потребителю B2 будем доставлять min = { 500 , 150 } = 150 единиц продукции.
Разместим в ячейку A1B2 значение равное 150
Мы полностью удовлетворили потребность потребителя B2. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4 B 5 B 6
A 1
-
   11  
150
   6  
-
   8  
-
   12  
-
   16  
-
   0  
500
A 2
-
   16  
-
   10  
-
   8  
-
   16  
-
   15  
-
   0  
300
A 3
-
   14  
-
   17  
-
   9  
-
   11  
-
   13  
-
   0  
200
A 4
-
   13  
-
   12  
-
   7  
-
   8  
-
   15  
-
   0  
100
Потребность 50 150 250 150 250 250

3)
Минимальный элемент матрицы тарифов находится в ячейке A4B3 и равен 7, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A4 к потребителю B3 наиболее рентабельный.
Запасы поставщика A4 составляют 100 единиц продукции. Потребность потребителя B3 составляет 250 единиц продукции. (см. таблицу пункта 2)
От поставщика A4 к потребителю B3 будем доставлять min = { 100 , 250 } = 100 единиц продукции.
Разместим в ячейку A4B3 значение равное 100
Мы полностью израсходoвали запасы поставщика A4. Вычеркиваем строку 4 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4 B 5 B 6
A 1
-
   11  
150
   6  
-
   8  
-
   12  
-
   16  
-
   0  
500
A 2
-
   16  
-
   10  
-
   8  
-
   16  
-
   15  
-
   0  
300
A 3
-
   14  
-
   17  
-
   9  
-
   11  
-
   13  
-
   0  
200
A 4
-
   13  
-
   12  
100
   7  
-
   8  
-
   15  
-
   0  
100
Потребность 50 150 250 150 250 250

4)
Минимальный элемент матрицы тарифов находится в ячейке A1B3 и равен 8, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B3 наиболее рентабельный.
Запасы поставщика A1 составляют 350 единиц продукции. Потребность потребителя B3 составляет 150 единиц продукции. (см. таблицу пункта 3)
От поставщика A1 к потребителю B3 будем доставлять min = { 350 , 150 } = 150 единиц продукции.
Разместим в ячейку A1B3 значение равное 150
Мы полностью удовлетворили потребность потребителя B3. Вычеркиваем столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4 B 5 B 6
A 1
-
   11  
150
   6  
150
   8  
-
   12  
-
   16  
-
   0  
500
A 2
-
   16  
-
   10  
-
   8  
-
   16  
-
   15  
-
   0  
300
A 3
-
   14  
-
   17  
-
   9  
-
   11  
-
   13  
-
   0  
200
A 4
-
   13  
-
   12  
100
   7  
-
   8  
-
   15  
-
   0  
100
Потребность 50 150 250 150 250 250

5)
Минимальный элемент матрицы тарифов находится в ячейке A1B1 и равен 11, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B1 наиболее рентабельный.
Запасы поставщика A1 составляют 200 единиц продукции. Потребность потребителя B1 составляет 50 единиц продукции. (см. таблицу пункта 4)
От поставщика A1 к потребителю B1 будем доставлять min = { 200 , 50 } = 50 единиц продукции.
Разместим в ячейку A1B1 значение равное 50
Мы полностью удовлетворили потребность потребителя B1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4 B 5 B 6
A 1
50
   11  
150
   6  
150
   8  
-
   12  
-
   16  
-
   0  
500
A 2
-
   16  
-
   10  
-
   8  
-
   16  
-
   15  
-
   0  
300
A 3
-
   14  
-
   17  
-
   9  
-
   11  
-
   13  
-
   0  
200
A 4
-
   13  
-
   12  
100
   7  
-
   8  
-
   15  
-
   0  
100
Потребность 50 150 250 150 250 250

6)
Минимальный элемент матрицы тарифов находится в ячейке A3B4 и равен 11, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B4 наиболее рентабельный.
Запасы поставщика A3 составляют 200 единиц продукции. Потребность потребителя B4 составляет 150 единиц продукции. (см. таблицу пункта 5)
От поставщика A3 к потребителю B4 будем доставлять min = { 200 , 150 } = 150 единиц продукции.
Разместим в ячейку A3B4 значение равное 150
Мы полностью удовлетворили потребность потребителя B4. Вычеркиваем столбец 4 таблицы, т.е исключаем его из дальнейшего рассмотрения.
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4 B 5 B 6
A 1
50
   11  
150
   6  
150
   8  
-
   12  
-
   16  
-
   0  
500
A 2
-
   16  
-
   10  
-
   8  
-
   16  
-
   15  
-
   0  
300
A 3
-
   14  
-
   17  
-
   9  
150
   11  
-
   13  
-
   0  
200
A 4
-
   13  
-
   12  
100
   7  
-
   8  
-
   15  
-
   0  
100
Потребность 50 150 250 150 250 250

7)
Минимальный элемент матрицы тарифов находится в ячейке A3B5 и равен 13, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B5 наиболее рентабельный.
Запасы поставщика A3 составляют 50 единиц продукции. Потребность потребителя B5 составляет 250 единиц продукции. (см. таблицу пункта 6)
От поставщика A3 к потребителю B5 будем доставлять min = { 50 , 250 } = 50 единиц продукции.
Разместим в ячейку A3B5 значение равное 50
Мы полностью израсходoвали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4 B 5 B 6
A 1
50
   11  
150
   6  
150
   8  
-
   12  
-
   16  
-
   0  
500
A 2
-
   16  
-
   10  
-
   8  
-
   16  
-
   15  
-
   0  
300
A 3
-
   14  
-
   17  
-
   9  
150
   11  
50
   13  
-
   0  
200
A 4
-
   13  
-
   12  
100
   7  
-
   8  
-
   15  
-
   0  
100
Потребность 50 150 250 150 250 250

8)
Минимальный элемент матрицы тарифов находится в ячейке A2B5 и равен 15, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B5 наиболее рентабельный.
Запасы поставщика A2 составляют 300 единиц продукции. Потребность потребителя B5 составляет 200 единиц продукции. (см. таблицу пункта 7)
От поставщика A2 к потребителю B5 будем доставлять min = { 300 , 200 } = 200 единиц продукции.
Разместим в ячейку A2B5 значение равное 200
Мы полностью удовлетворили потребность потребителя B5. Вычеркиваем столбец 5 таблицы, т.е исключаем его из дальнейшего рассмотрения.
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4 B 5 B 6
A 1
50
   11  
150
   6  
150
   8  
-
   12  
-
   16  
-
   0  
500
A 2
-
   16  
-
   10  
-
   8  
-
   16  
200
   15  
-
   0  
300
A 3
-
   14  
-
   17  
-
   9  
150
   11  
50
   13  
-
   0  
200
A 4
-
   13  
-
   12  
100
   7  
-
   8  
-
   15  
-
   0  
100
Потребность 50 150 250 150 250 250

9)
Минимальный элемент матрицы тарифов находится в ячейке A1B6 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B6 наиболее рентабельный.
Запасы поставщика A1 составляют 150 единиц продукции. Потребность потребителя B6 составляет 250 единиц продукции. (см. таблицу пункта 8)
От поставщика A1 к потребителю B6 будем доставлять min = { 150 , 250 } = 150 единиц продукции.
Разместим в ячейку A1B6 значение равное 150
Мы полностью израсходoвали запасы поставщика A1. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4 B 5 B 6
A 1
50
   11  
150
   6  
150
   8  
-
   12  
-
   16  
150
   0  
500
A 2
-
   16  
-
   10  
-
   8  
-
   16  
200
   15  
-
   0  
300
A 3
-
   14  
-
   17  
-
   9  
150
   11  
50
   13  
-
   0  
200
A 4
-
   13  
-
   12  
100
   7  
-
   8  
-
   15  
-
   0  
100
Потребность 50 150 250 150 250 250

10)
Минимальный элемент матрицы тарифов находится в ячейке A2B6 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B6 наиболее рентабельный.
Запасы поставщика A2 составляют 100 единиц продукции. Потребность потребителя B6 составляет 100 единиц продукции. (см. таблицу пункта 9)
От поставщика A2 к потребителю B6 будем доставлять 100 единиц продукции.
Разместим в ячейку A2B6 значение равное 100
Мы полностью израсходoвали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Поставщик Потребитель Запас
B 1 B 2 B 3 B 4 B 5 B 6
A 1
50
   11  
150
   6  
150
   8  
-
   12  
-
   16  
150
   0  
500
A 2
-
   16  
-
   10  
-
   8  
-
   16  
200
   15  
100
   0  
300
A 3
-
   14  
-
   17  
-
   9  
150
   11  
50
   13  
-
   0  
200
A 4
-
   13  
-
   12  
100
   7  
-
   8  
-
   15  
-
   0  
100
Потребность 50 150 250 150 250 250

Заполненные нами ячейки будем называть базисными, остальные - свободными.
Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.
Количество базисных ячеек (задействованных маршрутов) равно 9, что и требовалось.
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
S0 = 11 * 50 + 6 * 150 + 8 * 150 + 0 * 150 + 15 * 200 + 0 * 100 + 11 * 150 + 13 * 50 + 7 * 100 = 8650 ден. ед.
Общие затраты на доставку всей продукции, для начального решения , составляют 8650 ден. ед. .
Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем:
  • Находим потенциалы поставщиков и потребителей для имеющегося решения.
  • Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.
  • Выбираем свободную ячейку (с отрицательной оценкой), выбор которой, позволяет максимально снизить общую стоимость доставки всей продукции на данном шаге решения.
  • Находим новое решение, как минимум, не хуже предыдущего.
  • Вычисляем общую стоимость доставки всей продукции для нового решения.

    • Шаг 1

    ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
    Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.
    Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.
    Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.
    (ui + vj = cij, где cij - тариф клетки AiBj)
    Поскольку, число базисных клеток - 9, а общее количество потенциалов равно 10, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
    Примем u1 = 0.
    v1 + u1 = c11 v1 + u1 = 11v1 = 11 - 0 = 11
    v2 + u1 = c12 v2 + u1 = 6v2 = 6 - 0 = 6
    v3 + u1 = c13 v3 + u1 = 8v3 = 8 - 0 = 8
    v6 + u1 = c16 v6 + u1 = 0v6 = 0 - 0 = 0
    v6 + u2 = c26 v6 + u2 = 0u2 = 0 - 0 = 0
    v3 + u4 = c43 v3 + u4 = 7u4 = 7 - 8 = -1
    v5 + u2 = c25 v5 + u2 = 15v5 = 15 - 0 = 15
    v5 + u3 = c35 v5 + u3 = 13u3 = 13 - 15 = -2
    v4 + u3 = c34 v4 + u3 = 11v4 = 11 - ( -2 ) = 13
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    150
       8  
    -
       12  
    -
       16  
    150
       0  
    		u 1 = 0
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    200
       15  
    100
       0  
    		u 2 = 0
    A 3
    -
       14  
    -
       17  
    -
       9  
    150
       11  
    50
       13  
    -
       0  
    		u 3 = -2
    A 4
    -
       13  
    -
       12  
    100
       7  
    -
       8  
    -
       15  
    -
       0  
    		u 4 = -1
    V i v 1 = 11 v 2 = 6 v 3 = 8 v 4 = 13 v 5 = 15 v 6 = 0

    Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
    14 = c14 - ( u1 + v4 ) = 12 - ( 0 + 13 ) = -1
    15 = c15 - ( u1 + v5 ) = 16 - ( 0 + 15 ) = 1
    21 = c21 - ( u2 + v1 ) = 16 - ( 0 + 11 ) = 5
    22 = c22 - ( u2 + v2 ) = 10 - ( 0 + 6 ) = 4
    23 = c23 - ( u2 + v3 ) = 8 - ( 0 + 8 ) = 0
    24 = c24 - ( u2 + v4 ) = 16 - ( 0 + 13 ) = 3
    31 = c31 - ( u3 + v1 ) = 14 - ( -2 + 11 ) = 5
    32 = c32 - ( u3 + v2 ) = 17 - ( -2 + 6 ) = 13
    33 = c33 - ( u3 + v3 ) = 9 - ( -2 + 8 ) = 3
    36 = c36 - ( u3 + v6 ) = 0 - ( -2 + 0 ) = 2
    41 = c41 - ( u4 + v1 ) = 13 - ( -1 + 11 ) = 3
    42 = c42 - ( u4 + v2 ) = 12 - ( -1 + 6 ) = 7
    44 = c44 - ( u4 + v4 ) = 8 - ( -1 + 13 ) = -4
    45 = c45 - ( u4 + v5 ) = 15 - ( -1 + 15 ) = 1
    46 = c46 - ( u4 + v6 ) = 0 - ( -1 + 0 ) = 1
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    150
       8  
    -
      -1 12  
    -
      1 16  
    150
       0  
    		u 1 = 0
    A 2
    -
      5 16  
    -
      4 10  
    -
      0 8  
    -
      3 16  
    200
       15  
    100
       0  
    		u 2 = 0
    A 3
    -
      5 14  
    -
      13 17  
    -
      3 9  
    150
       11  
    50
       13  
    -
      2 0  
    		u 3 = -2
    A 4
    -
      3 13  
    -
      7 12  
    100
       7  
    -
      -4 8  
    -
      1 15  
    -
      1 0  
    		u 4 = -1
    V i v 1 = 11 v 2 = 6 v 3 = 8 v 4 = 13 v 5 = 15 v 6 = 0


    Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным.
    Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке A4B4 (44 =-4).
    Построим цикл для выбранной ячейки A4B4:
    Поставьте курсор мыши в выбранную свободную ячейку A4B4. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A4B4. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.
    Ячейки образующие цикл для свободной ячейки A4B4 :
    A4B4 , A4B3 , A1B3 , A1B6 , A2B6 , A2B5 , A3B5 , A3B4
    Пусть ячейка A4B4, для которой мы строили цикл, имеет порядковый номер один.
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    150
       8  
    -
       12  
    -
       16  
    150
       0  
    		500
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    200
       15  
    100
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    150
       11  
    50
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    100
       7  
    -
      -4 8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    Среди ячеек цикла A4B3 , A1B6 , A2B5 , A3B4 , номера которых четные, найдем ячейку, обладающую найменьшим значением.
    min = { 100, 150, 200, 150 } = 100
    В данном случае, это ячейка A4B3.
    Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A4 к потребителю B3, по которому доставляется меньше всего (100) единиц продукции . Данный маршрут мы исключим из схемы доставки продукции.
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    150
       8  
    -
       12  
    -
       16  
    150
       0  
    		500
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    200
       15  
    100
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    150
       11  
    50
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    100
       7  
    -
      -4 8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    От ячеек цикла с четными номерами отнимает 100. К ячейкам с нечетными номерами прибавляем 100.
    Что мы делаем?
    Мы вводим новый маршрут доставки продукции от поставщика A4 к потребителю B4. По данному маршруту доставим 100 единиц продукции, по цене доставки 8 за единицу продукции. Общие затраты увеличатся на 8 * 100 ден. ед.
    По маршруту от поставщика A4 к потребителю B3 мы полностью перестаем доставлять продукцию.
    Общие затраты уменьшатся на 7 * 100 ден. ед.
    От поставщика A1 к потребителю B3 дополнительно поставим 100 единиц продукции, по цене доставки 8 за единицу продукции. Общие затраты увеличатся на 8 * 100 ден. ед.
    Сократим поставку от поставщика A1 к потребителю B6 на 100 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 100 ден. ед.
    От поставщика A2 к потребителю B6 дополнительно поставим 100 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты увеличатся на 0 * 100 ден. ед.
    Сократим поставку от поставщика A2 к потребителю B5 на 100 единиц продукции, по цене доставки 15 за единицу продукции. Общие затраты уменьшатся на 15 * 100 ден. ед.
    От поставщика A3 к потребителю B5 дополнительно поставим 100 единиц продукции, по цене доставки 13 за единицу продукции. Общие затраты увеличатся на 13 * 100 ден. ед.
    Сократим поставку от поставщика A3 к потребителю B4 на 100 единиц продукции, по цене доставки 11 за единицу продукции. Общие затраты уменьшатся на 11 * 100 ден. ед.
    Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    150 + 100
       8  
    -
       12  
    -
       16  
    150 - 100
       0  
    		500
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    200 - 100
       15  
    100 + 100
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    150 - 100
       11  
    50 + 100
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    100 - 100
       7  
    + 100
      -4 8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    Что в итоге?
    Общие расходы на доставку продукции от поставщиков к потребителям изменятся на
    8 * 100 - 7 * 100 + 8 * 100 - 0 * 100 + 0 * 100 - 15 * 100 + 13 * 100 - 11 * 100 = ( 8 - 7 + 8 - 0 + 0 - 15 + 13 - 11 ) * 100 = -4 * 100   ден. ед.
    Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.
    ГЛАВНОЕ :
    В тот момент, когда мы нашли ячейку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на 44 * 100 = -4 * 100 = -400 ден. ед.
    Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 8650 + ( - 400 ) = 8250 ден. ед. .
    Если оценки всех свободных ячеек (незадействованных маршрутов) неотрицательные, то снизить общую стоимость доставки всей продукции невозможно.
    Воспользовавшись таблицей, в которой мы находили оценки свободных ячеек, вы можете убедиться, что в случае выбора:
                ячейки A1B4, общая стоимость доставки всей продукции изменилась бы на 14 * 150 = -1 * 150 = -150 ден. ед.
    Ячейка A4B3 выйдет из базиса, мы перестали доставлять продукцию от поставщика A4 к потребителю B3
    Ячейка A4B4 станет базисной, мы ввели новый маршрут доставки продукции от поставщика A4 к потребителю B4 .
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    -
       12  
    -
       16  
    50
       0  
    		500
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    100
       15  
    200
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    50
       11  
    150
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    -
       7  
    100
       8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    Шаг 2

    ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
    Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.
    Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.
    Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.
    (ui + vj = cij, где cij - тариф клетки AiBj)
    Поскольку, число базисных клеток - 9, а общее количество потенциалов равно 10, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
    Примем u1 = 0.
    v1 + u1 = c11 v1 + u1 = 11v1 = 11 - 0 = 11
    v2 + u1 = c12 v2 + u1 = 6v2 = 6 - 0 = 6
    v3 + u1 = c13 v3 + u1 = 8v3 = 8 - 0 = 8
    v6 + u1 = c16 v6 + u1 = 0v6 = 0 - 0 = 0
    v6 + u2 = c26 v6 + u2 = 0u2 = 0 - 0 = 0
    v5 + u2 = c25 v5 + u2 = 15v5 = 15 - 0 = 15
    v5 + u3 = c35 v5 + u3 = 13u3 = 13 - 15 = -2
    v4 + u3 = c34 v4 + u3 = 11v4 = 11 - ( -2 ) = 13
    v4 + u4 = c44 v4 + u4 = 8u4 = 8 - 13 = -5
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    -
       12  
    -
       16  
    50
       0  
    		u 1 = 0
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    100
       15  
    200
       0  
    		u 2 = 0
    A 3
    -
       14  
    -
       17  
    -
       9  
    50
       11  
    150
       13  
    -
       0  
    		u 3 = -2
    A 4
    -
       13  
    -
       12  
    -
       7  
    100
       8  
    -
       15  
    -
       0  
    		u 4 = -5
    V i v 1 = 11 v 2 = 6 v 3 = 8 v 4 = 13 v 5 = 15 v 6 = 0

    Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
    14 = c14 - ( u1 + v4 ) = 12 - ( 0 + 13 ) = -1
    15 = c15 - ( u1 + v5 ) = 16 - ( 0 + 15 ) = 1
    21 = c21 - ( u2 + v1 ) = 16 - ( 0 + 11 ) = 5
    22 = c22 - ( u2 + v2 ) = 10 - ( 0 + 6 ) = 4
    23 = c23 - ( u2 + v3 ) = 8 - ( 0 + 8 ) = 0
    24 = c24 - ( u2 + v4 ) = 16 - ( 0 + 13 ) = 3
    31 = c31 - ( u3 + v1 ) = 14 - ( -2 + 11 ) = 5
    32 = c32 - ( u3 + v2 ) = 17 - ( -2 + 6 ) = 13
    33 = c33 - ( u3 + v3 ) = 9 - ( -2 + 8 ) = 3
    36 = c36 - ( u3 + v6 ) = 0 - ( -2 + 0 ) = 2
    41 = c41 - ( u4 + v1 ) = 13 - ( -5 + 11 ) = 7
    42 = c42 - ( u4 + v2 ) = 12 - ( -5 + 6 ) = 11
    43 = c43 - ( u4 + v3 ) = 7 - ( -5 + 8 ) = 4
    45 = c45 - ( u4 + v5 ) = 15 - ( -5 + 15 ) = 5
    46 = c46 - ( u4 + v6 ) = 0 - ( -5 + 0 ) = 5
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    -
      -1 12  
    -
      1 16  
    50
       0  
    		u 1 = 0
    A 2
    -
      5 16  
    -
      4 10  
    -
      0 8  
    -
      3 16  
    100
       15  
    200
       0  
    		u 2 = 0
    A 3
    -
      5 14  
    -
      13 17  
    -
      3 9  
    50
       11  
    150
       13  
    -
      2 0  
    		u 3 = -2
    A 4
    -
      7 13  
    -
      11 12  
    -
      4 7  
    100
       8  
    -
      5 15  
    -
      5 0  
    		u 4 = -5
    V i v 1 = 11 v 2 = 6 v 3 = 8 v 4 = 13 v 5 = 15 v 6 = 0


    Оценка свободной ячейки A1B4 (незадействованного маршрута) отрицательная (14 =-1) , следовательно решение не является оптимальным.
    Построим цикл для выбранной ячейки A1B4:
    Поставьте курсор мыши в выбранную свободную ячейку A1B4. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A1B4. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.
    Ячейки образующие цикл для свободной ячейки A1B4 :
    A1B4 , A1B6 , A2B6 , A2B5 , A3B5 , A3B4
    Пусть ячейка A1B4, для которой мы строили цикл, имеет порядковый номер один.
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    -
      -1 12  
    -
       16  
    50
       0  
    		500
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    100
       15  
    200
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    50
       11  
    150
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    -
       7  
    100
       8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    Среди ячеек цикла A1B6 , A2B5 , A3B4 , номера которых четные, найдем ячейку, обладающую найменьшим значением.
    min = { 50, 100, 50 } = 50
    В данном случае, таких ячеек 2. Остановим свой выбор на ячейке A3B4, как обладающую наибольшим тарифом (11 ден.ед) среди 2.
    Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле и по которым доставляется меньше всего (50) единиц продукции, выберем маршрут от поставщика A3 к потребителю B4, как самый нерентабельный . Данный маршрут мы исключим из схемы доставки продукции.
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    -
      -1 12  
    -
       16  
    50
       0  
    		500
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    100
       15  
    200
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    50
       11  
    150
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    -
       7  
    100
       8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    От ячеек цикла с четными номерами отнимает 50. К ячейкам с нечетными номерами прибавляем 50.
    Что мы делаем?
    Мы вводим новый маршрут доставки продукции от поставщика A1 к потребителю B4. По данному маршруту доставим 50 единиц продукции, по цене доставки 12 за единицу продукции. Общие затраты увеличатся на 12 * 50 ден. ед.
    Сократим поставку от поставщика A1 к потребителю B6 на 50 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 50 ден. ед.
    От поставщика A2 к потребителю B6 дополнительно поставим 50 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты увеличатся на 0 * 50 ден. ед.
    Сократим поставку от поставщика A2 к потребителю B5 на 50 единиц продукции, по цене доставки 15 за единицу продукции. Общие затраты уменьшатся на 15 * 50 ден. ед.
    От поставщика A3 к потребителю B5 дополнительно поставим 50 единиц продукции, по цене доставки 13 за единицу продукции. Общие затраты увеличатся на 13 * 50 ден. ед.
    По маршруту от поставщика A3 к потребителю B4 мы полностью перестаем доставлять продукцию.
    Общие затраты уменьшатся на 11 * 50 ден. ед.
    Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    + 50
      -1 12  
    -
       16  
    50 - 50
       0  
    		500
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    100 - 50
       15  
    200 + 50
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    50 - 50
       11  
    150 + 50
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    -
       7  
    100
       8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    Что в итоге?
    Общие расходы на доставку продукции от поставщиков к потребителям изменятся на
    12 * 50 - 0 * 50 + 0 * 50 - 15 * 50 + 13 * 50 - 11 * 50 = ( 12 - 0 + 0 - 15 + 13 - 11 ) * 50 = -1 * 50   ден. ед.
    Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.
    ГЛАВНОЕ :
    В тот момент, когда мы нашли ячейку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на 14 * 50 = -1 * 50 = -50 ден. ед.
    Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 8250 + ( - 50 ) = 8200 ден. ед. .
    Если оценки всех свободных ячеек (незадействованных маршрутов) неотрицательные, то снизить общую стоимость доставки всей продукции невозможно.
    Ячейка A3B4 выйдет из базиса, мы перестали доставлять продукцию от поставщика A3 к потребителю B4
    Ячейка A1B4 станет базисной, мы ввели новый маршрут доставки продукции от поставщика A1 к потребителю B4 .
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    50
       12  
    -
       16  
    0
       0  
    		500
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    50
       15  
    250
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    -
       11  
    200
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    -
       7  
    100
       8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    Шаг 3

    ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
    Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.
    Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.
    Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.
    (ui + vj = cij, где cij - тариф клетки AiBj)
    Поскольку, число базисных клеток - 9, а общее количество потенциалов равно 10, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
    Примем u1 = 0.
    v1 + u1 = c11 v1 + u1 = 11v1 = 11 - 0 = 11
    v2 + u1 = c12 v2 + u1 = 6v2 = 6 - 0 = 6
    v3 + u1 = c13 v3 + u1 = 8v3 = 8 - 0 = 8
    v4 + u1 = c14 v4 + u1 = 12v4 = 12 - 0 = 12
    v6 + u1 = c16 v6 + u1 = 0v6 = 0 - 0 = 0
    v6 + u2 = c26 v6 + u2 = 0u2 = 0 - 0 = 0
    v4 + u4 = c44 v4 + u4 = 8u4 = 8 - 12 = -4
    v5 + u2 = c25 v5 + u2 = 15v5 = 15 - 0 = 15
    v5 + u3 = c35 v5 + u3 = 13u3 = 13 - 15 = -2
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    50
       12  
    -
       16  
    0
       0  
    		u 1 = 0
    A 2
    -
       16  
    -
       10  
    -
       8  
    -
       16  
    50
       15  
    250
       0  
    		u 2 = 0
    A 3
    -
       14  
    -
       17  
    -
       9  
    -
       11  
    200
       13  
    -
       0  
    		u 3 = -2
    A 4
    -
       13  
    -
       12  
    -
       7  
    100
       8  
    -
       15  
    -
       0  
    		u 4 = -4
    V i v 1 = 11 v 2 = 6 v 3 = 8 v 4 = 12 v 5 = 15 v 6 = 0

    Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
    15 = c15 - ( u1 + v5 ) = 16 - ( 0 + 15 ) = 1
    21 = c21 - ( u2 + v1 ) = 16 - ( 0 + 11 ) = 5
    22 = c22 - ( u2 + v2 ) = 10 - ( 0 + 6 ) = 4
    23 = c23 - ( u2 + v3 ) = 8 - ( 0 + 8 ) = 0
    24 = c24 - ( u2 + v4 ) = 16 - ( 0 + 12 ) = 4
    31 = c31 - ( u3 + v1 ) = 14 - ( -2 + 11 ) = 5
    32 = c32 - ( u3 + v2 ) = 17 - ( -2 + 6 ) = 13
    33 = c33 - ( u3 + v3 ) = 9 - ( -2 + 8 ) = 3
    34 = c34 - ( u3 + v4 ) = 11 - ( -2 + 12 ) = 1
    36 = c36 - ( u3 + v6 ) = 0 - ( -2 + 0 ) = 2
    41 = c41 - ( u4 + v1 ) = 13 - ( -4 + 11 ) = 6
    42 = c42 - ( u4 + v2 ) = 12 - ( -4 + 6 ) = 10
    43 = c43 - ( u4 + v3 ) = 7 - ( -4 + 8 ) = 3
    45 = c45 - ( u4 + v5 ) = 15 - ( -4 + 15 ) = 4
    46 = c46 - ( u4 + v6 ) = 0 - ( -4 + 0 ) = 4
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    50
       12  
    -
      1 16  
    0
       0  
    		u 1 = 0
    A 2
    -
      5 16  
    -
      4 10  
    -
      0 8  
    -
      4 16  
    50
       15  
    250
       0  
    		u 2 = 0
    A 3
    -
      5 14  
    -
      13 17  
    -
      3 9  
    -
      1 11  
    200
       13  
    -
      2 0  
    		u 3 = -2
    A 4
    -
      6 13  
    -
      10 12  
    -
      3 7  
    100
       8  
    -
      4 15  
    -
      4 0  
    		u 4 = -4
    V i v 1 = 11 v 2 = 6 v 3 = 8 v 4 = 12 v 5 = 15 v 6 = 0


    Все оценки свободных ячеек неотрицательные, следовательно, найдено оптимальное решение.
    Ответ:
    X 1 опт = 50 150 250 50 0 0
    0 0 0 0 50 250
    0 0 0 0 200 0
    0 0 0 100 0 0
    Smin = 11 * 50 + 6 * 150 + 8 * 250 + 12 * 50 + 15 * 50 + 0 * 250 + 13 * 200 + 8 * 100 = 8200
    Общие затраты на доставку всей продукции, для оптимального решения, составляют 8200 ден. ед.
    Замечание:
    Задача имеет не единственное решение, т.к. среди оценок свободных ячеек присутствуют оценки равные нулю.

  • Построим цикл для ячейки A2B3.
    • Пусть ячейка A2B3, для которой мы строили цикл, имеет порядковый номер один.
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    50
       12  
    -
       16  
    0
       0  
    		500
    A 2
    -
       16  
    -
       10  
    -
      0 8  
    -
       16  
    50
       15  
    250
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    -
       11  
    200
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    -
       7  
    100
       8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    Среди ячеек цикла A2B6 , A1B3 , номера которых четные, найдем ячейку, обладающую найменьшим значением.
    min = { 250, 250 } = 250
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250
       8  
    50
       12  
    -
       16  
    0
       0  
    		500
    A 2
    -
       16  
    -
       10  
    -
      0 8  
    -
       16  
    50
       15  
    250
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    -
       11  
    200
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    -
       7  
    100
       8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    Общие затраты на доставку всей продукции, по-прежнему, составляют S0 = 8200 + 23 * 250 = 8200 + 0 * 250 = 8200 ден. ед. .
    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4 B 5 B 6
    A 1
    50
       11  
    150
       6  
    250 - 250
       8  
    50
       12  
    -
       16  
    0 + 250
       0  
    		500
    A 2
    -
       16  
    -
       10  
    + 250
      0 8  
    -
       16  
    50
       15  
    250 - 250
       0  
    		300
    A 3
    -
       14  
    -
       17  
    -
       9  
    -
       11  
    200
       13  
    -
       0  
    		200
    A 4
    -
       13  
    -
       12  
    -
       7  
    100
       8  
    -
       15  
    -
       0  
    		100
    Потребность 50 150 250 150 250 250

    X 2 опт = 50 150 0 50 0 250
    0 0 250 0 50 0
    0 0 0 0 200 0
    0 0 0 100 0 0

    перейти к решению своей задачи





    Copyright © 2010-2011, www.reshmat.ru
    При копировании материалов ссылка на сайт www.reshmat.ru обязательна.
    обратная связь
    Яндекс цитирования Рейтинг@Mail.ru Rambler's Top100