Использование математических методов и моделей в управлении микроэкономическими системами (работа 1)

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ

(филиал в г. Воскресенске)

Кафедра «Прикладной математики»

КУРСОВАЯ РАБОТА

Дисциплина: «Моделирование микроэкономических процессов и систем»

Тема: « Использование математических методов и моделей в управлении микроэкономическими системами »

Выполнил:

студент 4-го курса (очное отделение)

Петров А.Ю. (шифр1906361)

Специальность: 080116 –

«Математические методы в экономике»

Руководитель: ст. преподаватель Нидеккер И.А.

Воскресенск, 2009 г.

Оглавление

Введение

Раздел I. «Сетевые модели»

Раздел II. «Использование метода анализа иерархий для организации поставок»

Заключение

Литература

Введение

Темой данной курсовой работы является «Использование математических методов и моделей в управлении микроэкономическими системами».

Курсовая работа имеет следующую структуру:

Введение

Раздел I «Сетевые модели».

Раздел II «Использование метода анализа иерархий для организации поставок».

Заключение

Список использованной литературы

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

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

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

Раздел I. «Сетевые модели»

Построение сети.

Данная ориентированная сеть состоит из 7 вершин, соединенных 8 ребрами. Источник – вершина 1, сток – вершина 7. Веса ребер указаны на сети, а также в таблице 1.


Таблица 2

Ребро (i, j)

Вес ребра (i, j)

(1, 2)

5

(1, 4)

11

(2, 3)

4

(3, 4)

2

(4, 5)

3

(4, 7)

15

(5, 6)

8

(6, 7)

3

Построение минимального остовного дерева.

Минимальное остовное дерево - это остовное дерево графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Шаг 0: C>0> = Ø, >0100090000030c05000000006a03000000006a03000026060f00ca06574d4643010000000000010079b00000000001000000a806000000000000a8060000010000006c000000000000000000000015000000220000000000000000000000020200002f03000020454d4600000100a80600000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db010000007800000078000000460000003402000028020000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c000000000000000840000580010000740100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d49484452000000120000001c0802000000e3a67870000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b000000fa49444154384fd593bb1183300c866526211d63900e2e6d36200d3d5c86207d1abc41da1c7430061dde8448e265c0dce174a8f143fc96f5f947745d07f6e1d84b48710ad97fad81381dc93a155aa4358092a954a6feb1378a2ae164520d6bf3d694049ab5798092206f674d3fa3847ed242d65732a651986c4f431b0fa57654ebf2e3da01d5947443cfb579791b2b2b1912e810d93ae07ac4a36c8c9cb51b28197fee04edd9c41249ee725c3486dc466884707e34c303f099fc358e531ee7dc9b9f51c5f27111e48c39d03531bc337f0b6b40e246053be575d5edf5bd75456426bcf732eb7d436f87a463773c329283d12367ef9eefef3e6ee61f4bdace77854d09e50000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000090410000e041030000000000008000000080feffaf410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c0000000400000051000000100300000000000000000000150000002200000000000000000000000000000000000000120000001c0000005000000090000000e000000030020000000000002000cc00160000002300000028000000120000001c00000001000800000000000000000000000000000000001a0000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c74004800000048489c009c487400bf740000bf744800489cdf00df9c48009c4848000101010101010101010101010101010101014943010101010101010101010101010101010101c0420101010101010101010101010101010101014943010101010101010101010101010101010101e44201010101010101010101010101010b0c12064943010101010101010101010101010f13060b19034301010101010101010101010101071501010249430101010809000000001501010117180101171543010117000304010101070d0e01171801011749430107000d0e01010101010b1601171801011726430f101206010101010101010101071501010249430b0c03040101010101010101010f13060814384307000d0e010101010101010101010b0c1206494307000d0e01010101010101010101010101015d440b0c0304010101010101010101010101010100800102000a0101010101010b110101010101010000010b0c0d0e010101010f100a010101010101120001010700030401010809000a010101010101000001010101020000000304050601010101010100800101010101010101010101010101010101010000010101010101010101010101010101010101120001010101010101010101010101010101010173440000000000000000000000000000000000000080010101010101010101010101010101010101000001010101010101010101010101010101010112000101010101010101010101010101010101017e44010101010101010101010101010101010101008001010101010101010101010101010101010181444c0000006400000000000000000000001500000022000000000000000000000016000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223001600030000001e00040000000701040004000000070104006d010000410b2000cc001c00120000000000230016000000000028000000120000001c00000001000800000000000000000000000000000000001a0000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c74004800000048489c009c487400bf740000bf744800489cdf00df9c48009c4848000101010101010101010101010101010101014943010101010101010101010101010101010101c0420101010101010101010101010101010101014943010101010101010101010101010101010101e44201010101010101010101010101010b0c12064943010101010101010101010101010f13060b19034301010101010101010101010101071501010249430101010809000000001501010117180101171543010117000304010101070d0e01171801011749430107000d0e01010101010b1601171801011726430f101206010101010101010101071501010249430b0c03040101010101010101010f13060814384307000d0e010101010101010101010b0c1206494307000d0e01010101010101010101010101015d440b0c0304010101010101010101010101010100800102000a0101010101010b110101010101010000010b0c0d0e010101010f100a010101010101120001010700030401010809000a010101010101000001010101020000000304050601010101010100800101010101010101010101010101010101010000010101010101010101010101010101010101120001010101010101010101010101010101010173440000000000000000000000000000000000000080010101010101010101010101010101010101000001010101010101010101010101010101010112000101010101010101010101010101010101017e44010101010101010101010101010101010101008001010101010101010101010101010101010181440c00000040092900aa000000000000002300160000000000040000002701ffff030000000000> = {1, 2, 3, 4, 5, 6, 7}


