Транспортная задача (практика) часть 1

Содержание лекции:

1. Математическая модель задачи.
2. Метод северо-западного угла.
3. Метод наименьшего элемента.

В курсе высшей математики раздела «Прикладная математика» большое значение уделялось решению транспортных задач. Это решение  базируется на создании опорного плана, где оптимальным методом его построения считается метод наименьших тарифов (метод наименьшего элемента). Метод наименьших тарифов состоит в последовательном отыскании, на каждом шаге построения, минимального значения коэффициента затрат на перевозку единицы груза. Однако для задания первого приближения достаточно использовать более оперативный метод – метод северо-западного угла. Этот метод удобно использовать при решении задачи с помощью программирования.

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

1. 1.      Математическая модель задачи

Условие:

Однородный груз сосредоточен у m поставщиков в объемах a₁, a₂, ... a_m.
Данный груз необходимо доставить n потребителям в объемах b_1, b₂ ... b_n.
Известны C_ij , i=1,2,...m; j=1,2,...n — стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю.

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

Исходные данные транспортной задачи записываются в виде таблицы:

Исходные данные задачи могут быть представлены в виде:

• вектора А=(a₁,a₂,...,a_m) запасов поставщиков
• вектора B=(b₁,b₂,...,b_n) запросов потребителей
• матрицы стоимостей:

Математическая модель транспортной задачи 

Переменными (неизвестными) транспортной задачи являются x_ij , i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок:

.

Так как произведение C_ij*X_ij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:

.

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

.

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

, i=1, 2, …, m.

Вторая группа из n уравнений выражает требование удовлетворить запросы всех n потребителей полностью и имеет вид:

, j=1, 2, …, n.

Учитывая условие неотрицательности объемов перевозок математическая модель выглядит следующим образом:

                                     (1)

, i=1, 2, …, m,                                           (2)

, j=1, 2, …, n,                                            (3)

x_ij  ³ 0, i=1, 2, …, m; j=1, 2, …, n.                           (4)

В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.:

.

Такая задача называется задачей с правильным балансом, а модель задачи закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а модель задачи — открытой.

Математическая формулировка транспортной задачи такова: найти переменные задачи X=(x_ij), i=1,2,...,m; j=1,2,...,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).

Задача

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

Решение:
1. Вводим переменные задачи (матрицу перевозок):

2. Записываем матрицу стоимостей:

3. Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X.

Z(X)=3x₁₁+5x₁₂+7x₁₃+4x₂₁+6x₂₂+10x₂₃.                  

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

1. 4.      Составим систему ограничений задачи. 

Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X равняться запасам второго поставщика:

x₁₁+x₁₂+x₁₃=40,

x₂₁+x₂₂+x₂₃=50.

Это означает, что запасы поставщиков вывозятся полностью.

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

x₁₁+x₂₁=20,

x₁₂+x₂₂=30,

x₁₃+x₂₃=40.

Это означает, что запросы потребителей удовлетворяются полностью.

Необходимо также учитывать, что перевозки не могут быть отрицательными:

x_ij  ³ 0, i=1, 2; j=1, 2, 3.

Ответ: Таким образом, математическая модель рассматриваемой задачи записывается следующим образом:

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

Z(X)=3x₁₁+5x₁₂+7x₁₃+4x₂₁+6x₂₂+10x₂₃.                      (5)

                                (6)

x_ij  ³ 0, i=1, 2; j=1, 2, 3.                            (7)

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

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

Три завода производят небольшие электрические моторы для четырех производителей бытовых приборов. Удельные производственные затраты на заводах отличаются из-за различий в оборудовании и производительности труда. Заказы клиентов показаны в таблице:

Удельные производственные затраты и ежемесячные производственные мощности показаны в таблице:

Затраты на доставку продукции клиентам также различны. Удельные затраты на транспортировку в долларах приводятся в таблице:

Руководство компании должно решить, сколько единиц продукции выпустить на каждом заводе, и сколько отправить каждому клиенту с каждого завода. При этом надо минимизировать суммарные производственные и транспортные расходы.

Математическая модель

Целевая функция в данной задаче имеет вид

Z(X)=17×(3x₁₁+2x₁₂+5x₁₃+7x₁₄)+20×(6x₂₁+4x₂₂+8x₂₃+3x₂₄)+24×(9x₃₁+x₃₂+5x₃₃+4x₃₄)

Система ограничений:

x_ij  ³ 0, i=1, 2, 3; j=1, 2, 3, 4.  

2. Метод северо-западного угла

Для составления опорного плана методом северо-западного угла рассмотрим следующую задачу.

Пример.

Имеются два цементных завода и три основных потребителя – домостроительные комбинаты. В таблице указаны суточные объемы производства цемента, суточная потребность в нем комбинатов и стоимость перевозки 1 т цемента от каждого завода к каждому комбинату.

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

Решение.

Проверим необходимое и достаточное условие разрешимости задачи.
∑ a_i = 400 + 500  = 900;

∑ b_j = 500 + 200 + 300 = 1000.

Условие баланса не соблюдается. Запасы не равны потребностям. Следовательно, модель транспортной задачи является открытой. Для того чтобы сбалансировать задачу, т. е. привести ее к закрытой модели, введем фиктивного поставщика (3-ю строку) с запасом в грузе 1000-900=100 т/сут и с нулевыми тарифами перевозок.

