Курсовая работа по «Теории принятия решения»

Рассмотрим маршрут доставки от поставщика А₂ к потребителю В₄ (ячейка А₂В₄). Запасы поставщика А₂ составляют 35 кг. Потребность потребителя В₄ составляет 85  кг. От поставщика А₂ к потребителю В₄ будем доставлять min{35,85}=35 кг. Разместим в ячейку А₂В₄ значение равное 35. Мы полностью израсходовали запасы поставщика А₂. Вычеркиваем строку 2 таблицы, т.е. исключаем ее из дальнейшего рассмотрения.

Табл.12

Поставщик	Потребитель				Запас
	В1	В2	В3	В4
А1	75   6	25   7	3	5	100
А2	1	55   2	60   5	35   6	150
А3	8	10	20	1	50
Потребность	75	80	60	85

 

Рассмотрим маршрут доставки от поставщика А₃ к потребителю В₄ (ячейка А₃В₄). Запасы поставщика А₃ составляют  50 кг. Потребность потребителя В₄ составляет  50 кг. От поставщика А₃ к потребителю В₄ будем доставлять 50 кг. Разместим в ячейку А₃В₄ значение равное 50. Мы полностью удовлетворили потребности потребителя В₄. Вычеркиваем столбец 4 таблицы, т.е. исключаем его из дальнейшего рассмотрения.

Табл.13

Поставщик	Потребитель				Запас
	В1	В2	В3	В4
А1	75   6	25   7	3	5	100
А2	1	55   2	60   5	35   6	150
А3	8	10	20	50   1	50
Потребность	75	80	60	85

 

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

Количество базисных ячеек равно 6. Найденное начальное решение (израсходованы  запасы поставщиков и удовлетворены все потребности потребителей). 

S₀=6*75 + 7*25 + 2*55 + 5*60 + 6*35 + 1*50 = 1295 денежных единиц.

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

Шаг1. Произведем оценку полученного решения.

Каждому поставщику A_i ставим в соответствие некоторое число – u_i, называемое потенциалом поставщика. Каждому потребителю B_j ставим в соответствие некоторое число – v_j, называется потенциалом потребителя. Для базисной ячейки, сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута

(u_i + v_j= с_ij, где с_ij - тариф клетки A_iB_j). Поскольку, число базисных клеток 6, а количество потенциалов 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Возьмем u₂=0.

 

 

v₁+u₁=c₁₁

v₂+u₁=c₁₂

v₂+u₂=c₂₂

v₃+u₂=c₂₃

v₄+u₂=c₂₄

v₄+u₃=c₃₄

v₁+u₁=6

v₂+u₁=7

v₂+u₂=2

v₃+u₂=5

v₄+u₂=6

v₄+u₃=1

v₂=2-0=2

u₁=7-2=5

v₁=6-5=1

v₃=5-0=5

v₄=6-0=6

u₃=1-6=-5

 

Табл. 14

Поставщик	Потребитель				Uj
	В1	В2	В3	В4
А1	75     6	25      7	3	5	U1=5
А2	1	55      2	60     5	35       6	U2=0
А3	8	10	20	50       1	U3=-5
Vi	V1=1	V2=2	V3=5	V4=6

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

Δ₁₃=с₁₃-(u₁+v₃)=3-(5+5)=-7

Δ₁₄=с₁₄-(u₁+v₄)=5-(5+6)=-6

Δ₂₁=с₂₁-(u₂+v₁)=1-(0+1)=0

Δ₃₁=с₃₁-(u₃+v₁)=8-(-5+1)=12

Δ₃₂=с₃₂-(u₃+v₂)=10-(-5+2)=13

Δ₃₃=с₃₃-(u₃+v₃)=20-(-5+5)=20

Табл.15

Поставщик	Потребитель				Uj
	В1	В2	В3	В4
А1	75     6	25      7	-7           3	-6             5	U1=5
А2	0           1	55      2	60     5	35       6	U2=0
А3	12         8	13         10	20        20	50       1	U3=-5
Vi	V1=1	V2=2	V3=5	V4=6

 

Среди оценок свободных ячеек есть отрицательные, следовательно решение  не является оптимальным. Выберем свободную  ячейку - А₁В₃(Δ₁₃=-7) (имеющую отрицательную оценку) и построим цикл.

