Решение задач оптимизации в различных вычислительных средах

 

 
 

Кафедра «Автомобили, тракторы и технический сервис» 

 
  
 
 
 
 
 
 
 
 

РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ  

В РАЗЛИЧНЫХ  ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ 

 
 
 
 
 

УЧЕБНОЕ ПОСОБИЕ  

для самостоятельной работы 

для обучающихся по дисциплине «Основы научных исследований» 
по направлению подготовки 23.03.03 «Эксплуатация транспортно-

технологических машин и комплексов» 

 

 

 
 
 
 
 
 
 
 
 
 

САНКТ-ПЕТЕРБУРГ 

2017 

 

УДК 629.1.05 
 

Агапов 
Д.С., 
Белинская 
И.В. 
Учебное 
пособие 
для 

самостоятельной работы  для обучающихся по дисциплине «Основы 
научных исследований» 
по 
направлению 
подготовки 
23.03.03 

Эксплуатация транспортно-технологических машин и комплексов. – 
СПб.: СПбГАУ. – 2017. –  72 с. 

 
 

 
Рецензенты: 
доктор 
технических 
наук, 
профессор 
кафедры 

«Гидравлика» 
Санкт-Петербургского 
государственного 

политехнического университета Куколев М.И., кандидат технических 
наук, доцент кафедры «Прикладная механика, физика и инженерная 
графика» Долгушин В.А.  

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

дисциплине 
«Основы 
научных 
исследований» 
составлены 
на 

основании требований ФГОС ВО по направлению подготовки 
23.03.03 Эксплуатация транспортно-технологических машин и 
комплексов (уровень бакалавриата) и др. нормативных документов. 

 
 
 
 
 
 

Рекомендованы к изданию и публикации на электронном 

носителе Учебно-методическим советом СПбГАУ протокол № 4 
от «30» марта 2017 года. 

 
 
 
 

© Агапов Д.С., Белинская И.В.,2017 

                                                 © ФГБОУ ВО СПбГАУ, 2017 

ОГЛАВЛЕНИЕ 

 

 
с. 

 
 

Цели и задачи учебного пособия по выполнению самостоятельной 
работы……………………………………………………………………………  

2 
 

1.Основные понятия оптимизации……………………………………………. 
3 

2. Линейное программирование………………………………………………. 
10 

2.1. Теоретический материал. Методология решения задачи линейного 
программирования с помощью MS Excel и MathCad……………………… 

10 

2.2. Задание на самостоятельную работу №1………………………………… 
24 

3 Транспортная задача…………………………………………………………. 
27 

3.1.Теоретический материал…………………………………………………... 
27 

3.2Методология решения «транспортной задачи» с помощью MS Excel….. 
30 

3.3. Задание на самостоятельную работу №2………………………………… 
32 

4 Дискретное программирование …………………………………………….. 
37 

4.1. Теоретический материал………………………………………………….. 
37 

 4.2.Методология решения задачи дискретного программирования с 
помощью MS Excel………………………………………………………….... 

38 

4.3. Задание на самостоятельную работу №3………………………………… 
41 

5 Сетевые задачи ………………………………………………………………. 
45 

5.1. Задача кратчайшего пути…………………………………………………. 
45 

5.2. Задача максимального потока сети………………………………………. 
50 

5.3. Задача построения маршрута минимальной стоимости………………… 
51 

5.4. Сетевая транспортная задача……………………………………………... 
53 

5.5. Задача отыскания критического пути……………………………………. 
55 

5.6. Задача коммивояжера……………………………………………………... 
57 

5.7. Задание на самостоятельную работу №4………………………………… 
61 

 

 

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 

ЦЕЛИ И ЗАДАЧИ 

УЧЕБНОГО ПОСОБИЯ ПОВЫПОЛНЕНИЮ  

САМОСТОЯТЕЛЬНОЙ РАБОТЫ 

В процессе изучения дисциплины «Основы научных исследований» 

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

инструментом решения данных задач является проведение оптимизационных 
процедур с помощью различным программных продуктов, таких как MS Office 
– MS Excel и MathCad. 

Цель – в результате изучения учебного пособия по самостоятельной 

работе по дисциплине «Основы научных исследований» бакалавр получает 
базовые 
знания, 
необходимые 
для 
понимания 
сущности 
составления 

математических 
зависимостей, 
решения 
оптимизационных 
задач 
в 

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

Для достижения данной цели студенту необходимо решить следующие 

задачи:  

- 
сформировать 
понимание 
сущности 
алгоритмов 
оптимизации, 

используемых при решении оптимизационных задач различных видов; 

- ознакомиться с различными способами математической записи 

