Транспортная модель открытого типа

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

опорный транспортный фогель стоимость

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

Решение транспортной задачи заключается в определении минимальных затрат на заданный условием план перевозки.

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления в п пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через - запасы груза в i-м пункте отправления, через - потребности в грузе в j-м пункте назначения, а через - количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

Для решения транспортной задачи используются три основных способа:

- метод северо-западного угла;

- метод минимальной стоимости;

- метод Фогеля.

С помощью указанных методов строятся опорные планы перевозок и корректируются с применением метода потенциалов.

Решение транспортной задачи позволяет принять оптимальное решение по построению плана перевозок.

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

В связи с поставленной целью необходимо решить ряд задач:

- построить опорные планы транспортной модели методами северо-западного угла, минимальной стоимости и методом Фогеля;

- произвести оценку полученных решений методом потенциалов;

- сделать выводы по результатам решения.

1. Транспортная модель закрытого типа

1.1 Условие задачи

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

Исходные данные:

а₁ =120

а₂ =110

а₃ = 20

а₄ = 70

b₁ = 225

b₂ = 135

b₃ = 140

1.2 Построение опорных планов транспортной модели

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

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

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

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

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	-	-	-	120
		1		2		9
A 2	-	-	-	110
		3		4		1
A 3	-	-	-	20
		6		4		8
A 4	-	-	-	70
		2		3		3
A 5	-	-	-	180
		0		0		0
Потребность	225	135	140

Рассмотрим маршрут доставки от поставщика A1 к потребителю B1 (ячейка A1B1).

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120, 225) = 120 единиц продукции.

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

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

Рассмотрим маршрут доставки от поставщика A2 к потребителю B1 (ячейка A2B1).

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B1 составляет 105 единиц продукции.

От поставщика A2 к потребителю B1 будем доставлять min = (110, 105) = 105 единиц продукции.

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

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

Рассмотрим маршрут доставки от поставщика A2 к потребителю B2 (ячейка A2B2).

Запасы поставщика A2 составляют 5 единиц продукции. Потребность потребителя B2 составляет 135 единиц продукции.

От поставщика A2 к потребителю B2 будем доставлять min = (5, 135) = 5 единиц продукции.

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

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

Рассмотрим маршрут доставки от поставщика A3 к потребителю B2 (ячейка A3B2).

Запасы поставщика A3 составляют 20 единиц продукции. Потребность потребителя B2 составляет 130 единиц продукции.

От поставщика A3 к потребителю B2 будем доставлять min = (20, 130) = 20 единиц продукции.

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

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

Рассмотрим маршрут доставки от поставщика A4 к потребителю B2 (ячейка A4B2).

Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B2 составляет 110 единиц продукции. От поставщика A4 к потребителю B2 будем доставлять min = (70, 110) = 70 единиц продукции.

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

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

Рассмотрим маршрут доставки от поставщика A5 к потребителю B2 (ячейка A5B2).

Запасы поставщика A5 составляют 180 единиц продукции. Потребность потребителя B2 составляет 40 единиц продукции. От поставщика A5 к потребителю B2 будем доставлять min = (180, 40) = 40 единиц продукции.

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

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

Рассмотрим маршрут доставки от поставщика A5 к потребителю B3 (ячейка A5B3).

Запасы поставщика A5 составляют 140 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A5 к потребителю B3 будем доставлять 140 единиц продукции.

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

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

В результате решения получим следующую таблицу.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	120	-	-	120
		1		2		9
A 2	105	5	-	110
		3		4		1
A 3	-	20	-	20
		6		4		8
A 4	-	70	-	70
		2		3		3
A 5	-	40	140	180
		0		0		0
Потребность	225	135	140

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

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

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

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

S0 = 1 * 120 + 3 * 105 + 4 * 5 + 4 * 20 + 3 * 70 + 0 * 40 + 0 * 140 = 745 ден. ед.

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

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

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

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

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

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

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

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

Итак, произведем расчеты согласно исходным данным приведенным выше методом минимальной стоимости.

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

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	-	-	-	120
		1		2		9
A 2	-	-	-	110
		3		4		1
