Контрольная работа по "Логистике". 78

Содержание

Задача №1

Исходные данные транспортной задачи приведены в таблице. Составить  план перевозки однородного груза  от пунктов производства к пунктам  потребления с минимальными суммарными транспортными затратами.

Решение:

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

Для разрешимости транспортной задачи необходимо, чтобы суммарные  запасы продукции у поставщиков  равнялись суммарной потребности  потребителей. Проверим это условие.

В нашем случае, запасы поставщиков - 400 единиц продукции меньше, чем  потребность потребителей - 540 на 140 единиц. Введем в рассмотрение фиктивного поставщика A4, с запасом продукции  равным 140. Стоимость доставки единицы  продукции от данного поставщика ко всем потребителям примем равной нулю.

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

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

2)   Минимальный элемент матрицы тарифов находится в ячейке A1B1 и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B1 наиболее рентабельный.

Запасы поставщика A1 составляют 210 единиц продукции. Потребность потребителя B1 составляет 190 единиц продукции. (см. таблицу пункта 1) 

От поставщика A1 к потребителю B1 будем доставлять min = { 210 , 190 } = 190 единиц продукции.

Разместим в ячейку A1B1 значение равное 190 

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

3)   Минимальный элемент матрицы тарифов находится в ячейке A2B2 и равен 3, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B2 наиболее рентабельный.

Запасы поставщика A2 составляют 130 единиц продукции. Потребность потребителя B2 составляет 130 единиц продукции. (см. таблицу пункта 2) 

От поставщика A2 к потребителю B2 будем доставлять 130 единиц продукции.

Разместим в ячейку A2B2 значение равное 130 

Мы полностью израсходoвали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

Мы полностью удовлетворили  потребность потребителя B2. Вычеркиваем  столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.

4)   Минимальный элемент матрицы тарифов находится в ячейке A1B5 и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B5 наиболее рентабельный.

Запасы поставщика A1 составляют 20 единиц продукции. Потребность потребителя B5 составляет 110 единиц продукции. (см. таблицу пункта 3) 

От поставщика A1 к потребителю B5 будем доставлять min = { 20 , 110 } = 20 единиц продукции.

Разместим в ячейку A1B5 значение равное 20 

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

5)   Минимальный элемент матрицы тарифов находится в ячейке A3B5 и равен 6, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B5 наиболее рентабельный.

Запасы поставщика A3 составляют 60 единиц продукции. Потребность потребителя B5 составляет 90 единиц продукции. (см. таблицу пункта 4) 

От поставщика A3 к потребителю B5 будем доставлять min = { 60 , 90 } = 60 единиц продукции.

Разместим в ячейку A3B5 значение равное 60 

Мы полностью израсходoвали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

6)   Минимальный элемент матрицы тарифов находится в ячейке A4B3 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A4 к потребителю B3 наиболее рентабельный.

Запасы поставщика A4 составляют 140 единиц продукции. Потребность потребителя B3 составляет 65 единиц продукции. (см. таблицу пункта 5) 

От поставщика A4 к потребителю B3 будем доставлять min = { 140 , 65 } = 65 единиц продукции.

Разместим в ячейку A4B3 значение равное 65 

Мы полностью удовлетворили  потребность потребителя B3. Вычеркиваем  столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.

7)   Минимальный элемент матрицы тарифов находится в ячейке A4B4 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A4 к потребителю B4 наиболее рентабельный.

Запасы поставщика A4 составляют 75 единиц продукции. Потребность потребителя B4 составляет 45 единиц продукции. (см. таблицу пункта 6) 

От поставщика A4 к потребителю B4 будем доставлять min = { 75 , 45 } = 45 единиц продукции.

Разместим в ячейку A4B4 значение равное 45 

Мы полностью удовлетворили  потребность потребителя B4. Вычеркиваем  столбец 4 таблицы, т.е исключаем его из дальнейшего рассмотрения.

8)   Минимальный элемент  матрицы тарифов находится в  ячейке A4B5 и равен 0, т.е. из незадействованных  маршрутов, маршрут доставки продукции  от поставщика A4 к потребителю  B5 наиболее рентабельный.

Запасы поставщика A4 составляют 30 единиц продукции. Потребность потребителя B5 составляет 30 единиц продукции. (см. таблицу пункта 7) 

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

Разместим в ячейку A4B5 значение равное 30 

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

Заполненные нами ячейки будем  называть базисными, остальные - свободными.

Для решения задачи методом  потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк  в таблице, n - количество столбцов в  таблице.

Количество базисных ячеек  равно 7. Требуется, чтобы было 8.

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

Будем считать, что от поставщика A2 к потребителю B1 доставляем 0 единиц продукции. 

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

Мы нашли начальное  решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей. 

S0 = 2 * 190 + 4 * 20 + 3 * 130 + 6 * 60 + 0 * 65 + 0 * 45 + 0 * 30 = 1210 ден. ед.

Общие затраты на доставку всей продукции, для начального решения , составляют 1210 ден. ед. .

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

Находим потенциалы поставщиков  и потребителей для имеющегося решения.

Находим оценки свободных  ячеек. Если все оценки окажутся неотрицательными - задача решена.

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

Находим новое решение, как  минимум, не хуже предыдущего.

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

ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО  РЕШЕНИЯ.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки AiBj)

Поскольку, число базисных клеток - 8, а общее количество потенциалов  равно 9, то для однозначного определения  потенциалов, значение одного из них  можно выбрать произвольно. 

Примем v5 = 0.

v5 + u1 = c15 v5 + u1 = 4 u1 = 4 - 0 = 4

v5 + u3 = c35 v5 + u3 = 6 u3 = 6 - 0 = 6

v5 + u4 = c45 v5 + u4 = 0 u4 = 0 - 0 = 0

v1 + u1 = c11 v1 + u1 = 2 v1 = 2 - 4 = -2

v1 + u2 = c21 v1 + u2 = 3 u2 = 3 - ( -2 ) = 5

v2 + u2 = c22 v2 + u2 = 3 v2 = 3 - 5 = -2

v3 + u4 = c43 v3 + u4 = 0 v3 = 0 - 0 = 0

v4 + u4 = c44 v4 + u4 = 0 v4 = 0 - 0 = 0