Главная | Обратная связь | Поможем написать вашу работу!

Условные обозначения в формулах экономико-математической модели

⇐ ПредыдущаяСтр 2 из 2

C_k - затраты на выполнение к-й работы сетевого графика;

t_k- время выполнения к-й работы;

a_k, b_k - коэффициент линейной зависимости затрат от времени;

d_k_,D_k - соответственно минимальное и максимальное время выполнения к-й работы;

T - планируемое время выполнения всего комплекса работ;

T_min, T_max - соответственно минимальное и максимальное возможные значения времени выполнения комплекса работ;

S_min, S_max - соответственно минимально и максимально возможные значения затрат на выполнение комплекса работ;

N_раб - число работ, включаемых в комплекс;

- булева переменная, имеющая значения 0 или 1;

N_пут - число полных путей;

- дополнительная переменная;

y_k - двойственная переменная.

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

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

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

Путь	Ранний срок	Поздний срок
L₁{1;5}	2+2=4	3+6=9
L₂{2;6}	1+1=2	5+4=9
L₃{3;8}	2+3=5	9+10=19
L₄{2;4;5;}	1+4+2=7	5+7+6=18
L₅{2;7;8}	1+4+3=8	5+8+10=23
L₆{1;4;7;8;}	2+4+4+3=13	3+7+8+10=28
L₇{3;7;4;5;}	2+4+4+2=12	9+8+7+6=30
L₈{3;7;6}	2+4+1=7	9+8+4=21
L₉{1;4;6}	2+4+1=7	3+7+4=14
	T_min=13	T_max=30

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

≤T≤30

Директивное время находим по формуле T_д=(Т_min+Т_max)/2

T_д=(13+30)/2≈22

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

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

t₁≥2	t₂≥1	t₃≥2	t₄≥4	t₅≥2	t₆≥1	t₇≥4	t₈≥3
t₁≤3	t₂≤5	t₃≤9	t₄≤7	t₅≤6	t₆≤4	t₇≤8	t₈≤10

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

t₁+ t₄+ t₆≤T

t₁-2≥0

t₂-1≥0

t₃-2≥0

t₄-4≥0

t₅-2≥0

t₆-1≥0

t₇-4≥0

t₈-3≥0

Введем новые переменные, связанные с базовыми следующим образом:

ф₁ = t₁- 2 ф₂ = t₂ - 1 ф₃ =t₃ - 2 ф₄ =t₄ - 4 ф₅ =t₅ - 2 ф₆ =t₆ - 1 ф₇ = t₇ - 4 ф₈ = t₈ - 3

Это приведет к тому, что ф_k≥0

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

t₁ =ф₁+2 t₂ =ф₂+1 t₃ =ф₃+2 t₄ =ф₄+4 t₅=ф₅+2 t₆ =ф₆+1 t₇= ф₇+4 t₈ = ф₈+3

ф₁+2 ≤3

ф₂+1≤5

ф₃+2≤9

ф₄ +4≤7

ф₅+2≤6

ф₆+1≤4

ф₇+4 ≤8

ф₈+3≤10

ф₁+2+ ф₅+2≤T

ф₂+1+ ф₆+1≤T

ф₃+2+ ф₈+3≤T

ф₂+1+ ф₄+4+ ф₅+2≤T

ф₂+1 + ф₇+4+ ф₈+3≤T

ф₁+2+ ф₄+4+ ф₇+4+ ф₈+3≤T

ф₃+2+ ф₇+4+ ф₄+4+ ф₅+2≤T

ф₃+2+ ф₇+4+ ф₆+1≤T

ф₁+2+ ф₄+4+ ф₆+1≤T

ф₁ ≤1

ф₂≤4

ф₃≤7

ф₄ ≤3

ф₅≤4

ф₆≤3

ф₇ ≤4

ф₈≤7

преобразований система ограничений примет вид:

ф₁+ ф₅≤T-4

ф₂+ ф₆≤T-2

ф₃+ ф₈≤T-5

ф₂+ ф₄+ ф₅≤T-7

ф₂+ф₇+ ф₈≤T-8

ф₁+ф₄+ ф₇+ ф₈≤T-13

ф₃+ ф₇+ ф₄+ ф₅≤T-12

ф₃+ ф₇+ ф₆≤T-7

ф₁+ ф₄+ ф₆≤T-7

Строим целевую функцию.

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

Z=215- 4t₁-5 t₂ - 2t₃- 3t₄- 4t₅- 1t₆- 2t₇- 3t₈→ min

При замене t_k на ф_k получим

Z=215- 4(ф₁+2)-5 (ф₂+1) - 2(ф₃+2)- 3(ф₄+4)- 4(ф₅+2)- 1(ф₆+1)- 2(ф₇+4)- 3(ф₈+3)→ min

или

Z=160- 4ф₁-5 ф₂-2ф₃- 3ф₄- 4ф₅- ф₆- 2ф₇- 3ф₈→ min