A 3	-	-	-	20
		6		4		8
A 4	-	-	-	70
		2		3		3
A 5	-	-	-	180
		0		0		0
Потребность	225	135	140

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

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120, 225) = 120 единиц продукции.

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

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

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

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A2 к потребителю B3 будем доставлять min = (110, 140) = 110 единиц продукции.

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

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

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

Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B1 составляет 105 единиц продукции.

От поставщика A4 к потребителю B1 будем доставлять min = (70, 105) = 70 единиц продукции.

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

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

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

Запасы поставщика A3 составляют 20 единиц продукции. Потребность потребителя B2 составляет 135 единиц продукции.

От поставщика A3 к потребителю B2 будем доставлять min = (20, 135) = 20 единиц продукции.

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

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

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

Запасы поставщика A5 составляют 180 единиц продукции. Потребность потребителя B1 составляет 35 единиц продукции.

От поставщика A5 к потребителю B1 будем доставлять min = (180, 35) = 35 единиц продукции.

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

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

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

Запасы поставщика A5 составляют 145 единиц продукции. Потребность потребителя B2 составляет 115 единиц продукции. От поставщика A5 к потребителю B2 будем доставлять min = (145, 115) = 115 единиц продукции.

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

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

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

Запасы поставщика A5 составляют 30 единиц продукции. Потребность потребителя B3 составляет 30 единиц продукции.

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

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

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

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

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

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

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

S0 = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 115 + 0 * 30 = 450 ден. ед.

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

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

Согласно условию задачи построим опорный план методом Фогеля.

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

Поставщик	Потребитель	Дi
	B 1	B 2	B 3
A 1	-	-	-	1
		1		2		9
A 2	-	-	-	2
		3		4		1
A 3	-	-	-	2
		6		4		8
A 4	-	-	-	1
		2		3		3
A 5	-	-	-	-
		0		0		0

Поставщик	Потребитель
	B 1	B 2	B 3
A 1	-	-	-
		1		2		9
A 2	-	-	-
		3		4		1
A 3	-	-	-
		6		4		8
A 4	-	-	-
		2		3		3
A 5	-	-	-
		0		0		0
j	1	1	2

Из полученных разностей выберем наибольшую.

Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A2B3, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A2 к потребителю B3, как минимум, на 2 ден. ед. меньше чем от остальных поставщиков к потребителю B3.

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A2 к потребителю B3 будем доставлять min = (110, 140) = 110 единиц продукции.

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

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

Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A4B3, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A4 к потребителю B3, как минимум, на 5 ден. ед. меньше чем от остальных поставщиков к потребителю B3 (см. правую таблицу).

Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B3 составляет 30 единиц продукции.

От поставщика A4 к потребителю B3 будем доставлять min = (70, 30) = 30 единиц продукции.

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

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

Наибольшей разностью обладает строка 3. В данной строке выберем ячейку A3B2, как обладающую наименьшим тарифом.

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

Запасы поставщика A3 составляют 20 единиц продукции. Потребность потребителя B2 составляет 135 единиц продукции.

От поставщика A3 к потребителю B2 будем доставлять min = (20, 135) = 20 единиц продукции.

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

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

Запасы поставщика A5 составляют 115 единиц продукции. Потребность потребителя B2 составляет 115 единиц продукции. От поставщика A5 к потребителю B2 будем доставлять 115 единиц продукции.

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

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

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	120	-	-	120
		1		2		9
A 2	-	-	110	110
		3		4		1
A 3	-	20	-	20
		6		4		8
A 4	40	-	30	70
		2		3		3
A 5	65	115	-	180
		0		0		0
Потребность	225	135	140

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

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

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

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

S0 = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 40 + 3 * 30 + 0 * 65 + 0 * 115 = 480 ден. ед.

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

По результатам построения опорных планов минимальное значение затрат было получено при построении опорного плана методом наименьшей стоимости и составили 450 ден. ед.

Перейдем к перепланировке перевозок методом потенциалов.

1.3 Оптимизация транспортной модели закрытого типа

Метод потенциалов на основе опорного плана, построенного методом северо-западного угла

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

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

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

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

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

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

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

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

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

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

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

