О методе решения задач злп в случае целочисленности искомых переменных

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

Суть алгоритма Гомери состоит в следующем: организуется итерационная процедура, на каждом шаге которой отыскивается оптимум с помощью симплекс-метода. Затем ... Если найденное решение не целочисленное, то вводится дополнительное ограничение задачи, которое отсекает найденный оптимум далее цикл повторяется, пока не будет найден целочисленный оптимум.

3.3. Алгоритм динамического программирования

Рассмотрим задачу динамического программирования а затем рассмотрим метод.

Задача формулируется след образом:

Для моментов времени i=1,n найти такие упр-я U=(U₁,U₂,…,U_n), которые переведут объект из состояния в состояние при выполнении ограничений:

Метод динамического программирования включается 3 основных этапа:

3. Определение оптимального управления U_n для последнего шага управления. Это решение соответствует частному значению критерия q завиясящей от управления U_n и предыдущего состояния

На n-ом шаге для отыскания местного оптимума делается перебор всех допустимых значений U_n и соответствующих ему значений Y_n-1. Результат q запоминается.

3. Определяются условно-оптимальные управления U_n-1, U_n-2,...,U_i,...U₁ аналогично этапу один. При этом вычисляются значения критерия Q_n-1, Q_n-2,...,Q_i,...,Q₁ с использованием уравнения следующего уравнения белмана:

Q_i=q_i(U_i,Y_i-1)+Q_i+1

3. Определение оптимального начального состояния Y₀ принадлежащего S₀ (Y₀ ϵ S₀)

3.4 Метод последовательного конструирования, анализа и отсеивания вариантов (так называемый киевский веник).

Является развитием динамического программирования, позволяет решать задачи от начала к концу.

Рассмотрем киевский веник на основе графика работы бригады

Дано:

а) Интервал времени [0,T]

б) Перечень работ j=1,2,…,N

в) , где

τ – длительность j-ой работы

τ_j – количество ресурсов для выполнения работы

f – потери при завершении работы в момент t

г) Интервал [0,T] разбит на подинтервалы

Требуется найти такие , чтобы

при удовлетворении ограничений

Алгоритм метода ПКАОВ (последовательного конструирования анализа и отсеивания вариантов) опирается на след правила доминирования последующих работ (фрагментов графика).

Из двух начальных отрезков графика

длиной n, доминирует над ( , если выполняется условие:

Данное правило представим в виде следующего укрупненного алгоритма:

3.5 Некоторые алгоритмы теории ...

В общем случае в расписании устанавливается:

1. номенклатуру выполняемых работ

2. моменты начала и окончания каждой работы

3. место выполнения

4. Затраты времени

Рассмотрим задачу составления расписаний и N работ

Задача составления расписания для двух станков предполагает, что задано длительность.

Требуется найти расписание, которое минимизирует суммарное время для выполнения всех работ, которые мы обозначим с учетом следующих условий:

1. Очередность выполнения этапов работ — неизменно

2. На каждом станке выполняется одновременно одна работа

3. Работы выполняются без перерыва если они начаты.

4. Второй этап не может опережать первый этап

....

Данную задачу решил Джонсон, поэтому способ ее решения называется алгоритмом Джонсона. Сформулируем правило Джонсона:

При произвольном выборе N работ порядок их выполнения, соответствующий минимум T должен быть таким, что работа n предшествует работе n+1 если

Из этого правила следует следующий простой практический алгоритм

1. Запас

n	1	2	3	…	…	…	N
				…	…	…

2. Найти minτ

3. Если min относится к I степени

4. Если min относится ко II степени

5. Вычеркнуть столбец

6. Перейти к шагу 2-5