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.Рассчетная часть

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

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

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

13?T?30

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

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

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

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

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 ф₂ = 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+ ф₅+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

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

ф₁+ ф₅?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

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

max

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

min

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

max

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

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

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

max

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

max

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

Получим:

Max

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

Получим:

max

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

Получим:

Max

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

Получим:

max

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

Получим:

Max

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

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

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

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

Z_дв = -14 - 45 - 72 - 33 - 44 - 31 - 42 - 73= -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-ю строчку.

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

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-ю строку ведущей строкой и произведем пересчет элементов.

Получим:

max

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

Z_дв=-35-2T

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

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

=1, =4, =5, =3, =4, =3, =Т-24, =7;

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

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

max

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

Z_дв=-11-3T

Z= 160-11-3T = 149-3T

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

=1, =4, =5, =Т-21, =4, =3, =0, =7;

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

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

max

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

Z_дв=31-5T

Z= 160+31-5T = 191-5T

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

=1, =4, =Т-16, =0, =4, =3, =0, =Т-14;

t₁= 3; t₂=5; t₃= Т-14; t₄= 4; t₅=6; t₆= 4; t₇=4; t₈=Т-11;

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

Получим:

max

max

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

Z_дв=63-7T

Z= 160+63-7T = 223-7T

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

=1, =4, =0, =0, =Т-12, =3, =0, =Т-14;

t₁= 3; t₂=5; t₃= 2; t₄= 4; t₅=Т-10; t₆= 4; t₇=4; t₈=Т-11;

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

Получим:

max

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

Z_дв=77-8T

Z= 160+77-8T = 237-8T

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

=Т-13, =4, =0, =0, =Т-12, =3, =0, =0;

t₁= Т-11; t₂=5; t₃= 2; t₄= 4; t₅=Т-10; t₆= 4; t₇=4; t₈=3;

Таким образом, весь интервал изменения 13?Т?30 разбивается на 6 составляющих частных интервала

1) 28?Т?30;

2) 24?Т?28;

3) 21?Т?24;

4) 16?Т?21;

5) 14?Т?16;

6) 13?Т?14;

В условии задачи дано: Т=22. Это значит, что будем рассматривать третий интервал

21?Т?24

Оптимальное значение неизвестных равно

t₁= 3; t₂=5; t₃= 7; t₄= 22-17=5; t₅=6; t₆= 4; t₇= 4; t₈=10;

Значение минимальных затрат будет рассчитываться по формуле:

Z= 149-3T=83

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

Дополнительно дано: директивные затраты равны 39 т.е.

.

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

28?Т?30;

24?Т?28;

21?Т?24;

16?Т?21;

14?Т?16;

13?Т?14;

Для первого частного интервала формула расчета затрат:

Z= 125-2T

Граница первого частного интервала: 28?Т?30

Таким образом, Z ¹ _min =65, Z ¹ _max =69

По аналогии, для второго частного интервала 24 ?Т ?28, целевая функция Z=125-2T , а граничные значения затрат Z ² _min =69, Z ² _max =77

По аналогии, для третьего частного интервала 21?Т?24, целевая функция

Z=149-3T,

а граничные значения затрат Z ³ _min =77

Z ³ _max =86

По аналогии, для четвертого частного интервала 16 ?Т ?21, целевая функция Z=191-5T, а граничные значения затрат Z ⁴ _min =86

Z ⁴ _max =111

По аналогии, для пятого частного интервала 14 T16, целевая функция Z=223-7T , а граничные значения затрат Z ⁵ _min =111

Z ⁵ _max =125

По аналогии, для шестого частного интервала 13 ?Т ?14, целевая функция Z=237-8T , а граничные значения затрат Z ⁶ _min =125

Z ⁶ _max =133

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

1) 65 Z 69

2) 69 Z 77

3) 77 Z 86

4) 86 Z 111

5) 111 Z 125

6) 125 Z 133

Таким образом, заданные в примере директивные затраты не попадают ни в один интервал.

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

Дополнительно введем вид затрат по объекту от времени:

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

28?Т?30, =125-2T +2,5Т=125+0,5Т

24?Т?28, =125-2T +2,5Т=125+0,5Т

21?Т?24, =149-3T+2,5Т=149-0,5Т

16?Т?21, =191-5T+2,5Т=191-2,5Т

14?Т?16, =223-7T+2,5Т=223-4,5Т

13?Т?14, =237-8T +2,5Т=237-5,5Т

Анализ общего вида позволит найти точку минимума.

При изменении 13 T 24 целевая функция убывает, т.к. коэффициент при Т отрицателен. При изменении 24 T 30 целевая функция Z возрастает, т.к. коэффициент при T положителен. В связи с чем в точке Т = 24 целевая функция примет минимальное значение, равное

Z^?_min= 149-0,5х24=137

Значение неизвестных составит:

t₁=13; t₂=5; t₃= 2; t₄= 4; t₅=14; t₆= 4; t₇=4; t₈=3;

3.Графическая часть

1) при минимизации затрат на выполнение комплекса работ при заданном времени, оптимальное значение неизвестных равно:

t₁= 3; t₂=5; t₃= 7; t₄= 22-17=5; t₅=6; t₆= 4; t₇= 4; t₈=10

2) при минимизации суммарных затрат по комплексу работ и объекту, оптимальное значение неизвестных равно:

t₁=13; t₂=5; t₃= 2; t₄= 4; t₅=14; t₆= 4; t₇=4; t₈=3

Список используемой литературы

1. Математические методы и модели в управлении на морском транспорте: учебное пособие. Т.Е. Маликова

2. Математическое моделирование производственных систем: методические указания. Т.Е. Маликова

Размещено на Allbest.ru