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

 

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

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

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

Запасы поставщика A1 составляют 20 единиц продукции. Потребность потребителя B2 составляет 19 единиц продукции. (см. таблицу пункта 2)

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

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

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

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

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

S0 = 1 * 19 + 1 * 1 + 4 * 19 + 3 * 1 + 26 * 18 + 24 * 2 + 21 * 1 + 3 * 19 = 693 ден. ед.

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

2. Минимальную стоимость перевозок найдем методом потенциалов на основе решения методом северо-западного угла.

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

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

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

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

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

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

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

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

- вычисляем общую стоимость  доставки.

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

 

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

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

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

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

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

Примем v4 = 0.

 

v4 + u3 = c34	v4 + u3 = 26	u3 = 26 - 0 = 26
v4 + u4 = c44	v4 + u4 = 19	u4 = 19 - 0 = 19
v5 + u4 = c45	v5 + u4 = 27	v5 = 27 - 19 = 8
v3 + u3 = c33	v3 + u3 = 23	v3 = 23 - 26 = -3
v3 + u2 = c23	v3 + u2 = 11	u2 = 11 - ( -3 ) = 14
v2 + u2 = c22	v2 + u2 = 18	v2 = 18 - 14 = 4
v2 + u1 = c12	v2 + u1 = 1	u1 = 1 - 4 = -3
v1 + u1 = c11	v1 + u1 = 15	v1 = 15 - ( -3 ) = 18

 

Поставщик	Потребитель					Uj
	B 1	B 2	B 3	B 4	B 5
A 1	19   15	1   1	- 28 22	- 22 19	- -4 1	-3
A 2	- -11 21	18   18	2   11	- -10 4	- -19 3	14
A 3	- -18 26	- -1 29	17   23	3   26	- -10 24	26
A 4	- -16 21	- -13 10	- -13 3	16   19	4   27	19
Vi	18	4	-3	0	8

 

Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):

13 = c13 - ( u1 + v3 ) = 22 - ( -3 + ( -3 ) ) = 28

14 = c14 - ( u1 + v4 ) = 19 - ( -3 + 0 ) = 22

15 = c15 - ( u1 + v5 ) = 1 - ( -3 + 8 ) = -4

21 = c21 - ( u2 + v1 ) = 21 - ( 14 + 18 ) = -11

24 = c24 - ( u2 + v4 ) = 4 - ( 14 + 0 ) = -10

25 = c25 - ( u2 + v5 ) = 3 - ( 14 + 8 ) = -19

31 = c31 - ( u3 + v1 ) = 26 - ( 26 + 18 ) = -18

32 = c32 - ( u3 + v2 ) = 29 - ( 26 + 4 ) = -1

35 = c35 - ( u3 + v5 ) = 24 - ( 26 + 8 ) = -10

41 = c41 - ( u4 + v1 ) = 21 - ( 19 + 18 ) = -16

42 = c42 - ( u4 + v2 ) = 10 - ( 19 + 4 ) = -13

43 = c43 - ( u4 + v3 ) = 3 - ( 19 + ( -3 ) ) = -13

 

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

A3B1 ( 31 =-18).

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

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

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

A3B1 , A3B3 , A2B3 , A2B2 , A1B2 , A1B1

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

Поставщик	Потребитель					Запас
	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	- -18 26	-   29	17   23	3   26	-   24	20
A 4	-   21	-   10	-   3	16   19	4   27	20
Потребность	19	19	19	19	4

 

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

min = { 17, 18, 19 } = 17

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

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

Поставщик	Потребитель					Запас
	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	- -18 26	-   29	17   23	3   26	-   24	20
A 4	-   21	-   10	-   3	16   19	4   27	20
Потребность	19	19	19	19	4

 

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

Мы вводим новый маршрут доставки продукции от поставщика A3 к потребителю B1. По данному маршруту доставим 17 единиц продукции, по цене доставки 26 за единицу продукции. Общие затраты увеличатся на 26 * 17 ден. ед.

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

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

От поставщика A2 к потребителю B3 дополнительно поставим 17 единиц продукции, по цене доставки 11 за единицу продукции. Общие затраты увеличатся на 11 * 17 ден. ед.

Сократим поставку от поставщика A2 к потребителю B2 на 17 единиц продукции, по цене доставки 18 за единицу продукции. Общие затраты уменьшатся на 18 * 17 ден. ед.

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

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

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

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