Глава 2 Транспортная задача

Поставщики (пункты отправки)

Потребители (пункты назначения)

Запасы товара, a_i

Спрос на товар, b_j

Упражнение 1.Получите опорный план транспортной задачи (таб. 24) тремя методами. Оптимизируйте план, полученный методом наименьших затрат.

Таблица 24

Решение.

Так как , то имеем закрытую транспортную задачу, n = 3, m = 5.

1 метод. Метод «северо-западного угла»

Таблица 25 заполняется, начиная с «северо-западного» угла, то есть с левой верхней клетки.

Дадим переменной x ₁₁ максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1; 1) – «северо-западный» угол таблицы поставок: x ₁₁ = min{200, 120} = 120. После этого спрос первого потребителя полностью удовлетворён, в результате чего первый столбец таблицы поставок исключается из дальнейшего рассмотрения (до тех пор, пока опорный план не будет составлен полностью). Заполненные клетки будем перечёркивать по диагонали сплошной линией, а исключённые из дальнейшего рассмотрения – пунктирной линией; при этом предложение первого поставщика уменьшается на 120 ед. и составит 80 ед.

Таблица 25

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, a_i

В₁ В₂ В₃ В₄ В₅

А₁ 200/ 80

А₂

А₃

Спрос на товар, b_j 120/ –

Теперь в таблице поставок 26 находим новый «северо-западный» угол – клетку (1; 2) и отправляем в неё максимально возможную поставку x ₁₂ = min{80, 110} = 80 и клетка (1; 2) перечёркивается сплошной линией. После этого мощность первого поставщика полностью использована, то есть клетки (1; 3), (1; 4) и (1; 5) исключаются из рассмотрения и перечёркиваются пунктиром. В оставшейся таблице вновь находим «северо-западный» угол и отправляем туда максимально возможную поставку. И так далее.

В результате получаем опорный план, в котором заполненными (базисными) являются n + m – 1 = 5 + 3 – 1 = 7 клеток.

Таблица 26

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, a_i

В₁ В₂ В₃ В₄ В₅

А₁ 200/ 80/ –

А₂ 300/ 270/ 190/ –

А₃ 200/ 190/ –

Спрос на товар, b_j 120/ – 110/ 30/ – 80/ – 200/ 10/ – 190/ –

Этому плану соответствует значение целевой функции F _сз = 18·120+ +26·80+12·30+19·80+23·190+19·10+14·190 = 13340.

2 метод. Метод наименьших затрат

Согласно этому методу на каждом шаге заполняется клетка с минимальным коэффициентом затрат.

В таблице поставок 27 находим клетку с наименьшим коэффициентом затрат. Это клетка (2; 1) с коэффициентом затрат, равным 7 (если таких клеток несколько, то выбираем ту, в которую возможна максимальная поставка), причём x ₂₁ = min{300, 120} = 120.

Таблица 27

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, a_i

В₁ В₂ В₃ В₄ В₅

А₁

А₂ 300/ 180

А₃

Спрос на товар, b_j 120/ –

Тогда спрос первого потребителя полностью удовлетворён, и первый столбец исключён из рассмотрения.

Таблица 28

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, a_i

В₁ В₂ В₃ В₄ В₅

А₁

А₂ 300/ 180

А₃ 200/ 90

Спрос на товар, b_j 120/ – 110/ –

В оставшейся таблице 28 наименьший коэффициент затрат равен 8 и находится в клетке (3; 2), x ₃₂ = min{200, 110} = 110. При этом из рассмотрения выбывает второй столбец.

Продолжая заполнение таблицы шаг за шагом (табл. 29), получаем x ₁₅ = min{200, 190} = 190, x ₁₃ = min{10, 80} = 10, x ₃₃ = min{90, 70} = 70, x ₃₄ = min{20, 180} = 20, x ₂₄ = 180. В результате получаем опорный план, в котором заполненными (базисными) являются 7 клеток.

Таблица 29

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, a_i

В₁ В₂ В₃ В₄ В₅

А₁ 200/ 10/ –

А₂ 300/ 180/ –

А₃ 200/ 90/ 20

Спрос на товар, b_j 120/ – 110/ – 80/ 70/ – 200/ 180/ – 190/ –

Соответствующее значение целевой функции равно F _нз = 16·10+9·190+ +7·120+23·180+8·110+17·70+19·20 = 9300.

3 метод. Метод аппроксимации Фогеля

