Файл: Практикум Челябинск 2019.pdf

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
519.8(07)
П844
И.А. Прохорова
ПРИКЛАДНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
Практикум
Челябинск
2019

Министерство науки и высшего образования Российской Федерации
Южно-Уральский государственный университет
Кафедра «Информационные технологии в экономике»
519.8(07)
П844
И.А. Прохорова
ПРИКЛАДНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
Практикум
Челябинск
Издательский центр ЮУрГУ
2019

2
УДК 519.876(075.8)+519.715(075.8)
П844
Одобрено
учебно-методической комиссией
Высшей школы экономики и управления
Рецензенты:
зав. кафедрой математики и информатики
ЧОУ ВО «Международный институт дизайна и сервиса»,
к.т.н., доцент Л.Ю. Овсяницкая,
зав. кафедрой гуманитарных, естественнонаучных и математических
дисциплин УрСЭИ (ф) ОУП ВО «АТиСО»,
к.т.н., доцент И.В. Сафронова
Прохорова, И.А.
П844
Прикладные методы оптимизации: практикум / И.А. Прохорова.
– Челябинск: Издательский центр ЮУрГУ, 2019. – 131 с.
Приведены практические работы, контрольные вопросы и задания для самостоятельной работы.
Практикум предназначен для бакалавров всех форм обучения по направлению подготовки «Прикладная информатика».
УДК 519.876(075.8)+519.715(075.8)

Издательский центр ЮУрГУ, 2019

