Построение оптимального плана перевозок груза с минимальной стоимостью

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

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

Задача 7.1

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

Решение: Общий объём запасов:

Общая потребность:

Т.к., то это транспортная задача закрытого типа.

Построение оптимального плана методом северо-западного угла.

Здесь в верхнем правом углу клеток записана стоимость перевозки.

Заполнять таблицу первоначального опорного плана начинаем с клетки а₁b₁ — это северо-западный угол.

Закрываем потребности b₁ поставкой из а₁ и этот столбец исключаем из дальнейшего рассмотрения. Остаток груза из а₁ отправляем потребителю b₂ и строку а₁ исключаем из дальнейшего рассмотрения. Затем весь груз из а₂ отправляем в b₂, исключая строку а₂ и частью груза из а₃ закрываем потребность b₂, исключая столбец b₂. Далее закрываем потребность b₃ поставкой из а₃, а остаток груза из а₃ отправляем потребителю b₄. Груз из а₄ отправляем потребителю b₄. Опорный план составлен.

Стоимость перевозок по этому плану:

Z₁ = 95· 17 + 10•12 + 70•11 + 80•19 + 135•22 + 25?27 + 85?7 = 8265 д.е.

Число заполненных клеток должно быть m + n -1 = 4 + 4 — 1 = 7, что так и есть, т. е. план не вырожден.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U₁ = 0. Потенциалы других строк и столбцов определяем по формулам:

U_i = C_ij — V_j; V_j = C_ij — U_i;

V₁ = C₁₁ — U₁ = 17 — 0 = 17; V₂ = C₁₂ — U₁ = 12 — 0 = 12; U₂ = C₂₂ — V₂ = 11 — 12 = -1;

U₃ = C₃₂ — V₂ = 19 — 12 = 7; V₃ = C₃₃ — U₃ = 22 — 7 = 15; V₄ = C₃₄ — U₃ = 27 — 7 = 20.

U₄ = C₄₄ — V₄ = 7 — 20 = -13;

Определяем характеристики клеток, оставшихся свободными по формуле:

E_ij = C_ij — (V_j + U_i) (вписаны в левый нижний угол) Е₁₃ = С₁₃ — (V₃ + U₁) = 17 — (15 + 0) = 2; Е₁₄ = С₁₄ — (V₄ + U₁) = 21 — (20 + 0) = 1;

Е₂₁ = С₂₁ — (V₁ + U₂) = 6 — (17 — 1) = -10; Е₂₃ = С₂₃ — (V₃ + U₂) = 20 — (15 — 1) = 6;

Е₂₄ = С₂₄ — (V₄ + U₂) = 28 — (20 — 1) = 9; Е₃₁ = С₃₁ — (V₁ + U₃) = 10 — (17 + 7) = -14;

Е₄₁ = С₄₁ — (V₁ + U₄) = 18 — (17 — 13) = 14; Е₄₂ = С₄₂ — (V₂ + U₄) = 14 — (12 — 13) = 15;

Е₄₃ = С₄₃ — (V₃ + U₄) = 23 — (15 — 13) = 21;

Среди характеристик свободных клеток есть две отрицательные (Е₂₁ = -10 и Е₃₁ = -14), значит полученный план не оптимален.

Строим для клетки а₃b₁ с отрицательной характеристикой (-14), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (80), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. № 2).

Таблица 2

Цена этого плана:

Z₂ = 15· 17 + 90•12 + 70•11 + 80•10 + 135•22 + 25?27 + 85?7 = 7145 д.е.

что меньше первого плана на 1120 ден. ед.

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

Далее без комментариев повторяем итерацию с перемещением перевозки по циклу в клетку a₁b₄ с отрицательной характеристикой (-13). Получаем третий план (табл. № 3).

Его цена:

Z₃ = 90•12 + 15?21 + 70•11 + 95•10 + 135•22 + 10?27 + 85?7 = 6950 д.е.

что меньше второго плана на 195 ден. ед.

Этот план оптимальный, т.к. все характеристики свободных клеток положительны.

Zопт = Z_min = Z₃ = 6950 ден. ед.

