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

 

 
 

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

 
  
 
 
 
 
 
 
 
 

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

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

 
 
 
 
 

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

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

для обучающихся по дисциплине «Основы научных исследований» 
по направлению подготовки 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), соответствует идеальному конечному 
результату, когда объекта нет, но его функция выполняется. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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