Принятие оптимальных решений в технологии транспортных процессов

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

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

высшего профессионального образования

«Воронежская государственная лесотехническая академия»

В.П. Белокуров С.В. Белокуров Г.А. Денисов Н.И. Злобина Э.Н. Бусарин

ПРИНЯТИЕ ОПТИМАЛЬНЫХ РЕШЕНИЙ 

В ТЕХНОЛОГИИ ТРАНСПОРТНЫХ ПРОЦЕССОВ

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

Воронеж 2013

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

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

высшего профессионального образования

«Воронежская государственная лесотехническая академия»

В.П. Белокуров   С.В. Белокуров   Г.А. Денисов   Н.И. Злобина   Э.Н. Бусарин

ПРИНЯТИЕ ОПТИМАЛЬНЫХ РЕШЕНИЙ 

В ТЕХНОЛОГИИ ТРАНСПОРТНЫХ ПРОЦЕССОВ

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

Воронеж 2013

УДК 656.13:004

П76

Печатается по решению учебно-методического совета
ФГБОУ ВПО «ВГЛТА» (протокол № 2 от 1 ноября 2013 г.)

Рецензенты: кафедра электротехники и автоматики

ФГБОУ ВПО Воронежский ГАУ;
д-р техн. наук, проф. Е.В. Кондрашова 

П76
Принятие оптимальных решений в технологии транспортных процессов

[Текст] : учебное пособие / В. П. Белокуров, С. В. Белокуров, Г. А. Денисов, 
Н. И. Злобина, Э. Н. Бусарин ; М-во образования и науки РФ, ФГБОУ ВПО 
«ВГЛТА». – Воронеж, 2013. – 187 с.

ISBN 978-5-7994-0599-1 (в обл.)

Учебное пособие посвящено прикладным аспектам теории принятия оптимальных 

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

Учебное пособие предназначено для студентов, обучающихся по направлению 

подготовки 190700 – Технология транспортных процессов, а также для аспирантов и 
магистров. 

УДК 656.13:004

© Белокуров В.П., Белокуров С.В., Денисов Г.А.,

Злобина Н.И., Бусарин Э.Н, 2013

ISBN 978-5-7994-0599-1
© ФГБОУ ВПО «Воронежская государственная

лесотехническая академия», 2013

Оглавление

Введение……………………………………………………………...
1. ПРИНЯТИЕ РЕШЕНИЯ..............................................................
2. МОДЕЛИРОВАНИЕ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ

2.1. Принципы составления простейших моделей……………..
2.2. Форма записи математической модели…………………….
2.3. Классификация оптимизационных задач…………………..

3. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ О РАСПРЕДЕЛЕНИИ 
РЕСУРСОВ В ТЕХНОЛОГИИ ГРУЗОВЫХ 
АВТОМОБИЛЬНЫХ ПЕРЕВОЗОК..............................................

3.1. Задачи о распределении одинаковых грузов………………
3.2. Задача о распределении разных ресурсов………………….
3.3. Решение задачи оптимизации в случае неопределенности

4. ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЕ 
ОПТИМИЗАЦИОННЫХ ЗАДАЧ………………………………..

4.1. Основные понятия в геометрических решениях 
оптимизационных задач…………………………………………….
4.2. Графическое решение задач линейного 
программирования……………………………………………….
4.3. Различные варианты оптимальных решений в задачах 
линейного программирования…………………………………..

5. ПРИНЯТИЕ РЕШЕНИЙ 
В МНОГОПАРАМЕТРИЧЕСКОЙ ОПТИМИЗАЦИИ………..

5.1. Понятие многопараметрической оптимизации……………
5.2. Метод последовательных уступок………………………….
5.3. Методы определения экспертных оценок………………….
5.4. Многопараметрическая оптимизация……………………...
5.5. Решение оптимизационных задач в относительных 
единицах………………………………………………………….

