Автоматизированные информационно-управляющие системы

Министерство образования и науки Российской Федерации 

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

 

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

СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) 

 

Кафедра компьютерных систем в управлении и проектировании (КСУП) 

 
 

В.В. Одиноков, Н. Ю. Хабибулина 

 
 
 
 
 

АВТОМАТИЗИРОВАННЫЕ ИНФОРМАЦИОННО
УПРАВЛЯЮЩИЕ СИСТЕМЫ 

 
 
 

Учебное пособие  

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Томск – 2014 

В.В. Одиноков, Хабибулина Н.Ю. 
 
Автоматизированные информационно-управляющие системы: учеб. пособие 
для бакалавров направления подготовки 27.03.04 Управление в технических 
системах / В.В. Одиноков, Н. Ю. Хабибулина. – Томск: Томск. гос. ун-т систем упр. и радиоэлектроники, 2014. – 129 с. 

 
 

 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

СОДЕРЖАНИЕ 

    

 

ВВЕДЕНИЕ ............................................................................................................................. 4 
1. ПРЕДМЕТ И ЗАДАЧИ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ ............................................. 5 
2. ЭТАПЫ  ОПЕРАЦИОННОГО  ИССЛЕДОВАНИЯ ...................................................... 7 

2.1. Структуризация проблемы ......................................................................................... 7 
2.2. Построение математической модели ........................................................................ 8 
2.3. Примеры задач........................................................................................................... 10 

3. ЛИНЕЙНОЕ  ПРОГРАММИРОВАНИЕ ....................................................................... 17 

3.1 Построение линейных оптимизационных моделей ................................................ 17 
3.2 Предварительное преобразование линейной модели ............................................. 28 
3.3. Графическая  интерпретация линейных моделей .................................................. 30 
3.4 Симплексный алгоритм ............................................................................................. 34 
3.5. Получение исходного базиса ................................................................................... 39 
3.6. Анализ моделей на чувствительность и двойственная задача ............................. 41 
3.7. Примеры задач........................................................................................................... 49 

4. СЕТЕВЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ ........................................................... 55 

4.1. Общие свойства сетевых моделей ........................................................................... 55 
4.2. Модель назначений ................................................................................................... 56 
4.3. Модель выбора кратчайшего пути .......................................................................... 60 
4.4. Транспортная задача ................................................................................................. 68 
4.5. Задача коммивояжера ............................................................................................... 84 
4.6. Примеры задач........................................................................................................... 89 

5. ЦЕЛОЧИСЛЕННОЕ  ПРОГРАММИРОВАНИЕ .......................................................... 97 

5.1 Общее описание модели ............................................................................................ 97 
5.2. Примеры моделей целочисленного программирования ....................................... 98 
5.3 Решение задачи целочисленного программирования .......................................... 103 
5.4 Примеры задач.......................................................................................................... 107 
5.5. Заключение .............................................................................................................. 111 

6. ДИНАМИЧЕСКОЕ  ПРОГРАММИРОВАНИЕ .......................................................... 112 

6.1. Общее описание метода ......................................................................................... 112 
6.2 Задача управления запасами ................................................................................... 115 
6.3 Модель распределения ресурса .............................................................................. 122 
6.4 Анализ на чувствительность ................................................................................... 126 
6.5. Заключение .............................................................................................................. 128 

 

 
 
 
 
 
 
 

ВВЕДЕНИЕ 

 

Данное пособие предназначено для обучения студентов-бакалавров 

направления подготовки «Управление в технических системах» по одно семестровой дисциплине «Автоматизированные информационно-управляющие 
системы». Изучение курса заканчивается сдачей экзамена. 

Термин «автоматизированное управление» означает совместное участие 

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

Полезно сравнить автоматизированное управление с автоматическим 

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

В результате анализа Федерального Государственного образовательного 

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