Шаг 1: C>1> = {1}, >010009000003f804000000005c03000000005c03000026060f00ae06574d46430100000000000100e7e300000000010000008c060000000000008c060000010000006c000000000000000000000015000000220000000000000000000000020200002f03000020454d46000001008c0600000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db010000007800000078000000460000002402000018020000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c000000000000000840000570010000640100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d49484452000000120000001c0802000000e3a67870000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b000000ec49444154384fd553b11183300c144ce29231c8a5813e1b90263d5c862023c01c710743a4a0c9e14d40c2c436d8bec4e950654bf77aeb5f8ea66982f088c321843804ecbfd1203a9c927d151951f500a2ad5ae19a1f67a3e8caa55876ebdd9d5245a0d3d86408c99a5163e4890a66a70d4c3239cb082ced6eb8c62b9507b5a7ffdc631003a717262cc4f9b05546a9f345d91858427af0c1a9b3f902d1e6a7c79a40d8f942b8d7fb1b8e154f29b9fc6facb8a394fc7a73198b1464bb15da20db0574666b26b2c9c462f776537467cb4a0533954ceb9d4d75ea3325cc00ddc5b707765ec988e31def77ffbecc33ece16709207fd94e0000000049454e44ae426082000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000090410000e041030000000000008000000080feffaf410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c0000000400000051000000040300000000000000000000150000002200000000000000000000000000000000000000120000001c0000005000000084000000d400000030020000000000002000cc00160000002300000028000000120000001c0000000100080000000000000000000000000000000000170000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c7400df9c4800489cdf0048000000bf744800bf74000001010101010101010101010101010101010100000101010101010101010101010101010101011f4401010101010101010101010101010101010134440101010101010101010101010101010101012b430101010101010101010101010101130000127043010101010101010101010101010101131201724501010101010101010101010101010113120115450101010809000000001601010101011312018745010113000304010101070d0e01010113120187450107000d0e01010101010b1501010113120180450f1014060101010101010101010101131201be450b0c03040101010101010101010113001201684507000d0e0101010101010101010101021201dc4507000d0e010101010101010101010101010129450b0c03040101010101010101010101010101e2450102000a0101010101010b11010101010101a744010b0c0d0e010101010f100a010101010101cc4501010700030401010809000a010101010101da43010101010200000003040506010101010101a44501010101010101010101010101010101010104430101010101010101010101010101010101018345010101010101010101010101010101010101fa43000000000000000000000000000000000000454501010101010101010101010101010101010193430101010101010101010101010101010101010b4501010101010101010101010101010101010113440101010101010101010101010101010101018e44010101010101010101010101010101010101a7444c0000006400000000000000000000001500000022000000000000000000000016000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223001600030000001e000400000007010400040000000701040067010000410b2000cc001c00120000000000230016000000000028000000120000001c0000000100080000000000000000000000000000000000170000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c7400df9c4800489cdf0048000000bf744800bf74000001010101010101010101010101010101010100000101010101010101010101010101010101011f4401010101010101010101010101010101010134440101010101010101010101010101010101012b430101010101010101010101010101130000127043010101010101010101010101010101131201724501010101010101010101010101010113120115450101010809000000001601010101011312018745010113000304010101070d0e01010113120187450107000d0e01010101010b1501010113120180450f1014060101010101010101010101131201be450b0c03040101010101010101010113001201684507000d0e0101010101010101010101021201dc4507000d0e010101010101010101010101010129450b0c03040101010101010101010101010101e2450102000a0101010101010b11010101010101a744010b0c0d0e010101010f100a010101010101cc4501010700030401010809000a010101010101da43010101010200000003040506010101010101a44501010101010101010101010101010101010104430101010101010101010101010101010101018345010101010101010101010101010101010101fa43000000000000000000000000000000000000454501010101010101010101010101010101010193430101010101010101010101010101010101010b4501010101010101010101010101010101010113440101010101010101010101010101010101018e44010101010101010101010101010101010101a7440c00000040092900aa000000000000002300160000000000040000002701ffff030000000000> = {2, 3, 4, 5, 6, 7}




Шаг 2: min l (1-2) = 5, j* = {2}, C>2> = {1, 2}, >>>> = {3, 4, 5, 6, 7}

Шаг 3: min l (2-3) = 4, j* = {3}, C>3> = {1, 2, 3}, >0100090000030005000000006003000000006003000026060f00b606574d4643010000000000010030160000000001000000940600000000000094060000010000006c000000000000000000000015000000220000000000000000000000020200002f03000020454d4600000100940600000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db010000007800000078000000460000002402000018020000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c000000000000000840000570010000640100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d49484452000000120000001c0802000000e3a67870000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b000000eb49444154384fd554b11183300c144c42c91e69a0cf0819c11e854b638f913b3a3c440a9a1cde8448b2098688c274a8b2ad7b49ff2f28e67986fc28f32184b804ec1c35282ea7a4d34512da0178abad97f823378a4171520df12e3ffd9240a7c9340869ccb462c2891269a50d2c7412d30854ffd5708d63ab03d4befd722fc18f3d4d585739ce67acb2b72debdca2b6255435e9d18fa2ceeb04de76f06495e0d13954f2504799d8a050723620482918c03537124fc690b50c5b3aee5dc07269ad3016d78fb07453563e9295846dcc890fc7e9f69361409cc2bddef75b3ae4d14aa4e423fd13435ee687f705df5dac212fa33cba0000000049454e44ae42608200000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000090410000e041030000000000008000000080feffaf410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000000c0300000000000000000000150000002200000000000000000000000000000000000000120000001c000000500000008c000000dc00000030020000000000002000cc00160000002300000028000000120000001c0000000100080000000000000000000000000000000000190000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c7400489cdf0048000000bf740000df9c4800bf744800bf9c9c009c48740001010101010101010101010101010101010100000101010101010101010101010101010101011f4401010101010101010101010101010101010134440101010101010101010101010101010101012b4301010101010101010101010101120000140170430101010101010101010101010101010107157245010101010101010101010101010101010818154501010108090000000014010101010101120d8745010112000304010101070d0e01010b0c001587450107000d0e01010101010b160101010f170180450f1013060101010101010101010101010715be450b0c03040101010101010101010b11011214684507000d0e0101010101010101010112001306dc4507000d0e010101010101010101010101010129450b0c03040101010101010101010101010101e2450102000a0101010101010b11010101010101a744010b0c0d0e010101010f100a010101010101cc4501010700030401010809000a010101010101da43010101010200000003040506010101010101a44501010101010101010101010101010101010104430101010101010101010101010101010101018345010101010101010101010101010101010101fa43000000000000000000000000000000000000454501010101010101010101010101010101010193430101010101010101010101010101010101010b4501010101010101010101010101010101010113440101010101010101010101010101010101018e44010101010101010101010101010101010101a7444c0000006400000000000000000000001500000022000000000000000000000016000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223001600030000001e00040000000701040004000000070104006b010000410b2000cc001c00120000000000230016000000000028000000120000001c0000000100080000000000000000000000000000000000190000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c7400489cdf0048000000bf740000df9c4800bf744800bf9c9c009c48740001010101010101010101010101010101010100000101010101010101010101010101010101011f4401010101010101010101010101010101010134440101010101010101010101010101010101012b4301010101010101010101010101120000140170430101010101010101010101010101010107157245010101010101010101010101010101010818154501010108090000000014010101010101120d8745010112000304010101070d0e01010b0c001587450107000d0e01010101010b160101010f170180450f1013060101010101010101010101010715be450b0c03040101010101010101010b11011214684507000d0e0101010101010101010112001306dc4507000d0e010101010101010101010101010129450b0c03040101010101010101010101010101e2450102000a0101010101010b11010101010101a744010b0c0d0e010101010f100a010101010101cc4501010700030401010809000a010101010101da43010101010200000003040506010101010101a44501010101010101010101010101010101010104430101010101010101010101010101010101018345010101010101010101010101010101010101fa43000000000000000000000000000000000000454501010101010101010101010101010101010193430101010101010101010101010101010101010b4501010101010101010101010101010101010113440101010101010101010101010101010101018e44010101010101010101010101010101010101a7440c00000040092900aa000000000000002300160000000000040000002701ffff030000000000> = {4, 5, 6, 7}