Построение оптимального плана методом минимального элемента.

Минимальная стоимость перевозок (6) в клетке а₂b₁ — отправляем весь груз из а₂ потребителю b₁ и строку а₂ исключаем из дальнейшего рассмотрения.

Следующий минимум (7) в клетке а₄b₄ — отправляем весь груз из а₄ потребителю b₄ и строку а₄ исключаем из дальнейшего рассмотрения.

Следующий минимум (10) в клетке а₃b₁ — закрываем потребность b₁ поставкой из а₃ и столбец b₁ исключаем из дальнейшего рассмотрения.

Следующий минимум (12) в клетке а₁b₂ — весь груз из а₁ отправляем в b₂ и строку а₁ исключаем из дальнейшего рассмотрения.

Следующий минимум (19) в клетке а₃b₂ — закрываем потребность b₂ поставкой из а₃ и столбец b₂ исключаем из дальнейшего рассмотрения.

Поставкой остатка груза из а₃ закрываем потребности b₃ и b₄.

Опорный план составлен.

Стоимость перевозок по этому плану:

Z₁ = 105· 12 + 70•6 + 25•10 + 55•19 + 135•22 + 25?27 + 85?7 = 7215 д.е.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U₁ = 0. Потенциалы других строк и столбцов определяем по формулам:

U_i = C_ij — V_j; V_j = C_ij — U_i;

Определяем характеристики клеток, оставшихся свободными по формуле:

E_ij = C_ij — (V_j + U_i) (вписаны в левый нижний угол).

Среди характеристик свободных клеток есть одна отрицательная (Е₂₂ = -4), значит полученный план не оптимален.

Строим для клетки а₂b, цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (55), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. № 2).

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

Далее без комментариев повторяем итерацию с перемещением перевозки (15) по циклу в клетку a₁b₄ с отрицательной характеристикой (-3). Получаем третий план (табл. № 3).

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

Zопт = Z_min = 6950 ден. ед.

Построение оптимального плана методом Фогеля.

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

Например, на первом шаге в первой строке минимальные затраты 17 и 12, разность — 5, во 2-ой строке 11 и 6, разность 5, в 3-ей 19 и 10, разность 9, в 4-ой 14 и 7, разность 7.

В 1-ом столбце минимальные затраты 10 и 6, разность 4, во 2-ом 12 и 11, разность 1, в 3-ем 20 и 17, разность 3, в 4-ом 21 и 7, разность 14.

Наибольшая из этих разностей — 14 соответствует 4-му столбцу. В этом столбце минимум затрат — 7 в строке 4. Заполняем клетку а₄b₄ объёмом поставок 85 единиц, который может быть поставлен от четвёртого поставщика и строку 4 из дальнейшего рассмотрения исключаем. По аналогии заполнены остальные клетки таблицы и получен опорный план.

Цена этого плана:

Z₁ = 90•12 + 15?21 + 70•11 + 95•10 + 135•22 + 10?27 + 85?7 = 6950 д.е.

Этот полученный план является оптимальным, т.к. такой же план получен при использовании методов северо-западного угла и минимального элемента.

Задача 7.2

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

Решение: Общий объём запасов:

Общая потребность:

Т.к., то это транспортная задача открытого типа.

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

Построение оптимального плана методом северо-западного угла.

Порядок составления опорного плана этим методом описан в задаче 7.1.

Стоимость перевозок по этому плану:

Z₁ = 95· 17 + 10•12 + 70•11 + 55•19 + 135•22 + 50?27 + 60?7 = 8290 д.е.

Число заполненных клеток должно быть m + n -1 = 4 + 5 — 1 = 8, что имеет место в действительности, т. е. план не вырожден.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U₁ = 0. Потенциалы других строк и столбцов определяем по формулам:

U_i = C_ij — V_j; V_j = C_ij — U_i;

Определяем характеристики клеток, оставшихся свободными по формуле:

E_ij = C_ij — (V_j + U_i) (вписаны в правый нижний угол).

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