При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем строкам и всем строкам находим разность между двумя минимальными коэффициентами затрат. Эти разности записываем в специально отведённые для этого строку и столбец таблицы поставок 30. Среди полученных разностей выбираем максимальную. В строке (или столбце), которой данная разность соответствует, заполняем клетку с минимальным коэффициентом затрат.

Если минимальный коэффициент затрат одинаков для нескольких клеток выбранной строки (столбца), то для заполнения выбираем ту клетку, которая расположена в столбце (строке) с максимальной разностью по столбцам (строкам).

Таблица 30

Пункты назначения a_i Разности по строкам

ПО В₁ В₂ В₃ В₄ В₅ I II III IV V

А₁

А₂

А₃

b_j

Разности по столбцам

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

Таблица 31

Пункты назначения a_i Разности по строкам

ПО В₁ В₂ В₃ В₄ В₅ I II III IV V

А₁ 200/ 10

А₂

А₃

b_j 190/ –

Разности по столбцам

В строке А₁ минимальный коэффициент затрат равен 9, а следующий за ним равен 16, разность между ними 16 – 9 = 7. В строке А₂ разность равна 12 – 7 = 5, и так далее. Вычислив все разности, видим, что наибольшая из них соответствует строке А₁. В этой строке минимальный коэффициент затрат находится в клетке (1; 5) и равен 9. Отправим в эту клетку максимально возможную поставку x ₁₅ = min{200, 190} = 190. При этом потребности пятого потребителя полностью удовлетворены, и он исключается из рассмотрения, а запасы пункта А₁ равны 200 – 190 = 10.

Второй этап. Снова вычисляем разности между минимальными коэффициентами затрат (табл. 32) и видим, что наибольшая из них соответствует строке А₂. В этой строке минимальный коэффициент затрат находится в клетке (2; 1) и равен 7. Отправим в эту клетку максимально возможную поставку x ₂₁ = min{300, 120} = 120. При этом потребности первого потребителя полностью удовлетворены, и он исключается из рассмотрения, а запасы пункта А₂ равны 300 – 120 = 180.

Таблица 32

Пункты назначения a_i Разности по строкам

ПО В₁ В₂ В₃ В₄ В₅ I II III IV V

А₁ 200/ 10

А₂ 300/ 180

А₃

b_j 190/ –

Разности по столбцам

–

–

–

–

Продолжая итерационный процесс (табл. 33), последовательно заполняем клетки (3; 2), (1; 3), (3; 4), (2; 3), (2; 4) поставками x ₃₂ = min{200, 110} = 110, x ₁₃ = = min{10, 80} = 10, x ₃₄ = min{90, 200} = 90, x ₂₃ = min{110, 70} = 70, x ₂₄ = 110.

Отметим, что на этапе V появляются строка и столбец, у которых разности максимальны. Поэтому выбирает клетку с минимальным коэффициентом затрат. В данном случае таких клеток две – (2; 3) и (3; 4). Нас интересует та, в которую можно отправить максимально возможную поставку, то есть клетка (3; 4).

Таблица 33

Пункты назначения a_i Разности по строкам

ПО В₁ В₂ В₃ В₄ В₅ I II III IV V

А₁ 200/ 10/ – –

А₂ 300/180/ 110/ –

А₃ 200/ 90/ –

b_j 110/ – 80/ 70/ – 200/ 110/– 190/ –

Разности по столбцам

–

– –

– – –

– – –

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

Соответствующее значение целевой функции равно F _Ф = 7·120+8·110+ +16·10+19·70+23·110+19·90+9·190 = 9160.

Оптимизируем план, полученный методом наименьших затрат (табл. 29), используя метод потенциалов.

Методом наименьших затрат получен опорный план:

, F _o =9300.

Согласно методу потенциалов каждой строке i и каждому столбцу j ставятся в соответствие числа u_i, v_j (потенциалы). Для каждой базисной переменной x_ij потенциалы u_i, v_j удовлетворяют уравнению:

c_ij + u_i + v_j = 0.

Так как базисных переменных n + m – 1 = 7, а потенциалов n + m = 8, то присвоим одному из потенциалов произвольное значение (например, u ₁ = 0) и вычислим значения остальных потенциалов:

Результаты вычислений занесём в таблицу 34.

Таблица 34

ПО ПН u_i

В₁ В₂ В₃ В₄ В₅

А₁

А₂ –5

А₃ –1

v_j –2 –7 –16 –18 –9

Далее, используя полученные значения потенциалов, для каждой свободной переменной вычисляем оценки d_ij по формуле:

d_ij = c_ij + u_i + v_j.

Результаты заносим в матрицу оценок (d_ij), проставив в клетках базисных переменных прочерки:

.

Так как в матрице оценок есть отрицательный элемент d ₂₃ = – 2, то опорный план неоптимальный. Для получения нового плана необходимо свободную переменную x ₂₃ перевести в базис. Чтобы определить, какую переменную нужно вывести из базиса, строим для клетки (2;3) цикл пересчёта.

Цикл пересчёта – это ломаная линия, вершины которой расположены в занятых клетках таблицы поставок (кроме одной, предназначенной для заполнения), а звенья – вдоль строк и столбцов, причём в каждой вершине цикла встречается лишь два звена, одно из которых находится в строке, а другое – в столбце, и в каждых строке и столбце чётное число вершин. Перемещение по циклу производится по следующим правилам:

– каждой из вершин, связанной циклом с данной свободной клеткой, приписывают определённый знак, причём свободной клетке соответствует знак «+», а далее – поочерёдно то «–», то «+»;

– в данную свободную клетку переносится меньшее из значений x_ij, стоящих в клетках со знаком «–», а соответствующая переменная x_ij становится свободной. Одновременно это число добавляется ко всем значениям x_ij, стоящим в клетках со знаком «+», и вычитается из всех значений x_ij, стоящих в клетках со знаком «–».

В данном случае цикл пересчёта и перемещение по циклу представлены в таблице 35.

Таблица 35

ПО ПН

В₁ В₂ В₃ В₄ В₅

А₁ 18

А₂

+ –

А₃

– +

Учитывая, что min{180, 70} = 70, в свободные переменные переходит x ₃₃. В результате получаем новый план, F ₁ = F ₀ + x’ ₂₃ d ₂₃ = 9300 + 70·(–2) = = 9160 (см. табл. 36).

Таблица 36

ПО ПН u_i

В₁ В₂ В₃ В₄ В₅

А₁

А₂ –3

А₃

v_j –4 –9 –16 –20 –9

Вычислим значения потенциалов для полученного плана:

и составим матрицу оценок:

.

Так как в матрице оценок нет отрицательных элементов, то полученный план:

оптимальный, и минимальное значение целевой функции F ^* = 9160.

Однако в матрице оценок присутствует элемент d ₂₂ = 0, что говорит о том, что оптимальный план не единственный. Для получения нового оптимального плана необходимо свободную переменную x ₂₂ перевести в базис. Чтобы определить, какую переменную нужно вывести из базиса, строим для клетки (2;2) цикл пересчёта в таблице 37 по сформулированным выше правилам.

Таблица 37

ПО ПН

В₁ В₂ В₃ В₄ В₅

А₁ 18

А₂

+ –

А₃

– +

Учитывая, что min{110, 110} = 110, в свободные переменные переходит любая из переменных x ₃₂ или x ₂₄, например, x ₂₄, при этом в клетку (3;2) отправляем фиктивную поставку (табл. 38), то есть x ₃₂ = 0 (если не сделать этого, число базисных переменных станет равным шести, а не семи, как должно быть в данной задаче). В результате получаем новый план, F ₂ = F ₁ + x’ ₂₂ d ₂₂ = = 9300 + 110·0 = 9160.

Таблица 38

ПО ПН u_i

В₁ В₂ В₃ В₄ В₅

А₁

А₂ –3

А₃

v_j –4 –9 –16 –20 –9

Вычислим значения потенциалов для полученного плана:

и составим матрицу оценок:

.

Так как в матрице оценок нет отрицательных элементов, то полученный план:

оптимальный, и минимальное значение целевой функции F ^* = 9160.

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

Ответ:

, ;

F ^* = 9160.

Упражнение 2. Получите опорный план транспортной задачи (табл. 39) тремя методами. Оптимизируйте план, полученный методом наименьших затрат.

Таблица 39

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, a_i

В₁ В₂ В₃ В₄ В₅

А₁

А₂

А₃

Спрос на товар, b_j

Решение.

,

.

Так как , то имеем закрытую транспортную задачу, n = 3, m = 5.

1 метод. Метод «северо-западного угла»

Таблица 40

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, a_i

В₁ В₂ В₃ В₄ В₅

А₁ 150/ 50

А₂

А₃

Спрос на товар, b_j 100/ –

Таблица 40 заполняется, начиная с левого верхнего угла. Дадим переменной x ₁₁ максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1;1) – «северо-западный» угол таблицы поставок: x ₁₁ = min{150, 100} = 100. После этого спрос первого потребителя полностью удовлетворён, в результате чего первый столбец таблицы поставок исключается из рассмотрения; при этом предложение первого поставщика уменьшается на 100 ед.