Шаг 4: min l (3-4) = 2, j* = {4}, C>4> = {1, 2, 3, 4}, >0100090000030c05000000006603000000006603000026060f00c206574d46430100000000000100cae60000000001000000a006000000000000a0060000010000006c000000000000000000000015000000220000000000000000000000020200002f03000020454d4600000100a00600000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db010000007800000078000000460000002402000018020000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c000000000000000840000570010000640100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d49484452000000120000001c0802000000e3a67870000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b000000eb49444154384fd5933b0e83300c861d4ec2c83dbac0de2374e94e8e5275498e51892d394407968adc84da098f0041aa192ae12989f9fcfa8de8fb1ef896f111224e811d6b0dc4e92669a5884c5a00a7a576a9feb13732537b676d867bfa6972029d3a552252aa6e66c2891c71a405163225dd08d6db68b8c643aa1d6a9d7ebc67e0da862a2c728ef2ec5576baaab4cb202f681e4d9b9cf3a602fbb85171885daec4bd3f3f7056be0a3f752f40186542002fc134e24e29430ff8a1c746e5d62a60b839d620c5028b3765ee67b1332ae8b7c5f6448aaa1943b2ff3714e00e4fb66e211f3b5bc00e66fb2ff60539d076f27f4bef090000000049454e44ae42608200000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000090410000e041030000000000008000000080feffaf410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c0000000400000051000000180300000000000000000000150000002200000000000000000000000000000000000000120000001c0000005000000098000000e800000030020000000000002000cc00160000002300000028000000120000001c00000001000800000000000000000000000000000000001c0000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c7400489cdf00df9c4800480000007474bf00489c9c00bf744800ffbf9c009c749c00bf7400009cbfff0001010101010101010101010101010101010100000101010101010101010101010101010101011f4401010101010101010101010101010101010134440101010101010101010101010101010101012b43010101010101010101010101010101011213704301010101010101010101010101010101121372450101010101010101010101010f100000000015450101010809000000001a0101011b060112138745010112000304010101070d0e010f190e121387450107000d0e01010101010b1701010b18121380450f1014060101010101010101010101151613be450b0c03040101010101010101010101080913684507000d0e0101010101010101010101011213dc4507000d0e010101010101010101010101010129450b0c03040101010101010101010101010101e2450102000a0101010101010b11010101010101a744010b0c0d0e010101010f100a010101010101cc4501010700030401010809000a010101010101da43010101010200000003040506010101010101a44501010101010101010101010101010101010104430101010101010101010101010101010101018345010101010101010101010101010101010101fa43000000000000000000000000000000000000454501010101010101010101010101010101010193430101010101010101010101010101010101010b4501010101010101010101010101010101010113440101010101010101010101010101010101018e44010101010101010101010101010101010101a7444c0000006400000000000000000000001500000022000000000000000000000016000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223001600030000001e000400000007010400040000000701040071010000410b2000cc001c00120000000000230016000000000028000000120000001c00000001000800000000000000000000000000000000001c0000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c7400489cdf00df9c4800480000007474bf00489c9c00bf744800ffbf9c009c749c00bf7400009cbfff0001010101010101010101010101010101010100000101010101010101010101010101010101011f4401010101010101010101010101010101010134440101010101010101010101010101010101012b43010101010101010101010101010101011213704301010101010101010101010101010101121372450101010101010101010101010f100000000015450101010809000000001a0101011b060112138745010112000304010101070d0e010f190e121387450107000d0e01010101010b1701010b18121380450f1014060101010101010101010101151613be450b0c03040101010101010101010101080913684507000d0e0101010101010101010101011213dc4507000d0e010101010101010101010101010129450b0c03040101010101010101010101010101e2450102000a0101010101010b11010101010101a744010b0c0d0e010101010f100a010101010101cc4501010700030401010809000a010101010101da43010101010200000003040506010101010101a44501010101010101010101010101010101010104430101010101010101010101010101010101018345010101010101010101010101010101010101fa43000000000000000000000000000000000000454501010101010101010101010101010101010193430101010101010101010101010101010101010b4501010101010101010101010101010101010113440101010101010101010101010101010101018e44010101010101010101010101010101010101a7440c00000040092900aa000000000000002300160000000000040000002701ffff030000000000> = {5, 6, 7}

