2. Наиболее поздний срок свершения событий

Этот параметр по­казывает такое максимально допустимое время свершения собы­тия, которое не нарушит срок завершения комплекса работ в це­лом, т. е. время свершения завершающего события.

Максимально допустимое время свержения события T^п_i (наи­более поздний срок свершения события i) определяется по пути максимальной продолжительности, последующему за данным со­бытием i: T^п_i = L_кр – max L_i,c , где — L_i,c продолжительность пути, последующего за данным со­бытием i.

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

Расчет наиболее поздних сроков свершения событий начинает­ся с завершающего события (С) и заканчивается исходным собы­тием (I). Для завершающего события (С) предполагается, что T^пc = T^pc.

Для любого другого события i сетевого графика, предшеству­ющего событию j, наиболее поздний срок его свершения T^п_i определяется по формуле T^п_i = min (T^пj – t_i,j ) , где T^пj — наиболее поздний срок свершения события j, последую­щего за событием i.

3. Резерв времени

Резерв времени свершения события — это такой промежуток времени, на который может быть увеличено время свершения это­го события без изменения срока завершения «комплекса работ в целом. Резерв времени свершения события j (Rj) определяется как разность между наиболее поздним сроком свершения этого события (Tⁿj) и наиболее ранним сроком его свершения (T^pj): Rj= Tⁿj- T^pj

№ 27 Задача о назначении. Специфика. Методы решения

В общем случае ЗОН имеет смысл – Необходимо распределить m работ или исполнителей по n станкам или местам работы. i-ая работа, выполняемая на j-ом станке, связана с затратами в размере c_ij

Задача состоит в таком распр.работ по станкам, которое соотв-ет min суммарных затрат выполнения всех работ.

Строки – работа, Столбцы – станки.

Специфика ЗОН – предложение a_i в каждом исходном пункте (для каждого поставщика) = 1 (i=1,m); спрос b_j = 1 (j=1,n)

Для того, чтобы ЗОН была сбалансирована и разрешима, в общ.случае должно m=n.

Переменные в ЗОН носят дискретный хар-р и явл-ся двоичными:

Xij=0, если i-ая работа не выполняется на j-ом станке

Xij=1, если i-ая работа выполняется на j-ом станке

Модель ЗОН:

_{m n}

∑ ∑ c_ij x_ij → min

^{i=1 j=1}

Ограничения: _{m n}

∑ xi_j =1 (j=1,n)-станок на одну работу, ∑ c_ij =1 (i=1,m)-работа на 1 станке; x_ij - двоичное

^{i=1 j=1}

Кажд работа вып-ся только на одном станке, а кажд станок вып-ет только 1 работу!!!

Метод решения ЗОН:

1. Для кажд строки задачи выбирается min элемент pi, после чего исходная матрица преображается путем вычитания из элементов кажд строки найденное значение pi. Новая матрица содержит нулевые эл-ты. Если из нулевых Эл-тов можно построить допустимое решение, то оно и будет явл-ся оптимальным. В противном случае переходим к шагу 2.

2. Для кажд столбца матрицы нах-ся значение min элемента qj. Новая матрица получается путем вычетания из элементов кажд столбца найденных значений qj. Если из нулевых элементов можно построить допустимое решение, то оно и будет явл-ся оптимальным. В противном случае переходим к шагу 3.

3. Дальнейшая процедура состоит в min числа прямых, проходящих через некоторые строки и столбцы с тем, чтобы все нули оказались вычеркнутыми. Затем выб-ся наим невычеркнутый эл-т. Этот эл-т вычитается из каждого невычеркнутого и прибавляется к кажд Эл-ту, стоящему на пересечении проведенных прямых. → получается новая матрица, в кот из нулевых Эл-тов ищется допустимое решение (если оно сущ-ет→оптимальное). В противном случ вновыь возвращаемся к шагу 3.

№ 28 Модель произ-ва с запасами

Специфика МПсЗ состоит в формировании показателя c_ij . Стоимость c_ij формируется след образом:

1. себестоимость, если i=j (производство и ренализация)

2. с/сть + ст-ть хранения, если i‹j

3. с/сть + щтрафы за несвоевременное выполнение заказов, если i›j

Эквивалентность между элементами МПсЗ и ТЗ:

ТЗ	МПсЗ
поставщики Ai-строки потребители Bj-столбцы наличие груза у поставщика ai потребность в грузе каждого потребителя bj транспортные тарифы cij	периоды пр-ва периоды потребления объем пр-ва в i-ом периоде объем реализации в j-ом периоде стоимость пр-ва и хранения за период от i до j.

№29 Процесс сведения игры к задаче линейного программирования

Перед тем, как решить игру необходимо её упростить, избавившись от лишних стратегий (дублированных и заведомо невыгодных)

S*_A = (p₁,…, p_m) – оптимальная стратегия для А

S*_B = (q₁,…, q_n) – оптим страт для B

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

a₁₁ p₁ / ν + a ₂₁ p₂ / ν +…+ a_mi p_m / ν ≥ 1

a₂₁ p₁ / ν + a ₂₂ p₂ / ν +…+ a_m2 p_m / ν ≥ 1

a_1n p₁ / ν + a _2n p₂ / ν +…+ a_mn p_m / ν ≥ 1

Пусть x₁= p₁/ ν , x₂= p₂ / ν (xi= p_i / ν)

_m

∑ x_i = 1/ ν → min

ⁱ⁼¹

После того, как нашли иксы не забывает найти p (p= x ν)!!!

№ 30 Динамическое программирование

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

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

Такие задачи называют многошаговыми.

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

Р. Беллман сформулировал принцип оптимальности:

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

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