Строим для клетки а₃b₁ с отрицательной характеристикой (-14), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (55), находящихся в углах цикла, смежных с этой клеткой. Получаем новый план (табл. № 2) с ценой z₂ = 7520.

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

Строим для клетки а₁b₄ с отрицательной характеристикой (-13), цикл (показан пунктиром) и перемещаем по нему наименьшую из перевозок (40), находящихся в углах цикла, смежных с этой клеткой.

Получаем новый план (табл. № 3) с ценой z₃ = 7000.

Таблица 3

Проверка методом потенциалов показывает, что этот план тоже не оптимален, т.к. среди характеристик свободных клеток есть отрицательные. Cтроим цикл для клетки а₃b₅ с характеристикой (-20).

Получаем четвёртый план (табл. № 4) c ценой z₄ = 6800.

Проверка методом потенциалов показывает, что этот план тоже не оптимален, т.к. среди характеристик свободных клеток есть отрицательные. Cтроим цикл для клетки а₂b₁ с характеристикой (-17).

Перемещаем по этому циклу наименьшую перевозку (15), отмеченную знаком «минус» .

Таблица 4

Получаем пятый план (табл. № 5) с ценой z₅ = 6545.

опорный план стоимость поставка Таблица 5

Ещё одна итерация по клетке а₁b₃ с перемещением 15 единиц груза и получаем оптимальный план с положительными характеристиками всех свободных клеток (табл.№ 6):

Таблица 6

Цена этого плана:

Z₆ = 65?12 + 15•17 + 25?21 + 70•11 + 95?10 + 120?22 + 85?7 = 6515 ден.ед.

Zопт = Z_min = Z₆ = 6515 ден. ед.

Т.о. у поставщика а₃ не будет запрошено 25 единиц груза, т.к. этой частью своего груза он прикрепился к фиктивному потребителю.

Построение оптимального плана методом минимального элемента.

Построение опорного плана эти методом описано в задаче 7.1.

Стоимость перевозок по этому плану Z₁ = 6740 д.е.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U₁ = 0. Потенциалы других строк и столбцов определяем по формулам:

U_i = C_ij — V_j; V_j = C_ij — U_i;

Определяем характеристики клеток, оставшихся свободными по формуле:

E_ij = C_ij — (V_j + U_i) (вписаны в правый нижний угол).

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

Второй план (табл. № 2) с ценой Z₂ = 6620 д.е.

Третий план (табл. № 3) с ценой Z₃ = 6540 д. е

Четвёртый план (табл. № 4) с ценой Z₄ = 6515 д. е

На четвёртой итерации получен оптимальный план, т.к. все характеристики свободных клеток положительны. Этот план совпадает с планом, полученным методом северо-западного угла.

Zопт = Z_min = Z₄ = 6515 ден. ед.

Построение оптимального плана методом Фогеля.

Построение опорного плана эти методом описано в задаче 7.1.

Т.о. получен опорный план с ценой: Z₁ = 6660 ден. ед.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U₁ = 0. Потенциалы других строк и столбцов определяем по формулам:

U_i = C_ij — V_j; V_j = C_ij — U_i;

Определяем характеристики клеток, оставшихся свободными по формуле:

E_ij = C_ij — (V_j + U_i) (вписаны в правый нижний угол).

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

Второй план (табл. № 2) с ценой Z₂ = 6590 д.е.

Таблица

Третий план (табл. № 3) с ценой Z₂ = 6590 д.е.

Очевидно, что полученный план является оптимальным, т.к. он не отличается от предыдущих оптимальных планов решения. Такой же план получен после итераций при использовании метода северо-западного угла и минимального элемента.

Zопт = Z_min = Z₃ = 6515 ден. ед.

Заключение

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

Цель данной работы — построение оптимального плана перевозок груза с минимальной стоимостью, была достигнута.

1. Дойхен Л. А. Математическое моделирование. — Хабаровск, 2002

2. Коровина А. П. Экономико-математическое моделирование. — М.: ИНФРА-М, 2007.

3. Стодоля И. Н. Экономическое моделирование. — М.: Альма, 2005.

4. Якушев Р. Н. Математическое моделирование в экономике. — М.: Экономист, 2006.