Шаг 5: min l (4-5) = 3, j* = {5}, C>5> = {1, 2, 3, 4, 5}, >0100090000030605000000006003000000006003000026060f00b606574d4643010000000000010098ac0000000001000000940600000000000094060000010000006c000000000000000000000015000000220000000000000000000000020200002f03000020454d4600000100940600000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db01000000780000007800000046000000180200000c020000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c000000000000000840000564010000580100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d49484452000000120000001c0802000000e3a67870000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b000000e049444154384fd554b11584200c0d4e62c91ed730104c71f575b8c10d60e393316ceee1265c08a8a050602715107ff2f37f8439e7a07d75ed108f7804ec5e6bc01ea7a4512c59ca00ac831ad652ffd89b5fb3a4a09ce3b97cb507c1efac160811da1e98b0f3813453060b958a6104ca6b361ce358aa823a97dfce1daccbe819f2bec5f9a651de95561df4dceb312e459d3306e6c7a3686f54b2aa63de58f82c6a400604290b0650ce28b1b5588ab07841b0ade2d9054c77cd8548a1232c9d94a39f9a9542def871704ea726038887f97cf92b25591b89bc03627e83e4631ebc3f34f8aa4fa8bea5420000000049454e44ae426082000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000090410000e041030000000000008000000080feffaf410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c0000000400000051000000180300000000000000000000150000002200000000000000000000000000000000000000120000001c0000005000000098000000e800000030020000000000002000cc00160000002300000028000000120000001c00000001000800000000000000000000000000000000001c0000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c74009cbfff0048000000bf744800ffdfdf00489cdf009c484800bf74000074489c009c749c00df9c48000101010101010101010101010101010101018745010101010101010101010101010101010101d24301010101010101010101010101010101010172450101010101010101010101010101010101017c45010101010101010101010101010700001801e84301010101010101010101010101010101071bf644010101010101010101010101010101010f1a9743010101080900000000180101010101010f192d43010116000304010101070d0e010101010b1718450107000d0e01010101010b14010f150b0c0ac8430f1013060101010101010101010f10000a0125450b0c03040101010101010101010112060101404407000d0e0101010101010101010108090003264507000d0e010101010101010101010101010194440b0c030401010101010101010101010101011b450102000a0101010101010b11010101010101f944010b0c0d0e010101010f100a010101010101fa4401010700030401010809000a0101010101011a45010101010200000003040506010101010101cb4401010101010101010101010101010101010129450101010101010101010101010101010101015a440101010101010101010101010101010101012c45000000000000000000000000000000000000d94301010101010101010101010101010101010125450101010101010101010101010101010101010b430101010101010101010101010101010101011745010101010101010101010101010101010101334301010101010101010101010101010101010104454c0000006400000000000000000000001500000022000000000000000000000016000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223001600030000001e000400000007010400040000000701040071010000410b2000cc001c00120000000000230016000000000028000000120000001c00000001000800000000000000000000000000000000001c0000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c74009cbfff0048000000bf744800ffdfdf00489cdf009c484800bf74000074489c009c749c00df9c48000101010101010101010101010101010101018745010101010101010101010101010101010101d24301010101010101010101010101010101010172450101010101010101010101010101010101017c45010101010101010101010101010700001801e84301010101010101010101010101010101071bf644010101010101010101010101010101010f1a9743010101080900000000180101010101010f192d43010116000304010101070d0e010101010b1718450107000d0e01010101010b14010f150b0c0ac8430f1013060101010101010101010f10000a0125450b0c03040101010101010101010112060101404407000d0e0101010101010101010108090003264507000d0e010101010101010101010101010194440b0c030401010101010101010101010101011b450102000a0101010101010b11010101010101f944010b0c0d0e010101010f100a010101010101fa4401010700030401010809000a0101010101011a45010101010200000003040506010101010101cb4401010101010101010101010101010101010129450101010101010101010101010101010101015a440101010101010101010101010101010101012c45000000000000000000000000000000000000d94301010101010101010101010101010101010125450101010101010101010101010101010101010b430101010101010101010101010101010101011745010101010101010101010101010101010101334301010101010101010101010101010101010104450c00000040092900aa000000000000002300160000000000040000002701ffff030000000000> = {6, 7}

Шаг 6: min l (5-6) = 8, j* = {6}, C>6> = {1, 2, 3, 4, 5, 6}, >0100090000030c05000000006403000000006403000026060f00be06574d46430100000000000100602f00000000010000009c060000000000009c060000010000006c000000000000000000000015000000220000000000000000000000020200002f03000020454d46000001009c0600000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db010000007800000078000000460000001c02000010020000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c0000000000000008400005680100005c0100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d49484452000000120000001c0802000000e3a67870000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b000000e349444154384fd553c11184200c8c54e2fd7c5c215e1f570276237df8d332fc49275e1604116106ee272f206c36d90dcdbeef54bf443d048847c0fe6b8d9ac729b90c4db0868548ab41e954ffdc1bd62c4d50cec7397de58384dd36f60ce9c7edc4d81d0261a60bcc3225c30c94f76c3cc607550615d3bbb320bd4ea8b06b6b9caf1d65ad3e105b50db418f694dea7cad800d7a7ddf109b95ccea1835c6ca79b18d0156ca840126a795d878219dbb06e618631782fc1635238321092a3926e5ec27b09261be1abccb3913dff35b9705cca530d466f9405c0ef3e30ed6e7fdeef261fe017112f9995b7639c80000000049454e44ae42608200000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000090410000e041030000000000008000000080feffaf410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000001c0300000000000000000000150000002200000000000000000000000000000000000000120000001c000000500000009c000000ec00000030020000000000002000cc00160000002300000028000000120000001c00000001000800000000000000000000000000000000001d0000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c7400bf74000048000000df9c4800bf7448007400480000747400489cdf0074740000ffbfbf004800740048489c000101010101010101010101010101010101018745010101010101010101010101010101010101d24301010101010101010101010101010101010172450101010101010101010101010101010101017c4501010101010101010101010101010700000ae84301010101010101010101010101081b060f1cf64401010101010101010101010101071201011897430101010809000000001201010118140101022d43010118000304010101070d0e0118191a080918450107000d0e01010101010b15010b16170012c8430f101306010101010101010101010214010125450b0c03040101010101010101010108091201404407000d0e01010101010101010101010f1000264507000d0e010101010101010101010101010194440b0c030401010101010101010101010101011b450102000a0101010101010b11010101010101f944010b0c0d0e010101010f100a010101010101fa4401010700030401010809000a0101010101011a45010101010200000003040506010101010101cb4401010101010101010101010101010101010129450101010101010101010101010101010101015a440101010101010101010101010101010101012c45000000000000000000000000000000000000d94301010101010101010101010101010101010125450101010101010101010101010101010101010b430101010101010101010101010101010101011745010101010101010101010101010101010101334301010101010101010101010101010101010104454c0000006400000000000000000000001500000022000000000000000000000016000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223001600030000001e000400000007010400040000000701040073010000410b2000cc001c00120000000000230016000000000028000000120000001c00000001000800000000000000000000000000000000001d0000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c7400bf74000048000000df9c4800bf7448007400480000747400489cdf0074740000ffbfbf004800740048489c000101010101010101010101010101010101018745010101010101010101010101010101010101d24301010101010101010101010101010101010172450101010101010101010101010101010101017c4501010101010101010101010101010700000ae84301010101010101010101010101081b060f1cf64401010101010101010101010101071201011897430101010809000000001201010118140101022d43010118000304010101070d0e0118191a080918450107000d0e01010101010b15010b16170012c8430f101306010101010101010101010214010125450b0c03040101010101010101010108091201404407000d0e01010101010101010101010f1000264507000d0e010101010101010101010101010194440b0c030401010101010101010101010101011b450102000a0101010101010b11010101010101f944010b0c0d0e010101010f100a010101010101fa4401010700030401010809000a0101010101011a45010101010200000003040506010101010101cb4401010101010101010101010101010101010129450101010101010101010101010101010101015a440101010101010101010101010101010101012c45000000000000000000000000000000000000d94301010101010101010101010101010101010125450101010101010101010101010101010101010b430101010101010101010101010101010101011745010101010101010101010101010101010101334301010101010101010101010101010101010104450c00000040092900aa000000000000002300160000000000040000002701ffff030000000000> = {7}