Оценка свободной ячейки A2B3 (незадействованного маршрута) отрицательная (?23 =-3), следовательно решение не является оптимальным.

Построим цикл для выбранной ячейки A2B3:

Ячейки образующие цикл для свободной ячейки A2B3:

A2B3, A2B2, A5B2, A5B3

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

Среди ячеек цикла A2B2, A5B3, номера которых четные, найдем ячейку, обладающую наименьшим значением.

min = (5, 140) = 5

В данном случае, это ячейка A2B2.

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

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

Мы вводим новый маршрут доставки продукции от поставщика A2 к потребителю B3. По данному маршруту доставим 5 единиц продукции, по цене доставки 1 за единицу продукции. Общие затраты увеличатся на 1 * 5 ден. ед.

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

Общие затраты уменьшатся на 4 * 5 ден. ед.

От поставщика A5 к потребителю B2 дополнительно поставим 5 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты увеличатся на 0 * 5 ден. ед.

Сократим поставку от поставщика A5 к потребителю B3 на 5 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 5 ден. ед.

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

1 * 5 - 4 * 5 + 0 * 5 - 0 * 5 = (1 - 4 + 0 - 0) * 5 = -3 * 5 ден. ед.

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

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

Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 745 + (- 15) = 730 ден. ед.

Метод потенциала на основе опорного плана, построенного методом минимальной стоимости

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

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

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

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

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

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

S_min = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 115 + 0 * 30 = 450

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

Метод потенциалов на основе опорного плана, построенного методом Фогеля

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

Оценка свободной ячейки A5B3 (незадействованного маршрута) отрицательная (53 =-1), следовательно решение не является оптимальным.

Построим цикл для выбранной ячейки A5B3:

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

Ячейки образующие цикл для свободной ячейки A5B3:

A5B3, A5B1, A4B1, A4B3

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

Среди ячеек цикла A5B1, A4B3, номера которых четные, найдем ячейку, обладающую наименьшим значением.

min = (65, 30) = 30

В данном случае, это ячейка A4B3.

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

Мы вводим новый маршрут доставки продукции от поставщика A5 к потребителю B3. По данному маршруту доставим 30 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты увеличатся на 0 * 30 ден. ед.

Сократим поставку от поставщика A5 к потребителю B1 на 30 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 30 ден. ед.

От поставщика A4 к потребителю B1 дополнительно поставим 30 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 30 ден. ед.

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

Общие затраты уменьшатся на 3 * 30 ден. ед.

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

Общие расходы на доставку продукции от поставщиков к потребителям изменятся на

0 * 30 - 0 * 30 + 2 * 30 - 3 * 30 = (0 - 0 + 2 - 3) * 30 = -1 * 30 ден. ед.

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

Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 480 + (- 30) = 450 ден. ед.

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

2. Транспортная модель открытого типа

2.1 Условия задачи

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

Исходные данные:

а₁ =120

а₂ =110

а₃ = 20

а₄ = 70

b₁ = 225

b₂ = 100

b₃ = 140

Решим поставленную задачу тремя способами: методом северо-западного угла, методом наименьшей стоимости и методом Фогеля.

2.2 Построение опорных планов транспортной модели

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

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

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

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

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

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	-	-	-	120
		1		2		9
A 2	-	-	-	110
		3		4		1
A 3	-	-	-	20
		6		4		8
A 4	-	-	-	70
		2		3		3
A 5	-	-	-	145
		0		0		0
Потребность	225	100	140

При анализе методом северо-западного угла анализ начинаем с ячейки А1В1.

Рассмотрим маршрут доставки от поставщика A1 к потребителю B1 (ячейка A1B1).

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120, 225) = 120 единиц продукции.

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

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

Рассмотрим маршрут доставки от поставщика A2 к потребителю B1 (ячейка A2B1).

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B1 составляет 105 единиц продукции.

От поставщика A2 к потребителю B1 будем доставлять min = (110, 105) = 105 единиц продукции.

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

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

Затем переходим к удовлетворению потребности поставщика В2 и так далее. В результате получим таблицу.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	120	-	-	120
		1		2		9
