Метод фогеля

Вместо максимума задача сводится к поиску минимума

На каждом шаге метода Фогеля для каждой i-й строки вычисляются тарифы как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются тариф для каждого j-го столбца. После чего выбирается минимальный тариф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному тарифу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом .

Если существует несколько одинаковых по величине максимальных штрафов в матрице, то в соответствующих строках или столбцах выбирается одна не вычеркнутая клетка с минимальным тарифом .

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

// не уверен что правильно

Метод ближайшего соседа

i\j	1	2	3	4	5
1	∞	35	45	20	11
2	9	∞	17	6	8
3	21	31	∞	2	11
4	30	15	40	∞	10
5	10	9	8	7	∞

Находится путь минимальной длины предполагая что ком может выехать из любого города

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

Берем дальше если минимальный попадает на город который уже был то надо брать другой

1 -> 5 (11) -> 4(7)

Z=11+7+15+17+21=71

Дальше делаем тоже самое с каждым городом ( выходим из города 2 3 4 и т д )

Потом результаты сравниваем. Усё.

Задача нелинейного программирования

Z( =Z(x₁ …x_n) (1)

Φ_i( =(≤,=,≥)b_i (i=1 …n)

Общая задача формулируется так

Если z(x) и φ(х) нелинейные (выпуклые вогнутые, больше чем первой степени)

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

Вопрос 18.

Сетевое планирование и управления (СПУ). Сетевой график и его свойства. Основные понятия СПУ: критический путь, ранние и поздние сроки совершения событий; резерв времени события; полный резерв времени работы; свободный резерв времени работы. Линейный график комплекса работ. Решение задачи оптимизации графика выполнения работ при ограниченных ресурсах.

Всякий намеченный комплекс работ, необходимых для достижения некоторой цели, называют проектом. Проект (или комплекс работ) подразделяется на отдельные работы. Каждая отдельная работа, входящая в комплекс (проект), требует затрат времени. Некоторые работы могут выполняться только в определенном порядке. При выполнении комплекса работ всегда можно выделить ряд событий, то есть итогов какой-то деятельности, позволяющих приступить к выполнению следующих работ. Если каждому событию поставить в соответствие вершину графа, а каждой работе — ориентированное ребро, то получится некоторый граф. Он будет отражать последовательность выполнения отдельных работ и наступление событий в едином комплексе. Если над ребрами проставить время, необходимое для завершения соответствующей работы, то получится сеть. Изображение такой сети называют сетевым графиком. Сетевой график состоит из двух типов основных элементов: работ и событий. Работа представляет собой выполнение некоторого мероприятия (например, погрузка боезапаса или переход корабля в пункт базирования). Этот элемент сетевого графика связан с затратой времен и расходом ресурсов. Поэтому работа всегда имеет начало и конец. Кроме того, каждая работа должна иметь определение, раскрывающее ее содержание (например, уяснение боевой задачи, приготовление корабля к походу и т.д.).

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

Начальная и конечная точки работы, то есть начало и окончание некоторого мероприятия (например, окончание приготовления корабля к бою), называются событиями. Следовательно, событие, в отличие от работы, не является процессом и не сопровождается никакими затратами времени или ресурсов.

Событие, следующее непосредственно за данной работой, называется последующим событием по отношению к рассматриваемой работе. Событие, непосредственно предшествующее рассматриваемой работе, называется предшествующим.

Наименования "предшествующий" и "последующий" относятся также и к работам. Каждая входящая в данное событие работа считается предшествующей каждой выходящей работе, и наоборот, каждая выходящая работасчитается последующей для каждой входящей.

Из определения отношения "предшествующий—последующий" вытекают свойства сетевого графика.

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

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

Путь – это любая последовательность работ в сетевом графике, в которой конечное событие одной работы совпадает с начальным событием следующей за ней работы.

Критический путь – максимальный по продолжительности полный путь.

К временным параметрам событий относятся:

− ранний срок наступления события i – T i( ) р;

− поздний срок наступления события i – T i п ( );

− резерв времени наступления события i – R i . ( )

T i р ( ) – это время, необходимое для выполнения всех работ, предшествующих данному событию i.

T i п ( ) – это такое время наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети.

R i – ( ) это такой промежуток времен, на который может быть отсрочено наступление этого события без нарушения сроков завершения разработки в целом

Разность между продолжительность критического пути T_кр и продолжительностью любого другого пути TL называется полным резервом времени пути L, т.е. R_L = T_ђр−T_L. Этот резерв показывает, на сколько в сумме может быть увеличена продолжительность всех работ данного пути L, чтобы при этом не изменился общий срок окончания всех работ, т.е. T_кр.

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

Линейный график строится либо по сетевому графику, либо по матрице.

Суть: Пусть комплекс работ предоставлен следующем сетевом графиком:

5

3

8 (30)

2 (60)

5 (40)

1

4 (30)

7 (20)

2

4

3 (50)

4 (70)

Кажд. раб. (i, j) на ЛГ из-ся в привязке к оси времени соотв. прямыми, отрезками, длина которых в выбранном масштабе равна продолжительности tij – раб.

Поэтому время у отрезков не прост-ся, но ук-ся интенсивность потр-я рес-в.

Работы из-ся в той же последовательности, что и на сетевом графике.

5

5

3, 5

4, 3

2

1

40

5

5

60

40

4

5

30

3

20

30

50

2

14

10

8

7

3

1

На различных участках разная интенсивность. Чтобы –rij <=100 придётся двигать работы. Сумма всех rij <=100.

Какие работы можем двигать в пределах резервов?

1. Найти полные резервы работ.

I Этап: 0-3

Rij=r12=r13=50+30+80<=100 +

II Этап: 3-7

R3-7=r13+r23+r24+r25=170>=100 -

Какие работы будем сдвигать:

Расставим приоритеты работ(по резерву):

Правило: Первый приоритет получают работы, которые уже начаты.

r13=1; r24=2 (т.к. лежит на критическом пути)

Далее по минимальному резерву

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

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

Rn(2,3)=5; Rn(2,5)=6; Rn(2,4)=0;