Решение задач по математике онлайн

Программы для решения типовых задач по высшей математике

Главная

Заказать решение

Ссылки
Главная   >   Пример №2. Транспортная задача. Метод минимального элемента. (фиктивный поставщик)

Транспортная задача.
Пример №2. Метод минимального элемента. (фиктивный поставщик)

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

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


Введенная Вами таблица дает нам следующую информацию:

  • Запасы однотипной продукции, которая находится у поставщиков A1, A2, A3.
  • Потребность в однотипной продукции потребителей B1, B2, B3, B4.
  • Стоимость доставки единицы продукции от каждого поставщика к каждому потребителю. (тарифы маршрутов)

  • Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1 7 8 1 2200
    A 2 4 5 9 8180
    A 3 9 2 3 6190
    Потребность 150 180 150 140

    Требуется составить план перевозок, при котором общая стоимость перевозок минимальная.

    РЕШЕНИЕ :

  • Найдем начальное решение методом минимального элемента.

  • Суммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.

    Запасы поставщиков: 200 + 180 + 190 = 570 единиц продукции.
    Потребность потребителей: 150 + 180 + 150 + 140 = 620 единиц продукции.

    Разница в 50 единиц продукции.
    Введем в рассмотрение фиктивного поставщика A4, с запасом продукции равным 50 единиц.
    Стоимость доставки единицы продукции от поставщика A4 ко всем потребителям примем равной нулю. (см. таблицу 1)

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

    Маршруты доставки продукции от фиктивного поставщика A4 к потребителям будем рассматривать в последнюю очередь.

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

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
       1  
       2  
    200
    A 2
       4  
       5  
       9  
       8  
    180
    A 3
       9  
       2  
       3  
       6  
    190
    A 4
       0  
       0  
       0  
       0  
    50
    Потребность 150180150140

    Наименьший тариф равен 1 ден. ед.
    От поставщика A1 к потребителю B3 будем доставлять min = { 200 , 150 } = 150 единиц продукции.
    2)

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150
       1  
       2  
    200   50
    A 2
       4  
       5  
       9  
       8  
    180
    A 3
       9  
       2  
       3  
       6  
    190
    A 4
       0  
       0  
       0  
       0  
    50
    Потребность 150180150   0 140

    2 маршрута обладают наименьшим тарифом - 2 ден. ед.   Из этих 2 маршрутов выберем произвольный.
    От поставщика A1 к потребителю B4 будем доставлять min = { 50 , 140 } = 50 единиц продукции.
    3)

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150
       1  
    50
       2  
    200   0
    A 2
       4  
       5  
       9  
       8  
    180
    A 3
       9  
       2  
       3  
       6  
    190
    A 4
       0  
       0  
       0  
       0  
    50
    Потребность 150180150   0 140   90

    Наименьший тариф равен 2 ден. ед.
    От поставщика A3 к потребителю B2 будем доставлять min = { 190 , 180 } = 180 единиц продукции.
    4)

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150
       1  
    50
       2  
    200   0
    A 2
       4  
       5  
       9  
       8  
    180
    A 3
       9  
    180
       2  
       3  
       6  
    190   10
    A 4
       0  
       0  
       0  
       0  
    50
    Потребность 150180   0 150   0 140   90

    Наименьший тариф равен 4 ден. ед.
    От поставщика A2 к потребителю B1 будем доставлять min = { 180 , 150 } = 150 единиц продукции.
    5)

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150
       1  
    50
       2  
    200   0
    A 2
    150
       4  
       5  
       9  
       8  
    180   30
    A 3
       9  
    180
       2  
       3  
       6  
    190   10
    A 4
       0  
       0  
       0  
       0  
    50
    Потребность 150   0 180   0 150   0 140   90

    Наименьший тариф равен 6 ден. ед.
    От поставщика A3 к потребителю B4 будем доставлять min = { 10 , 90 } = 10 единиц продукции.
    6)

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150
       1  
    50
       2  
    200   0
    A 2
    150
       4  
       5  
       9  
       8  
    180   30
    A 3
       9  
    180
       2  
       3  
    10
       6  
    190   0
    A 4
       0  
       0  
       0  
       0  
    50
    Потребность 150   0 180   0 150   0 140   80

    Наименьший тариф равен 8 ден. ед.
    От поставщика A2 к потребителю B4 будем доставлять min = { 30 , 80 } = 30 единиц продукции.
    7)

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150
       1  
    50
       2  
    200   0
    A 2
    150
       4  
       5  
       9  
    30
       8  
    180   0
    A 3
       9  
    180
       2  
       3  
    10
       6  
    190   0
    A 4
       0  
       0  
       0  
       0  
    50
    Потребность 150   0 180   0 150   0 140   50

    От поставщика A4 к потребителю B4 будем доставлять 50 единиц продукции.
    8)

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150
       1  
    50
       2  
    200   0
    A 2
    150
       4  
       5  
       9  
    30
       8  
    180   0
    A 3
       9  
    180
       2  
       3  
    10
       6  
    190   0
    A 4
       0  
       0  
       0  
    50
       0  
    50   0
    Потребность 150   0 180   0 150   0 140   0

    Мы израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
    Мы нашли начальное решение.
    Стоимость доставки продукции, для начального решения, не сложно посчитать.
    S = 150 * 1 + 50 * 2 + 150 * 4 + 30 * 8 + 180 * 2 + 10 * 6 + 50 * 0 =   1510 ден. ед.

    Полученное начальное решение является оптимальным?

    Для того, чтобы иметь возможность ответить на этот вопрос, количество задействованных маршрутов должно равняться 4 + 4 - 1 = 7, где
    4 - количество строк в таблице.
    4 - количество столбцов в таблице.
    Количество задействованных маршрутов не может получиться больше 7, меньше - возможно.
    Посчитайте. Количество задействованных маршрутов равно 7, что и требовалось.

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


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

  • Находим потенциалы поставщиков и потребителей.
  • Зная потенциалы, находим оценки незадействованных маршрутов.
  • Если оценки всех незадействованных маршрутов неотрицательные, то уменьшить общую стоимость доставки нельзя. Задача решена.

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

    Каждому поставщику A i ставим в соответствие некоторое число - u i , называемое потенциалом поставщика.
    Каждому потребителю B j ставим в соответствие некоторое число - v j , называемое потенциалом потребителя.

  • Найдем потенциалы поставщиков и покупателей. (поверьте, это очень просто)
  • Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.
    Примем v4 = 0.

    A1B4 :         v4 + u1 = 2         u1 = 2 - 0 = 2
    A2B4 :         v4 + u2 = 8         u2 = 8 - 0 = 8
    A3B4 :         v4 + u3 = 6         u3 = 6 - 0 = 6
    A4B4 :         v4 + u4 = 0         u4 = 0 - 0 = 0
    A1B3 :         v3 + u1 = 1         v3 = 1 - 2 = -1
    A2B1 :         v1 + u2 = 4         v1 = 4 - 8 = -4
    A3B2 :         v2 + u3 = 2         v2 = 2 - 6 = -4
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150
       1  
    50
       2  
    u 1 = 2
    A 2
    150
       4  
       5  
       9  
    30
       8  
    u 2 = 8
    A 3
       9  
    180
       2  
       3  
    10
       6  
    u 3 = 6
    A 4
       0  
       0  
       0  
    50
       0  
    u 4 = 0
    V i v 1 = -4 v 2 = -4 v 3 = -1 v 4 = 0

  • Найдем оценки незадействованных маршрутов (в таблице они располагаются в нижнем левом углу ячейки).
  • Оценка незадействованного маршрута = тариф маршрута - ( потенциал поставщика + потенциал потребителя ).
    A1B1 :         11 = 7 - ( 2 + ( -4 ) ) = 9
    A1B2 :         12 = 8 - ( 2 + ( -4 ) ) = 10
    A2B2 :         22 = 5 - ( 8 + ( -4 ) ) = 1
    A2B3 :         23 = 9 - ( 8 + ( -1 ) ) = 2
    A3B1 :         31 = 9 - ( 6 + ( -4 ) ) = 7
    A3B3 :         33 = 3 - ( 6 + ( -1 ) ) = -2
    A4B1 :         41 = 0 - ( 0 + ( -4 ) ) = 4
    A4B2 :         42 = 0 - ( 0 + ( -4 ) ) = 4
    A4B3 :         43 = 0 - ( 0 + ( -1 ) ) = 1
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4
    A 1
      9 7  
      10 8  
    150
       1  
    50
       2  
    u 1 = 2
    A 2
    150
       4  
      1 5  
      2 9  
    30
       8  
    u 2 = 8
    A 3
      7 9  
    180
       2  
      -2 3  
    10
       6  
    u 3 = 6
    A 4
      4 0  
      4 0  
      1 0  
    50
       0  
    u 4 = 0
    V i v 1 = -4 v 2 = -4 v 3 = -1 v 4 = 0


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

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150
       1  
    50
       2  
    200
    A 2
    150
       4  
       5  
       9  
    30
       8  
    180
    A 3
       9  
    180
       2  
      -2 3  
    10
       6  
    190
    A 4
       0  
       0  
       0  
    50
       0  
    50
    Потребность 150180150140

    Пусть ячейка A3B3, для которой мы строили цикл, имеет порядковый номер один.
    Среди ячеек цикла, номера которых четные, найдем ячейку обладающую наименьшим значением.
    min = { 10, 150 } = 10.

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150
       1  
    50
       2  
    200
    A 2
    150
       4  
       5  
       9  
    30
       8  
    180
    A 3
       9  
    180
       2  
      -2 3  
    10
       6  
    190
    A 4
       0  
       0  
       0  
    50
       0  
    50
    Потребность 150180150140

    От ячеек цикла с четными номерами отнимает 10. К ячейкам с нечетными номерами прибавляем 10.

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    150 - 10
       1  
    50 + 10
       2  
    200
    A 2
    150
       4  
       5  
       9  
    30
       8  
    180
    A 3
       9  
    180
       2  
    + 10
      -2 3  
    10 - 10
       6  
    190
    A 4
       0  
       0  
       0  
    50
       0  
    50
    Потребность 150180150140

    Достаточно взглянуть на таблицу и Вы увидите, что баланс не нарушится.
    Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.
    А вот общие затраты на доставку всей продукции изменятся на величину
    3 * 10 - 6 * 10 + 2 * 10 - 1 * 10 = ( 3 - 6 + 2 - 1 ) * 10 = -2 * 10 = 33 * 10.
    Выражение стоящее в скобках равно оценке нового маршрута!!
    Поэтому новая стоимость доставки вычисляется именно так:
    S = 1510 + 33 * 10 = 1510 - 2 * 10 =   1490 ден. ед.

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

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    140
       1  
    60
       2  
    200
    A 2
    150
       4  
       5  
       9  
    30
       8  
    180
    A 3
       9  
    180
       2  
    10
       3  
       6  
    190
    A 4
       0  
       0  
       0  
    50
       0  
    50
    Потребность 150180150140

    Шаг 2

    Полученное решение является оптимальным?

    Каждому поставщику A i ставим в соответствие некоторое число - u i , называемое потенциалом поставщика.
    Каждому потребителю B j ставим в соответствие некоторое число - v j , называемое потенциалом потребителя.

  • Найдем потенциалы поставщиков и покупателей. (поверьте, это очень просто)
  • Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.
    Примем v4 = 0.

    A1B4 :         v4 + u1 = 2         u1 = 2 - 0 = 2
    A2B4 :         v4 + u2 = 8         u2 = 8 - 0 = 8
    A4B4 :         v4 + u4 = 0         u4 = 0 - 0 = 0
    A1B3 :         v3 + u1 = 1         v3 = 1 - 2 = -1
    A2B1 :         v1 + u2 = 4         v1 = 4 - 8 = -4
    A3B3 :         v3 + u3 = 3         u3 = 3 - ( -1 ) = 4
    A3B2 :         v2 + u3 = 2         v2 = 2 - 4 = -2
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    140
       1  
    60
       2  
    u 1 = 2
    A 2
    150
       4  
       5  
       9  
    30
       8  
    u 2 = 8
    A 3
       9  
    180
       2  
    10
       3  
       6  
    u 3 = 4
    A 4
       0  
       0  
       0  
    50
       0  
    u 4 = 0
    V i v 1 = -4 v 2 = -2 v 3 = -1 v 4 = 0

  • Найдем оценки незадействованных маршрутов (в таблице они располагаются в нижнем левом углу ячейки).
  • Оценка незадействованного маршрута = тариф маршрута - ( потенциал поставщика + потенциал потребителя ).
    A1B1 :         11 = 7 - ( 2 + ( -4 ) ) = 9
    A1B2 :         12 = 8 - ( 2 + ( -2 ) ) = 8
    A2B2 :         22 = 5 - ( 8 + ( -2 ) ) = -1
    A2B3 :         23 = 9 - ( 8 + ( -1 ) ) = 2
    A3B1 :         31 = 9 - ( 4 + ( -4 ) ) = 9
    A3B4 :         34 = 6 - ( 4 + 0 ) = 2
    A4B1 :         41 = 0 - ( 0 + ( -4 ) ) = 4
    A4B2 :         42 = 0 - ( 0 + ( -2 ) ) = 2
    A4B3 :         43 = 0 - ( 0 + ( -1 ) ) = 1
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4
    A 1
      9 7  
      8 8  
    140
       1  
    60
       2  
    u 1 = 2
    A 2
    150
       4  
      -1 5  
      2 9  
    30
       8  
    u 2 = 8
    A 3
      9 9  
    180
       2  
    10
       3  
      2 6  
    u 3 = 4
    A 4
      4 0  
      2 0  
      1 0  
    50
       0  
    u 4 = 0
    V i v 1 = -4 v 2 = -2 v 3 = -1 v 4 = 0


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

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    140
       1  
    60
       2  
    200
    A 2
    150
       4  
      -1 5  
       9  
    30
       8  
    180
    A 3
       9  
    180
       2  
    10
       3  
       6  
    190
    A 4
       0  
       0  
       0  
    50
       0  
    50
    Потребность 150180150140

    Пусть ячейка A2B2, для которой мы строили цикл, имеет порядковый номер один.
    Среди ячеек цикла, номера которых четные, найдем ячейку обладающую наименьшим значением.
    min = { 30, 140, 180 } = 30.

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    140
       1  
    60
       2  
    200
    A 2
    150
       4  
      -1 5  
       9  
    30
       8  
    180
    A 3
       9  
    180
       2  
    10
       3  
       6  
    190
    A 4
       0  
       0  
       0  
    50
       0  
    50
    Потребность 150180150140

    От ячеек цикла с четными номерами отнимает 30. К ячейкам с нечетными номерами прибавляем 30.

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    140 - 30
       1  
    60 + 30
       2  
    200
    A 2
    150
       4  
    + 30
      -1 5  
       9  
    30 - 30
       8  
    180
    A 3
       9  
    180 - 30
       2  
    10 + 30
       3  
       6  
    190
    A 4
       0  
       0  
       0  
    50
       0  
    50
    Потребность 150180150140

    Достаточно взглянуть на таблицу и Вы увидите, что баланс не нарушится.
    Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.
    А вот общие затраты на доставку всей продукции изменятся на величину
    5 * 30 - 8 * 30 + 2 * 30 - 1 * 30 + 3 * 30 - 2 * 30 = ( 5 - 8 + 2 - 1 + 3 - 2 ) * 30 = -1 * 30 = 22 * 30.
    Выражение стоящее в скобках равно оценке нового маршрута!!
    Поэтому новая стоимость доставки вычисляется именно так:
    S = 1490 + 22 * 30 = 1490 - 1 * 30 =   1460 ден. ед.

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

    Поставщик Потребитель Запас
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    110
       1  
    90
       2  
    200
    A 2
    150
       4  
    30
       5  
       9  
       8  
    180
    A 3
       9  
    150
       2  
    40
       3  
       6  
    190
    A 4
       0  
       0  
       0  
    50
       0  
    50
    Потребность 150180150140

    Шаг 3

    Полученное решение является оптимальным?

    Каждому поставщику A i ставим в соответствие некоторое число - u i , называемое потенциалом поставщика.
    Каждому потребителю B j ставим в соответствие некоторое число - v j , называемое потенциалом потребителя.

  • Найдем потенциалы поставщиков и покупателей. (поверьте, это очень просто)
  • Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.
    Примем v4 = 0.

    A1B4 :         v4 + u1 = 2         u1 = 2 - 0 = 2
    A4B4 :         v4 + u4 = 0         u4 = 0 - 0 = 0
    A1B3 :         v3 + u1 = 1         v3 = 1 - 2 = -1
    A3B3 :         v3 + u3 = 3         u3 = 3 - ( -1 ) = 4
    A3B2 :         v2 + u3 = 2         v2 = 2 - 4 = -2
    A2B2 :         v2 + u2 = 5         u2 = 5 - ( -2 ) = 7
    A2B1 :         v1 + u2 = 4         v1 = 4 - 7 = -3
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4
    A 1
       7  
       8  
    110
       1  
    90
       2  
    u 1 = 2
    A 2
    150
       4  
    30
       5  
       9  
       8  
    u 2 = 7
    A 3
       9  
    150
       2  
    40
       3  
       6  
    u 3 = 4
    A 4
       0  
       0  
       0  
    50
       0  
    u 4 = 0
    V i v 1 = -3 v 2 = -2 v 3 = -1 v 4 = 0

  • Найдем оценки незадействованных маршрутов (в таблице они располагаются в нижнем левом углу ячейки).
  • Оценка незадействованного маршрута = тариф маршрута - ( потенциал поставщика + потенциал потребителя ).
    A1B1 :         11 = 7 - ( 2 + ( -3 ) ) = 8
    A1B2 :         12 = 8 - ( 2 + ( -2 ) ) = 8
    A2B3 :         23 = 9 - ( 7 + ( -1 ) ) = 3
    A2B4 :         24 = 8 - ( 7 + 0 ) = 1
    A3B1 :         31 = 9 - ( 4 + ( -3 ) ) = 8
    A3B4 :         34 = 6 - ( 4 + 0 ) = 2
    A4B1 :         41 = 0 - ( 0 + ( -3 ) ) = 3
    A4B2 :         42 = 0 - ( 0 + ( -2 ) ) = 2
    A4B3 :         43 = 0 - ( 0 + ( -1 ) ) = 1
    Поставщик Потребитель U j
    B 1 B 2 B 3 B 4
    A 1
      8 7  
      8 8  
    110
       1  
    90
       2  
    u 1 = 2
    A 2
    150
       4  
    30
       5  
      3 9  
      1 8  
    u 2 = 7
    A 3
      8 9  
    150
       2  
    40
       3  
      2 6  
    u 3 = 4
    A 4
      3 0  
      2 0  
      1 0  
    50
       0  
    u 4 = 0
    V i v 1 = -3 v 2 = -2 v 3 = -1 v 4 = 0


    Оценки всех незадействованных маршрутов неотрицательные. Следовательно, уменьшить общую стоимость доставки мы не сможем.

    Ответ:
    X опт = 0 0 110 90
    150 30 0 0
    0 150 40 0
    0 0 0 50

    S = 1460 ден. ед.


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





    Copyright © 2010-2014, www.reshmat.ru
    При копировании материалов ссылка на сайт www.reshmat.ru обязательна.
    почта: matematika1974@yandex.ru
    Рейтинг.ru