A 2	105	5	-	110
		3		4		1
A 3	-	20	-	20
		6		4		8
A 4	-	70	-	70
		2		3		3
A 5	-	5	140	145
		0		0		0
Потребность	225	100	140

Затраты на перевозку составят:

S0 = 1*120+105*3+5*4+20*4+70*3+5*0+140*0 = 665 ден. ед.

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

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

Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.

От поставщика A1 к потребителю B1 будем доставлять min = (120, 225) = 120 единиц продукции.

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

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

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

Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A2 к потребителю B3 будем доставлять min = (110, 140) = 110 единиц продукции.

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

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

И так далее пока не израсходуем все ресурсы.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	120	-	-	120
		1		2		9
A 2	-	-	110	110
		3		4		1
A 3	-	20	-	20
		6		4		8
A 4	70	-	-	70
		2		3		3
A 5	35	80	30	145
		0		0		0
Потребность	225	100	140

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

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

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

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

S0 = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 80 + 0 * 30 = 450 ден. ед.

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

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

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

Поставщик	Потребитель	i
	B 1	B 2	B 3
A 1	- 1	- 2	- 9	1
A 2	- 3	- 4	- 1	2
A 3	- 6	- 4	- 8	2
A 4	- 2	- 3	- 3	1
A 5	- 0	- 0	- 0	-
Поставщик	Потребитель
	B 1	B 2	B 3
A 1	- 1	- 2	- 9
A 2	- 3	- 4	- 1
A 3	- 6	- 4	- 8
A 4	- 2	- 3	- 3
A 5	- 0	- 0	- 0
j	1	1	2

Из полученных разностей выберем наибольшую.

Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A2B3, как обладающую наименьшим тарифом.

Стоимость доставки единицы продукции от поставщика A2 к потребителю B3, как минимум, на 2 ден. ед. меньше чем от остальных поставщиков к потребителю B3.

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

От поставщика A2 к потребителю B3 будем доставлять min = (110, 140) = 110 единиц продукции.

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

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

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	-	-	-	120
		1		2		9
A 2	-	-	110	110
		3		4		1
A 3	-	-	-	20
		6		4		8
A 4	-	-	-	70
		2		3		3
A 5	-	-	-	145
		0		0		0
Потребность	225	100	140

Затем по аналогии находим небольшую разность за исключением строки А2. Так до тех пор пока не удовлетворим потребности всех потребителей. В результате получим таблицу.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	120	-	-	120
		1		2		9
A 2	-	-	110	110
		3		4		1
A 3	-	20	-	20
		6		4		8
A 4	40	-	30	70
		2		3		3
A 5	65	80	-	145
		0		0		0
Потребность	225	100	140

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

S0 = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 40 + 3 * 30 + 0 * 65 + 0 * 80 = 480 ден. ед.

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

2.3 Оптимизация транспортной модели открытого типа

Метод потенциала на основе опорного плана, построенного методом северо-западного угла

Произведем оценку полученного решения методом северо-западногоугла.

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

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

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

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

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

Затраты на перевозку по данному плану составят:

S =120*1+110*1+20*4+70*3+105*0+10*0+30*0 = 520 ден. ед.

Метод потенциала на основе опорного плана, построенного методом минимальной стоимости

Произведем оценку плана, построенного методом минимальной стоимости.

Примем v1 = 0.

v1 + u1 = c11 v1 + u1 = 1 u1 = 1 - 0 = 1

v1 + u4 = c41 v1 + u4 = 2 u4 = 2 - 0 = 2

v1 + u5 = c51 v1 + u5 = 0 u5 = 0 - 0 = 0

v2 + u5 = c52 v2 + u5 = 0 v2 = 0 - 0 = 0

v3 + u5 = c53 v3 + u5 = 0 v3 = 0 - 0 = 0

v3 + u2 = c23 v3 + u2 = 1 u2 = 1 - 0 = 1

v2 + u3 = c32 v2 + u3 = 4 u3 = 4 - 0 = 4

Поставщик	Потребитель	U j
	B 1	B 2	B 3