6. ТЕОРИЯ ВЕРОЯТНОСТЕЙ ДЛЯ ПРИНЯТИЯ 
ОПТИМАЛЬНЫХ РЕШЕНИЙ В УСЛОВИЯХ 
НЕОПРЕДЕЛЕННОСТЕЙ………………………………………..

6.1. Основные понятия теории вероятностей…………………..

6
7
11
11
12
15

16
16
24
30

34

34

40

45

47
47
47
52
57

61

65
65

6.2. Теория вероятностей в оптимизационных задачах
в случае их неопределенности………………………………….

7. АНАЛИЗ В ЗАДАЧАХ ОПЕРАТИВНОГО 
ОПТИМИЗАЦИОННОГО УПРАВЛЕНИЯ…………………….

7.1. Анализ в случае использования математических моделей.
7.2. Симплекс – метод в решении оптимизационных задач…..
7.3. Принятие решений в случае отклонения ресурсов 
от первоначально запланированных…………………………….

8. ЦЕЛОЧИСЛЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО 
ПРОГРАММИРОВАНИЯ…………………………………………

8.1. Общие понятия о задачах целочисленного 
программирования……………………………………………….
8.2. Особенности решения задач. Метод целочисленного 
программирования……………………………………………….
8.3. Задачи раскроя в целочисленном программировании…….
8.4. Булевы переменные в задачах целочисленного 
программирования……………………………………………….
8.5. Решение задач оптимизации с использованием булевых 
переменных……………………………………………………….

9. ТЕОРИЯ ГРАФОВ В ЗАДАЧАХ ЛИНЕЙНОГО 
ПРОГРАММИРОВАНИЯ…………………………………………

9.1. Основные понятия теории графов………………………….
9.2. Задачи оптимизации на сетях……………………………….
9.3. Критический путь в сетевых графиках…………………….

10. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ………………...

10.1. Основные понятия нелинейного программирования……
10.2. Аналитические методы определения экстремума 
в задачах безусловной оптимизации……………………………
10.3. Вычислительные методы в задачах условной 
оптимизации……………………………………………………...
10.4. Задачи условной оптимизации, учитывающие 
начальные и граничные условия………………………………...

71

83
83
85

92

97

97

98

104

106

111

115
115
116
132
141
141

144

148

152

11. ОПТИМАЛЬНОЕ ПРОЕКТИРОВАНИЕ…………………...

11.1. Основные понятия о системе автоматизированного 
проектирования (САПР)…………………………………………
11.2. Инженерные и экономические расчеты в САПР…………
11.3. Структура и параметры объекта проектирования……….
11.4. Исходные данные для использования методов 
оптимального проектирования………………………………….
11.5. Задачи оптимизации технологических процессов……….
11.6. Методы перебора возможных вариантов и методы 
решения задач оптимизации в САПР…………………………...

БИБЛИОГРАФИЧЕСКИЙ СПИСОК………………………………

155

155
156
158

162
175

178
184

ВВЕДЕНИЕ

Решения человечество принимало всегда и во всех сферах своей деятель
ности. Раньше хотели, чтобы принимаемые решения были правильными. Теперь принято говорить, что решения должны быть оптимальными. Важная область принятия решения связана с производством. Чем больше объем производства, тем труднее, принять решение и, следовательно, легче допустить 
ошибку. Возникает естественный вопрос: нельзя ли во избежание таких ошибок 
использовать ЭВМ? В настоящее время применение ЭВМ в управлении производством достигло очень больших масштабов.

Класс задач, которые могут быть решены с помощью ЭВМ, – это задачи 

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

Вопросам принятия решений на основе применения ЭВМ и математиче
ских моделей посвящена многочисленная литература, в том числе фундаментальные работы отечественных учѐных А. Г. Аганбегяна, Е. С. Вентцель, 
Л. В. Канторовича, Н. Н. Моисеева, Г. С. Поспелова, Н. П. Федоренко,
Д. Б. Юдина и др.

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

Глава 1. ПРИНЯТИЕ РЕШЕНИЯ

Основными этапами задач принятия оптимальных решений являются эта
пы, представленные на рис. 1.

