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

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

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

ak, bk — коэффициент линейной зависимости затрат от времени;

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

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

Tmin, Tmax — соответственно минимальное и максимальное возможные значения времени выполнения комплекса работ;

Smin, Smax — соответственно минимально и максимально возможные значения затрат на выполнение комплекса работ;

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

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

Nпут — число полных путей;

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

yk — двойственная переменная.

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

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

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

13?T?30.

Директивное время находим по формуле Tд=(Тmin+Тmax)/2.

Tд=(13+30)/2?22.

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

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

t1+ t5? T.

t2+ t6? T.

t3+ t8? T.

t2+ t4+ t5? T.

t2+ t7+ t8? T.

t1+ t4+ t7+ t8? T.

t3+ t7+ t4+ t5? T.

t3+ t7+ t6? T.

t1+ t4+ t6? T.

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

ф1 = t1- 2ф2 = t2 — 1ф3 =t3 — 2 ф4 =t4 — 4ф5 =t5 — 2ф6 =t6 — 1ф7 = t7 — 4ф8 = t8 — 3.

Это приведет к тому, что фk?0.

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

t1 =ф1+2 t2 =ф2+1 t3 =ф3+2 t4 =ф4+4 t5=ф5+2 t6 =ф6+1 t7= ф7+4 t8 = ф8+3.

ф1+2+ ф5+2?T.

ф2+1+ ф6+1?T.

ф3+2+ ф8+3?T.

ф2+1+ ф4+4+ ф5+2?T.

ф2+1 + ф7+4+ ф8+3?T.

ф1+2+ ф4+4+ ф7+4+ ф8+3?T.

ф3+2+ ф7+4+ ф4+4+ ф5+2?T.

ф3+2+ ф7+4+ ф6+1?T.

ф1+2+ ф4+4+ ф6+1?T.

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

ф1+ ф5? T-4.

ф2+ ф6? T-2.

ф3+ ф8? T-5.

ф2+ ф4+ ф5? T-7.

ф2+ф7+ ф8? T-8.

ф1+ф4+ ф7+ ф8? T-13.

ф3+ ф7+ ф4+ ф5? T-12.

ф3+ ф7+ ф6? T-7.

ф1+ ф4+ ф6? T-7.

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

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

Z=215- 4t1−5 t2 — 2t3- 3t4- 4t5- 1t6- 2t7- 3t8> min.

При замене tkна фk получим.

Z=215- 4(ф1+2)-5 (ф2+1) — 2(ф3+2) — 3(ф4+4) — 4(ф5+2) — 1(ф6+1) — 2(ф7+4) — 3(ф8+3)> min.

или.

Z=160- 4ф1−5 ф2−2ф3- 3ф4- 4ф5- ф6- 2ф7- 3ф8> min.

Z'=4ф1+5 ф2+2ф3+3ф4+4ф5+ ф6+ 2ф7+ 3ф8 > max.

y1=-ф1+1?0.

y2= -ф2+4?0.

y3= -ф3+7?0.

y4= -ф4+3?0.

y5= -ф5+4?0.

y6= -ф6+3.

y7= -ф7+4?0.

y8= -ф8+7?0.

y9= -ф1- ф5+T-4>0.

y10=- ф2- ф6+T-2>0.

y11= - ф3- ф8+T-5>0.

y12= -ф2- ф4- ф5+T-7>0.

y13= -ф2-ф7- ф8+T-8>0.

y14= -ф1-ф4- ф7- ф8+T-13>0.

y15= -ф3- ф7- ф4- ф5+T-12>0.

y16= -ф3- ф7- ф6-T-7>0.

y17= -ф1- ф4- ф6+T-7>0.

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

max.

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

min.

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

max.

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

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

y1 = 4, y2 = 5, y3 = 2, y4 = 3, y5 = 4, y6 = 1, y7 = 2, y8 = 3.

Остальные переменные равны 0.

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

Zдв = -14 — 45 — 72 — 33 — 44 — 31 — 42 — 73= -95.

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

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

13? T? 30.

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

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

ф1 = 1ф2 =4 ф3 =7 ф4 =3 ф5 =4 ф6 =3 ф7 =4 ф8 =7.

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

Z' = Z’дв = -Zдв = -95.

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

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

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

30? T? ?

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

Tmax = 30.

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

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

Zдв=-35−2T.

Z= 160−35−2T = 125−2T.

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

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

t1= 3;t2=5;t3= Т-21; t4= 7; t5=6; t6= 4; t7=8; t8=10;

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

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

Zдв=-35−2T.

Z= 160−35−2T = 125−2T.

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

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

t1= 3;t2=5;t3= 7; t4= 7; t5=6; t6= 4; t7= Т-20; t8=10;

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

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

Zдв=-11−3T.

Z= 160−11−3T = 149−3T.

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

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

t1= 3;t2=5;t3= 7; t4= Т-17; t5=6; t6= 4; t7= 4; t8=10;

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

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

Zдв=31−5T.

Z= 160+31−5T = 191−5T.

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

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

t1= 3;t2=5;t3= Т-14; t4= 4; t5=6; t6= 4; t7=4; t8=Т-11;

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

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

Zдв=63−7T.

Z= 160+63−7T = 223−7T.

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

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

t1= 3;t2=5;t3= 2; t4= 4; t5=Т-10; t6= 4; t7=4; t8=Т-11;

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

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

Zдв=77−8T.

Z= 160+77−8T = 237−8T.

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

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

t1= Т-11;t2=5;t3= 2; t4= 4; t5=Т-10; t6= 4; t7=4; t8=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.

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

t1= 3;t2=5;t3= 7; t4= 22−17=5; t5=6; t6= 4; t7= 4; t8=10;

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

Z= 149−3T=83.