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

 

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

S₀=1120+(1*35-5*35+3*35-6*35)=875 денежных единиц.

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

Табл.21

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

 

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

Каждому поставщику 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₂=1

v₂+u₂=2

v₃+u₁=3

v₄+u₂=6

v₄+u₃=1

v₂=2-0=2

u₁=6-1=5

v₁=1-0=1

v₃=3-5=-2

v₄=6-0=6

u₃=1-6=-5

 

Табл.22

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

 

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

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

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

Δ₂₃=с₂₃-(u₂+v₃)=5-(-2+0)=7

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

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

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

Табл.23

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

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

Табл.24

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

 

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

S₀=875+(5*35-6*35+1*35-6*35)=665 денежных единиц.

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

Табл.25

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

 

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

Каждому поставщику 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₂=1

v₂+u₂=2

v₃+u₁=3

v₄+u₁=5

v₄+u₃=1

v₂=2-0=2

u₁=6-1=5

v₁=1-0=1

v₃=3-5=-2

v₄=5-5=0

u₃=1-0=1

 

 

Табл.26

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

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

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

Δ₂₃=с₂₃-(u₂+v₃)=5-(0+(-2))=7

Δ₂₄=с₂₄-(u₂+v₄)=6-(0+0)=6

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

Δ₃₂=с₃₂-(u₃+v₂)=10-(1+2)=7

Δ₃₃=с₃₃-(u₃+v₃)=20-(1-(-2))=19

Табл.27

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

Все оценки свободных ячеек неотрицательные, следовательно, найдено оптимальное  решение.

	5	0	60	35
Хопт. =	70	80	0	0
	0	0	0	50

 

S_min=6*5+70*1+80*2+60*3+35*5+50*1=665

Общие затраты на доставку всей продукции  для оптимального решения составят 665 руб. При этом от поставщика А₁ доставляется: 5кг - потребителю В₁, 60кг - потребителю В₃, 35кг - потребителю В₄;от поставщика А₂ доставляется: 70кг - потребителю В₁, 80кг - потребителю В₂; от поставщика А₃ доставляется: 50кг - потребителю В₄.

 

3. Дискретное программирование.

 

Дискретное программирование –  это раздел математического программирования, изучающий задачи, в которых на искомые переменные налагается условие  целочисленности, а область допустимых решений конечна. В экономике  существует огромное количество задач с дискретной природой. Прежде всего это задачи с физической неделимостью многих факторов и объектов расчета. Например, нельзя построить 3/2 завода. Количество комплектов, число агрегатов, число типовых размеров предприятий, типовые мощности предприятий – всё это вносит дискретность в оптимизационные расчеты.

Дискретными являются задачи с логическими  переменными, принимающими только два  значения 0 или 1. Иногда дискретное программирование называется целочисленным, однако ДП не всегда целочисленное. Например, ряд вместимостей (М³) – 1,3; 1,6; 1,9;… дискретный, но не целочисленный. Отсюда целочисленное программирование правильно считать частным случаем ДП.

 

3.1. Пример целочисленной задачи линейного программирования. Алгоритм метода Гомори.

 

max (min) Z=∑C_jX_j (1)

∑a_ijx_j=b_i (i=1,m) (2)

x_j≥0 (j=1,n) (3)

x_j – целые (j=1,n) (4)

Алгоритм метода Гомори состоит  из следующих этапов:

1. Решается задача 1-3 с отброшенным условием целочисленности;
2. Полученное оптимальное решение (если оно существует) проверяется на целочисленность. Если условие целочисленности выполняется по всем переменным, то оптимальное решение задач 1-4 совпадает с оптимальным решением задач 1-3. Если это условие не выполняется хотя бы по одной переменной, то переходят к третьему этапу. Если задача 1-3 оказывается неразрешимой, то задача 1-4 тоже не имеет решений.
3. Строится дополнительное ограничение, отсекающее часть области, в которой содержится оптимальное решение задачи 1-3 и не содержится ни одного допустимого решения задачи 1-4.
4. Последний этап представляет возвращение к ЗЛП с отброшенным условием целочисленности, но с расширенной системой ограничений, в которую включенное дополнительное ограничение, полученное на 3 этапе. К расширенной системе ограничений вновь применяется симплексная процедура. Если найденное таким образом решение будет опять не целым, то формируется новое дополнительно ограничение и процесс вычисления повторяется.

Алгоритм метода Гомори позволяет  за конечное число шагов  прийти к оптимальному целочисленному решению, если оно существует.

Основное в алгоритме: это составление  дополнительного ограничения, которое  называется правильным отсечением. Правильное отсечение должно удовлетворять  следующим условиям:

1. Быть линейным
2. Отсекать найденное оптимальное целочисленное решение задачи 1-3
3. Не отсекать ни одной из целочисленных точек 1-4

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