авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 4 | 5 ||

«ЗАДАЧИ И МЕТОДЫ КОНЕЧНОМЕРНОЙ ОПТИМИЗАЦИИ Часть 3 Д. И. Коган Динамическое программирование и дискретная много- критериальная ...»

-- [ Страница 6 ] --

Из теоремы 4.4 следует, что для любого консервативного оператора U совокупность оценок U(E ) = ЕU(x0) может быть по строена применением рекуррентных соотношений динамиче ского программирования (4.69)–(4.70).

Алгоритм, который по соотношениям (4.69)–(4.70) последо вательно определяет множества оценок ЕU(x), х D, назовем алгоритмом A(U ). Отличие A(U ) от основанного на соотноше ниях (4.31)–(4.32) алгоритма синтеза полной совокупности эф фективных оценок E заключается в следующем: на каждом эта пе применения получаемое множество оценок, условно обоз начим его M, заменяется подмножеством U(M );

подмножество U(M ) на последующих этапах работы алгоритма используется как заменитель множества M. Итогом работы алгоритма A(U ) является множество ЕU(x0). В случае, если оператор U консерва тивен, это множество совпадает с искомой совокупностью U(E ).

Если процедура выделения из M подмножества U(M ) требует выполнения относительно небольшого числа элементарных операций, то при переходе от алгоритма синтеза полной сово купности эффективных оценок к алгоритму A(U ) число выпол няемых арифметических операций уменьшается пропорцио нально отношению среднего числа оценок в множествах Е(x) к среднему числу оценок в множествах ЕU (x).

Приведем несколько примеров консервативных и неконсер вативных операторов. Пусть M – непустое множество оценок.

~ Оператор U осуществляет выбор из M подмножества крайних в ~ M оценок. Легко проверяется, что для оператора U условия (4.71)–(4.72) выполняются. Следовательно, этот оператор кон ~ сервативен и алгоритм A(U ) является способом построения полной совокупности крайних в решаемой задаче оценок.

Оператор U осуществляет выбор из M непустого подмноже ства оценок, которые крайними не являются;

в особом случае, когда все оценки множества M крайние, полагаем U'(М ) = М.

Оператор U' неконсервативен. Покажем это на следующем при мере.

Введем в рассмотрение систему а, описываемую графом Gа с состояниями S, A*, B*, A1, A2, A3, B1, B2, B3, F. Состояние S – начальное, состояние F – финальное. В графе имеются следую щие дуги: (S, A*), (S, В*), (A*, A1), (A*, A2), (A*, A3), (В*, В1), (В*, В2), (В*, В3), ), (A1, F ), (A2, F ), (A3, F ), (В1, F ), (В2, F ), (В3, F ).

Векторные веса дуг (A1, F ), (A2, F ), (A3, F ), (В1, F ), (В2, F ), (В3, F ) равны соответственно (1, 100), (10,10), (100, 1), (90, 11), (7, 13), (2, 90);

каждая из остальных дуг имеет вес (0, 0). При меняя алгоритм А(U' ), получаем последовательно: ЕU' (F) = {(0, 0)};

ЕU' (A1) = {(1, 100)};

ЕU' (A2) = {(10, 10)};

ЕU(A3) = {(100, 1)};

ЕU(В1) = {(90, 11)};

ЕU' (В2) = {(7, 13)};

ЕU' (В3) = {(2, 90)};

ЕU' (A*) = = U'({(1, 100), (10, 10), (100, 1)}) = {(10, 10)};

ЕU' (В*) = U'({(90, 11), (7, 13), (2, 90)}) = {(7, 13)}. Для начального состояния S имеем: ЕU' (S) = {(10, 10), (7, 13)}. В то же время, легко опреде ляется, что Е = Е(S) = eff {(1, 100), (10, 10), (100, 1), (90, 11), (7, 13), (2,90)} = {(1, 100), (2,90), (7, 13), (90, 11), (100, 1)}. От сюда U'(E ) = {(2,90), (7, 13), (90, 11)}. Таким образом, в рас смотренном примере ЕU' (S) не совпадает с U'(E(S )), оператор U' неконсервативен. Отметим также, что в построенном примене нием алгоритма А(U') множестве ЕU' (S ) содержится оценка (10, 10), которая в задаче Z эффективной не является.