требований предъявляемых к оптимизируемой системе; 

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

её математическую модели; 

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

формирования отчёты по его результатам. 

Изучение 
учебного 
пособия 
по 
дисциплине 
«Основы 
научных 

исследований» 
позволяет 
достичь 
развития 
у 
студентов 
следующих 

компетенций: 

- ПК-4 – способность проводить технико-экономический анализ, 

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

техническими данными, материалами и оборудованием; 

- ПК-19 – способность в составе коллектива исполнителей к выполнению 

теоретических, экспериментальных, вычислительных исследований по научно-
техническому 
обоснованию 
инновационных 
технологий 
эксплуатации 

транспортно-технологических машин и оборудования. 

1. ОСНОВНЫЕ ПОНЯТИЯ ОПТИМИЗАЦИИ 

 

Традиционно на практике принят способ принятия решений, основанный 

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

Понятие «оптимизация» широко используется по всех отраслях 

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

результата или минимальных затрат на производства.  

Задачу оптимизации в общем виде можно сформулировать следующим 

образом (табл. 1.1). 

 

Таблица 1.1. Постановка задачи оптимизации в общем случае 

№ 
Название 
Математическая запись 
Описание 

1 

Целевая 
функция 
(критерий 

оптимизации) 

F = f(xj)  max (min, 

const); 

n
j
,1

 

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

Возможны три 
вида 
целевой 
функции: 

максимизация, 
минимизация, 
назначение 

заданного значения 

2 Ограничения 

gi(xj) = (=;)bi, 

m
i
,1

; 
n
j
,1

. 

n
k
xij

 ,1
 — целые 

(для задач целочисленного 

программирования); 

0  xj  1, 
k
j
,1

 — для 

задач с булевыми 

переменными 

Устанавливают 
зависимости 
между 

переменными. Могут быть односторонними 
и 
двусторонними. 
При 
решении 
задач 

двустороннее ограничение записывается в виде 
двух односторонних 

3 
Граничные 

условия 
dj  xj  Dj; 
n
j
,1

 

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

оптимальном решении 

Многие проблемы производства, проектирования, прогнозирования в 

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

— максимизация выпуска продукции при ограничениях на сырье для их 

производства; 

— составление штатного расписания для достижения наилучших результатов 

при наименьших расходах; 

— минимизация затрат на транспортировку продукции. 

Решение задач, удовлетворяющее всем ограничениям и граничным 

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

оптимизации — ее размерность, которая определяется числом переменных и 
числом ограничений т. При n<т задачи решения не имеют. 

Необходимым требованием задач оптимизации является условие п > т. 

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

Решение оптимизационных задач включает в себя следующие этапы: 

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

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

Наиболее важным этапом является выбор критериев оптимальности 

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

оптимальной структуры является структурной оптимизацией.  

Оптимальным выбранный вариант решения задачи является, если он 

удовлетворяет двум условиям: 

 наличие хотя бы одного критерия; 
 наличие не менее двух сравниваемых вариантов (необходимость 

осуществления выбора). 

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

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

варианте, всегда нужно указывать эти критерии (то есть «оптимальный по …»); 
и то, что может быть оптимальным при одном критерии, необязательно будет 
таковым при другом. В целом, характеризуя объект, сложно выбрать такой 
один критерий, который бы обеспечил всю полноту требований, а стремление к 
всеобъемлющему решению и назначение большого числа критериев сильно 
усложняет задачу. Поэтому в разных задачах количество критериев может быть 
различным. Задачи однокритериальной оптимизации (с одним критерием 
оптимизации) называют скалярными, а многокритериальной — векторной 
оптимизации. 
Кроме 
того, 
количество 
параметров, 
характеризующих 

оптимизируемый объект (задачу), также может быть различным, причём 
параметры 
могут 
меняться 
непрерывно 
или 
дискретно 
(дискретная 

оптимизация). 

В предельном случае решение практических задач сельскохозяйственного 

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

Сведение задачи к однокритериальной требует введения существенных 

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

В задачах многокритериальной оптимизации абсолютно однозначное 

