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

Теоретическая часть | Математические методы линейного программирования в сетевой системе | Минимизация затрат на выполнение комплекса работ при заданном времени | Минимизация суммарных затрат по комплексу работ и объекту |

Читайте также:

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

Путь	Ранний срок	Поздний срок
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

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

13≤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

y₁=-τ₁+1≥0

y₂= -τ₂+4≥0

y₃= -τ₃+7≥0

y₄= -τ₄+3≥0

y₅= -τ₅+4≥0

y₆= -τ₆+3

y₇= -τ₇+4≥0

y₈= -τ₈+7≥0

y₉= -τ₁- τ₅+T-4>0

y₁₀=- τ₂- τ₆+T-2>0

y₁₁= - τ₃- τ₈+T-5>0

y₁₂= -τ₂- τ₄- τ₅+T-7>0

y₁₃= -τ₂-τ₇- τ₈+T-8>0

y₁₄= -τ₁-τ₄- τ₇- τ₈+T-13>0

y₁₅= -τ₃- τ₇- τ₄- τ₅+T-12>0

y₁₆= -τ₃- τ₇- τ₆-T-7>0

y₁₇= -τ₁- τ₄- τ₆+T-7>0

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

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

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

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_дв									T-4	T-2	T-5	T-7	T-8	T-13	T-12	T-7	T-7

max

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

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

	- τ₁	-y₂	-y₃	-y₄	-y₅	-y₆	-y₇	-y₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
y₁	-1
τ₂		-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_дв									T-5	T-2	T-5	T-7	T-8	T-14	T-12	T-7	T-8	-4

max

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

	- τ₁	- τ ₂	-y₃	-y₄	-y₅	-y₆	-y₇	-y₈	-y₉	-y₁₀	-y₁₁	-y₁₂	-y₁₃	-y₁₄	-y₁₅	-y₁₆	-y₁₇	b
y₁	-1
y₂		-1
τ₃			-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_дв									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
y₂		-1
y₃			-1
τ₄				-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_дв									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
y₂		-1
y₃			-1
y₄				-1
τ₅					-1				-1			-1			-1			-4
τ₆						-1				-1						-1	-1	-1
τ₇							-1						-1	-1	-1	-1		-2
τ₈								-1			-1		-1	-1				-3
Z_дв									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₁₇

y₁

-1

y₂

-1

y₃

-1

y₄

-1

y₅

-1

τ₆

-1

τ₇

-1

-2

τ₈

-1

-3

Z_дв

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₁₇

y₁

-1

y₂

-1

y₃

-1

y₄

-1

y₅

-1

y₆

-1

τ₇

-1

-2

τ₈

-1

-3

Z_дв

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₁₇

y₁

-1

y₂

-1

y₃

-1

y₄

-1

y₅

-1

y₆

-1

y₇

-1

τ₈

-1

-3

Z_дв

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₁₇

y₁

-1

y₂

-1

y₃

-1

y₄

-1

y₅

-1

y₆

-1

y₇

-1

y₈

-1

Z_дв

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-й элемент заключительной строки будет отрицателен. Но так как предел изменения задан

13 ≤ 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₆

-1

y₇

-1

y₈

-1

Z_дв

T-23

T-9

T-18

T-23

T-28

30-T

T-14

-35-2T

max

Полученный план будет оптимален при 28≤Т≤30. Значение целевой функции двойственной задачи в зависимости от значения T будет определяться по формуле:

Z_дв=-35-2T

Z= 160-35-2T = 125-2T

При этом основные и исходные переменные примут следующие значения:

=1, =4, =Т-23, =3, =4, =3, =4, =7;

t₁= 3; t₂=5; t₃= Т-21; t₄= 7; t₅=6; t₆= 4; t₇=8; t₈=10;

Если значение Т будет меньше 28, то 14-й элемент заключительной строчки будет отрицательным. Поэтому выберем 14-й столбец ведущим столбцом и 7-ю строку ведущей строкой и произведем пересчет элементов.

Получим:

Дата добавления: 2015-10-28; просмотров: 43 | Нарушение авторских прав

<== предыдущая страница	\|	следующая страница ==>
Минимизация времени выполнения комплекса работ при заданных затратах	\|	Минимизация времени выполнения комплекса работ при заданных затрат

mybiblioteka.su - 2015-2024 год. (0.037 сек.)