Оценку R = (r1, r2, …, rl) из M назовем s-оценкой (от supported solution, см. [27]), если она является оптимальным решением задачи l i yi max ( y, y,..., y )M 1 2 l i = при некотором наборе положительных коэффициентов 1, 2, …, l. Отметим, что для произвольной задачи многокритериальной оптимизации Z множество s-оценок из E(Z) – это совокупность оценок всех решений, оптимальных в однокритериальных зада чах, получаемых из Z линейной сверткой критериев. Весовые коэффициенты свертки 1, 2, …, l – произвольные положи тельные числа. Можно дополнительно предположить, что сумма коэффициентов свертки равна единице. В таком случае при рас смотрении бикритериальных задач считается, что первый коэф фициент свертки равен, а второй (1 – ), где принадлежит интервалу (0, 1).

Через US обозначим оператор выбора подмножества s-оце нок. Известно, что U S ( M ) = eff (conv eff ( M )) eff ( M ), (4.73) где conv eff ( M ) – выпуклая оболочка множества eff (M ).

Л е м м а 4. 3. Для любых множеств оценок М1, М2, …, Мn и меет место равенство US (М1 М2 … Мn) = US (US (М1) US (М2) … US (Мn)).

Покажем сначала справедливость включения US (М1 М … Мn) US (US (М1) US (М2) … US (Мn)). Действи тельно, пусть принадлежащая некоторому множеству Mj, j {1, 2, …, n}, оценка m входит в US (М1 М2 … Мn), выделяю щий ее в совокупности М1 М2 … Мn вектор весовых ко эффициентов обозначим. В таком случае тот же вектор вы деляет оценку m сначала в совокупности Mj;

затем в совокуп ности US (US (М1) US (М2) … US (Мn)).

Выполнение обратного включения докажем методом от про тивного. Пусть входящая в множество US (US (М1) US (М2) … US (Мn)) оценка m совокупности US (М1 М2 … Мn) не принадлежит. Так как m US (US (М1) US (М2) … US (Мn)), то имеется вектор * такой, что для любой оценки t из US (М1) US (М2) … US (Мn) выполняется неравенство:

(*, m) (*, t ). (4.74) Вместе с тем, так как оценка m совокупности US (М1 М … Мn) не принадлежит, для вектора * в некотором множе стве Mj, j {1, 2, …, n}, найдется оценка r такая, что:

(*, r ) (*, m). (4.75) В совокупности US (Мj), согласно ее определению, обяза тельно имеется оценка t такая, что:

(*, t ) (*, r ). (4.76) Из (4.75) и (4.76) имеем:

(*, t ) (*, m). (4.77) Но так как t принадлежит совокупности US (М1) US (М2) … US (Мn), на основании (4.74) получаем:

(*, m) (*, t ), что противоречит (4.73).

Лемма доказана.

Л е м м а 4. 4. Для любого множества l-мерных векторов оценок М и произвольного вектора d той же размерности имеет место равенство US (d М ) = d US (М ).

Действительно, оценка d + m принадлежит совокупности US (d + m) тогда и только тогда, когда существует вектор * та кой, что для любой оценки t из d M выполняется неравенство (*, d + m) (*, t). Но это эквивалентно выполнению для лю бой оценки x из M неравенства (*, m) (*, x). Последнее же означает, что оценка m принадлежит множеству US (M ), т.е.

вектор d + m входит в совокупность d US (M ).

Лемма доказана.

Т е о р е м а 4. 5. Оператор US консервативен.

Сформулированная теорема является прямым следствием лемм 4.3 и 4.4.

Сейчас введем оператор U*, который из совокупности оце нок М выделяет непустое подмножество оценок, не являющихся s-оценками;

в случае, когда US (М ) = М считаем, что U*(М ) так же совпадает с М. Покажем, что оператор U* консервативным не является.

Рассмотрим введенную выше систему а,. Применяя алго ритм А(U*), получаем последовательно: ЕU*(F ) = {(0, 0)};

ЕU*(A1) = {(1, 100)};

ЕU*(A2) = {(10, 10)};

ЕU*(A3) = {(100, 1)};

ЕU*(В1) = {(90, 11)};

ЕU*(В2) = {(7, 13)};

ЕU*(В3) = {(2, 90)};

ЕU*(A*) = U'({(1, 100), (10,10), (100, 1)}) = {(10, 10)};