Z’= 4ф₁+5 ф₂+2ф₃+3ф₄+4ф₅+ ф₆+ 2ф₇+ 3ф₈ → max

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

	-ф₁	-ф₂	-ф₃	-ф₄	-ф₅	-ф₆	-ф₇	-ф₈	b
y₁	1								1
y₂		1							4
y₃			1						7
y₄				1					3
y₅					1				4
y₆						1			3
y₇							1		4
y₈								1	7
y₉	1				1				T-4
y₁₀		1				1			T-2
y₁₁			1					1	T-5
y₁₂		1		1	1				T-7
y₁₃		1					1	1	T-8
y₁₄	1			1			1	1	T-13
y₁₅			1	1	1		1		T-12
y₁₆			1			1	1		T-7
y₁₇	1			1		1			T-7
Z’	-4	-5	-2	-3	-4	-1	-2	-3	0

max

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

	-y₁	-y₂	-y₃	-y₄	-y₅	-y₆	-y₇	-y₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
ф₁	-1								-1					-1			-1	-4
ф₂		-1								-1		-1	-1					-5
ф₃			-1								-1				-1	-1		-2
ф₄				-1								-1		-1	-1		-1	-3
ф₅					-1				-1			-1			-1			-4
ф₆						-1				-1						-1	-1	-1
ф₇							-1						-1	-1	-1	-1		-2
ф₈								-1			-1		-1	-1				-3
Z’_дв	-1	-4	-7	-3	-4	-3	-4	-7	4-T	2-T	5-T	7-T	8-T	13-T	12-T	7-T	7-T	0

min

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

	-y₁	-y₂	-y₃	-y₄	-y₅	-y₆	-y₇	-y₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
ф₁	-1								-1					-1			-1	-4
ф₂		-1								-1		-1	-1					-5
ф₃			-1								-1				-1	-1		-2
ф₄				-1								-1		-1	-1		-1	-3
ф₅					-1				-1			-1			-1			-4
ф₆						-1				-1						-1	-1	-1
ф₇							-1						-1	-1	-1	-1		-2
ф₈								-1			-1		-1	-1				-3
Z_дв	1	4	7	3	4	3	4	7	T-4	T-2	T-5	T-7	T-8	T-13	T-12	T-7	T-7	0

max

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

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

II шаг. Выберем ведущими 2-ю строку и 2-й столбец и произведем пересчет элементов. Получим:

	- ф₁	- ф ₂	-y₃	-y₄	-y₅	-y₆	-y₇	-y₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
y₁	-1								1					1			1	4
y₂		-1								1		1	1					5
ф₃			-1								-1				-1	-1		-2
ф₄				-1								-1		-1	-1		-1	-3
ф₅					-1				-1			-1			-1			-4
ф₆						-1				-1						-1	-1	-1
ф₇							-1						-1	-1	-1	-1		-2
ф₈								-1			-1		-1	-1				-3
Z_дв	1	4	7	3	4	3	4	7	T-5	T-6	T-5	T-11	T-12	T-14	T-12	T-7	T-8	-24

max

III шаг. Выберем ведущими 3-ю строку и 3-й столбец и произведем пересчет элементов.

	- ф₁	- ф₂	- ф₃	-y₄	-y₅	-y₆	-y₇	-y₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
y₁	-1								1					1			1	4
y₂		-1								1		1	1					5
y₃			-1								1				1	1		2
ф₄				-1								-1		-1	-1		-1	-3
ф₅					-1				-1			-1			-1			-4
ф₆						-1				-1						-1	-1	-1
ф₇							-1						-1	-1	-1	-1		-2
ф₈								-1			-1		-1	-1				-3
Z_дв	1	4	7	3	4	3	4	7	T-5	T-6	T-12	T-11	T-12	T-14	T-19	T-14	T-8	-38

max

IV шаг. Выберем ведущими 4-ю строку и 4-й столбец и произведем пересчет элементов.

Получим:

	- ф₁	- ф₂	- ф₃	- ф₄	-y₅	-y₆	-y₇	-y₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
y₁	-1								1					1			1	4
y₂		-1								1		1	1					5
y₃			-1								1				1	1		2
y₄				-1								1		1	1		1	3
ф₅					-1				-1			-1			-1			-4
ф₆						-1				-1						-1	-1	-1
ф₇							-1						-1	-1	-1	-1		-2
ф₈								-1			-1		-1	-1				-3
Z_дв	1	4	7	3	4	3	4	7	T-5	T-6	T-12	T-14	T-12	T-17	T-22	T-14	T-11	-47

Max

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

Получим:

	- ф₁	- ф₂	- ф₃	- ф₄	- ф₅	-y₆	-y₇	-y₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