3
ВВЕДЕНИЕ
Целью дисциплины «Прикладные методы оптимизации» является освоение математических методов решения задач оптимизации, возникающих в области экономики, финансов, менеджмента, маркетинга.
В процессе изучения этой дисциплины у студентов должны быть сформированы теоретические знания и практические навыки в получении решения и анализе полученных результатов.
Задачей курса «Прикладные методы оптимизации» является ознакомление с различными направлениями решения оптимизационных задач и основными методами их решения с учетом ограничений, определяемых постановками задач в соответствующей предметной области.
В целях более эффективного усвоения учебного материала каждая тема практикума содержит краткую теоретическую справку, подробные методические указания с описанием решения конкретных задач, контрольные вопросы и задания для самостоятельной работы.
Практическая работа 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
КРАТКАЯ СПРАВКА
Линейное программирование – это наука о методах исследования и отыскания экстремальных (наибольших или наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.
Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются
системой ограничений.
Определение 1. Задача, в которой требуется минимизировать (или максимизировать) линейную форму
(max)
min
x
c
n
i
i
i




1
(1.1) при условии, что
 







n
i
j
i
ij
n
,
j
,
b
,
x
a
1 1
,
n
i
x
i
,
1
,
0


называется задачей линейного программирования в произвольной форме записи.
Определение 2. Задача в матричной форме вида


 












,
0
,
max min
x
b
x
A
x
c
(1.2) называется симметричной формой записи задачи линейного программирования.

4
Определение 3. Задача линейного программирования вида













,
x
,
b
x
A
max
min
x
c
0
(1.3) называется канонической формой записи задачи линейного программирования.
Любую задачу линейного программирования можно привести к канонической форме:

если система ограничений задана в форме
,
b
x
A


то можно, введя дополнительные переменные, привести ее к виду
0 0






y
,
x
,
b
y
E
x
A
, где






m
n
n
x
...,
,
x
y
1
;

если система ограничений задана в форме
,
b
x
A


то можно, введя дополнительные переменные, привести ее к виду
0 0






y
,
x
,
b
y
E
x
A
Допустимым решением (планом) задачи линейного программирования называется вектор Х = ( х
1
,х
2
, х
3
,…х
n
), удовлетворяющий системе ограничений.
Множество допустимых решений образует область допустимых решений.
Допустимое решение, при котором целевая функция достигает своего экстремального значения, называется оптимальным решением задачи линейного программирования.
Для того, чтобы построить математическую модель задачи линейного программирования, необходимо выполнить следующую последовательность действий:
1. Ввести обозначения переменных.
2. Составить целевую функцию, исходя из целей экономических исследований.
3. Записать систему ограничений, учитывая ограничения в использовании экономических показателей задачи и их количественные закономерности.
1.1. Решение задачи линейного программирования с помощью
программы Microsoft Office Excel. Анализ чувствительности
КРАТКАЯ СПРАВКА
Для решения задач линейного программирования в Microsoft Office Excel используется надстройка Поиск решения, которая вызывается командой Данные /
Поиск решения.
Если данная надстройка не установлена, то необходимо проделать следующую последовательность действий:

5

нажать на кнопку Office
, далее на кнопку Параметры Excel (рис. 1.1.1)
(или команда Файл / Параметры, или Настройка панели быстрого доступа
/ Другие команды…);
Рис. 1.1.1. Вызов диалогового окна Параметры Excel

в диалоговом окне Параметры Excel выбрать Надстройки и нажать на кнопку Перейти (рис. 1.1.2);
Рис. 1.1.2. Диалоговое окно Параметры Excel

6

в открывшемся диалоговом окне Надстройки установить флажок Поиск
решения (рис. 1.1.3); ОК.
Рис. 1.1.3. Диалоговое окно Надстройки
Пример 1.1. Предприятие изготавливает и реализует два вида продукции – П
1
и П
2
. Для производства продукции используются два вида сырья – A и B. Максимально возможные запасы сырья в сутки составляют
400 и 365 кг соответственно. Расход сырья на изготовление единицы каждого вида продукции и запасы сырья приведены в таблице 1.1.
Таблица 1.1
Сырье
Расходы сырья на 1 кг продукции
Запас сырья, кг
П
1
П
2
A
0,8 0,5 400
B
0,4 0,8 365
Изучение рынка сбыта показало, что суточный спрос на продукцию П
1
превышает спрос на продукцию П
2
не более, чем на 100 кг.
Спрос на продукцию П
2
не превышает 350 кг в сутки.
Розничная цена 1 кг продукции П
1
составляет 16 рублей, продукции П
2

14 рублей.
Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?
Решение
1. Составим математическую модель задачи.
Обозначим через
х
1

суточный объем выпуска продукции П
1
, кг;
х
2

суточный объемвыпуска продукции П
2
, кг.

7
Так как производство продукции П
1
и П
2
ограничено имеющимися в распоряжении предприятия запасами сырья каждого вида и спросом на данную продукцию, кроме того количество изготавливаемой продукции не может быть отрицательным, следовательно, должны выполняться следующие неравенства:

















.
x
;
x
,
x
,
x
x
,
x
,
x
,
,
x
,
x
,
0 0
350 100 365 8
0 4
0 400 5
0 8
0 2
1 2
2 1
2 1
2 1
(1.4)
Здесь 1-е и 2-е ограничения – это ограничения на сырье; 3-е и 4-е ограничения – это ограничения на спрос.
Доход от реализации х
1 кг продукции П
1
и х
2
кг продукции П
2
составит
F(X) = 16x
1
+ 14x
2
.
(1.5)
Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных ограничений требуется найти такое, при котором функция F (X) принимает максимальное значение.
2. Введем исходные данные. Для этого

создадим экранную форму для ввода условий задачи: переменных, целевой функции, ограничений и граничных условий;

введем исходные данные в экранную форму: коэффициенты целевой функции, коэффициенты при переменных в ограничениях, правые части ограничений. Экранная форма для ввода условий задачи вместе с введенными в нее исходными данными приведена на рисунке 1.1.4;
Рис. 1.1.4. Экранная форма для ввода условий задачи

8

введем зависимости из математической модели в экранную форму: а) формулу для расчета целевой функции (ячейка F14). Значение целевой функции определяется выражением (1.5).
Используя обозначения соответствующих ячеек в Excel, формулу для расчета целевой функции можно записать как сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B14:C14), на соответствующие ячейки, отведенные для коэффициентов целевой функции (B4:C4), то есть
=СУММПРОИЗВ(B14:C14;B4:C4).
После этого в целевой ячейке F14 появится 0 (нулевое значение) (рис.
1.1.5);
Рис. 1.1.5. Экранная форма задачи после ввода всех необходимых формул б) формулы для расчета левых частей ограничений.
Левые части ограничений исходной задачи представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B14:C14), на соответствующие ячейки, отведенные для коэффициентов конкретного ограничения, то есть
=СУММПРОИЗВ($B$14:$C$14;B8:C8);
=СУММПРОИЗВ($B$14:$C$14;B9:C9);
=СУММПРОИЗВ($B$14:$C$14;B10:C10);
=СУММПРОИЗВ($B$14:$C$14;B11:C11).
На экране в ячейках D8, D9, D10 и D11 появится 0 (нулевое значение)
(см. рис. 1.1.5).
На рисунке 1.1.6 показан результат введения зависимостей в режиме просмотра формул.

9
Рис. 1.1.6. Экранная форма задачи в режиме (Формулы / Показать
формулы)
3. Решим задачу, используя надстройку Поиск решения.
Для этого необходимо выполнить команду Данные / Поиск решения. В открывшемся диалоговом окне Поиск решения (рис. 1.1.7) необходимо:
Рис. 1.1.7. Диалоговое окно Поиск решения