Ячейки, образующие цикл для свободной ячейки А₁В₃: А₁В₃, А₁В₂, А₂В₂, А₂В₃.Среди ячеек цикла, номера которых четные найдем ячейку, обладающую наименьшим значением min{25,60}=25 (ячейка А₁В₂).

Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика А₁ к потребителю В₂, по которому доставляется всего (25) единиц продукции. Данный маршрут исключим из схемы доставки продукции. От ячеек с четными номерами отнимем 25, а к четным прибавим 25.

 

Табл.16

Поставщик	Потребитель				Запас
	В1	В2	В3	В4
А1	75   6	25-25   7	-7    25    3	5	100
А2	1	55+25  2	60-25   5	35   6	150
А3	8	10	20	50  1	50
Потребность	75	80	60	85

 

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

S₀=1295+(3*25-7*25+2*25-5*25)=1120 денежных единиц.

Ячейка А₁В₂ выйдет из базиса, а ячейка А₁В₃ станет базисной, вводится новый маршрут доставки от поставщика А₁ к потребителю В₃.

Табл.17

Поставщик	Потребитель				Запас
	В1	В2	В3	В4
А1	75   6	7	25   3	5	100
А2	1	80   2	35   5	35   6	150
А3	8	10	20	50   1	50
Потребность	75	80	60	85

Шаг2. Произведем оценку полученного решения.

Каждому поставщику A_i ставим в соответствие некоторое число – u_i, называемое потенциалом поставщика. Каждому потребителю B_j ставим в соответствие некоторое число – v_j, называется потенциалом потребителя. Для базисной ячейки, сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута

(u_i + v_j= с_ij, где с_ij - тариф клетки A_iB_j). Поскольку, число базисных клеток 6, а количество потенциалов 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Возьмем u₂=0.

 

 

v₁+u₁=c₁₁

v₃+u₁=c₁₃

v₂+u₂=c₂₂

v₃+u₂=c₂₃

v₄+u₂=c₂₄

v₄+u₃=c₃₄

v₁+u₁=6

v₃+u₁=3

v₂+u₂=2

v₃+u₂=5

v₄+u₂=6

v₄+u₃=1

v₂=2-0=2

u₁=3-5=-2

v₁=6-(-2)=8

v₃=5-0=5

v₄=6-0=6

u₃=1-6=-5

 

Табл.18

Поставщик	Потребитель				Uj
	В1	В2	В3	В4
А1	75     6	7	25        3	5	U1=-2
А2	1	80      2	35     5	35       6	U2=0
А3	8	10	20	50       1	U3=-5
Vi	V1=8	V2=2	V3=5	V4=6

 

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

Δ₁₂=с₁₂-(u₁+v₂)=7-(-2+2)=7

Δ₁₄=с₁₄-(u₁+v₄)=5-(-2+6)=1

Δ₂₁=с₂₁-(u₂+v₁)=1-(0+8)=-7

Δ₃₁=с₃₁-(u₃+v₁)=8-(-5+8)=5

Δ₃₂=с₃₂-(u₃+v₂)=10-(-5+2)=13

Δ₃₃=с₃₃-(u₃+v₃)=20-(-5+5)=20

Табл.19

Поставщик	Потребитель				Uj
	В1	В2	В3	В4
А1	75     6	7             7	25        3	1              5	U1=-2
А2	-7          1	80      2	35     5	35       6	U2=0
А3	5           8	13         10	20        20	50       1	U3=-5
Vi	V1=8	V2=2	V3=5	V4=6

 

Оценка свободной ячейки А₂В₁ отрицательная, следовательно, решение не является оптимальным. Построим цикл для выбранной ячейки А₂В₁. Ячейки, образующие цикл для свободной ячейки А₂В₁: А₂В₁, А₂В₃, А₁В₃, А₁В₁. Среди ячеек цикла А₂В₃, А₁В₁, номера которых четные, найдем ячейку, обладающую наименьшим значением min{35,75}=35. Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика А₂ к потребителю В₁, по которому доставляется меньше всего (35) единиц продукции. Данный маршрут исключим из схемы доставки продукции. От ячеек с четными номерами отнимем 35, а к четным прибавим 35.

Табл.20

Поставщик	Потребитель				Uj
	В1	В2	В3	В4
А1	75-35  6	7	25+35      3	5	U1=-2
А2	-7    35       1	80      2	35-35     5	35       6	U2=0
А3	8	10	20	50       1	U3=-5
Vi	V1=8	V2=2	V3=5	V4=6