Теперь в таблице поставок (табл. 41) находим новый «северо-западный» угол – клетку (1;2) и отправляем в неё максимально возможную поставку x ₁₂ = min{50, 70} = 70 и так далее. На четвёртом шаге максимально возможную поставку нужно отправить в клетку (2;3), при этом удовлетворяются и спрос потребителя, и мощность поставщика. Поэтому необходимо отправить фиктивную поставку в одну из незачёркнутых клеток 2-ой строки или 3-го столбца, например, в клетку (3;3), то есть x ₃₃ = 0 (если не сделать этого число базисных переменных станет равным шести, а не семи как должно быть в данной задаче).

В результате получаем опорный план, в котором заполненными (базисными) являются n + m – 1 = 5 + 3 – 1 = 7 клеток.

Этому плану соответствует значение целевой функции F _сз = 20·100+ +3·50+10·20+12·130+16·0+16·110+48·90 = 9900.

Таблица 41

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, a_i

В₁ В₂ В₃ В₄ В₅

А₁ 150/ 50/ –

А₂ 150/ 130/ –

А₃ 200/ 90/ –

Спрос на товар, b_j 100/ – 70/ 20/ – 130/ – 110/ – 90/ –

2 метод. Метод наименьших затрат

В таблице поставок (табл. 42) находим клетки с наименьшим коэффициентом затрат. Это клетка (1;2) с коэффициентом затрат, равным 3, причём x ₁₂ = min{150, 70} = 70.

Таблица 42

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, a_i

В₁ В₂ В₃ В₄ В₅

А₁ 150/ 80

А₂

А₃

Спрос на товар, b_j 70/ –

Тогда спрос второго потребителя полностью удовлетворён, и второй столбец исключён из рассмотрения.

В оставшейся таблице 43 наименьший коэффициент затрат равен 9 и находится в клетке (1;3), x ₁₃ = min{80, 130} = 80. При этом из рассмотрения выбывает первая строка.

Таблица 43

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, a_i

В₁ В₂ В₃ В₄ В₅

А₁ 150/ 80/ –

А₂ 150/ 100/ –

А₃ 200/ 110/ –

Спрос на товар, b_j 100/ – 70/ – 130/ 50/ – 110/ – 90/ –

Продолжая заполнение таблицы 43 шаг за шагом, получаем x ₂₃ = = min{150,50} = 50, x ₂₁ = min{100,100} = 100, x ₂₁ = 0 (фиктивная поставка), x ₃₄ = min{200,110} = 110, x ₃₅ = 90. В результате получаем опорный план, в котором заполненными (базисными) являются 7 клеток.

Соответствующее значение целевой функции равно F _нз = 3·70+9·80+ +14·100+12·50+25·0+16·110+48·90 = 9010.

3 метод. Метод аппроксимации Фогеля

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

Вычислив все разности, видим, что наибольшая из них соответствует столбцу В₁. В этой строке минимальный коэффициент затрат находится в клетке (1;5) и равен 35. Отправим в эту клетку максимально возможную поставку x ₁₃ = min{200,90} = 90. При этом потребности пятого потребителя полностью удовлетворены, и он исключается из рассмотрения, а запасы пункта А₁ равны 150 – 90 = 60.

Таблица 44

Пункты назначения a_i Разности по строкам

ПО В₁ В₂ В₃ В₄ В₅ I II III IV V

А₁ 150/ 60

А₂

А₃

b_j

Разности по столбцам

Продолжая итерационный процесс, последовательно заполняем клетки (1;2), (2;1), (3;2), (2;3), (3;3), (3;4) таблицы 45 поставками x ₁₂ = min{60,70} = = 60, x ₂₁ = min{150, 100} = 100, x ₃₂ = min{200, 10} = 10, x ₂₃ = min{50, 130} = = 50, x ₃₃ = min{190, 80} = 80, x ₃₄ = 110.

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

Соответствующее значение целевой функции равно F _Ф = 3·60+35·90+ +14·100+12·50+11·10+16·80+16·110 = 8480.

Таблица 45

Пункты назначения a_i

⇐ Предыдущая 1 23

Поделиться с друзьями:

Дата добавления: 2017-02-25; Мы поможем в написании ваших работ!; просмотров: 608 | Нарушение авторских прав

Поиск на сайте:

Лучшие изречения:

Победа - это еще не все, все - это постоянное желание побеждать. © Винс Ломбарди
==> читать все изречения...
1337 - | 1270 -

© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.097 с.