Использование математических методов и моделей в управлении микроэкономическими системами (работа 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.