y₁	-1								1					1			1	4
y₂		-1								1		1	1					5
y₃			-1								1				1	1		2
y₄				-1								1		1	1		1	3
y₅					-1				1			1			1			4
ф₆						-1				-1						-1	-1	-1
ф₇							-1						-1	-1	-1	-1		-2
ф₈								-1			-1		-1	-1				-3
Z_дв	1	4	7	3	4	3	4	7	T-9	T-6	T-12	T-18	T-12	T-17	T-26	T-14	T-11	-63

max

VI шаг. Выберем ведущими 6-ю строку и 6-й столбец и произведем пересчет элементов.

Получим:

	- ф₁	- ф ₂	- ф₃	- ф₄	- ф₅	- ф₆	-y₇	-y₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
y₁	-1								1					1			1	4
y₂		-1								1		1	1					5
y₃			-1								1				1	1		2
y₄				-1								1		1	1		1	3
y₅					-1				1			1			1			4
y₆						-1				1						1	1	1
ф₇							-1						-1	-1	-1	-1		-2
ф₈								-1			-1		-1	-1				-3
Z_дв	1	4	7	3	4	3	4	7	T-9	T-9	T-12	T-18	T-12	T-17	T-26	T-17	T-14	-66

Max

VII шаг. Выберем ведущими 7-ю строку и 7-й столбец и произведем пересчет элементов.

Получим:

	- ф₁	- ф₂	- ф₃	- ф₄	- ф₅	- ф₆	- ф₇	-y₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
y₁	-1								1					1			1	4
y₂		-1								1		1	1					5
y₃			-1								1				1	1		2
y₄				-1								1		1	1		1	3
y₅					-1				1			1			1			4
y₆						-1				1						1	1	1
y₇							-1						1	1	1	1		2
ф₈								-1			-1		-1	-1				-3
Z_дв	1	4	7	3	4	3	4	7	T-9	T-9	T-12	T-18	T-16	T-21	T-30	T-21	T-14	-74

max

VIII шаг. Выберем ведущими 8-ю строку и 8-й столбец и произведем пересчет элементов.

Получим:

	- ф₁	- ф ₂	- ф₃	- ф₄	- ф₅	- ф₆	- ф₇	- ф₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
y₁	-1								1					1			1	4
y₂		-1								1		1	1					5
y₃			-1								1				1	1		2
y₄				-1								1		1	1		1	3
y₅					-1				1			1			1			4
y₆						-1				1						1	1	1
y₇							-1						1	1	1	1		2
y₈								-1			1		1	1				3
Z_дв	1	4	7	3	4	3	4	7	T-9	T-9	T-19	T-18	T-23	T-28	T-30	T-21	T-14	-95

Max

В заключительной строке все элементы положительны, следовательно, достигнут опорный план задачи.

Проверим правильность заполнения. В опорном плане, соответствующем таблице

y₁ = 4, y₂= 5, y₃= 2, y₄= 3, y₅= 4, y₆= 1, y₇= 2, y₈= 3. Остальные переменные равны 0.

Подставляя значения переменных в выражение для Z_дв, получим:

Z_дв= -1 4 - 4 5 - 7 2 - 3 3 - 4 4 - 3 1 - 4 2 - 7 3= -95

Таким образом, изменение целевой функции найдено правильно.

Полученный план оптимален (элементы заключительной строки и элементы заключительного столбца больше 0), при T ≥ 30. В противном случае 15-й элемент заключительной строки будет отрицателен. Но так как предел изменения задан

≤ T ≤ 30

то план оптимален при Т = 30.

При этом значение целевой функции равно -95. Основные переменные имеют следующие значения:

ф₁= 1 ф₂=4 ф₃=7 ф₄=3 ф₅=4 ф₆=3 ф₇=4 ф₈=7

То есть получаем значения ф_k, которые приравниваются к k-м элементам заключительной строки. правомерность этого обуславливается принципом двойственности. Так как полученный план при T = 29 оптимален, значение целевой функции основной задачи совпадает со значение целевой функции двойственной задачи, т.е.

Z’ = Z’_дв = -Z_дв = -95

Значение исходной целевой функции будет равно

Z = A + B + Z_дв =65, где A + B = 160

Правильность произведенных расчетов проверяется тем, что минимальная граница полученного интервала

30 ≤ T ≤ ∞

обязательно совпадет с максимальной границей времени выполнения комплекса работ

T_max = 30

Однако если значение T сократить (присвоить значение менее 30), то 15-й элемент заключительной строчки станет меньше 0. Выберем заданный столбец ведущим, а ведущая строка определится по минимуму из отношений b_i / a_ij, т.е. ведущей получим 3-ю строчку.

Произведем пересечение элементов матрицы. Получим:

- ф₁

- ф ₂

- ф₃

- ф₄

- ф₅

- ф₆

- ф₇

- ф₈

-y₉

-y₁₀

-y₁₁

-y₁₂

-y₁₃

-y₁₄

-y₃

-y₁₆

-y₁₇

y₁

-1

y₂

-1

y₁₅

-1

y₄

-1

y₅

-1

y₆

⇐ Предыдущая 12

Воспользуйтесь поиском по сайту: