Математические методы производственных систем

 

 

Содержание.

• Минимизация затрат на выполнение комплекса работ при заданном времени.

 

• Расчетная часть

 

 

• Минимизация времени выполнения комплекса работ при заданных затратах

 

• Минимизация суммарных затрат по комплексу работ и обьекту

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Исходные данные.

MN-83,значит A=3.

Дано:

Комплекс, состоящий из 8 работ, порядок выполнения которых  определяется сетевым графиком.

По работам сетевого графика  установлены следующие значения характеристик:

Таблица 1

Порядковый № работы     Характеристики	1	2	3	4	5	6	7	8
аk	15	20	10	15	10	15	20	10
вk	-1	-2	-3	-4	-1	-2	-3	-4
dk	4	3	2	1	4	3	2	1
Dk	10	8	3	3	9	7	6	2

 

Расчетная часть

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

L₁{1;2;5;8}  4+3+4+1=12    10+8+9+2=29

L₂{3;5;8}      2+4+1=7          3+9+2=14

L₃{4;6;8}      1+3+1=5          3+7+2=12

L₄{1;8}          4+1=5              10+2=12

L₅{1;2;5;6;7}  4+3+4+3+2=16     10+8+9+7+6=40

L₆ {3;5;6;7}     2+4+3+2=11          3+9+7+6=25

L ₇{4;7}           1+2=3                     3+6=9

Tmin=16                 Tmax=40

Таким образом, время выполнения комплекса работ может изменяться в пределах:

16≤ T ≤40

2.Построим математическую  модель данной задачи.

2.1 Строим систему ограничений:

1 гр. dx=t₁ ≥4 ; t₂ ≥3 ; t₃ ≥2 ; t₄  ≥1 ; t₅ ≥4; t₆ ≥3 ; t₇ ≥2 ; t₈≥1

2гр. Dk= t₁ ≤ 10 ; t₂ ≤ 8 ; t₃ ≤ 3 ; t₄ ≤ 3 ; t₅ ≤ 9 ; t₆ ≤ 7 ;t₇ ≤ 6 ; t₈≤ 2

Система ограничений примет следующий  вид:

τ₁≤6 ; τ₂≤5 ; τ₃≤1 ; τ₄≤2 ; τ₅≤5 ; τ₆≤4 ; τ₇≤4 ; τ₈≤1

t₁+t₂+t₅+t₈≤T

t₃+t₅+t₈≤T

t₄+t₆+t₈≤T

t₁+t₈≤T

t₁+t₂+t₅+t₆+t₇≤T

t₃+t₅+t₆+t₇≤T 

t₄+t₇≤T

 

 

τ₁=t₁-4   »   t₁=τ+4

τ₂=t₂-3   »   t₂=τ₂+3

τ₃=t₃-2   »   t₃=τ₃+2

τ₄=t₄-1   »   t₄=τ₄+1

τ₅=t₅-4    »  t₅=τ₅+4

τ₆=t₆-3    »   t₆=τ₆+

τ₇=t₇-2    »    t₇=τ₇+2

τ₈=t₈-1    »   t₈=τ₈+1

После несложных преобразований система  ограничений примет вид:

t₁+t₂+t₅+t₈≤T-12

t₃+t₅+t₈≤T-7

t₄+t₆+t₈≤T-4

t₁+t₈≤T-5

t₁+t₂+t₅+t₆+t₇≤T-16

t₃+t₅+t₆+t₇≤T-11 

t₄+t₇≤T-3

2.2.Строим целевую функцию по  формуле: Z=

Целевая функция при основных переменных имеет вид

Z=15+20+10+15+10+15+20+10=100

100+(-1)t₁+(-2)t₂+(-3)t₃+(-4)t₄+(-1)t₅+(-2)t₆+(-3)t₇+(-4)t₈→min

При замене tkᵥ на  τk получим:

Z=100+(-1)(τ₁+4)+(-2)(τ₂+3)+(-3)(τ₃+2)+(-4)(τ₄+1)+(-1)(τ₅+4)+(-2)(τ₆+3)+(-3)(τ₇+2)+

+(-4)(τ₈+1)→min

или

Z=60-τ₁ - 2τ₂ - 3τ₃ - 4τ₄ - τ₅ - 2τ₆ - 3τ₇ - 4τ₈→min

 Исключив константу, полученную целевую функцию запишем в следующем виде:

Z'=τ₁+2τ₂+3τ₃+4τ₄+τ₅+2τ₆+3τ₇+4τ₈→max

Целевая функция Z будет стремиться к минимуму при Z', стремящемуся к  максимуму.

 

3.Представим исходную  задачу в матричной форме.

	-Ԏ₁	-Ԏ₂	-Ԏ₃	-Ԏ₄	-Ԏ₅	-Ԏ₆	-Ԏ₇	-Ԏ₈	b
y₁	1								6
y₂		1							5
y₃			1						1
y₄				1					2
y₅					1				5
y₆						1			4
y₇							1		4
y₈								1	1
y₉	1	1			1			1	T-12
y₁₀			1		1			1	T-7
y₁₁				1		1		1	T-4
y₁₂	1							1	T-5
y₁₃			1		1	1	1		T-11
y₁₄	1	1			1	1	1		T-16
y₁₅				1			1		T-3
Z дв	-1	-2	-3	-4	-1	-2	-3	-4	0 max

Таблица 2.

 

 

 

 

 

Составим двойственную(сопряженную)задачу.

Таблица 3.

 

	-y₁	-y₂	-y₃	-y₄	-y₅	-y₆	-y₇	-y₈	-yֹ₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	b
τ₁	-1								-1			-1		-1		-1
τ₂		-1							-1					-1		-2
τ₃			-1							-1			-1			-3
τ₄				-1							-1				-1	-4
τ₅					-1				-1	-1			-1	-1		-1
τ₆						-1					-1		-1	-1		-2
τ₇							-1						-1	-1	-1	-3
τ₈								-1	-1	-1	-1	-1				-4
Z дв.	-6	-5	-1	-2	-5	-4	-4	-1	12-Т	7-Т	4-Т	5-Т	11-Т	16-Т	3-Т	0 min

 

Перейдем от задачи на минимум  к задаче на максимум. Для этого  целевую функцию умножим на -1.                                    

Таблица 4.

                             

	-y₁	-y₂	-y₃	-y₄	-y₅	-y₆	-y₇	-y₈	-yֹ₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	b
τ₁	-1								-1			-1		-1		-1
τ₂		-1							-1					-1		-2
τ₃			-1							-1			-1			-3
τ₄				-1							-1				-1	-4
τ₅					-1				-1	-1			-1	-1		-1
τ₆						-1					-1		-1	-1		-2
τ₇							-1						-1	-1	-1	-3
τ₈								-1	-1	-1	-1	-1				-4
Z дв.	6	5	1	2	5	4	4	1	Т-12	Т-7	Т-4	Т-5	Т-11	Т-16	Т-3	0 max

 

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

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

  Таблица 5.

	-τ₁	-y₂	-y₃	-y₄	-y₅	-y₆	-y₇	-y₈	-yֹ₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	b
у₁	-1								1			1		1		1
τ₂		-1							-1					-1		-2
τ₃			-1							-1			-1			-3
τ₄				-1							-1				-1	-4
τ₅					-1				-1	-1			-1	-1		-1
τ₆						-1					-1		-1	-1		-2
τ₇							-1						-1	-1	-1	-3
τ₈								-1	-1	-1	-1	-1				-4
Z дв.	6	5	1	2	5	4	4	1	Т-18	Т-7	Т-4	Т-11	Т-11	Т-22	Т-3	6 max