Несмотря на то, что данное пособие является самодостаточным и содер
жит всю необходимую информацию для выполнения контрольных работ и 
для сдачи экзамена, для углубленного знакомства с рассматриваемым предметом рекомендуется знакомство с дополнительной литературой. При этом, 
так как курс «Исследование операций» сформировался достаточно давно, то 
можно пользоваться достаточно старыми изданиями. Особо рекомендуется 
учебник в трех томах [1], в котором оптимальным образом сочетаются доступность изложения и математическая корректность. Книги [2-5], вышедшие 
в последнее время и в своем большинстве являющиеся переизданиями, также 
полезны для лучшего знакомства с рассматриваемым предметом.  

 

1. ПРЕДМЕТ И ЗАДАЧИ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ 

 
Краткое определение: исследованием операций (ИО) называется научный 

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

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

Решения принимаются также давно, как существует само человечество. 

Например, прежде чем идти охотиться на мамонта, первобытные люди должны были принять решение: в каком месте устроить засаду? Как расставить 
охотников? Чем их вооружить? Мы с Вами каждый день также принимаем 
множество решений. Например, как одеться, выходя на улицу,  в каком месте 
перейти улицу и т.д. При этом мы не используем никаких методов ИО, а руководствуемся только своим опытом и здравым смыслом.  

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

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

Впервые название «Исследование операций» появилось в годы второй 

мировой войны, когда в вооруженных силах США и Англии были сформированы группы научных работников, которые готовили проекты решений для 

командующих боевыми действиями. Эти решения описывали распределение 
сил и средств по различным объектам. В дальнейшем ИО охватило самые 
разные области деятельности людей от экономики до охраны природы. Перечислим ряд типичных задач ИО, взятых из разных областей. 

1. План снабжения предприятий. Имеется ряд предприятий, потребляю
щих известные виды сырья, и есть ряд сырьевых баз, которые могут поставлять это сырье предприятиям. Базы связаны с предприятиями какими-то путями сообщения, например, железнодорожными, со своими тарифами. Требуется разработать план снабжения предприятия сырьем: с какой базы, в каком 
количестве и какое сырье доставлять, чтобы потребности в сырье были обеспечены при минимальных расходах на перевозки. 

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

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

4. Снегозащита дорог. Во многих местах метели представляют серьезную 

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

5. Противолодочный рейд. Известно, что в некотором районе находится 

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

6. Выборочный контроль продукции. Завод выпускает определенного 

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

7. Библиотечное обслуживание. Крупная библиотека обслуживает запро
сы, поступающие от абонентов. Различные книги пользуются различным 
спросом. Имеется ряд возможностей распределения книг по стеллажам и хранилищам. Требуется разработать систему библиотечного обслуживания, при 
которой запросы удовлетворяются максимально быстро. 

2. ЭТАПЫ  ОПЕРАЦИОННОГО  ИССЛЕДОВАНИЯ 

 
2.1. Структуризация проблемы 
 
Всякое операционное исследование, иными словами применение мето
дов ИО, состоит из этапов: 

1) возникновение проблемы; 
2) структуризация проблемы (формулировка задачи); 
3) построение математической модели; 
4) нахождение математического решения; 
5) внедрение результатов операционного исследования. 
Рассмотрим эти этапы. Строго говоря, этап возникновение проблемы  

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

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

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

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

значения которых может выбирать ЛПР. Данные параметры принято называть элементами решения или управляемыми параметрами (переменными). Например, если составляется план перевозок  одного типа груза из пунктов отправления  A1, A2, …, Am в пункты назначения B1, B2, …, Bn,  то элементами решения будут числа xjj, показывающие, какое количество груза  будет 
отправлено из i-го  пункта отправления в j-ый пункт назначения. Совокупность чисел x11, x12, …, x1n, …, xm1, xm2, …, xmn образует решение. В дальнейшем  будем обозначать любое решение как X. 

Критерии сравнения решений W1, W2, …, Wr  выбираются так, чтобы 

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

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

Неуправляемые параметры – параметры, значения которых влияют на 

ход операции, но эти значения не зависят от желания ЛПР.  Примерами таких 
параметров являются: температура наружного воздуха; скорость ветра; количество оборудования на предприятии, если ЛПР не хочет (или не может) развивать основные средства. Обозначим множество неуправляемых параметров 
как S.  

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

 
2.2. Построение математической модели 
 
