Файл: Методы оптимизации лабораторный практикум.pdf

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Рубцовский институт (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования Алтайский государственный университет»
МЕТОДЫ ОПТИМИЗАЦИИ ЛАБОРАТОРНЫЙ ПРАКТИКУМ
Учебно-методическое пособие Рубцовск 2016
© Рубцовский институт (филиал) АлтГУ, Об издании –
1
,
2

сведения об издании
УДК 51:007(076.5)
ББК я 73-5 М 545 Составитель АС. Шевченко Рецензент Доцент, кандидат технических наук Е.А. Жданова М 545 Методы оптимизации лабораторный практикум учебно- методическое пособие Электронный ресурс / АлтГУ, Рубцовский ин-т (фил сост. АС. Шевченко. – Электрон. текст. дан.
(3,1 Мб). – Рубцовск Рубцовский институт (филиал) АлтГУ,
2016. – 1 эл. оп. диск (CD-R). – Систем. требования PCI, Intel
Pentium, 1 ГГц 256 Мб опер. памяти 30 Мб свобод. диск. пространства ОС Windows XP и выше Adobe Reader. – Загл. с экрана.
Учебно-методическое электронное издание Лабораторный практикум содержит краткие теоретические сведения и примеры решения типовых задач с помощью математических пакетов и электронных таблиц MS Excel. Каждая лабораторная работа содержит по 10 вариантов индивидуальных заданий. Пособие предназначено для студентов, обучающихся по направлению подготовки Прикладная информатика, а также для преподавателей вузов, инженеров и научных работников.
© Рубцовский институт (филиал) АлтГУ, 2016

производственно-технические сведения Редактор КГ. Анисимов Верстка АС. Шевченко Дата подписания к использованию 01.02.2016 Объем издания 3,1 Мб Комплектация издания 1 эл. оп. диск (CD-R) Тираж 50 дисков Рубцовский институт (филиал) АлтГУ
658225, Рубцовск, пр. Ленина, 200 Б

Содержание
ПРЕДИСЛОВИЕ ЛАБОРАТОРНАЯ РАБОТА №1 ЗАДАЧА СОСТАВЛЕНИЯ РАЦИОНА Необходимые теоретические сведения
Исходные данные для лабораторной работы
ЛАБОРАТОРНАЯ РАБОТА №2 ТРАНСПОРТНАЯ ЗАДАЧА Необходимые теоретические сведения
Исходные данные для лабораторной работы
ЛАБОРАТОРНАЯ РАБОТА №3 ЗАДАЧА О НАЗНАЧЕНИЯХ Необходимые теоретические сведения
Исходные данные для лабораторной работы
ЛАБОРАТОРНАЯ РАБОТА №4 ЗАДАЧИ НА БЕЗУСЛОВНЫЙ ЭКСТРЕМУМ Необходимые теоретические сведения
Исходные данные для лабораторной работы
ЛАБОРАТОРНАЯ РАБОТА №5 ЗАДАЧИ НА УСЛОВНЫЙ ЭКСТРЕМУМ Необходимые теоретические сведения
Исходные данные для лабораторной работы
ЛАБОРАТОРНАЯ РАБОТА №6 ЗАДАЧА КОММИВОЯЖЕРА Необходимые теоретические сведения
Исходные данные для лабораторной работы
ЛАБОРАТОРНАЯ РАБОТА №7 ЗАДАЧА О МИНИМАЛЬНОМ ПУТИ В ГРАФЕ Общая постановка задачи
Исходные данные для лабораторной работы
ЛАБОРАТОРНАЯ РАБОТА №8 МАТРИЧНЫЕ ИГРЫ Необходимые теоретические сведения
Исходные данные для лабораторной работы
ЛИТЕРАТУРА

ПРЕДИСЛОВИЕ
Одной из ключевых компетентностей будущего специалиста как экономического, таки технического профилей является способность применения математических методов в сочетании с информационными технологиями. Способность достижения значимых результатов в профессиональной деятельности часто напрямую связана с осведомленностью оме- тодах и способах решения математических задач с использованием специального программного обеспечения. Владение хотя бы одной из систем компьютерной математики (Maple, Mathematica, MathCAD, MatLab, Maxi- ma и др) позволяет будущему специалисту, не владеющему в полной мере техникой математических преобразований, самостоятельно выполнять громоздкие вычисления, решать сложные прикладные задачи. В лабораторном практикуме изложены необходимые основы математического аппарата и примеры его использования в современных экономических приложениях. Основной упор сделан на приобретение навыков использования математического аппарата и формирования умений решения, поставленных задач, с помощью доступного программного обеспечения математические пакеты Maple, Mathcad Prime и среда электронных таблиц
MS Excel. Каждый тип задач сопровождается подробным пошаговым описанием составления математической модели задачи и путей решения. Содержание лабораторного практикума составлено в соответствии с учебной программой и на основе курса лекций по дисциплине Методы оптимизации Лабораторный практикум предназначен для студентов всех форм обучения направления подготовки Прикладная информатика при изучении дисциплины Методы оптимизации. Отдельные темы могут быть использованы для изучения студентами направления подготовки Менеджмент, Государственное муниципальное управление, Экономика.

ЛАБОРАТОРНАЯ РАБОТА №1 ЗАДАЧА СОСТАВЛЕНИЯ РАЦИОНА Цель работы овладеть навыками составления математической модели задачи о диете и ее решения в математических пакетах Maple, Mathcad
Prime ив. Требуется
− изучить теоретический материал выполнить математическую постановку задачи
− решить задачу в математических пакетах Maple, Mathcad Prime ив среде электронных таблиц MS Excel. Необходимые теоретические сведения Другая классическая задача линейного программирования связана с проблемой подбора оптимального набора пищевых продуктов для составления диеты. Задача имеет следующее экономическое содержание. Рассмотрим условную ситуацию. Дневная диета содержит m видов различных питательных веществ
1 2
,
,
,
m
S S
S соответственно не менее
1 2
,
,
,
m
b b
b условных единиц. Имеется n различных видов продуктов
1 2
,
,
,
n
P P
P , каждый из которых содержит m видов питательных веществ, например, жиров, белков, углеводов. Обозначим
ij
a − содержание в весовых единицах го питательного вещества в единице веса го продукта,
j
c


1,
j
n

− стоимость единицы веса продукта с номером j. Необходимо определить состав и количество продуктов, необходимых для включения в диету. При этом суточные потребности должны быть удовлетворены с минимальными денежными затратами. Сведем данные условия в таблицу 1.1. Составим экономико-математическую модель задачи. Введем обозначения
1
x
– количество потребления продукта вида
1
P
,
2
x
– количество потребления продукта вида
2
P
,
…
n
x – количество потребления продукта видав сутки. В результате потребления
1
x
ед. продукта вида
1
P
содержание питательного вещества
1
S
в суточной норме потребления составит
11 1
a x
усл. единиц. Общее содержание питательного вещества
1
S
в рационе определяется выражением
11 1 12 ах а ха x



. Поскольку содержание питательного вещества
1
S
в рационе не должно быть меньше минимальной суточной потребности организма, те. величины
1
b
, то должно выполняться неравенство ах а ха x
b

 

. В общем виде, содержание го питательного вещества в рационе не должно быть меньше
i
b , поэтому необходимо выполнение неравенства
1 1 2 ах а ха x
b

 

. Выполнение подобных ограничений описывает требование к диете, которое разрешает потреблять каждый вид питательного вещества в объеме не менее минимальной суточной потребности организма. Таблица 1.1 – Исходная информация задачи о диете Виды питательных веществ Виды продуктов Минимальная суточная потребность в питательном веществе, усл.ед.
1
P
2
P
…
j
P
…
n
P
1
S
11
a
12
a
…
1 j
a
…
1n
a
1
b
2
S
21
a
22
a
…
2 j
a
…
2n
a
2
b
…
…
…
i
S
1
i
a
2
i
a
…
ij
a
…
in
a
i
b
…
…
…
m
S
1
m
a
2
m
a
…
mj
a
…
mn
a
m
b Стоимость единицы веса продукта
1
c
2
c
…
j
c
… Кроме того,
1 2
,
,...,
0
n
x x
x

, так как количество потребляемых продуктов не может быть отрицательным числом. Стоимость всего рациона определяет линейная функция
 
1 1 2
2
n
n
Z X
c x
c x
c x


 Итак, экономико-математическая формулировка задачи о диете имеет вид найти неотрицательные значения переменных


1 2
,
,...,
n
X
x x
x

, удовлетворяющих условиям
11 1 12 2
1 1
21 1 22 2
2 2
1 1 2
2 1
2
,
,
,
ах а ха x
b
a x
a x
a x
b
a x
a x
a x
b
x x
x





















и минимизирующих функцию
 
1 1 2
2
min
n
n
Z X
c x
c x
c x


 Рассмотрим задачу с конкретными данными. Пример. Пусть имеются 8 видов продуктов содержащих 9 питательных веществ и незаменимых компонент. В 100 граммах продукта содержится известное
ij
a количество питательного вещества или незаменимого компонента. Кроме того, известны
i
b
– ежесуточная минимальная потребность организма в веществах


1,9
i
S
i

,
j
c и
j
e – стоимость и энергетическая ценность (в килокалориях) 100 грамм продукта Все указанные величины представлены в табл. 1.2. Требуется рассчитать суточную диету так, чтобы обеспечить необходимое количество питательных веществ и незаменимых компонент при минимальных затратах на продукты. Найти калорийность K полученной оптимальной диеты. Решение Для решения сформулированной задачи составим ее математическую модель.
1. Введем обозначения
j
x − неизвестное пока количество (грамм) продукта, входящего в диету.
2. Составим целевую функцию – стоимость диеты
 


8 1
1 2
3 4
5 6
7 8
1 100 1
1.6 10 7
2.6 13 11 3
2.5
min.
100
j
j
j
Z X
c x
x
x
x
x
x
x
x
x













(1.1)

Таблица 1.2 − Данные к задаче о диете Питательные вещества Мин. суточная потребность, г Содержание питательных веществ в 100 г продукта
Хл
еб
ржа
н
ой
М
асл
о Творог
ж
и
рн
ы
й
К
ру
п
а
греч
н
ев
ая
М
ясо
св
и
н
ое
К
ол
ба
са
ва
рен
ая
Яб
л
ок
и
М
орк
ов
ь Белки
90 6.6 0.5 14 12.6 14.3 12.1 0.4 1.3 Жиры
95 1.2 82.5 18 3.3 33.3 13.5 0.4 0.1 Углеводы
330 34.2 0.8 2.8 62.1 0
0 9.8 7.2 Ретинол витамин А)
0.00017 0
0.54 0.1 0
0 0
0 0 Каротин (витамин А)
0.0059 0
0.38 0.06 0.01 0
0 0.03 9 Витамин
1
B
0.0013 0.18 0
0.05 0.43 0.4 0.06 0.03 0.06 Витамин
2
B
0.0017 0.08 0.1 0.3 0.2 0.1 0.13 0.02 0.07 Витамин РР
0.018 0.67 0.05 0.3 4.19 2.2 0
0.3 1 Витамин С
0.08 0
0 0.3 0
0 0
165 5 Стоимость 100 г продукта руб)
1.6 10 7
2.6 13 11 3
2.5 Энергетическая ценность 100 г продукта (Ккал)
181 748 239 335 491 170 45 34 3. Сформулируем ограничения рассматриваемой задачи. По минимальным потребностям организма. Это ограничение можно записать в виде







