Методы_оптимизации,_Лаба_№_2,_Суслов_М_В_,_ПИ_310з. Отчет по лабораторной работе 2 Решение транспортной задачи методами северозападного угла и минимального элемента

• Название: Отчет по лабораторной работе 2 Решение транспортной задачи методами северозападного угла и минимального элемента
• Дата: 24.11.2022
• Размер: 28.36 Kb.
• Имя файла: Методы_оптимизации,_Лаба_№_2,_Суслов_М_В_,_ПИ_310з.docx
• Тип: Отчет; #809351

ФГБОУ ВО

Уфимский Государственный Авиационный Технический Университет

Кафедра АСУ

Отчет по

лабораторной работе №2

«Решение транспортной задачи методами северо-западного угла и минимального элемента»

по дисциплине «Методы оптимизации»

Вариант №13

Выполнил:

ст. гр. ПИ-310з

Данилкин А.И.
Проверил:

старший преподаватель

Кондратьева О.В.

Уфа 2022

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

Три предприятия данного экономического района могут производить некоторую однородную продукцию в количествах соответственно равных А1 = 120, А2 = 310, А3 = 120 единиц. Эта продукция должна быть поставлена пяти потребителям в количествах, соответственно равных В1 = 110, В2 = 110, В3 = 100 В4 = 120, В5 = 110 единиц. Затраты, связанные с производством и доставкой единицы продукции, задаются матрицей С.



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

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

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

Пункты отправления	Пункты назначения					Запасы
						120
						310
						120
Потребности	110	110	100	120	110	550

У нас 3 пункта отправления и 5 пунктов назначения. Следовательно, опорный план задачи определяется числами, стоящими в 3 + 5 – 1 = 7 заполненных клетках. Начнем пошагово заполнять эту таблицу данными по перевозкам. Согласно методу северо-западного угла, мы всегда выбираем левый верхний угол таблицы. Мысленно вычеркиваем строки и столбцы по мере заполнения пунктов назначения и опустошения пунктов отправления.
Шаг 1.

Перевозим 120 ед. товара из в .

пуст. Вычеркиваем строку .

имеет еще место для 110 ед. товара.

Шаг 2.

Перевозим 70 ед. товара из в .

хранит еще 200 ед. товара.

полон. Вычеркиваем столбец .
Шаг 3.

Перевозим 80 ед. товара из в .

хранит еще 120 ед. товара.

полон. Вычеркиваем столбец .
Шаг 4.

Перевозим 120 ед. товара из в .

пуст. Вычеркиваем строку .

имеет еще место для 10 ед. товара.
Шаг 5.

Перевозим 10 ед. товара из в .

хранит еще 100 ед. товара.

полон. Вычеркиваем столбец .
Шаг 6.

Перевозим 70 ед. товара из в .

хранит еще 30 ед. товара.

полон. Вычеркиваем столбец .
Шаг 6.

Перевозим 30 ед. товара из в .

пуст.

полон.
В результате выполнения шагов получаем:

Пункты отправления	Пункты назначения					Запасы
	170						170/0
	70	80	120				270/200/120/0
			10	70	30		110/100/30/0
Потребности	240/70/0	80/0	130/10/0	70/0	30/0		550

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

Опорный план:



Помножив количество грузов на тарифы получаем общую стоимость перевозок:

3730
Вычисление методом минимального элемента.

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

Пункты отправления	Пункты назначения													Запасы
	7		9			10			6			5		170
	12		8			6			5			13		270
	6		2			8			2			4		110
Потребности	240			80			130			70		30		550

Как и в предыдущем методе, опорный план задачи определяется числами, стоящими в 7 заполненных клетках. Начнем пошагово заполнять эту таблицу данными по перевозкам. Согласно методу минимального элемента, мы всегда выбираем клетку с самым дешевым тарифом. Мысленно вычеркиваем строки и столбцы по мере заполнения пунктов назначения и опустошения пунктов отправления.
Шаг 1.

Самый дешевый тариф 2 находится в клетках и . Выбираем произвольную клетку. Пусть это будет .

Перевозим 80 ед. товара из в .

имеет еще место для 30 ед. товара.

полон. Вычеркиваем столбец .


Шаг 2.

Самый дешевый тариф 2 находится в клетке .

Перевозим 30 ед. товара из в .

пуст. Вычеркиваем строку .

имеет еще место для 40 ед. товара.
Шаг 3.

Самый дешевый тариф 5 находится в клетках и . Выбираем произвольную клетку. Пусть это будет .

Перевозим 30 ед. товара из в .

имеет еще место для 140 ед. товара.

полон. Вычеркиваем столбец .
Шаг 4.

Самый дешевый тариф 5 находится в клетке .

Перевозим 40 ед. товара из в .

имеет еще место для 140 ед. товара.

полон. Вычеркиваем столбец .
Шаг 5.

Самый дешевый тариф 6 находится в клетке .

Перевозим 130 ед. товара из в .

имеет еще место для 140 ед. товара.

полон. Вычеркиваем столбец .
Шаг 6.

Самый дешевый тариф 7 находится в клетке .

Перевозим 140 ед. товара из в .

пуст. Вычеркиваем строку .

имеет еще место для 100 ед. товара.
Шаг 7.

Последний тариф 12 находится в клетке .

Перевозим 100 ед. товара из в .

пуст.

полон.

В результате выполнения шагов получаем:

Пункты отправления	Пункты назначения														Запасы
	7			9			10			6			5			170/140/0
		140												30
	12			8			6			5			13			270/230/100/0
		100						130			40
	6			2			8			2			4			110/30/0
					80						30
Потребности	240/100/0		80/0			130/0			70/40/0			30/0			550

Результат решения методом минимального элемента

Опорный план:



Помножив количество грузов на тарифы получаем общую стоимость перевозок:

3530

Вывод

Перевозки, рассчитанные методом минимального элемента (3530), оказались выгоднее перевозок, рассчитанных методом северо-западного угла (3730), на 200.