Моделирование задач принятия решений в системе МАТПРОГ

Федеральное государственное бюджетное 

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

«Московский государственный технический университет имени Н.Э. Баумана 

(национальный исследовательский университет)»
З.Н. Русакова
Моделирование задач принятия решений 
в системе МАТПРОГ
Учебное пособие
Под редакцией И.В. Рудакова

УДК 681.3.06 
ББК 32.973-018 
Р88 
 
Издание доступно в электронном виде на портале ebooks.bmstu.ru  
по адресу: http://ebooks.bmstu.ru/catalog/199/book1725.html 
Факультет «Информатика и системы управления» 
Кафедра «Программное обеспечение ЭВМ и информационные технологии» 
Р88 
Рекомендовано Редакционно-издательским советом  
МГТУ им. Н.Э. Баумана в качестве учебного пособия 
 
 
Русакова, З. Н. 
 
 
Моделирование задач принятия решений в системе 
МАТПРОГ : учебное пособие / З. Н. Русакова; под ред.  
И. В. Рудакова. — Москва : Издательство МГТУ им. Н. Э. Баумана, 2018. — 41, [3] с. : ил. 
 
ISBN 978-5-7038-4772-5 
 
Дано подробное описание инструментального средства поддержки 
принятия решений МАТПРОГ, предназначенного для выполнения  лабораторного практикума по дисциплине «Типы и структуры данных».  
На конкретных примерах продемонстрированы методики и приемы решения задач принятия решений. Приведены краткие теоретические сведения, а также контрольные вопросы и задания. 
Для студентов 2-го курса, изучающих дисциплину «Типы и структуры данных».  
 
УДК 681.3.06 
ББК 32.973-018 
 
 
 МГТУ им. Н.Э. Баумана, 2018 
 
 
 Оформление. Издательство  
ISBN 978-5-7038-4772-5                               МГТУ им. Н.Э. Баумана, 2018 
2 

ПРЕДИСЛОВИЕ 
Предлагаемое учебное пособие предназначено для студентов 
2-го курса МГТУ им. Н.Э. Баумана четвертого семестра бакалавриата по направлению «Программная инженерия», изучающих дисциплину «Типы и структуры данных».  
Цель пособия — изучение методов моделирования задач принятия решений: оптимизационных, статистических, экспертных. 
Для автоматизации процесса решения преподавателями кафедры 
«Программное обеспечение ЭВМ и информационные технологии» разработан программный инструментарий системы поддержки принятия решений МАТПРОГ.  
В системе МАТПРОГ можно выполнять моделирование следующих прикладных задач: 
 потоковые задачи в сетях (определение максимального потока и минимального разреза сети, определение дерева разрезов 
сети, поисковых задач в графах); 
 поиск в графах И–ИЛИ, описывающих произвольную предметную область; 
 оптимизационные задачи линейного программирования 
(симплекс-метод, транспортная задача); 
 задачи регрессионного анализа (оценивание параметров линейных регрессий для заданной матрицы плана и вектора наблюдений, вычисление обратной матрицы). 
Разработанное инструментальное средство позволяет осуществить моделирование потоковых и поисковых задач в графах, 
моделирование семантических сетей, планирование вычислений 
при логическом синтезе программ, моделирование оптимизационных задач. 
В пособии рассмотрены методы решения задач, дана их математическая постановка и приведен алгоритм решения, руководство пользователя представлено в справках меню системы МАТПРОГ.  
После изучения материалов учебного пособия студенты овладеют методами моделирования задач принятия решений. 
3 

1. ОПТИМАЛЬНОЕ РЕШЕНИЕ ОБЩЕЙ ЗАДАЧИ 
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 
1.1. Математическая модель 
В общей задаче линейного программирования (ЗЛП) требуется 
определить максимум (или минимум) линейной целевой функции 
n
1
.
j
j
j
z
c x  


При линейных ограничениях вида 
n
n
1
,
1
,
ij
j
i
j
a x
b
ij
j
i
j
a x
b



 или 



 
где i = 1, …, m;  j = 1, …, n; 
j
x  > 0. 
Введением слабых переменных запишем ЗЛП в канонической 
форме: 
n
j
j
j
Z
с x
 
1
max(min)



при ограничениях 
n
1
,
ij
j
j
a x
b  



i
где i = 1, ..., m;  j = 1, ..., n;  xj ≥ 0. 
Оптимальное решение задачи достигается в одной из угловых 
точек пространства решений. На основе этой идеи разработан 
симплекс-метод решения ЗЛП. 
1.2. Решение симплекс-методом  
Рассмотрим последовательность решения ЗЛП симплексметодом применительно к задаче максимизации (минимизации). 
По условию задачи составим ее математическую модель. Составленную модель преобразуем к канонической форме. Все ограничения преобразуем в равенства с неотрицательной правой частью. 
Все переменные неотрицательны.  
4 

Целевую функцию требуется максимизировать или минимизировать. 
Каноническую модель задачи запишем в форме симплекстаблицы так, чтобы все свободные члены были неотрицательными. При этом может определиться базис с начальным опорным 
планом. Если начальный опорный плана выделен, то следует перейти к проверке его оптимальности.  
В противном случае ищем начальный опорный план, выполняя симплексные преобразования с положительными разрешающими элементами, отвечающими минимальным симплексным 
отношениям. Если в ходе преобразований встретится нулевая 
строка, все элементы которой, кроме свободного члена, нули, то 
система ограничительных уравнений задачи несовместна. Если же 
встретится нулевая строка, в которой, кроме свободного члена, 
других положительных элементов нет, то система ограничительных уравнений не имеет неотрицательных решений.  
Найденный начальный опорный план исследуем на оптимальность.  
Если в индексной строке ( f-строке) нет отрицательных элементов (не считая свободного члена), то план оптимален. Если 
при этом нет и нулевых элементов, то оптимальный план единственный. Если же есть хотя бы один нулевой элемент, то оптимальных планов бесконечное множество. Если в f-строке есть хотя 
бы один отрицательный элемент, которому соответствует столбец 
неположительных элементов, то . 
Если в f-строке есть хотя бы один отрицательный элемент, а в 
его столбце есть хотя бы один положительный, то переходим к 
новому опорному плану, более близкому к оптимальному. Для 
этого указанный столбец назначим разрешающим, по минимальному симплексному отношению определим разрешающую строку.  
Если в столбце свободных членов есть отрицательные числа, 
то разрешающий элемент выберем следующим образом: просмотрим строку, отвечающую какому-либо отрицательному свободному члену, например, f-строку, и выберем в ней какой-либо отрицательный элемент, а соответствующий ему столбец примем за разрешающий. Затем составим отношения элементов столбца свободных членов к соответствующим элементам разрешающего 
столбца, имеющим одинаковые знаки (симплексные отношения). 
Из симплексных отношений выберем наименьшее. Оно и опреде5