Шаг 7: min l (6-7) = 3, j* = {7}, C>7> = {1, 2, 3, 4, 5, 6, 7}, >0100090000030205000000006003000000006003000026060f00b606574d46430100000000000100cc190000000001000000940600000000000094060000010000006c000000000000000000000015000000220000000000000000000000020200002f03000020454d4600000100940600000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db010000007800000078000000460000002002000014020000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c00000000000000084000056c010000600100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d49484452000000120000001c0802000000e3a67870000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b000000e649444154384fd593311283201045174f624991433893c68c6d8e82b7d16364c60e0e91c2c6919b187601258a19482715b0f396ddff17b62c0be4af221f41e212d87fad01bb9c92aa65c16a1580eedb5ec7fa37bde192828242ba73fc6a0d02eee6ae3648ddcd1b63771808337d61f6a568d880e298cd8cb17bea84da3fefcf05e871c00a7999e37cfa2887323f0a2839ea318c519db70a1434be42296e06bb3f917b4fbfb9aaaa5c0e3d012703ac941103c8829dc4a42d61deb9bd0b26dd219775c461e1a46cfd44ac743e86d89949e1bd14942bdd002a42bda04169f2304f5df077a70ff30786cf8de9c3a1f4c20000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000090410000e041030000000000008000000080feffaf410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c0000000400000051000000100300000000000000000000150000002200000000000000000000000000000000000000120000001c0000005000000090000000e000000030020000000000002000cc00160000002300000028000000120000001c00000001000800000000000000000000000000000000001a0000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c740048000000bfbfff007474bf009c749c00bf744800489cdf00bf740000bf7474000101010101010101010101010101010101018745010101010101010101010101010101010101d24301010101010101010101010101010101010172450101010101010101010101010101010101017c45010101010101010101010101010101140401e843010101010101010101010101010101070a01f64401010101010101010101010101010108190197430101010809000000001801010101010f150e2d43010117000304010101070d0e01010101050618450107000d0e01010101010b16010101010b11c8430f1012060101010101010101010101010f1525450b0c03040101010101010101011304010114404407000d0e0101010101010101010809000012264507000d0e010101010101010101010101010194440b0c030401010101010101010101010101011b450102000a0101010101010b11010101010101f944010b0c0d0e010101010f100a010101010101fa4401010700030401010809000a0101010101011a45010101010200000003040506010101010101cb4401010101010101010101010101010101010129450101010101010101010101010101010101015a440101010101010101010101010101010101012c45000000000000000000000000000000000000d94301010101010101010101010101010101010125450101010101010101010101010101010101010b430101010101010101010101010101010101011745010101010101010101010101010101010101334301010101010101010101010101010101010104454c0000006400000000000000000000001500000022000000000000000000000016000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223001600030000001e00040000000701040004000000070104006d010000410b2000cc001c00120000000000230016000000000028000000120000001c00000001000800000000000000000000000000000000001a0000000000000000000000ffffff000074bf0074000000ffffbf00749cdf00ffdf9c0074bfff00bfffff0000007400ffbf74009cdfff00000048009c480000ffffdf00dfffff0000489c00df9c740048000000bfbfff007474bf009c749c00bf744800489cdf00bf740000bf7474000101010101010101010101010101010101018745010101010101010101010101010101010101d24301010101010101010101010101010101010172450101010101010101010101010101010101017c45010101010101010101010101010101140401e843010101010101010101010101010101070a01f64401010101010101010101010101010108190197430101010809000000001801010101010f150e2d43010117000304010101070d0e01010101050618450107000d0e01010101010b16010101010b11c8430f1012060101010101010101010101010f1525450b0c03040101010101010101011304010114404407000d0e0101010101010101010809000012264507000d0e010101010101010101010101010194440b0c030401010101010101010101010101011b450102000a0101010101010b11010101010101f944010b0c0d0e010101010f100a010101010101fa4401010700030401010809000a0101010101011a45010101010200000003040506010101010101cb4401010101010101010101010101010101010129450101010101010101010101010101010101015a440101010101010101010101010101010101012c45000000000000000000000000000000000000d94301010101010101010101010101010101010125450101010101010101010101010101010101010b430101010101010101010101010101010101011745010101010101010101010101010101010101334301010101010101010101010101010101010104450c00000040092900aa000000000000002300160000000000040000002701ffff030000000000> = Ø

Минимальное остовное дерево будет выглядеть следующим образом:

Сумма весов ребер остовного дерева равна 5+4+2+3+8+3 = 25 ед.

Пример:

Необходимо соединить населенные пункты под номерами 1 – 7 автомобильными дорогами, при условии, что их протяженность будет минимальна.

Расстояния указаны рядом с каждым ребром сети.

Построение минимального остовного дерева решает эту задачу.

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

Нахождение кратчайшего маршрута.

Нахождение кратчайшего маршрута заключается в соединении источника (1) со стоком (7) минимальным расстоянием.

Шаг 1: Начальная точка {1}.

Находим кратчайший маршрут до следующей точки.


Шаг 2: Точки {1} и {2} соединяем кратчайшим маршрутом со следующей точкой.

Шаг 3: Точки {1} и {3} соединяем кратчайшим маршрутом со следующей точкой.


В результате получаем два альтернативных пути – один из них обозначен пунктиром.

Шаг 4: Точку {4} соединяем кратчайшим маршрутом со следующей точкой.

Шаг 5: Точки {4} и {5} соединяем кратчайшим маршрутом со следующей точкой.


Шаг 6: Точки {4} и {6} соединяем кратчайшим маршрутом со следующей точкой.

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

Таблица 2

Узел сети

Кратчайший маршрут

топология

протяженность

2

1-2

5

3

1-2-3

9

4

1-2-3-4 или 1-4

11

5

1-2-3-4-5 или 1-4-5

14

6

1-2-3-4-5-6 или 1-4-5-6

22

7

1-2-3-4-5-6-7 или 1-4-5-6-7

25

Пример:

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

С помощью алгоритма построения кратчайшего маршрута такой тип задачи можно решить. В результате расчетов минимальное время в пути будет составлять 25 часов.