На этапе построения математической модели необходимо предста
вить критерии сравнения решений количественно, то есть в виде формул. 
Кроме того, требуется записать в виде формул ограничения, которым должны 
удовлетворять допустимые решения. Обозначим множество допустимых решений, удовлетворяющих всем ограничениям, как XД. Реализация данного 
этапа предполагает обязательный выбор одного или нескольких методов ИО. 
Эти методы различаются между собой прежде всего типами используемых 
математических моделей. Все математические  модели (методы) ИО можно 
разделить на классы (рис.1).   

 

  

Рис.1. Классификация моделей исследования операций 

 

Модели ИО

Прямые
Обратные

Детерминированные
Стохастические

Прямые методы отвечают на вопрос: что будет, если в заданных усло
виях мы примем какое-то конкретное решение XXД? Иными словами, какие 
значения примут критерии сравнения решений? Математическая модель в 
данном случае содержит только зависимости критериев от управляемых и неуправляемых параметров. 

Обратные (оптимизационные) методы позволяют ответить на вопрос: 

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

  
 
Max WL(S, X) 
 
                                                       (2.1) 

  
 
XXД 

В отличие от прямой модели, обратная модель, во-первых, содержит 

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

В качестве второго признака классификации методов (моделей) ИО 

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

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

После того, как математическая модель построена, приступают к поиску 

решения модели. Для этого используется, как правило, ЭВМ. Программа, реализующая метод ИО, или разрабатывается или, что чаще, выбирается готовой. 
Как правило, в процессе выполнения данного этапа преследуются две цели: 

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

параметры модели, которые принимаются детерминированными, на самом 
деле полностью таковыми не являются. 

Что касается внедрения результатов операционного исследования, то 

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

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

 
2.3. Примеры задач 

Рассматриваемые ниже задачи 1 и 2 представляют собой «игрушечные» 

примеры применения оптимизационных детерминированных методов, а задачи 3 и 4 – примеры применения прямых стохастических методов. 

 
Задача 2.1 
Фирма выпускает три различных продукта 1, 2, 3 из муки. Мука может 

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

 

Продукт
Поставщик 1
Поставщик 2
Ограничения на объем 

продукции

1
0,4
1,2
3,6

2
0,4
0,4
2,4

3
0,6
1,2
4,8

Относительная 

прибыль
10
20

Рис. 2. Численные параметры задачи 2.1 

 

Решение 

Структурирование проблемы: 
1) управляемыми переменными (элементами решения) являются: 
      x1 – количество муки, закупаемого у первого поставщика; 
      x2 – количество муки, закупаемого у второго поставщика; 
2) критерием сравнения решений является объем прибыли; 

3) существуют три ограничения: объем выпуска каждого продукта не 

должен превышать величины спроса на этот продукт. 

Построение модели: 
  
10x1 + 24x2  max, 

  
0,4x1 + 1,2x2  3,6, 

  
042x1 + 0,4x2  2,4, 

  
0,6x1 + 1,2x2  4,8, 

  
x1  0, x2  0. 

Решение модели. Так как управляемых переменных всего две, решение 

модели найдем графически (рис.3). Для этого, во-первых, изобразим на плоскости две координатные оси: x1 и x2. Во-вторых, построим на этой координатной плоскости область допустимых решений. Для построения такой области 
следует построить на плоскости прямые, имеющие уравнения: 

  
0,4x1 + 1,2x2 = 3,6, 

  
0,4x1 + 0,4x2 = 2,4, 

  
0,6x1 + 1,2x2 = 4,8, 

  
x1 = 0, x2 = 0. 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Каждая из этих прямых делит координатную плоскость на две полуплоско
сти, на одной из которых соответствующее ограничение модели выполняется, а 
на другой – нет. Для определения полуплоскости, на которой ограничение выполняется, достаточно взять любую точку, например (0,0), и проверить, выполняется ли соответствующее неравенство для координат этой точки. На рис. 3 область допустимых решений показана с помощью штриховых линий.  

В-третьих, для поиска в области допустимых решений наилучшей точки 

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

1,5

3

6

4

x2

2
4
6
8
10

x1

(4,5; 1,5)

Рис. 3. Графическое решение задачи 2.1