Системный анализ и исследование операций

Московский 
государственный 
горный 
университет 

РЕДАКЦИОННЫЙ 

С О В Е Т 

ИЗДАТЕЛЬСТВО 
М О С К О В С К О Г О 
ГОСУДАРСТВЕННОГО 
ГОРНОГО УНИВЕРСИТЕТА 

Председатель 

Л. А. 
ПУЧКОВ 
ректор 
МГГУ, 
чл. -корр. 
РАН 

Зам. 
председателя 

Л.Х. 
ГИТИС 
директор 
Издательства 
МГГУ 

Члены 
редсовета 

И. В. 
ДЕМЕНТЬЕВ 
академик 
РАЕН 

А. П. 
ДМИТРИЕВ 
академик 
РАЕН 

Б.А. 
КАРТОЗИЯ 
академик 
РАЕН 

М.В. 
КУРЛЕНЯ 
академик 
РАН 

В. И. 
ОСИПОВ 
академик 
РАН 

э.м. 
СОКОЛОВ 
академик 
МАН 
ВШ 

КН. 
ТРУБЕЦКОЙ 
академик 
РАН 

В В. ХРОНИН 
профессор 

В.А. 
ЧАНТУРИЯ 
академик 
РАН 

Е.И. 
ШЕМЯКИН 
академик 
РАН 

Ю.Г. Черников 

СИСТЕМНЫЙ 
АНАЛИЗ 
И ИССЛЕДОВАНИЕ 
ОПЕРАЦИЙ 

Допущено Учебно-методическим объединением вузов 
по университетскому политехническому образованию 
в качестве учебного пособия для студентов высших 
учебных заведений, обучающихся по направлениям 
552800 и 230100 «Информатика и вычислительная 
техника» по специальности 230102 «Автоматизированные системы обработки информации и управления» 

Высшее 

горное 

образование 

А

МОСКВА 
ИЗДАТЕЛЬСТВО МОСКОВСКОГО 

} ГОСУДАРСТВЕННОГО ГОРНОГО УНИВЕРСИТЕТА 
2006 

УДК 681.3.07 
ББК 32.973.26-018.2 
4 45 

Книга соответствует 
«Гигиеническим требованиям к изданиям книжным 
для взрослых. 
СанПиН 1.2.1253—03», 
утвержденным 
Главным 
государственным санитарным 
врачом России 30 марта 2003 г. 
Экспертиза 
проведена 
Учебно-методическим 
объединением 
высших 
учебных заведений по университетскому 
политехническому 
образованию 
(письмо № 16-07/515 от 20.05.04) 

Рецензенты: 

• 
д-р техн. наук, проф. А.В. Ильюша 
(кафедра «Менеджмент в международном топливно-энергетическом 
бизнесе» Московского 
государственного университета управления); 

• 
д-р техн. наук, проф. Ю.А. Ивашкин 
(зав. кафедрой 
«Компьютерные технологии и системы» Московского государственного университета прикладной биотехнологии) 

Черников Ю.Г. 

Ч 45 
Системный анализ и исследование операций: Учебное пособие 

для вузов. — М.: Издательство Московского государственного горного 
университета, 2006. — 370 с. 

ISBN 5-7418-0424-1 (в пер.) 
Изложено введение в системный анализ и методологию исследования 
операций. Рассмотрены основные разделы исследования операций: линейное, 
целочисленное и динамическое программирование, теория игр и транспортные задачи линейного программирования. Приведены примеры решения задач с использованием современных пакетов прикладных программ, Java Applets 
и без их применения. Дано решение задач линейного программирования с использованием языка моделирования AMPL. 

Для студентов, обучающихся по направлениям 552800 и 230100 «Информатика и вычислительная техника» по специальности 230102 «Автоматизированные системы обработки информации и управления». 

УДК 681.3.07 
ББК 32.973.26-018.2 

ISBN 5-7418-0424-1 
© Ю.Г. Черников, 2006 
© Издательство МГГУ, 2006 
© Дизайн книги. 

Издательство МГГУ, 2006 

ПРЕДИСЛОВИЕ 

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

Опубликованы и публикуются учебники и учебные пособия 
с разным уровнем, глубиной рассмотрения и охватом моделей, 
методов и алгоритмов решения задач оптимизации. Один из недостатков некоторых учебных материалов — рассмотрение только математических моделей и методов, часто не сопровождаемых численными примерами, без которых достаточно трудно разобраться в них. Совершенно очевидно, что в настоящее время 
студенты, обучающиеся по направлениям 552800 и 230100 «Информатика и вычислительная техника» по специальности 230102 
«Автоматизированные системы обработки информации и управления» должны знать и понимать в общей постановке все 
стандартные, ставшие уже классическими математические модели и методы. 

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

5 

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

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

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

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

6 

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

Это обусловлено, в частности, и тем, что в связи с широким 
разнообразием программного обеспечения методов оптимизации 
и развитием Интернета, с подключением к нему многих пользователей возможно широкое применение программного обеспечения. В данной работе этому вопросу уделено достаточно большое 
внимание. Выполнив ряд задач данного пособия самостоятельно 
(тем самым «набив руку»), студент, а также другие заинтересованные лица могут начинать подготавливать и решать свои собственные задачи, хотя сначала и в первом приближении. 

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

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

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

Однако все это предполагает, прежде всего, четкое знание и 
владение как математическими моделями, так и методами и ал
7 

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

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

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

ВВЕДЕНИЕ 
В СИСТЕМНЫЙ 
АНАЛИЗ 

1.1 
П О Н Я Т И Я И ОПРЕДЕЛЕНИЯ 
СИСТЕМНОГО АНАЛИЗА 

1.1.1. Определение понятия «система» 

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

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

Понятие «система» в переводе с греческого означает «составленное из частей», «соединение», от «соединяю, составляю». 

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

11