Рис. 1. Основные этапы задач принятия оптимальных решений

Выбор задачи.
Выбор задачи – важнейший вопрос. Решение задачи, 

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

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

2) надо четко знать, в каком смысле искомое решение должно быть наи
лучшим.

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

Составление модели. Модели, бесконечные в своем разнообразии, мож
но классифицировать по самым различным признакам. В первую очередь все 
модели можно подразделить на физические и описательные.

К физическим относятся модели воздушных лайнеров для исследования в 

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

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

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

Моделям свойственны не только достоинства, но и недостатки. Главный

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

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

Как же оценить адекватность моделей? Любая оценка – это сравнение с 

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

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

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

Хорошую модель составить не просто. Вот что пишет по этому поводу 

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

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

Для обеспечения успеха моделирования надо выполнить три правила:

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

Но в жизни, к сожалению, не всегда так легко отделить главное от второ
степенного и составить приемлемую математическую модель.

Составление алгоритма. Если модель описывает зависимость между 

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

Алгоритмы могут быть записаны в различной форме: словесным описа
нием необходимых действий, указанием последовательности выполняемых работ по пунктам с помощью формул и т. д. Удобной формой записи алгоритма 
является блок-схема. Она не только достаточно наглядно описывает алгоритм,
но и является основной для составления программы.

Составление программы. Алгоритм записывают с помощью обычных 

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

Ввод исходных данных. Прежде чем ввести исходные данные в ЭВМ, их, 

естественно, необходимо собрать. Причем не все имеющиеся на производстве 

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

Глава 2. МОДЕЛИРОВАНИЕ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ

2.1. Принципы составления простейших моделей

Прежде чем приступить к составлению модели, введем некоторые поня
тия. То, что мы хотим спроектировать, будем называть объектом проектирования (ОП). Каждый ОП обладает определенными свойствами. Эти свойства могут быть как количественными, так и качественными. Примерами количественных свойств могут быть масса, производительность, стоимость и т. д. Примерами качественных свойств – надежность, удобство эксплуатации и, наконец, само понятие «качество», например, качество автоперевозок.

Качественные свойства ОП измерять числом мы не умеем. Поэтому, если 

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

В дальнейшем будем учитывать только те свойства ОП, которые могут 

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

С точки зрения того, знаем мы значения параметров или нет, параметры 

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

Математическая модель состоит; из трех составляющих: целевой функ
ции (ЦФ), ограничения (ОГР) и граничных условий (ГРУ). Рассмотрим эти составляющие. Граничные условия показывают предельно допустимые значения 
искомых переменных. Ограничение показывает зависимость между значениями 
искомых переменных. Целевая функция показывает, в каком смысле решение 

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

1. Задают не конкретные значения некоторых искомых величин, а гра
ничные условия, т.е. предельно допустимые значения всех искомых величин; 

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

2.2. Форма записи математической модели

Чтобы решать самые разнообразные задачи оптимизации необходимо 

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

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

j=1, 2 ,…, n, что сокращенно обозначается
n
j
,1
. При этом j – порядковый но
мер искомой переменной; i – порядковый номер ограничения 
m
i
,1
; m – число 

всех ограничений.

В этом случае в общем виде для n переменных и m ограничений матема
тическая модель может быть записана в виде:

n
j
m
i
b
x
a

x
x
x
g

x
x
x
g

x
x
x
g

x
x
x
f
F

j
j
j

n
m

n
i

n

n

,1
;
,1
;

;0
)
...,
,
(

;0
)
...,
,
(

;0
)
...,
,
(

(min);
max
)
...,
,
(

2
1

2
1

2
1
1

2
1

(2.1)

где aj и bj – нижнее и верхнее предельно допустимые значения xj.

Данную задачу (2.1) представим более компактно:

n
j
m
i

ГРУ
b
x
a

ОГР
x
g

ЦФ
x
f
F

j
j
j

j

j

,1
;
,1

;

;
0
)
(

;
(min)
max
)
(

1
(2.2)