Составим математическую модель задачи:

Найти переменные задачи, обеспечивающие минимум целевой функции

Z(X)=100x₁₁+150x₁₂+250x₁₃+200x₂₁+300x₂₂+300x₂₃+0x₃₁+0x₃₂+0x₃₃

и удовлетворяющие системе ограничений

и условиям неотрицательности

x_ij  ³ 0, i=1, 2, 3; j=1, 2, 3.                           

Найдем опорный план методом северо-западного угла.

Порядок заполнения таблицы:

x₁₁=min(500; 400)=400 – запасы завода №1 исчерпаны;

x₂₁=min(500-400=100; 500)=100 – потребности комбината №1 удовлетворены;

x₂₂=min(200; 500-100=400)=200 – потребности комбината №2 удовлетворены;

x₂₃=min(300; 500-100-200=200)=200 – запасы завода №2 исчерпаны;

x₃₃=min(300-200=100; 100)=100  – запасы завода №3 исчерпаны и потребности комбината №3 удовлетворены.

Целевая функция (суммарные транспортные расходы):

Z(X)=100×400+200×100+300×200+300×200+0×100=180000 руб.

1. 3.      Метод наименьшего элемента

У компании есть три склада, с которых она может доставлять продукцию трем розничным торговым точкам. Спрос на продукцию составляет на первой точке 30 ящиков, на второй – 40, на третьей – 50. Запас данной продукции на складе 1 составляет 60 ящиков, на складе 2 – 20 и на складе 3 – 40. Затраты на транспортировку одного ящика продукции со складов к торговым точкам представлены в таблице.

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

Решение.

Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 60 + 20 + 40 = 120;

∑ b = 30 + 40 + 50 = 120.

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

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

Порядок заполнения таблицы:

x₁₁=min(30; 60)=30 – потребности В1 удовлетворены;

x₁₂=min(40; 60-30=30)=30 – запасы А1 исчерпаны;

x₂₂=min(40-30=10; 20)=10 – потребности В2 удовлетворены;

x₂₃=min(50; 20-10=10)=10 – запасы А2 исчерпаны;

x₃₃=min(50-10=40; 40)=40  – запасы А3 исчерпаны и потребности В3 удовлетворены.

Целевая функция (суммарные транспортные расходы):

 у. е.

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

Задача № 1. Закрытая транспортная задача.

Имеются 3 (m) поставщика и 5 (n) потребителей. Мощность (запасы) поставщиков и спрос (потребность) потребителей, а также  затраты на перевозку для каждой пары «поставщик-потребитель» сведены в таблице поставок.

Задача ставится таким образом: найти объемы перевозок для каждой пары «поставщик-потребитель» так, чтобы:

1. мощности всех поставщиков были реализованы;
2. спрос всех потребителей был удовлетворен;
3. суммарные затраты на перевозку были бы минимальные.

Данный пример является сбалансированной задачей, так как суммы потребностей и запасов равны 700.

Экономико-математическая модель.

Искомый объем перевозки от i-ого поставщика к j-ому потребителю обозначим через . Тогда определяются ограничения для условия реализации всех мощностей:

Ограничения для удовлетворения спросов всех потребителей:

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует ввести дополнительное ограничение: .

Суммарные затраты на перевозку выражаются через коэффициенты затрат и поставки и определяют целевую функцию.

Табличная модель. Массив [В4:F6] – матрица переменных. Ячейка [В19] содержит целевую функцию, определяемую, как СУММПРОИЗВ [В4:F6] на Матрицу тарифов [В15:F17].

Рис. 1.Табличное представление модели

Рис. 2. Табличная модель с представленными формулами

Оптимизация. Решение задачи № 1.Сервис   Поиск решения.

Рис. 3. Диалоговое окно надстройки Поиск решения

Рис. 4. Решение транспортной задачи

Вывод:
 Минимальные суммарные затраты на перевозку груза в размере 8200 д.е. достигаются путем распределения поставок, представленных в ячейках [B4:F6]. Так, например, поставщик А2 должен поставить груз к потребителю В1 в объеме 80 ед. груза, к потребителю В2 в объеме 50 ед. груза и к потребителю В5 в объеме 120 ед. груза. К потребителям В3 и В4 ехать не надо.

Задача № 2. Открытая транспортная задача.

Задача № 3. Открытая транспортная задача.

Оптимизация. Решение задачи № 1.Сервис   Поиск решения.

Рис. 5. Диалоговое окно надстройки Поиск решения

Рис. 6. Решение транспортной задачи

Вывод:
 Минимальные суммарные затраты на перевозку груза в размере 8200 д.е. достигаются путем распределения поставок, представленных в ячейках [B4:F6]. Так, например, поставщик А2 должен поставить груз к потребителю В1 в объеме 80 ед. груза, к потребителю В2 в объеме 50 ед. груза и к потребителю В5 в объеме 120 ед. груза. К потребителям В3 и В4 ехать не надо.

Список литературы

1. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002.

2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001.

3. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента. СПб.: Лань, 2000.

4. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. М.: Изд. ДЕЛО, 2003.

5. Ларичев О.И. Теория и методы принятия решений. М.: Логос, 2000.