ЕU*(В*) = = U' ({(90, 11), (7, 13), (2, 90)}) = {(7, 13)}. Для начального со стояния S имеем: ЕU*(S ) = {(10, 10), (7, 13)}.

В то же время Е = Е(S ) = {(1, 100), (2,90), (7, 13), (90, 11), (100, 1)}. Далее получаем U*(E ) = {(2, 90), (7, 13)}. Таким обра зом, в рассмотренном примере ЕU*(S ) не совпадает с U*(Е ), опе ратор U* неконсервативен.

Оценку R = (r1, r2, …, rl) из M назовем S 2-оценкой, если она является оптимальным решением задачи l i yi2 (4.78) max ( y, y,..., y )M 1 2 l i = при некотором наборе положительных коэффициентов 1, 2, …, m.

Через U S обозначим оператор выбора подмножества S 2-оце нок.

Т е о р е м а 4. 6. Оператор U S неконсервативен.

Покажем, что для оператора U S не выполняется второе ус ловие консервативности.

Пусть М = {(9, 1),(6, 6), (1, 9)} и d = (11, 11). В таком случае US (М ) = {(9, 1), (1, 9)}. Действительно, оценка (6, 6) в мно жество U S (М ) не входит, ибо неравенства 36 + 36(1 – ) 81 + (1 – ) и 36 + 36(1 – ) + 81(1 – ) ни при каком значении параметра одновременно не вы полняются (как легко подсчитывается, первое изнеравенство имеет место при 7/16, а второе неравенство – при 9/16). В то же время неравенство 81 + (1 – ) + 81(1 – ) имеет место при 0,5;

неравенство + 81(1 – ) 81 + (1 – ) верно при 0,5.

Получаем, что d U S (М ) = {(20, 12), (12, 20)}.

Далее имеем: d М = {(20, 12), (17, 17) (12, 20)} и U S (d М ) ={(20,12), (17, 17) (12,20)}. Действительно, оценка (20, 12) в множество U S (d М ) входит, ибо неравенства 400 + 144 (1 – ) 289 + 289(1 – ) и 400 + 144(1 – ) 144 + 400(1 – ) имеют место, например, при = 0,9. Оценка (17, 17) в мно жество U S (d М ) входит, ибо неравенства 289 + 289(1 – ) 400 + 144(1 – ) и 289 + 289(1 – ) 144 + 400(1 – ) имеют место, например, при = 0,5. Оценка (12, 20) в мно жество U S (d М) входит, ибо неравенства 144 + 400(1 – ) 400 + 144(1 – ) и 144 + 400(1 – ) 289 + 289(1 – ) имеют место, например, при = 0,1.

Таким образом, множества U S (d М ) и d U S (М ) не сов 2 падают, оператор U S консервативным не является. Теорема до казана.

Если используемый оператор выбора U консервативен, то для каждой конкретной, моделируемой системой + бикритери альной задачи Z синтез совокупности оценок, выделяемых опе ратором U из полной совокупности E(Z ) можно осуществлять использованием рекуррентных соотношений (4.69)–(4.70), адап тированных для задачи Z.

В качестве иллюстрации рассмотрим вопрос построения полной совокупности s-оценок для бикритериальной задачи о ранце.

5 x1 + 3 x2 + 4 x3 + 6 x4 + 2 x5 + x6 max, (4.79) x1 + 2 x2 + 3 x3 + x4 + 5 x5 + 2 x6 max, (4.80) 3 x1 + 4 x2 + 3 x3 + 2 x4 + 3x5 + x6 10, (4.81) x j {0;

1}, j = 1, 6. (4.82) Определяя для этой задачи полную совокупность эффектив ных оценок основанным на на ранее записанных соотношениях (0,0,...,0), если i : 0 pi ai1 ;

E (1, p) = (4.46) (c11, c21,..., cm1 ) при ai1 pi для всех i = 1, d, E (k, p ), если i : 0 pi aik +1 ;

E (k + 1, p) = eff ( E (k, p) {C k +1 E (k, p a k +1 )}) (4.47) при aik +1 pi для всех i = 1, d, мк алгоритмом Aранец, заполняем табл. 4.3.

При синтезе для задачи (4.75)–(4.78) полной совокупности s-оценок используем соотношения (0, 0,..., 0), если i : 0 pi ai1 ;