A 1	120	-	-	u 1 = 1
		1		2		9
A 2	-	-	110	u 2 = 1
		3		4		1
A 3	-	20	-	u 3 = 4
		6		4		8
A 4	70	-	-	u 4 = 2
		2		3		3
A 5	35	80	30	u 5 = 0
		0		0		0
V i	v 1 = 0	v 2 = 0	v 3 = 0

12 = c12 - (u1 + v2) = 2 - (1 + 0) = 1

13 = c13 - (u1 + v3) = 9 - (1 + 0) = 8

21 = c21 - (u2 + v1) = 3 - (1 + 0) = 2

22 = c22 - (u2 + v2) = 4 - (1 + 0) = 3

31 = c31 - (u3 + v1) = 6 - (4 + 0) = 2

33 = c33 - (u3 + v3) = 8 - (4 + 0) = 4

42 = c42 - (u4 + v2) = 3 - (2 + 0) = 1

43 = c43 - (u4 + v3) = 3 - (2 + 0) = 1

Поставщик	Потребитель	U j
	B 1	B 2	B 3
A 1	120	-	-	u 1 = 1
		1	1	2	8	9
A 2	-	-	110	u 2 = 1
	2	3	3	4		1
A 3	-	20	-	u 3 = 4
	2	6		4	4	8
A 4	70	-	-	u 4 = 2
		2	1	3	1	3
A 5	35	80	30	u 5 = 0
		0		0		0
V i	v 1 = 0	v 2 = 0	v 3 = 0

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

Smin = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 80 + 0 * 30 = 450

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

Метод потенциала на основе опорного плана, построенного методом Фогеля

Произведем оценку решения методом потенциала.

Примем v1 = 0.

v1 + u1 = c11 v1 + u1 = 1 u1 = 1 - 0 = 1

v1 + u4 = c41 v1 + u4 = 2 u4 = 2 - 0 = 2

v1 + u5 = c51 v1 + u5 = 0 u5 = 0 - 0 = 0

v2 + u5 = c52 v2 + u5 = 0 v2 = 0 - 0 = 0

v3 + u5 = c53 v3 + u5 = 0 v3 = 0 - 0 = 0

v3 + u2 = c23 v3 + u2 = 1 u2 = 1 - 0 = 1

v2 + u3 = c32 v2 + u3 = 4 u3 = 4 - 0 = 4

Поставщик	Потребитель	U j
	B 1	B 2	B 3
A 1	120	-	-	u 1 = 1
		1		2		9
A 2	-	-	110	u 2 = 1
		3		4		1
A 3	-	20	-	u 3 = 4
		6		4		8
A 4	70	-	-	u 4 = 2
		2		3		3
A 5	35	80	30	u 5 = 0
		0		0		0
V i	v 1 = 0	v 2 = 0	v 3 = 0

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

Smin = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 80 + 0 * 30 = 450

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

Заключение

В начале данной работы ставились следующие задачи:

- построение опорных планов методами северо-западного угла, методом минимальной стоимости и методом Фогеля;

- произвести оценку полученного решения методом потенциалов.

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

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

Список использованных источников

опорный транспортный фогель стоимость

1. Шапкин А.С. Математические методы и модели исследования операций [Текст]: учебник / А.С. Шапкин, Н.П. Мазаева. - М.: Издательско-торговая корпорация «Дашков и Ко», 2004. - 400 с., С. 119 - 146.

2. Кремер, Н.Ш. Исследование операций в экономике [Текст]: учебное по-собие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; под ред. Н.Ш. Кремера. - М.: ЮНИТИ, 2003. - 407 с., С. 123 - 153.

3. Кузнецов, Б.Т. Математические методы и модели исследования опера-ций [Текст]: учебное пособие / Б.Т. Кузнецов. - М.: ЮНИТИ-ДАНА, 2005. - 390 с., С. 103 - 129.

4. Хазанова, Л.Э. Математическое моделирование в экономике [Текст]: учебное пособие / Л.Э. Хазанова. - М.: Издательство БЕК, 1998. - 141 с., С. 45 - 76.

Размещено на Allbest.ru