Нахождение максимального потока.

Найти максимальный поток можно одним из нижеописанных способов.

4.1 Серия последовательных шагов.

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

Шаг 1: построим поток 1-2-3-4-5-6-7 и найдем максимальную пропускную способность этого пути.

Min (C>ij>) = C>34> = 2

Φ>1> = 2

Поток не полный

Шаг 2: построим поток 1-4-5-6-7

Min (C>ij>) = C>45> = 1

Φ>2> = Φ>1 >+ 1= 3


Поток не полный

Шаг 3: построим поток 1-4-7

Min (C>ij>) = C>14> = 10

Φ>3> = Φ>2 >+ 10= 13

Φ>3> =13 – полный поток> >

Метод разделяющих сечений

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


Χ = {1}, >010009000003ea0300000000c00200000000c002000026060f007605574d46430100000000000100ba2b0000000001000000540500000000000054050000010000006c00000000000000000000000d000000220000000000000000000000470100002f03000020454d4600000100540500000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db01000000780000007800000046000000d0010000c4010000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c00000000000000084000051c010000100100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d494844520000000b0000001c0802000000381dd252000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b0000009649444154384fbd92c915c020084431d55990e5d88ba5580a4150961cccc5a73799efb0991011b6e7d9cba49e207e9340ba5229f49ab5965c3b25456c6585280216298d656526cf048ad1b2e0ab5e84588cd85012d56927c1782851f78415e80b8ac4b71cb1b72caec96062c468802469cb31be9719e6795933360fd7606006c1c621b78c5dde80ad45195bcb7878e77f9cf8eb273c5e5de02f086ed7fe1d0000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000030410000e041030000000000008000000080ffff5f410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000002002000000000000000000000d00000022000000000000000000000000000000000000000b0000001c0000005000000080000000d000000050010000000000002000cc000e00000023000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101434c0000006400000000000000000000000d0000002200000000000000000000000e000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223000e00030000001e0004000000070104000400000007010400f5000000410b2000cc001c000b000000000023000e0000000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101430c00000040092900aa0000000000000023000e0000000000040000002701ffff030000000000> = {2, 3, 4, 5, 6, 7}

С>1 >= С(1; 2) + С(1; 3) = 5+11=16

Χ = {1, 2}, >010009000003ea0300000000c00200000000c002000026060f007605574d46430100000000000100ba2b0000000001000000540500000000000054050000010000006c00000000000000000000000d000000220000000000000000000000470100002f03000020454d4600000100540500000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db01000000780000007800000046000000d0010000c4010000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c00000000000000084000051c010000100100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d494844520000000b0000001c0802000000381dd252000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b0000009649444154384fbd92c915c020084431d55990e5d88ba5580a4150961cccc5a73799efb0991011b6e7d9cba49e207e9340ba5229f49ab5965c3b25456c6585280216298d656526cf048ad1b2e0ab5e84588cd85012d56927c1782851f78415e80b8ac4b71cb1b72caec96062c468802469cb31be9719e6795933360fd7606006c1c621b78c5dde80ad45195bcb7878e77f9cf8eb273c5e5de02f086ed7fe1d0000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000030410000e041030000000000008000000080ffff5f410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000002002000000000000000000000d00000022000000000000000000000000000000000000000b0000001c0000005000000080000000d000000050010000000000002000cc000e00000023000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101434c0000006400000000000000000000000d0000002200000000000000000000000e000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223000e00030000001e0004000000070104000400000007010400f5000000410b2000cc001c000b000000000023000e0000000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101430c00000040092900aa0000000000000023000e0000000000040000002701ffff030000000000> = {3, 4, 5, 6, 7}

С>2 >= С(1; 4) + С(2; 3) = 11+4=15

Χ = {1, 3}, >010009000003ea0300000000c00200000000c002000026060f007605574d46430100000000000100ba2b0000000001000000540500000000000054050000010000006c00000000000000000000000d000000220000000000000000000000470100002f03000020454d4600000100540500000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db01000000780000007800000046000000d0010000c4010000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c00000000000000084000051c010000100100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d494844520000000b0000001c0802000000381dd252000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b0000009649444154384fbd92c915c020084431d55990e5d88ba5580a4150961cccc5a73799efb0991011b6e7d9cba49e207e9340ba5229f49ab5965c3b25456c6585280216298d656526cf048ad1b2e0ab5e84588cd85012d56927c1782851f78415e80b8ac4b71cb1b72caec96062c468802469cb31be9719e6795933360fd7606006c1c621b78c5dde80ad45195bcb7878e77f9cf8eb273c5e5de02f086ed7fe1d0000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000030410000e041030000000000008000000080ffff5f410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000002002000000000000000000000d00000022000000000000000000000000000000000000000b0000001c0000005000000080000000d000000050010000000000002000cc000e00000023000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101434c0000006400000000000000000000000d0000002200000000000000000000000e000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223000e00030000001e0004000000070104000400000007010400f5000000410b2000cc001c000b000000000023000e0000000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101430c00000040092900aa0000000000000023000e0000000000040000002701ffff030000000000> = {2, 4, 5, 6, 7}

С>3 >= С(1; 2) + С(2; 3) + С(1, 4) + С(3, 4) = 5+4+11+2=22

Χ = {1, 2, 3}, >010009000003ea0300000000c00200000000c002000026060f007605574d46430100000000000100ba2b0000000001000000540500000000000054050000010000006c00000000000000000000000d000000220000000000000000000000470100002f03000020454d4600000100540500000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db01000000780000007800000046000000d0010000c4010000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c00000000000000084000051c010000100100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d494844520000000b0000001c0802000000381dd252000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b0000009649444154384fbd92c915c020084431d55990e5d88ba5580a4150961cccc5a73799efb0991011b6e7d9cba49e207e9340ba5229f49ab5965c3b25456c6585280216298d656526cf048ad1b2e0ab5e84588cd85012d56927c1782851f78415e80b8ac4b71cb1b72caec96062c468802469cb31be9719e6795933360fd7606006c1c621b78c5dde80ad45195bcb7878e77f9cf8eb273c5e5de02f086ed7fe1d0000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000030410000e041030000000000008000000080ffff5f410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000002002000000000000000000000d00000022000000000000000000000000000000000000000b0000001c0000005000000080000000d000000050010000000000002000cc000e00000023000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101434c0000006400000000000000000000000d0000002200000000000000000000000e000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223000e00030000001e0004000000070104000400000007010400f5000000410b2000cc001c000b000000000023000e0000000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101430c00000040092900aa0000000000000023000e0000000000040000002701ffff030000000000> = {4, 5, 6, 7}

