Контрольная работа по «Методам оптимальных решений»

Задание 2.

На четыре базы А1, А2, А3, А4 поступил однородный груз в определенном количестве (запасы). Полученный груз требуется перевезти в пять пунктов (потребности). Расстояния между пунктами назначения указаны в матрице расстояний. Стоимость перевозок пропорциональная количеству груза и расстоянию, на которое этот груз перевозится.

1. Построить начальный опорный план тремя способами.
2. Спланировать перевозки так, чтобы их общая стоимость была минимальной.
3. Решить данную задачу в программе Microsoft Excel.

Вариант 2

Пункты отправления	Пункты назначения					Запасы
	В1	В2	В3	В4	В5
А1	15	1	22	19	1	20
А2	21	18	11	4	3	20
А3	26	29	23	26	24	20
А4	21	10	3	19	27	20
Потребности	19	19	19	19	4

 

Решение.

1. 1. Решим задачу методом минимальной стоимости.

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

От поставщика A1 к потребителю B2 будем доставлять min = { 20 , 19 } = 19 единиц продукции.

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

 

Пункты отправления	Пункты назначения					Запасы
	В1	В2	В3	В4	В5
А1	− 15	19 1	− 22	− 19	− 1	20
А2	− 21	− 18	− 11	− 4	− 3	20
А3	− 26	− 29	− 23	− 26	− 24	20
А4	− 21	− 10	− 3	− 19	− 27	20
Потребности	19	19	19	19	4

 

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

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

От поставщика A1 к потребителю B5 будем доставлять

min = { 1 , 4 } = 1 единиц продукции. Разместим в ячейку A1B5 значение равное 1.

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

 

Пункты отправления	Пункты назначения					Запасы
	В1	В2	В3	В4	В5
А1	− 15	19 1	− 22	− 19	1 1	20
А2	− 21	− 18	− 11	− 4	− 3	20
А3	− 26	− 29	− 23	− 26	− 24	20
А4	− 21	− 10	− 3	− 19	− 27	20
Потребности	19	19	19	19	4

 

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

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

От поставщика A2 к потребителю B5 будем доставлять

min = { 20 , 3 } = 3 единиц продукции.

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

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

 

Пункты отправления	Пункты назначения					Запасы
	В1	В2	В3	В4	В5
А1	− 15	19 1	− 22	− 19	1 1	20
А2	− 21	− 18	− 11	− 4	3 3	20
А3	− 26	− 29	− 23	− 26	− 24	20
А4	− 21	− 10	− 3	− 19	− 27	20
Потребности	19	19	19	19	4

 

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

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

От поставщика A4 к потребителю B3 будем доставлять

min = { 20 , 19 } = 19 единиц продукции.

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

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

 

Пункты отправления	Пункты назначения					Запасы
	В1	В2	В3	В4	В5
А1	− 15	19 1	− 22	− 19	1 1	20
А2	− 21	− 18	− 11	− 4	3 3	20
А3	− 26	− 29	− 23	− 26	− 24	20
А4	− 21	− 10	19 3	− 19	− 27	20
Потребности	19	19	19	19	4

 

 

Пункты отправления	Пункты назначения					Запасы
	В1	В2	В3	В4	В5
А1	− 15	19 1	− 22	− 19	1 1	20
А2	− 21	− 18	− 11	17 4	3 3	20
А3	− 26	− 29	− 23	− 26	− 24	20
А4	− 21	− 10	19 3	− 19	− 27	20
Потребности	19	19	19	19	4