EU S (1, p) = (4.83) (c11, c21,..., cm1 ) при ai1 pi для всех i = 1, d, EU (k, p), если i : 0 pi aik +1 ;

S EU S (k + 1, p) = U S ( EU S (k, p) {C k +1 EU S (k, p a k +1 ) (4.84) при aik +1 pi для всех i = 1, d.

В процессе вычислений заполняем табл. 4.4. Отличие про цедуры счета по соотношениям (4.83)–(4.84) от процесса счета по соотношениям (4.46)–(4.47) в том, что при заполнении каж дой очередной клетки таблицы получаемое множество оценок, условно обозначим его M, заменяется подмножеством US (M );

подмножество US (M ) на последующих этапах работы алгоритма используется как заменитель множества M. Итогом работы примененной к исходным данным задачи (4.79)–(4.82) и основанной на соотношениях (4.83)–(4.84) процедуры является множество EU S (6, 10).

Так как оператор U S консервативен, найденное множество EU S (6, 10) = {(16, 7), (13, 11)} – полная совокупность s-оценок в рассматриваемой задаче.

Выполним соответствующую проверку. Как показывает за полнение табл. 4.3, полная совокупность эффективных в (4.75)– (4.78) оценок трехэлементна: (16, 7), (14, 9) и (13, 11). Оценки (16, 7) и (13, 11) являются s-оценками, ибо в задаче (4.75)–(4.78) они – крайние оценки. Оценка (14, 9) s-оценкой не является, так как неравенства 14 + 9(1 – ) 16 + 7(1 – ), 14 + 9(1 – ) 13 + не выполняются одновременно ни при каком значении.

Множество US ({(16, 7), (14, 9), (13, 11)}) действительно совпа дает с EU S (6, 10).

Таблица 4. Таблица эффективных оценок для задачи (4.48)–(4.52) 0 1 2 3 4 5 6 7 8 9 ( ( ( ( ( (5, (5 (5 (5, (5, (5, 0,0) 0,0) 0,0) 5,1) 5,1) 1),1),1) 1) 1) 1) ( (5, ( ( 5,1) 1),1) ( ( ( (8 (8, (8, (8, 0,0) 0,0) 0,0) 5,1) ( (3, (3,3) 3) 3) 3) 3,2) 2),2) ( ( (5, (9 (9, (9, ( ( ( 5,1) 5,1) 1) (9,4) 4) 4) ( 0,0) 0,0) 0,0) ( ( (4,,4) (7 (7, (7, 2,6) 4,3) 4,3) 3),5) 5) 5) ( ( ( (1 (1 (1 ( 1,2) ( ( ( 6,1) 6,1) 1,2) 1,2) (1 5,5) 5,5) ( 0,0) 0,0) 6,1) ( ( (1 (1 0,4) 5,5) (1 ( 4,3) 4,3) 0,4) 0,4) 3,6) 3,6) (,5) (1 (1 ( (1 1,2) 1,2) (1 5,5) ( ( ( 6,1) 6,1) 1,2) (1 (1 5,5) 5,5) ( ( ( ( ( ( (1 0,4) 0,4) (1 (1 3,7) 0,0) 0,0) 6,1) 2,5) 2,5) 0,4) (8 (8 ( 3,7) 3,7) ( ( (8,,6),6) (1 (1 2,9) 4,3) 4,3) 6) (6 (6 2,9) 2,9) (9,,8),8) 10) (1 (1 (7, ( ( 1,2) (1 2,4) 10) (1 ( ( (1 2,4) (1 (1 6,7) 6,7) 6,1) 7,3) ( ( 6,1) ( ( 0,4) (1 1,6) 5,5) (1 ( ( 0,0) 1,2) 2,5) 3,7) (8, 1,6) (9 (1 4,9) 4,9) 1,2) ( 6) (9,8) 3,7) ( (1 ( 4,3) 5,5) (3,,8) (7 (1 3,11) 3,11) 7),10) 2,9) Таблица 4. Таблица s-оценок для задачи (4.48)–(4.52) 0 1 2 3 4 5 6 7 8 9 ( ( ( ( (5 (5 (5 (5 (5 (5, (5, 0,0) 0,0) 0,0) 5,1),1),1),1),1),1) 1) 1) (5 (5 ( ( ( ( (,1),1),1) (8 (8 (8, (8, 0,0) 0,0) 0,0) 5,1) (3 (3 (3,3),3) 3) 3),2),2),2) ( (5 (5 (9 (9 (9, ( ( ( 5,1),1),1) (9,4),4) 4) ( 0,0) 0,0) 0,0) ( (4 (4,4) (7 (7 (7, 2,6) 4,3),3),3),5),5) 5) ( ( (6 (1 (1 1,2) (1 ( ( ( ( 6,1),1) 1,2) 1,2) (1 5,5) 5,5) ( 0,0) 0,0) 6,1) ( (4 (1 (1 0,4) 5,5) (1 ( 4,3),3) 0,4) 0,4) 3,6) 3,6) (,5) ( (6 (1 (1 (1 ( 6,1),1) 1,2) 1,2) 1,2) (1 (1 5,5) (1 5,5) 5,5) ( ( ( ( (2 (1 (1 ( 0,0) 0,0) 6,1) 2,5),5) 0,4) 0,4) 0,4) (1 (1 2,9) (6 2,9) 2,9) ( (4 (8 (6 (9, 4,3),3),6),8),8) 10) ( (7 1,2) ( (1 (1 ( ( 6,1),3) (1 2,4) 2,4),10) (1 ( ( 6,1) (1 6,7) 6,7) ( ( (3 0,4) (1 ( 0,0) 1,2) ( 2,5),7) (8 1,6) 1,6) 5,5) (1 ( 1,2) ( (5,6) (9 (7 (1 3,11) 3,11) 4,3),5) (3,8),10) 2,9),7) Задачи к главе 1. Методом последовательных уступок построить полную совокупность эффективных оценок для задачи о назначениях с двумя неоднотипными максимизируемыми критериями n К1(А, ) = ai(i ) и К2(В, ) = min bi(i).

i i = Для каждой эффективной оценки указать порождающее ее Па рето-оптимальное решение. Исходная информация по задаче считается определенной парой матриц 9 7 7 4 3 0 6 5 1 1 9 8 2 1 1 0 7 9 A = 3 4 7 4 9 и B = 9 2 1 1 7.

3 1 3 8 5 0 9 1 9 8 2 2 6 8 3 6 8 7 2. Предыдущую задачу решить с использованием рекур рентных соотношений бикритериального динамического про граммирования.

3. Используя метод последовательных уступок, найти две крайние оценки и по одной эффективной оценке, соседней с ка ждой крайней оценкой, для задачи о назначениях с максимизи n n ai(i ) и Q2() = bi(i ).

руемыми критериями Q1() = Исход i =1 i = ная информация по задаче считается определенной парой мат риц 9 8 7 4 3 0 5 5 1 1 9 8 2 1 1 0 7 9 A = 3 4 7 4 9 и B = 9 2 8 1 7.

3 1 3 8 5 0 9 1 1 8 2 2 6 8 6 6 8 7 4. Предыдущую задачу решить с использованием рекур рентных соотношений бикритериального динамического про граммирования.

мк 5. Алгоритмом Aранец построить полную совокупность эф фективных оценок для трехкритериальной задачи о ранце 7х1 + 3х2 +6х3 + 9х4 + х5 + 4х6 max, 4х1 + 4х2 + 4х3 + 2х4 + 4х5 + 6х6 max, х1 + 5х2 + х3 + 5х4 + 5х5 + 3х6 max при условиях 2х1 + х2 + 2х3 + 4х4 +3х5 + 2х6 10;

хi {0, 1}, i= 1, 5.

Для каждой эффективной оценки указать порождающее ее Парето-оптимальное решение.

6. Предыдущую задачу решить методом последовательной генерации списков.

7. Задача однопроцессорного обслуживания множества зая вок определяется следующими исходными данными: обслужи ванию подлежат заявки 1, 2, 3, 4, 5;

продолжительности обслу живания заявок: (1) = 3, (2) = 2, (3) = 4, (4) = 1, (5) = 2;

функ ции индивидуального штрафа по заявкам: 1(t) = 4t2, 2(t) = 3t, 3 (t) = t2 + t, 4 (t) = t2 + 2t, 5 (t) = t3 + 1. Рассматриваются два минимизируемых критерия – суммарный штраф по всем заявкам и максимальный из индивидуальных штрафов. Требуется по строить полную совокупность эффективных оценок. Для двух крайних оценок указать порождающие их Парето-оптимальные решения.

8. Пусть M – множество оценок в произвольной бикритери альной задаче. Является ли консервативным оператор U,q ( M ), который для каждой оценки (х, у) из М вычисляет характеристи ку х + (1 – )у, упорядочивает множество оценок M по убыва нию указанной характеристики и далее выбирает из M оценки, стоящие на q первых местах (здесь – произвольная константа из интервала (0, 1), q – произвольная натуральная константа).

9. Для задачи о ранце 7х1 +2х2 + 6х3 + 9х4 + х5 + 4х6 max, х1 + 5х2 + х3 + 5х4 + 5х5 + 7х6 max при условиях 2х1 + х2 + 2х3 + 4х4 + 3х5 + 2х6 10;

хi {0, 1}, i= 1, 5 ;

построить полную совокупность s-оценок.

10. Для бикритериальной задачи о назначениях с критерия n n ми Q1() = ai (i ) и Q2() = bi(i ) построить полную совокуп i =1 i = ность s-оценок. Исходная информация по задаче считается оп ределенной парой матриц 9 8 7 4 3 0 5 5 1 1 9 8 2 1 1 0 7 9 A = 3 4 7 4 9 и B = 9 2 8 1 7.

3 1 3 8 5 0 9 1 1 8 2 2 6 8 6 6 8 7 ЛИТЕРАТУРА 1. А л е к с е е в, О. Г. Комплексное применение методов дискрет ной оптимизации / О.Г. Алексеев. – М.: Наука, 1987. – 247 с.

2. Б а т и щ е в, Д. И. Вопросы синтеза совокупностей эффективных оценок в многокритериальной задаче о ранце / Д. И. Батищев, Д. И. Коган, М. В. Лейкин // Математическое моделирование и оп тимальное управление: Вестник Нижегородского университета. – Н. Новгород, 2002, вып. 1 (25), с. 211–223.

3. Б е л л м а н, Р. Динамическое программирование / Р. Беллман. – М.: ИЛ, 1960. – 400 с.

4. Б е л л м а н, Р. Прикладные задачи динамического программиро вания / Р. Беллман, С. Дрейфус. – М.: Наука, 1965. – 457 с.

5. Г а б а с о в, Р. Основы динамического программирования / Р. Га басов, Ф. М. Кириллова. – Минск: Изд-во БелГУ, 1975. – 262 с.

6. Г е й л, Д. Теория линейных экономических моделей / Д. Гейл. – М.: ИЛ, 1963. – 418 с.

7. Г э р и, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.

8. Д а н ц и г, Д. Линейное программирование, его обобщения и при менения / Д. Данциг. – М.: Прогресс, 1966. – 600 с.

9. К л и н и, С. Математическая логика / С. Клини. – М.: Мир, 1973.

– 480 с.

10. К о г а н, Д. И. Дискретные многокритериальные задачи распределительного типа / Д. И. Коган. – Н. Новгород: Изд-во ННГУ, 1991. – 82 с.

11. К о г а н, Д. И. Двухкритериальные задачи о назначениях: оцен ки сложности и алгоритмы решения / Д. И. Коган // Изв. РАН.

Теория и системы управления. 1996. №3. С. 80 – 85.

12. К о г а н, Д. И. Задача диспетчеризации: анализ вычислительной сложности и полиномиально разрешимые подклассы / Д. И. Коган, Ю. С. Федосенко // Дискретная математика. 1996. Т. 8, №3. С. – 147.


13. К о р б у т, А. А. Дискретное программирование / А. А. Корбут, Ю. Ю. Финкельштейн. – М.: Наука, 1969. – 368 с.

14. К р и с т о ф и д е с, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – М.: Мир, 1988. – 432 с.

15. Л и п с к и й, В. Комбинаторика для программистов / В. Липский.

– М.: Мир, 1978. – 213 с.

16. М а л ь ц е в, А. И. Алгоритмы и рекурсивные функции / А. И.

Мальцев. – М.: Наука, 1965. – 391с.

17. М е л а м е д, И. И. Исследование линейной свертки критериев в бикритериальной задаче о ранце // Меламед И.И., Сигал И.Х., Владимирова Н.Ю. Журнал вычислительной математики и мате матической физики, том 39, №5, 1999, с.753-758.

18. П а п а д и м и т р и у, Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу, К. Стайглиц. – М.: Мир, 1985. – 510 с.

19. П о д и н о в с к и й, В. В. Парето-оптимальные решения много критериальных задач / В. В. Подиновский, В. Д. Ногин. – М.: Нау ка, 1982. – 254 с.

20. Р у б и н ш т е й н, М. И. Об алгоритмах решения задачи о назна чении / М. И. Рубинштейн // Автоматика и телемеханика.1981. №7.

С. 145 – 154.

21. С и г а л, И. Х. Введение в прикладное дискретное программи рование / И. Х. Сигал, А. П. Иванова. – М.: Наука, 2002. – 237 с.

22. Т а н а е в, В. С. Теория расписаний. Одностадийные системы / В. С. Танаев, В. С. Гордон, Я. М. Шафранский. – М.: Наука, 1984.

– 382 с.

23. Т а н а е в, В. С. Теория расписаний. Многостадийные системы / В. С. Танаев, Ю. Н. Сотсков, В. А. Струсевич. – М.: Наука, 1989. – 328 с.

24. Т а н а е в, В. С. Введение в теорию расписаний / В. С. Танаев, В.

В. Шкурба. – М.: Наука, 1975. – 256 с.

25. Ф и н к е л ь ш т е й н, Ю. Ю. Приближенные методы и приклад ные задачи дискретного программирования / Ю. Ю. Финкель штейн. – М.: Наука, 1976. – 264 с.

26. Х е д л и, Д ж. Нелинейное и динамическое программирование / Дж. Хедли. – М.: Мир, 1967. – 506 с.

27. Ю д и н, Д. Б. Линейное программирование / Д. Б. Юдин, Е. Г.

Гольштейн. – М.: Наука, 1969.

28. K l a m r o t h, K. Dynamic Programming Approaches to the Multiple Criteria Knapsack Problem / K. Klamroth, M. Wiecek. // Technical Re port No 666. Dept. of Math. Sc., Clemson University. Clemson, SC.

1998.

(www.math.clemson.edu/affordability/publications/kla-wie3.ps) СОДЕРЖАНИЕ ВВЕДЕНИЕ..................................................................................... Глава 1. МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ЗАДАЧАХ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ..................... 1.1. Принцип динамического программирования. Основные рекуррентные соотношения динамического программирования................................................................................................................... 1.2. Решение методом динамического программирования дискретных оптимизационных задач............................................. Глава 2. ПРИМЕНЕНИЕ МЕТОДА ДИНАМИЧЕСКОГО ПРО ГРАММИРОВАНИЯ К ЗАДАЧАМ СИНТЕЗА РАСПИСА НИЙ ОБСЛУЖИВАНИЯ........................................................ 2.1. Задачи обслуживания множеств заявок............................... 2.2. Однопроцессорные задачи синтеза расписаний обслужи вания конечных детерминированных потоков заявок................. 2.3. Задачи синтеза расписаний обслуживания для систем с параллельными и последовательными процессорами............... 2.4. Задачи оптимального обслуживания стационарных объ ектов, расположенных в одномерной зоне.................................... Глава 3. ТРУДНОРЕШАЕМЫЕ ЗАДАЧИ:

ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ ПОДКЛАССЫ, ПРИБЛИЖЕННЫЕ И ЭВ РИСТИЧЕСКИЕ АЛГОРИТМЫ............................................. 3.1. Полиномиально разрешимые и NP - трудные задачи......... 3.2. Полиномиально разрешимые подклассы труднорешае мых задач.......................................................................................... 3.3. Принципы построения приближенных и эвристических алгоритмов....................................................................................... 3.4. Эвристические алгоритмы для задач синтеза расписаний обслуживания................................................................................... Глава 4. ДИСКРЕТНЫЕ МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ.

МНОГОКРИТЕРИАЛЬНОЕ ДИНАМИЧЕСКОЕ ПРОГРАМ МИРОВАНИЕ......................................................................... 4.1. Концепция Парето-оптимального решения и схемы компромисса между критериями.......................................... 4.2. Синтез Парето-оптимальных решений методом последо вательных уступок........................................................................... 4.3. Синтез полных совокупностей эффективных оценок на основе рекуррентных соотношений многокритериального ди нами ческого программирования............................................................. 4.4. Вопросы построения представительных совокупностей эффективных оценок. Концепция консервативного оператора.. ЛИТЕРАТУРА..........................................................................

Pages:     | 1 |   ...   | 4 | 5 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.