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

 

Пункты отправления	Пункты назначения					Запасы
	В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	1 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	19 26	− 29	− 23	− 26	− 24	20
А4	− 21	− 10	19 3	1 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	19 26	− 29	− 23	1 26	− 24	20
А4	− 21	− 10	19 3	1 19	− 27	20
Потребности	19	19	19	19	4

 

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

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

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

S0 = 1*19 + 1*1 + 4*17 + 3*3 + 26*19 + 26*1 + 3*19 + 19*1 = 693 ден. ед.

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

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

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

В нашем случае, потребность всех потребителей - 80 единиц продукции равна запасам всех поставщиков.

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

Запасы поставщика A1 составляют 20 единиц продукции. Потребность потребителя B1 составляет 19 единиц продукции. От поставщика A1 к потребителю B1 будем доставлять min = { 20 , 19 } = 19 единиц продукции. Разместим в ячейку A1B1 значение равное 19.

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

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

Запасы поставщика A1 составляют 1 единиц продукции. Потребность потребителя B2 составляет 19 единиц продукции. (см. таблицу пункта 2) От поставщика A1 к потребителю B2 будем доставлять min = { 1 , 19 } = 1 единиц продукции.

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

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

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1	19   15	1   1	-   22	-   19	-   1	20
A 2	-   21	18   18	2   11	-   4	-   3	20
A 3	-   26	-   29	17   23	3   26	-   24	20
A 4	-   21	-   10	-   3	16   19	4   27	20
Потребность	19	19	19	19	4

 

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

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

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

S0 = 15 * 19 + 1 * 1 + 18 * 18 + 11 * 2 + 23 * 17 + 26 * 3 + 19 * 16 + 27 * 4 = 1513 ден. ед.

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

3. Решим задачу методом Фогеля.

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

Поставщик	Потребитель					∆i
	B 1	B 2	B 3	B 4	B 5
A 1	-   15	-   1	-   22	-   19	-   1	0
A 2	-   21	-   18	-   11	19   4	-   3	1
A 3	-   26	-   29	-   23	-   26	-   24	1
A 4	-   21	-   10	-   3	-   19	-   27	7
∆i	6	9	8	15	2

 

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

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

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

От поставщика A2 к потребителю B4 будем доставлять min = { 20 , 19 } = 19 единиц продукции. Размещаем данные в ячейку.

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

2) Найдем разность между  наименьшими свободными тарифами

Поставщик	Потребитель					∆i
	B 1	B 2	B 3	B 4	B 5
A 1	-   15	19   1	-   22	-   19	-   1	0
A 2	-   21	-   18	-   11	19   4	-   3	8
A 3	-   26	-   29	-   23	-   26	-   24	1
A 4	-   21	-   10	-   3	-   19	-   27	7
∆i	6	9	8	-	2