1 2
3 4
5 6
7 8
1 2
3 4
5 6
7 8
1 2
3 4
5 6
7 8
1 2
3 4
5 6
1 6.6 0.5 14 12.6 14.3 12.1 0.4 1.3 90,
100 1
1.2 82.5 18 3.3 33.3 13.5 0.4 0.1 95,
100 1
34.2 0.8 2.8 62.1 0
0 9.8 7.2 330,
100 1
0 0.54 0.1 0
0 0
100
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x





































7 8
1 2
3 4
5 6
7 8
1 2
3 4
5 6
7 8
1 2
3 4
5 6
7 8
0 0
0.00017,
1 0
0.38 0.06 0.01 0
0 0.03 9
0.0059,
100 1
0.18 0
0.05 0.43 0.4 0.06 0.03 0.06 0.0013,
100 1
0.08 0.1 0.3 0.2 0.1 0.13 0.02 0.07 0.0017,
100 1
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x































1 2
3 4
5 6
7 8
1 2
3 4
5 6
7 8
0.67 0.05 0.3 4.19 2.2 0
0.3 1
0.018,
00 1
0 0
0.3 0
0 0
165 5
0.08.
100
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x









































(1.2) В левой части каждого неравенства записано фактическое суточное потребление питательных веществ и незаменимых компонент. Условие неотрицательности:


0 1,8
j
x
j


(1.3)
4. После нахождения оптимального решения рассчитаем калорийность полученной диеты


8 1
2 3
1 4
5 6
7 8
1 1
181 748 239 100 100 335 491 170 45 34
опт
опт
опт
опт
j
j
j
опт
опт
опт
опт
опт
K
e x
x
x
x
x
x
x
x
x












(1.4) Таким образом, целевая функция (1.1) и ограничения (1.2−1.3) и формула (1.4) образуют математическую модель задачи о диете. Решение задачи в пакете Maple Подключаем пакет simplex:
>with(simplex):
2. Задаем целевую функцию
>Z:=1/100*(1.6*x[1]+10*x[2]+7*x[3]+2.6*x[4]+13*x[5]+11*x[6]+3*x[
7]+2.5*x[8]):
3. Задаем систему ограничений

>C:={1/100*(6.6*x[1]+0.5*x[2]+14*x[3]+12.6*x[4]+14.3*x[5]+12.1*x[
6]+0.4*x[7]+13*x[8])>=90,
1/100*(1.2*x[1]+82.5*x[2]+18*x[3]+3.3*x[4]+33.3*x[5]+13.5*x[6]+0.4*x[7]+
0.1*x[8])>=95,
1/100*(34.2*x[1]+0.8*x[2]+2.8*x[3]+62.1*x[4]+0*x[5]+0*x[6]+9.8*x[7]+7.2*
x[8])>=330,
1/100*(0*x[1]+0.54*x[2]+0.1*x[3]+0*x[4]+0*x[5]+0*x[6]+0*x[7]+0*x[8])>=0
.00017,
1/100*(0*x[1]+0.38*x[2]+0.06*x[3]+0.01*x[4]+0*x[5]+0*x[6]+0.03*x[7]+9*x
[8])>=0.0059,
1/100*(0.18*x[1]+0*x[2]+0.05*x[3]+0.43*x[4]+0.4*x[5]+0.06*x[6]+0.03*x[7]
+0.006*x[8])>=0.0013,
1/100*(0.08*x[1]+0.1*x[2]+0.3*x[3]+0.2*x[4]+0.1*x[5]+0.13*x[6]+0.02*x[7]+
0.07*x[8])>=0.0017,
1/100*(0.67*x[1]+0.05*x[2]+0.3*x[3]+4.19*x[4]+2.2*x[5]+0*x[6]+0.3*x[7]+1
*x[8])>=0.018, Находим оптимальное решение задачи Находим минимальное значение функции Z в найденных точках минимальную стоимость Задаем энергетическую ценность 100 г продукта (Ккал Найденное оптимальное решение записываем в виде вектора
>xopt:=array([0,86.71755999,0,710.8430021,0,0,0.04848487988,0]);
8. Находим энергетическую ценность диеты
>K:=sum(xopt[i]*E[i],i=1..8)/100;

Решение задачи в пакете Mathcad Prime Для решения задачи в пакете Mathcad Prime необходимо Задать исходные данные. На вкладке Математика выбрать Блок решения. В области Начальные приближения присвоить переменным, те. вектору X начальные (любые, например, нулевые) значения и определить целевую функцию – стоимость разрабатываемой диеты. В области Ограничения ввести все необходимые ограничения. В области «Решатель» найти оптимальное решение с помощью функции minimize, вычислить минимальное значение стоимости полученной диеты и ее энергетическую ценность.

Решение задачи в среде электронных таблиц MS Excel Идентифицируйте свою работу, переименовав Лист 1 в Титульный лист и записав номер лабораторной работы, ее название, кто выполнили проверил. Наследующем листе (см. рис, с именем Задача составления рациона, создайте таблицу для ввода условий задачи и введите исходные данные. Таблицу дополните столбцом Фактическое суточное потребление. Создайте вторую таблицу, указав в ней продукты диеты и переменные математической модели. В ячейках D17:K17 поместите нулевые начальные) значения искомых переменных
1 2
8
,
,
,
x В ячейку D18 введите формулу целевой функции – стоимости рассчитываемой диеты. Это можно осуществить двумя способами. Способ введите формулу

  1   2   3   4   5   6   7   8