С>4 >= С(1; 4) + С(3, 2) = 11+2=13

Χ = {1, 2, 3, 4}, >010009000003ea0300000000c00200000000c002000026060f007605574d46430100000000000100ba2b0000000001000000540500000000000054050000010000006c00000000000000000000000d000000220000000000000000000000470100002f03000020454d4600000100540500000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db01000000780000007800000046000000d0010000c4010000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c00000000000000084000051c010000100100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d494844520000000b0000001c0802000000381dd252000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b0000009649444154384fbd92c915c020084431d55990e5d88ba5580a4150961cccc5a73799efb0991011b6e7d9cba49e207e9340ba5229f49ab5965c3b25456c6585280216298d656526cf048ad1b2e0ab5e84588cd85012d56927c1782851f78415e80b8ac4b71cb1b72caec96062c468802469cb31be9719e6795933360fd7606006c1c621b78c5dde80ad45195bcb7878e77f9cf8eb273c5e5de02f086ed7fe1d0000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000030410000e041030000000000008000000080ffff5f410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000002002000000000000000000000d00000022000000000000000000000000000000000000000b0000001c0000005000000080000000d000000050010000000000002000cc000e00000023000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101434c0000006400000000000000000000000d0000002200000000000000000000000e000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223000e00030000001e0004000000070104000400000007010400f5000000410b2000cc001c000b000000000023000e0000000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101430c00000040092900aa0000000000000023000e0000000000040000002701ffff030000000000> = {5, 6, 7}

С>5 >= С(4; 5) + С(4, 7) = 3+15=18

Χ = {1, 2, 3, 4, 5}, >010009000003ea0300000000c00200000000c002000026060f007605574d46430100000000000100ba2b0000000001000000540500000000000054050000010000006c00000000000000000000000d000000220000000000000000000000470100002f03000020454d4600000100540500000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db01000000780000007800000046000000d0010000c4010000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c00000000000000084000051c010000100100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d494844520000000b0000001c0802000000381dd252000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b0000009649444154384fbd92c915c020084431d55990e5d88ba5580a4150961cccc5a73799efb0991011b6e7d9cba49e207e9340ba5229f49ab5965c3b25456c6585280216298d656526cf048ad1b2e0ab5e84588cd85012d56927c1782851f78415e80b8ac4b71cb1b72caec96062c468802469cb31be9719e6795933360fd7606006c1c621b78c5dde80ad45195bcb7878e77f9cf8eb273c5e5de02f086ed7fe1d0000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000030410000e041030000000000008000000080ffff5f410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000002002000000000000000000000d00000022000000000000000000000000000000000000000b0000001c0000005000000080000000d000000050010000000000002000cc000e00000023000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101434c0000006400000000000000000000000d0000002200000000000000000000000e000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223000e00030000001e0004000000070104000400000007010400f5000000410b2000cc001c000b000000000023000e0000000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101430c00000040092900aa0000000000000023000e0000000000040000002701ffff030000000000> = {6, 7}

С>6 >= С(4; 7) + С(5, 6) = 8+15=23

Χ = {1, 2, 3, 4, 6}, >010009000003ea0300000000c00200000000c002000026060f007605574d46430100000000000100ba2b0000000001000000540500000000000054050000010000006c00000000000000000000000d000000220000000000000000000000470100002f03000020454d4600000100540500000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db01000000780000007800000046000000d0010000c4010000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c00000000000000084000051c010000100100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d494844520000000b0000001c0802000000381dd252000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b0000009649444154384fbd92c915c020084431d55990e5d88ba5580a4150961cccc5a73799efb0991011b6e7d9cba49e207e9340ba5229f49ab5965c3b25456c6585280216298d656526cf048ad1b2e0ab5e84588cd85012d56927c1782851f78415e80b8ac4b71cb1b72caec96062c468802469cb31be9719e6795933360fd7606006c1c621b78c5dde80ad45195bcb7878e77f9cf8eb273c5e5de02f086ed7fe1d0000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000030410000e041030000000000008000000080ffff5f410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000002002000000000000000000000d00000022000000000000000000000000000000000000000b0000001c0000005000000080000000d000000050010000000000002000cc000e00000023000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101434c0000006400000000000000000000000d0000002200000000000000000000000e000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223000e00030000001e0004000000070104000400000007010400f5000000410b2000cc001c000b000000000023000e0000000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101430c00000040092900aa0000000000000023000e0000000000040000002701ffff030000000000> = {5, 7}

С>7 >= С(4; 5) + С(4, 7) + С(5, 6) + С(6, 7) = 3+15+8+3=29

Χ = {1, 2, 3, 4, 5, 6}, >010009000003ea0300000000c00200000000c002000026060f007605574d46430100000000000100ba2b0000000001000000540500000000000054050000010000006c00000000000000000000000d000000220000000000000000000000470100002f03000020454d4600000100540500000c00000001000000000000000000000000000000560500000003000040010000b300000000000000000000000000000000e2040038bb0200460000002c00000020000000454d462b014001001c000000100000000210c0db01000000780000007800000046000000d0010000c4010000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c00000000000000084000051c010000100100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d494844520000000b0000001c0802000000381dd252000000017352474200aece1ce9000000097048597300000ec400000ec401952b0e1b0000009649444154384fbd92c915c020084431d55990e5d88ba5580a4150961cccc5a73799efb0991011b6e7d9cba49e207e9340ba5229f49ab5965c3b25456c6585280216298d656526cf048ad1b2e0ab5e84588cd85012d56927c1782851f78415e80b8ac4b71cb1b72caec96062c468802469cb31be9719e6795933360fd7606006c1c621b78c5dde80ad45195bcb7878e77f9cf8eb273c5e5de02f086ed7fe1d0000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000030410000e041030000000000008000000080ffff5f410000008000000080ffff0b422100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000002002000000000000000000000d00000022000000000000000000000000000000000000000b0000001c0000005000000080000000d000000050010000000000002000cc000e00000023000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101434c0000006400000000000000000000000d0000002200000000000000000000000e000000230000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c0223000e00030000001e0004000000070104000400000007010400f5000000410b2000cc001c000b000000000023000e0000000000280000000b0000001c0000000100080000000000000000000000000000000000160000000000000000000000ffffff00489cdf00df9c4800bfffff000000740074bfff00bf74000048000000ffdf9c00dfffff0000489c009cdfff00000048009c480000ffffdf000074bf00bfdf9c004800740074000000ffffbf00740048000101010101010101010101000101010101010101010101430101010101010101010101000101010101010101010101800101010101010101010101080101010101010101010101070101010101010101010101070b0000070101060000000744010213140101011000030143010a0b03010104050e0f014301010c15140110080901014301010102070c0d070101014301010104050013140101014301010101020003010101014301010104050007010101014301010110081112090101014301010c0d0701060e0f010143010a0b0809010a0b030101430106000701010106080901430200000003010405000003430101010101010101010101430101010101010101010101430101010101010101010101430000000000000000000000430101010101010101010101430101010101010101010101430101010101010101010101430101010101010101010101430c00000040092900aa0000000000000023000e0000000000040000002701ffff030000000000> = {7}

