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

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Введение

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

а1 =120

а2 =110

а3 = 20

а4 = 70

b1 = 225

b2 = 135

b3 = 140

 

2. Построение опорных планов транспортной модели
1. Построение опорного плана методом северо-западного угла

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

В нашем случае, запасы поставщиков - 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 ден. ед..

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

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

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

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

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

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

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

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

Согласно условию задачи составим таблицу (тарифы 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