решение, удовлетворяющее всем критериям, выбрать невозможно 
(за 

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

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

В оптимизационных задачах для удобства и однозначности восприятия 

критерии Ki (где i = 1,…, m; m — число критериев) нормируют, то есть 
приводят к следующему виду: Ki ≥ 0; критерии Ki убывают с улучшением 

решения, с ростом качества проектируемого объекта (встречается и обратное 
требование). 

Следовательно, наилучшее значение критерия равно нулю. Решения, у 

которого все критерии нулевые (Ki = 0), соответствует идеальному конечному 
результату, когда объекта нет, но его функция выполняется. 

Изучением проблем, связанных с выбором оптимальных решений, 

занимаются теория исследования операций и теория принятия решений. 

Операция – это любое управляемое мероприятие, направленное на 

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

Исследование операций – наука, занимающаяся разработкой и 

применением 
методов 
нахождения 
оптимальных 
решений 
на 
основе 

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

Теория принятия решений — область исследования, вовлекающая 

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

Для решения реальных проблем в агропромышленном секторе методами 

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

Модель представляет собой отражение реального объекта или процесса. 

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

Математическая модель реальной системы – это совокупность 

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

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

Математическое 
программирование 
- 
это область математики, 

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

Математическая оптимизационная модель состоит из четырёх 

ключевых объектов: 
- исходные данные; 
- неизвестные; 
- ограничения; 
- целевая функция. 

Исходные данные представляют требования задачи. Это могут быть 

стоимости или потребности в ресурсах, условия эксплуатации оборудования, 
вместимость складов, грузоподъёмность транспорта и т.д. 

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

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

Ограничения могут быть самыми различными (временные, финансовые, 

трудовые, информационные и пр.) 

Целевая функция представляет желаемое направление оптимизации, 

минимизации цены, максимизация коэффициента использования и т.д. 

Общая запись задач оптимизации задаёт большое разнообразие их 

классов. От класса задачи зависит подбор метода (эффективность её решения). 
Методы 
оптимизации 
классифицируют 
в 
соответствии 
с 
задачами 

оптимизации: 

1. Локальные методы: сходятся к какому-нибудь локальному экстремуму 

целевой функции. В случае унимодальной целевой функции, этот экстремум 
единственен, и будет глобальным максимумом/минимумом. 

2. Глобальные методы: имеют дело с многоэкстремальными целевыми 

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

Существующие в настоящее время методы поиска можно разбить на три 

большие группы в зависимости от вида функции f x
(
)  и множества X : 

а) 
детерминированные; 

б) 
случайные (стохастические); 

в) 
комбинированные 
(задачи 
оптимизации 
с 

неопределенностями)/игровые. 

Детерминированная модель отражает поведение системы с позиции 

полной определенности в настоящем и будущем.  

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

поведение системы и, следовательно, оценивает будущее с позиций 
вероятности тех или иных событий. 

Игровая модель дает возможность изучать конфликтные ситуации, в 

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

По критерию размерности допустимого множества, методы оптимизации 

делят 
на 
методы 
одномерной 
оптимизации 
и 
методы 
многомерной 

оптимизации. Одномерные и многомерные задачи могут быть малой и большой 
размерности. Если размерность вектора 
 равна 1 (
=1), то задача называется 

однопараметрической 
задачей 
оптимизации 
(одномерной 
задачей 

оптимизации). Если размерность вектора 
больше 1 (
>1), то задача 

называется многопараметрической задачей оптимизации (многомерной задачей 
оптимизации). 

По виду целевой функции и допустимого множества, задачи оптимизации 

и методы их решения можно разделить на следующие классы: 

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

являются 
линейными 
функциями, 
разрешаются 
так 

называемыми методами линейного программирования. 

2. В противном случае имеют дело с задачей нелинейного программирования 

и применяют соответствующие методы. В свою очередь из них выделяют 
две частные задачи:  

o 
если 
и 
 — выпуклые функции, то такую 

задачу называют задачей выпуклого программирования; 

o 
если 
, то имеют дело с задачей целочисленного (дискретного) 

программирования. 

По требованиям к гладкости и наличию у целевой функции частных 

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

приближений; 

 методы первого порядка: требуют вычисления первых частных производных 

функции; 

 методы 
второго 
порядка: 
требуют 
вычисления 
вторых 
частных 

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

 аналитические методы (например, метод множителей Лагранжа и условия 

Каруша-Куна-Таккера); 

 численные методы; 

 графические методы. 

В зависимости от природы множества X задачи математического 

программирования классифицируются как: 

 
задачи 
дискретного 
программирования 
(или 
комбинаторной 

оптимизации) — если X конечно или счётно; 

 
задачи целочисленного программирования — если X является 

подмножеством множества целых чисел; 

 
задачей нелинейного программирования, если ограничения или 

целевая функция содержат нелинейные функции и X является подмножеством 
конечномерного векторного пространства. 

Задачи оптимизации могут быть: 
 безусловными и условными. Если имеются ограничения на вектор 
, 

то задача называется задачей оптимизации с ограничениями или 
задачей 
условной 
оптимизации. 
Существует 
следующая 

классификация безусловных методов оптимизации (рис.1).