задать целевую функцию: установить целевую ячейку (F14) и указать направление оптимизации целевой функции (в нашем случае: Равной
максимальному значению);

в поле Изменяя ячейки: ввести адреса ячеек с первоначальными значениями переменных B14:C14;

ввести ограничения: а) нажать кнопку Добавить (поле Ограничения:), после чего появится диалоговое окно Добавления ограничения (рис. 1.1.8);

10
Рис. 1.1.8. Диалоговое окно Добавление ограничения б) в поле Ссылка на ячейку: ввести адрес ячейки, в которой записана левая часть первого ограничения задачи, D8; в) в поле знака открыть список предлагаемых знаков и выбрать

; г) в поле Ограничение: ввести адрес ячейки, в которой записана правая часть первого ограничения F8; д) остальные ограничения вводятся аналогично, используя кнопку
Добавить окна Добавление ограничения; е) подтвердить ввод всех перечисленных выше условий нажатием кнопки OK.
Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений, то это делают, нажав кнопки
Изменить или Удалить (см. рис. 1.1.7);

установить параметры решения задачи, нажав кнопку Параметры и заполнив некоторые поля диалогового окна Параметры поиска
решения (рис. 1.1.9). В нашем примере

это: линейная модель (для решения задач линейного программирования) и неотрицательные
значения (если такие ограничения накладываются на все переменные задачи).
Рис. 1.1.9. Диалоговое окно Параметры поиска решения

11
КРАТКАЯ СПРАВКА
Параметр Максимальное время: служит для ограничения времени, отпускаемого на поиск решения. В поле можно ввести время (в секундах), не превышающее 32767; значение 100, используемое по умолчанию, подходит для большинства простых задач.
Предельное число итераций – ограничивает время, требующееся для отыскания решения, путем ограничения числа итераций. Это значение должно быть положительным целым числом до 32767.
Относительная погрешность – контролирует точность ответов, получаемых при поиске решений. Поле должно содержать число в интервале от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность.
Высокая точность увеличивает время, которое требуется для того, чтобы сошелся процесс оптимизации.
Допустимое отклонение – служит для задания величины отклонения от оптимального решения, если изменяемые ячейки ограничены множеством целых чисел. Чем выше отклонение (допустимое отклонение в процентах), тем быстрее процесс решения. Установка отклонения не играет роли, если не введены целочисленные ограничения.
Сходимость – применяется только к нелинейным задачам. Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск оптимального решения прекращается.
Установка флажка Линейная модель обеспечивает ускорение поиска решения линейной задачи за счет применения симплекс-метода.
Флажок Показывать результаты итераций позволяет по шагам следить за поиском решения.
Флажок Автоматическое масштабирование включается в том случае, когда разброс значений параметров очень велик.
Подтвердите установленные параметры нажатием кнопки ОК;

запустить задачу на решение (в окне Поиск решения кнопка Выполнить)
(см. рис. 1.1.7);

после запуска на решение задачи на экране появится диалоговое окно
Результаты поиска решения с одним из трех сообщений:
1)
Решение найдено. Все ограничения и условия оптимальности
выполнены (рис. 1.1.10).
Рис. 1.1.10. Диалоговое окно Результаты поиска решения

12 2)
Значения целевой ячейки не сходятся. Такое сообщение выдается в случае неограниченности целевой функции.
3)
Поиск не может найти подходящего решения. Такое сообщение выдается в случае несовместимости системы ограничений.
Иногда сообщения 2 и 3 свидетельствуют не о характере оптимального решения задачи, а о том, что при вводе условий задачи в MS Office Excel были допущены ошибки, не позволяющие Excel найти оптимальное решение, которое в действительности существует.
В нашем примере в результате решения задачи появляется сообщение
«Решение найдено. Все ограничения и условия оптимальности выполнены»
(см. рис. 1.1.10).
Таким образом, предприятие должно выпускать в сутки 312,5 кг продукции П
1
и 300 кг продукции П
2
, при этом доход от реализации продукции составит 9200 рублей (рис. 1.1.11).
Рис. 1.1.11. Экранная форма задачи после получения решения
В окне Результаты поиска решения представлены названия трех типов отчетов (см. рис. 1.1.10): Результаты, Устойчивость и Пределы.
Каждый отчет появляется на отдельном листе рабочей книги. Для того, чтобы просмотреть отчет, достаточно выделить его название в списке Тип
отчета.
Отчет Результаты состоит из трех таблиц (рис. 1.1.12):
1) таблица 1 содержит информацию о целевой функции (в нашем примере о максимальном значении);
2) таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи;
3) таблица 3 показывает результаты оптимального решения для исходных ограничений и граничных условий.