С>8 >= С(4; 7) + С(6, 7) = 15+3=18

Минимальное сечение:

Max Φ = min C>i> = min(16, 15, 22, 13, 18, 23, 29, 18) = 13

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


Пример:

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

После построения полного и максимального потока видно, что участки 1 – 4, 3 – 4, 4 – 5, 6 – 7 нагружены полностью, в то время как на участках 1 – 2, 2 – 3, 4 – 7, 5 – 6 не использована пропускная способность в размерах 3, 2, 5, 5 соответственно.

Раздел II. «Использование метода анализа иерархий для организации поставок»

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

К1 – надежность поставки

К2 – цена

К3 – качество товара

К4 – условия платежа

К5 – возможность внеплановых поставок

Матрица сравнений критериев относительно цели:

Матрицы сравнения альтернатив (поставщиков) относительно критериев:

k1 k2 k3 k4 k5

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

Для матрицы сравнения критериев относительно цели найдем собственный вектор и вес каждого критерия:

Критерий

k1

k2

k3

k4

k5

собственный вектор

вес

k1

1

5

8

2

7

3,545

0,535

k2

1/5

1

3

4

1/2

1,037

0,157

k3

1/8

1/3

1

2

1

0,608

0,092

k4

1/2

1/4

1/2

1

1/3

0,461

0,070

k5

1/7

2

1

3

1

0,970

0,146

Σ

6,621

1,000

Проверим согласованность матрицы:

>>

>>

n = 5

L = 0,229

R = 1,120

T = 0,204 > 0,1 – уровень согласованности не приемлем.

Изменим суждения ЛПР для достижения согласованности матрицы.

>>

>>

n = 5

L = 0,049

R = 1,120

T = 0,043 < 0,1 – уровень согласованности приемлем.

Найдем веса альтернатив по критериям и проверим их согласованность.

Альтернативы относительно критерия k1

Альтернативы

A1

A2

A3

A4

собственный вектор

вес

A1

1,000

7,000

0,500

8,000

2,300

0,480

A2

0,143

1,000

0,125

3,000

0,481

0,100

A3

2,000

8,000

1,000

0,200

1,337

0,279

A4

0,125

0,333

5,000

1,000

0,676

0,141

4,795

1,000

Проверим согласованность матрицы:

>>

>>

n = 4

L = 0,925

R = 0,900

T = 1,027 > 0,1 – матрица не согласована.

Альтернативы относительно критерия k2

Альтернативы

A1

A2

A3

A4

собственный вектор

вес

A1

1,000

4,000

6,000

8,000

3,722

0,654

A2

0,250

1,000

8,000

0,143

0,731

0,129

A3

0,167

0,125

1,000

3,000

0,500

0,088

A4

0,125

7,000

0,333

1,000

0,735

0,129

5,688

1,000

>>

>>

n = 4

L = 0,495

R = 0,900

T = 0,550 > 0,1 – матрица не согласована.

Альтернативы относительно критерия k3

Альтернативы

A1

A2

A3

A4

собственный вектор

вес

A1

1,000

4,000

0,111

8,000

1,373

0,282

A2

0,250

1,000

1,000

2,000

0,841

0,173

A3

9,000

1,000

1,000

3,000

2,280

0,468

A4

0,125

0,500

0,333

1,000

0,380

0,078

4,873

1,000

>>

>>

n = 4

L = 0,760

R = 0,900

T = 0,844 > 0,1 – матрица не согласована.

Альтернативы относительно критерия k4

Альтернативы

A1

A2

A3

A4

собственный вектор

вес

A1

1,000

4,000

6,000

8,000

3,722

0,637

A2

0,250

1,000

3,000

2,000

1,107

0,189

A3

0,167

0,333

1,000

3,000

0,639

0,109

A4

0,125

0,500

0,333

1,000

0,380

0,065

5,848

1,000

>>

>>

n = 4

L = 0,041

R = 0,900

T = 0,046 < 0,1 – матрица согласована.

Альтернативы относительно критерия k5

Альтернативы

A1

A2

A3

A4

собственный вектор

вес

A1

1,000

0,250

6,000

8,000

1,861

0,402

A2

4,000

1,000

0,333

2,000

1,278

0,276

A3

0,167

3,000

1,000

3,000

1,107

0,239

A4

0,125

0,500

0,333

1,000

0,380

0,082

4,626

1,000

>>

>>

n = 4

L = 0,808

R = 0,900

T = 0,898 > 0,1 – матрица не согласована.

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

V>A>>1> = 0,489

V>A>>2> = 0,143

V>A>>3> = 0,249

V>A>>4> = 0,119

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

Заключение

Данная курсовая работа состоит из двух частей:

Раздел I «Сетевые модели».

Раздел II «Использование метода анализа иерархий для организации поставок».

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

Рассмотрена задача о минимизации времени в пути автотранспорта из начального узла в конечный узел сети, который составил 25 часов.

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

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

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

Литература

Шикин Е.В., Шикина Г.Е. Исследование операций: учеб. – М.: «Издательство Проспект»,2006.

Таха Хемди А. Введение в исследование операций. – М. Издательский дом «Вильямс», 2005.

Экономико-математическое моделирование: учебник под общ.ред. И.Н.Дрогобыцкого. – М. «Экзамен», 2006.

Ларичев О.И. Теория и методы принятия решений: - М.: Логос, 2003.

Тимашков П.С. Математические методы принятия решений: Учеб.пособие МГУПЭСИ – М., 2003.

Лагоша Б.А. Моделирование микроэкономических процессов и систем в инвестиционной деятельности : Учеб.пособие. – М.: Изд-во МГОУ, 2007.

Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: - М.: Финансы и статистика, 2002.

Математические методы и модели исследования операций: учеб. Под ред. В.А.Колемаева. – М.: ЮНИТИ – ДАНА, 2008.