ПРИЕМ УЧАЩИХСЯ В ДШИ № 13 в 2015 году;pdf

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ
ДЛЯ СТУДЕНТОВ НАПРАВЛЕНИЯ
230100 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА (АСУ)»
СОСТАВИТЕЛЬ: СТ. ПР. АСТАХОВА Л.Г.
1
СОДЕРЖАНИЕ
1. Лабораторная
работа
№1
(4ч.)
Решение
задач
линейного
программирования…………………………………………………………………..1
2. Лабораторная
работа
№2(4ч.)
Двойственная
задача
линейного
программирования………………………………………………………………..…2
3. Лабораторная
работа №3. (6ч.) Графическое решение задач линейного
программирования. Анализ устойчивости……………………………………….4
4. Лабораторная работа №4(4ч.) Транспортная задача…..………………………5
5. Лабораторная работа № 5(4ч.) Алгоритм Гомори.....................………………..7
6. Лабораторная работа №6 (4ч.) Метод ветвей и границ………………………11
7. Лабораторная работа № 7(4ч.) Динамическое программирование……………..13
8. Лабораторная работа № 8(6ч.)Нелинейное программирование. Определение
экстремума функции при линейных ограничениях……………….……………….16
2
Лабораторная работа №1 (4ч.)
Тема: Решение задач линейного программирования.
программирования
Цель работы – знакомство с методами решения задач линейного программирования
программирования, их
освоение, а также сравнение эффективности применения этих методов для конкретных целевых
функций.
Теоретические сведения
Для того, чтобы мы могли говорить,
говорить что имеем дело с оптимизационной
оптимизационн задачей, должны быть
определены:
a) целевая функция (целевые
целевые функции
функции) => однокритериальная (многокритериальная
многокритериальная) задача;
b) переменная (переменные), от которой (которых) зависит целевая функция => однопараметрическая
(многопараметрическая) задача;
c) ограничения на функции или (и)
(и переменные => безусловная (ограничений
ограничений нет) и условная
(ограничения есть) оптимизация.
Оптимизационная задача – это математическая задача, которая состоит в нахождении
значений переменных, которые
которые, во
во-первых, удовлетворяют ограничениям,
ниям, а,
а во-вторых,
во
доставляют
наилучшее (max; min) значение целевой функции.
ЗЛП – задача, математическая модель которой имеет вид:
Если в задач целевая функция стремится к min, а ограничения заданы равенствами,
равенствами то говорят,
что задача представлена в канонической
нонической форме.
Рассмотрим алгоритм симлекс-метода
метода более неформально на задаче на максимизацию функции
и следующими ограничениями:
Перед чтением лучше ознакомиться с некоторой литературой по теме, так как иначе некоторые
термины, используемые в статье,
ье, и шаги алгоритма могут быть непонятны.
Задание.
1.
Решить ЗЛП Симплекс-методом
методом.
2.
Написать программу.
Вариант 1
Вариант 5
Вариант 9
Вариант 2
Вариант 10
Вариант 6
3
Вариант 3
Вариант 7
Вариант 4
Вариант 8
Вариант 11
Лабораторная работа №2(4ч
№2(4ч.)
Тема: Двойственная задача линейного программирования.
Цель работы – знакомство с методами решения задач линейного программирования
программирования, их
освоение, а также сравнение эффективности применения этих методов для конкретных целевых
функций.
Теоретические сведения
Оптимизационная задача – это математическая задача, которая состоит
состо
в нахождении
значений переменных, которые
которые, во
во-первых, удовлетворяют ограничениям, а,
а во-вторых,
во
доставляют
наилучшее (max; min) значение целевой функции.
ЗЛП – задача, математическая модель которой имеет вид:
Если в задач целевая функция стремится к min, а ограничения заданы равенствами,
равенствами то говорят,
что задача представлена в канонической форме.
Каждой задаче линейного программирования соответствует так называемая двойственная
задача. В ней по сравнению с исходной задачей строки переходят в столбцы,
столбцы неравенства меняют
знак, вместо максимума ищется минимум (или, наоборот, вместо минимума - максимум). Задача,
4
двойственная к двойственной - эта сама исходная задача. Сравним исходную задачу (слева) и
двойственную к ней (справа):
45 Х1+ 80 Х2 → max ,
400 W1 + 450 W2 → min ,
5 Х1+ 20 Х2 ≤ 400 ,
5 W1 + 10 W2 ≥ 45,
10 Х1 + 15Х2 ≤ 450 ,
20 W1 + 15 W2 ≥ 80,
Х1 ≥ 0 ,
W1 ≥ 0,
Х2 ≥ 0 .
W2 ≥ 0.
Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых
функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с
минимумом в двойственной). При этом оптимальные значения W1 и W2 показывают стоимость
материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать
с рыночными ценами этих факторов производства, W1 и W2 называют "объективно обусловленными
оценками" сырья и рабочей силы.
Линейное программирование как научно-практическая дисциплина.Из всех задач оптимизации
задачи линейного программирования выделяются тем, что в них ограничения - системы линейных
неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном
линейном пространстве. Целевые функции также линейны.
Задания.
К данной ЗЛП составить двойственную задачу и решить симплекс – методом. Написать
программу.
Вариант 1
Вариант 5
Вариант 9
Вариант 2
Вариант 6
Вариант 10
Вариант 3
Вариант 7
Вариант 11
Вариант 4
Вариант 8
5
Лабораторная работа №3. (6ч.)
Тема: Графическое решение задач линейного программирования
программирования. Анализ устойчивости.
устойчивости
Цель работы – знакомство с методами решения задач линейного программирования
программирования, их
освоение, а также сравнение эффективности применения этих методов для конкретных целевых
функций.
Теоретические сведения
Для того, чтобы мы могли говорить,
говорить что имеем дело с оптимизационной
оптимизационн задачей, должны быть
определены:
d) целевая функция (целевые
целевые функции
функции) => однокритериальная (многокритериальная
многокритериальная) задача;
e) переменная (переменные), от которой (которых) зависит целевая функция => однопараметрическая
(многопараметрическая) задача;
f) ограничения на функции или (и)
(и переменные => безусловная (ограничений
ограничений нет) и условная
(ограничения есть) оптимизация.
Оптимизационная задача – это математическая задача, которая состоит в нахождении
значений переменных, которые
которые, во
во-первых, удовлетворяют ограничениям,
ниям, а,
а во-вторых,
во
доставляют
наилучшее (max; min) значение целевой функции.
ЗЛП – задача, математическая модель которой имеет вид:
Если в задач целевая функция стремится к min, а ограничения заданы равенствами,
равенствами то говорят,
что задача представлена в канонической форме.
Задания.
Решить ЗЛП графическим методом
методом. Написать программу.
6
Вариант 1
Вариант 5
Вариант 9
Вариант 2
Вариант 6
Вариант 10
Вариант 3
Вариант 7
Вариант 11
Вариант 4
Вариант 8
Лабораторная работа №4(4ч.)
Тема: Транспортная задача.
Цель работы – знакомство с методами построения опорного плана транспортной задачи и
методом потенциалов для нахождения оптимального плана. Освоение метода потенциалов.
Теоретические сведения
Задача заключается в том, чтобы организовать план перевозок товара от поставщиков к
потребителям таким образом, чтобы стоимость перевозок была минимальна. При этом весь товар
должен быть вывезен, и все потребители удовлетворены.
7
Задание.
Найти опорный план:
1. По методу «Северо-западного
западного угла»
2. По методу «Минимального
Минимального элемента
элемента»
3. По методу Фогеля.
Решить задачу методом потенциалов и распределительным методом.
Написать программу.
1. Найти оптимальный план транспортной задачи:
А1
В1
5
В2
4
В3
3
В4
4
запасы
160
А2
3
2
5
5
140
А3
1
6
3
2
60
80
60
80
потребности 80
2. Найти оптимальный план транспортной задачи:
А1
В1
4
В2
2
В3
3
В4
1
запасы
60
А2
6
3
5
6
140
А3
3
2
6
3
70
50
50
70
потребности 80
8
3. Найти оптимальный план транспортной задачи:
А1
В1
6
В2
7
В3
3
В4
2
запасы
180
А2
5
1
4
3
90
А3
3
2
6
2
170
45
100
160
потребности 45
4. Найти оптимальный план транспортной задачи:
А1
В1
6
В2
7
В3
3
В4
2
запасы
150
А2
5
1
4
3
50
А3
3
2
6
2
160
100
75
60
потребности 75
Лабораторная работа № 5(4ч.)
Тема: Алгоритм Гомори.
Цель работы - ознакомиться с методами целочисленного линейного программирования.
Методические указания
Для решения полностью целочисленных задач использовать первый алгоритм Гомори. Для
решения частично целочисленных задач используется второй алгоритм Гомори.
Порядок выполнения работы
1. В соответствии с вариантом задания решить задачу целочисленного линейного программирования.
Для задач с двумя переменными проиллюстрировать полученные отсечения графически.
2. Сгенерировать задачу линейного программирования небольшой размерности и выполнить ручной
просчет одним из методов Гомори (по указанию преподавателя). Проиллюстрировать полученные
отсечения графически.
Варианты заданий
1. Три вида деталей можно производить на станках двух разных типов. Производительность станков и
себестоимость одной детали каждого вида указаны в следующей таблице:
Вид деталей
1
2
3
Производительность станков (деталей
в час)
1 тип
2 тип
20
30
50
45
20
60
Станки могут работать не более 12 и 8 часов соответственно. На рынок имеет смысл поставлять не
отдельные детали, а комплекты. Комплект состоит из 16 деталей первого вида, 12 деталей второго
9
вида и 24 детали третьего вида. Требуется максимизировать количество комплектов, поступающих на
рынок.
2. В цехе предприятия решено установить дополнительное оборудование, для размещения которого
выделено 19/3 м2 площади. На приобретение оборудования предприятие может израсходовать 10 тыс.
руб., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1000
руб., а II вида — 3000 руб. Приобретение одного комплекта оборудования I вида позволяет увеличить
выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида — на 4 ед. Зная, что для
установки одного комплекта оборудования I вида требуется 2 м2 площади, а оборудования II вида —
1 м2 площади, определить такой набор дополнительного оборудования, который дает возможность
максимально увеличить выпуск продукции.
3. Министерству необходимо составить план развития каждого из 4 предприятий, выпускающих
однородную продукцию. Число возможных вариантов развития i-гo предприятия равно 4. Реализация
j-ого варианта развития i-го предприятия обеспечивает выпуск продукции в объеме bij млн. единиц.
При этом экономический эффект развития i-ого предприятия по j-ому варианту равен сij. Составить
такой план развития предприятий, при котором экономический эффект от реализации выбранных
вариантов развития предприятий является максимальным.
B
C
8 5 6 8 9/8 6/5 7/6 9/8
6787
7/6 8/7 9/8 8/7
7 5 7 8 8/7 6/5 8/7 9/8
7 6 8 6 8/7 7/6 9/8 7/6
4. Для выполнения четырех видов землеройных работ могут быть использованы экскаваторы четырех
типов. Производительность экскаватора i-го типа при выполнении j-й работы задается матрицей
0,9 0,6 0,7 0,9
0,7 0,8 0,9 0,8
0,8 0,6 0,8 0,9
0,8 0,7 0,9 0,7
Учитывая, что на каждой из работ может быть занят только лишь один экскаватор и что все
экскаваторы должны быть задействованы, найти такое распределение экскаваторов между работами,
которое обеспечивает максимальную производительность.
5. Пароход может быть использован для перевозки 11 наименований груза, масса, объем и цена
единицы каждого из которых приведены в следующей таблице:
Параметры
Номер груза
единицы груза
1
2
3
4
5
6
7
8
9
10 11
Масса (т)
80 62 92 82 90 60 81 83 86 65 83
Объем (м2)
Цена (тыс. руб)
100 90
4,4 2,7
96
3,2
110 120 80
2,8 2,7 2,8
114 60
3,3 3,5
106 114 86
4,7 3,9 4,0
На пароход может быть погружено не более 800 т груза общим объемом, не превышающим 600 м2.
Определить, сколько единиц каждого груза следует поместить на пароход так, чтобы общая
стоимость размещенного груза была максимальной.
6. Плановое задание по изготовлению 2 видов костюмов необходимо распределить между 3
швейными фабриками. Производственные мощности i -й фабрики ( i = 1,2,3 ) позволяют за
рассматриваемый период времени выпустить rij костюмов j -й модели ( j =1,2). При этом, если все
производственные мощности фабрики идут на производство костюмов одного типа, то костюмы
10
других видов производиться не могут. Заданы величины себестоимости sij изготовления j -й модели
на i -й фабрике.
- плановое задание
Требуется найти оптимальный план производства при условии минимизации себестоимости при
допустимости перевыполнения планового задания.
7. Полуфабрикаты поступают на предприятие в виде листов фанеры. Всего имеется две партии
материала, причем первая партия содержит 400 листов, а вторая 250 листов фанеры. Из поступающих
листов фанеры необходимо изготовить комплекты двух видов. Комплект первого вида включает 4
детали 1-го типа, 3 детали 2-го типа и 2 детали 3-го типа. Комплект второго вида включает 2 детали 1го типа, 4 детали 2-го типа и 3 детали 3-го типа. Лист фанеры каждой партии может раскраиваться
различными способами.
Количество деталей каждого типа, которое получается при раскрое одного листа
соответствующей партии по тому или иному способу раскроя, представлено в следующей таблице.
Стоимость одного листа первой партии составляет 100 руб., а стоимость одного листа второй
партии – 120 руб. Цена комплекта первого вида составляет 160 руб., цена комплекта второго вида –
200 руб.
Способ раскроя
Способ раскроя
Детали
(1 п)
Детали
(2 п)
1
2
3
1
2
1
0
6
9
1
6
5
2
4
3
4
2
5
4
3
10
16
0
3
8
0
Требуется раскроить материал так, чтобы обеспечить максимальную прибыль от продажи всех
комплектов деталей.
8. Для народного ополчения необходимо оружие – топоры, вилы и деревянные дубинки. Для
производства одного топора, необходимо 4 кг железа и 3 кг – берёзы. Для производства одних вил,
необходимо 2 кг железа и 4 кг ясеня. Для деревянной дубинки требуется 5 кг ясеня и 3 кг берёзы.
Ресурсы ополченцев ограничены: 40 кг железа, 100 кг ясеня и 45 кг берёзы.
Задача: вооружить любым оружием максимальное число ополченцев.
Содержание отчета
Отчет по работе должен содержать титульный лист, цель работы, вариант задания,
графическую иллюстрацию решения с полученными отсечениями, выводы.
№ варианта
1
Сложность задания 10
(максимальное
количество баллов)
2
11
3
11
4
9
5
11
6
12
7
11
8
10
11
1.
2.
3.
4.
Контрольные вопросы
Первый алгоритм Гомори.
Второй алгоритм Гомори.
Третий алгоритм Гомори.
Понятие лексикографического отсечения
Задание 1.
Решить методом Гомори-1 задачи целочисленного линейного программирования, условия
которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также
следующие задачи.
Во всех задачах, которые предлагаются ниже, все переменные неотъемлемые и целые.
1)
5 x1 + 6 x2 + 6 x3 → min
2 x1 + 4 x2
≥ 10
3 x1 + 2 x2 + 2 x3 ≥ 10;
2)
6 x1 + 4 x2 → min
2 x1 + x2 ≥ 3
x1 – x2 ≤ 1;
3)
6 x1 + 4 x2 → min
2 x1 + x2 ≥ 3
x1 – 2 x2 ≤ 2
3 x1 + 2 x2 ≥ 1;
4)
x1 + x2 → min
– x1 – x2
+ x5 = –1
–2 x1 + 2 x2 + x3
= –2
–4 x1 + 2 x2
+ x4
= –1;
5)
6 x1 + 4 x2 → min
2 x1 + x2 ≥ 3
x1 – x2 ≥ 1;
6)
2 x1 + 3 x2 → min
x1 + 2 x2 ≥ 16
2 x1 + x2 ≥ 16;
8)
5 x2
+ 7 x4 → min
= –16
– 10 x2 + x3 + x4
x1 – 3 x2
– 3 x4
= –12
– 6 x2
– 2 x4 + x5 = –17;
7)
5 x1
3 x1
2 x1
x1
9)
x1
– 3 x2 → max
+ 2 x2 ≥ 6
– 3 x2 ≥ – 6
– x2 ≤ 4
– 5 x4 – 7 x5 → max
– x4 – 2 x5 = – 7
– x3 + 3 x4 – 6 x5 = – 3
– x4 – 4 x5 = –11;
x2
10)
8 x1 + 2 x2 → max
x1 – 4 x2 + x3
=4
– 4 x1 + x2
+ x4
=4
x1 + x2
+ x5 = 6.
Ответы:
1) x* = (3; 1; 0), L(x*)= 21.
2) x* = (1; 1),
L(x*)= 10.
3) x* = (1; 1),
L(x*)= 10.
4) x* = (1; 0; 0; 3; 0), L(x*)= 1.
5) x* = (2; 0),
L(x*)= 12.
6) x* = (6; 5),
L(x*)= 27.
7) x* = (18; 14), L(x*)= 48.
8) x* = (0; 4; 24; 0; 7), L(x*)= 20.
9) x* = (0; 0; 0; 3; 2), L(x*)= −29.
10) x* = (5; 1; 0; 0; 0), L(x*)= 42.
Задание2.
Решить методом Гомори-2 задачи частично целочисленного линейного программирования,
условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9),
а также следующие задачи.
12
1)
x1 + 8 x2 → max
3 x1 + x2 ≤ 9
0.16 x1 + x2 ≤ 1.9
xj ≥ 0, xj — целое, j = 1,2;
2)
– 6 x1 – x2 → min
– 2.9 x1 + 6 x2 ≤ 17.4
3 x1 – x2 ≤ 1
xj ≥ 0, xj — целое, j = 1,2;
3)
0.25 x1 +
x2 → max
x2 ≤ 1.75
0.5 x1 +
x1 + 0.3 x2 ≤ 1.5
xj ≥ 0, xj — целое, j = 1,2;
4)
– 2 x1 – 4 x2 → min
2 x1 + x2 ≤ 19.33
x1 + 3 x2 ≤ 10
xj ≥ 0, xj — целое, j = 1,2;
5)
x1 + x2 → max
2 x1 + 11 x2 ≤ 38
x1 + x2 ≤ 7
4 x1 – 5 x2 ≤ 5
xj ≥ 0, j = 1,2, x2 — целое;
6)
x1 + x2 → max
2 x1 + 11 x2 ≤ 38
x1 +
x2 ≤ 7
4 x1 – 5 x2 ≤ 5
xj ≥ 0, j = 1,2, x1 — целое;
7))
→ max
x1
x1 + 3 x2 ≤ 12
3 x1 – 8 x2 ≤ 24
xj ≥ 0, j = 1,2, x1 — целое;
8)
– 8 x1 – 6 x2
→ min
3 x1 + 5 x2 + x3
= 11
4 x1 + x2
+ x4 = 8
xj ≥ 0, j = 1,2, x1 — целое.
Ответы:
1) x* = (2; 1),
L(x*)= 10.
2) x* = (1; 3),
L(x*)= –9.
3) x* = (1; 1),
L(x*)= 1.25.
4) x* = (7; 1),
L(x*)= –18.
5) x* = (3.75; 2), L(x*)= 5.75.
6) x* = (4; 2.73), L(x*)= 6.73.
7) x* = (9; 0.38), L(x*)= 9.
8) x* = (1; 1.6; 0; 2.41), L(x*)= –17.6.
Лабораторная работа №6 (4ч.)
Тема: МЕТОД ВЕТВЕЙ И ГРАНИЦ.
Цель работы – знакомство с методом ветвей и границ, его освоение.
Теоретические сведения
Постановка целочисленной задачи линейного программирования (ЦЗЛП).
Найти вектор x = (x 1 ...,x n ), что минимизирует целевую функцию
L( x ) = c 1 x 1 + ... + c n x n
и удовлетворяет систему ограничений
a 1 1 x 1 + . . . + a 1 n x n R 1 a1 0
.......................
a m 1 x 1 + . . . + a m n x n R m am 0
x j ≥ 0 , j=1...,n
x j — цели, j=1...,n.
где символ R i (i=1...,m) заменяет один из знаков: ≤ , = , ≥ .
Алгоритм метода Ленд-Дойга.
(1)
(2)
(3)
(4)
13
1.
Определяются множества D(k;r ) условиями (2), (3) и дополнительными
ограничениями, которые возникают в процессе разветвления (см. пункт 5). На 0-м шаге возлагаем
D(0;1)=D, где D задается условиями (13.2) (13.3).
2.
Решаются вспомогательные ЗЛП на множествах D(k;r ). Пусть x(k;r ) — оптимальные
решения указанных ЗЛП.
3.
Вычисляются границы на множествах D(k;r ) за формулой ξ(k;r ) = ]L(x (k;r ))[ , где ]z[
— наименьшее целое число, не меньше z .
4.
Если существуют k , l такие, что x(k;l ) — целочисленное решение и для всех веток r на
k-у шаге выполняются соотношения
L(x (k;l ))= ξ(k;l ) ≤ ξ(k;r )
то x * = x(k;l ) — оптимальное решение ЦЗЛП.
5.
Разветвление осуществляется по нецелочисленной компоненте xj(k;r ) (с минимальным
j ) решения x(k;r), что отвечает перспективной ветке k;r (если таких веток несколько, то выбирается
ветка с минимальным r), добавлением к D(k;r) одного из подмножеств xj≤ [xj(k;r )] или
xj≥ [xj(k;r )] +1.
Задание.
Решить методом ветвей и границ задачи целочисленного линейного программирования,
условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9),
а также следующие задачи (без использования программного обеспечения).
Во всех задачах выполняются условия: x j ≥ 0 , x j — целое, j=1,2.
1)
x1 +
x2 → max
2 x1 + 11 x2 ≤ 38
x1 +
x2 ≤ 7
4 x1 – 5 x2 ≤ 5;
2)
–2 x1 – x2 → min
6 x1 + 4 x2 ≤ 24
x1 – x2 ≤ 3
– x1 + 3 x2 ≤ 3;
4)
x1 + x2 → min
– x1 – x2 ≤ – 1
– 2 x1 + 2 x 2 ≤ – 2
– 4 x1 + 2 x2 ≤ – 1;
5)
5 x1 + 7 x2 → min
– 10 x1 + x2 ≤ – 16
– 3 x1 – 3 x2 ≤ – 12
– 6 x1 – 2 x2 ≤ – 17
7)
x1 + 4 x2 → min
x1 – 3 x2 ≤ –1
8 x1 – x2 ≥ 6
3 x1 – 11 x2 ≤ –7;
8) –5 x1 – 7 x2 → max
2 x1 + x2 ≥ 3
20 x1 – x2 ≥ 15
x1 – x2 ≤ –2;
6 x1 + 4 x2 → min
2 x1 + x2 ≥ 3
x1 – 2 x2 ≤ 2
3x1 + 2x2 ≥ 1;
3)
6) 2 x1 – x2 → max
2 x1 + x2 ≤ 8
x1 + 3 x2 ≥ 6
3 x1 + x2 ≥ 3;
9)
x1 + 2 x2→ min
2 x1 + 2 x2 ≥ 5
x1 – 3 x2 ≤ –1
x1 – x2 ≥ 2.
Ответы:
1) x* = (3; 2) или x* = (2; 3), L(x*)= 5.
2) x* = (3; 1), L(x*)= –7.
3) x* = (1; 1), L(x*)= 10.
4) x* = (1; 0), L(x*)= 1.
5) x* = (4; 0), L(x*)=20.
6) x* = (3; 1), L(x*)= 5.
7) x* = (1; 1), L(x*)= 5.
8) x* = (1; 3), L(x*)= –26.
9) x* = (4; 2), L(x*)= 8.
14
Лабораторная работа № 7(4ч.)
Тема: Динамическое программирование.
Цель работы - Ознакомиться с методами динамического программирования.
Рассмотреть типовые модели динамического программирования.
Теоретические сведения
Модельная задача: поиск кратчайшего пути на графе.
N1
3
4
2
1
2
2
3
5
3
2
iН
1
4
3
N0
4
1
2
0
N2
1
iК
1
1
N3
N 1 (далее)
Рис.1
На дугах проставлены расстояния между двумя вершинами. В вершинах - кратчайшее расстояние
до конечной вершины iK .
Кратчайший путь iH → iK имеет длину 5.
Этот граф без циклов.
Таким образом, можно разметить любой граф без циклов.
Двигаемся от конечной вершины к начальной:
любая вершина - состояние процесса,
дуги - переходы.
Таким образом, задача: на множестве всех траекторий выбрать ту, длина которой минимальна.
Z j (i ) = min ( f j (i, u ) + Z j +1 (ϕ (i, u )) ) - уравнение Беллмана
u∈Ui
Z j (i ) -функция Беллмана
Z k (ik ) = 0 (н.у. для рекурсии)
ik -конечная вершина.
Методика применения функции Беллмана для решения исходной задачи.
Рассмотрим множество вершин N1 , из которых можно попасть только в конечную (см. рис.1),
Z k (ik ) = 0 ( ik -конечная вершина).
С помощью уравнения Беллмана можно рассчитать Z (i ) в любой точке множества N1 .
Для каждой из этих вершин можно зафиксировать управление u , на котором
достигается min уравнения Беллмана.
Рассмотрим множество вершин, N 2 , из которых можно попасть только в N1 .
С помощью
уравнения Беллмана можно вычислить Z (i ) в любой точке N 2 и зафиксировать u, на котором
достигается min уравнения Беллмана.
15
Описанные действия повторяют, пока не вычислят Z (i ) в начальной вершине. Это и будет
значение функционала.
Описанный процесс часто называют обратным ходом, за которым следует прямой, в течение
которого определяют оптимальную траекторию, которая определяется через выбранные при
обратном ходе управления для каждой вершины.
Примеры задач динамического программирования
1. Задача о рюкзаке.
Задано конечное множество предметов, которые имеют вес и стоимость
i -й предмет : вес - a i
стоимость - ci
Надо выбрать такую совокупность предметов, чтобы суммарный вес был не более наперед заданного
значения, а стоимость максимальна.
n
max∑cixi при ∑ ai ≤ y,где y - грузоподъемность (максимально возможный вес)
i =1
Чтобы решить эту задачу с помощью динамического программирования, надо представить ее
решение в виде процесса:
Z (y) = max ( ci + Z(y − a i ))
i∈I z
где I z = { i : a i ≤ y} -уравнение Беллмана для задачи о рюкзаке.
Зная значения Z для малых аргументов, можно вычислить его для любого аргумента.
Процесс построения функции Беллмана не формализуется. Это творческий процесс, т.е.
динамическое программирование, это идея, которая в каждой предметной области реализуется посвоему.
2. Задача оптимального распределения ресурсов.
Существует n предприятий, между ними надо распределить ζ 0 средств. Известно, что выдача i -му
предприятию xi средств дает доход f i ( xi ).
Требуется распределить средства так, чтобы суммарный доход был максимальным:
n
S = ∑ f i ( xi ) → max
i =1
xi ≥ 0, i = 1, n ,
n
x
∑
i =1
i
=ζ 0
Эту задачу удобно решать методом динамического программирования.
Пусть все xi кратны ∆ ( ∆ -некоторая константа), например:
x1 x 2 x3
40 80 120 ...( ∆ = 40)
Представим процесс решения задачи как n -шаговый.
На первом шаге выдадим средства первому предприятию
1) x1 : ζ 1 = ζ 0 − x1 - оставшиеся средства (первому предприятию выдано x1 средств)
2) x 2 : ζ 2 = ζ 1 − x 2
:
:
n) x n : ζ n = 0 (все средства распределены)
16
Введем функцию Беллмана
Z k (ζ k ) - максимальный доход, который может быть получен при
распределении средств ζ k между предприятиями k+1, ... , n.
Z k (ζ k ) = max { f k +1 ( x k +1 ) + Z k +1 ( ζ k - x k +1 )}
0 ≤ xk +1 ≤ ζ k
Замечание:
Если разбиение задачи размера n сводит ее к n задачам размера n−1 , то рекурсивный алгоритм
имеет экспоненциальную сложность. В этом случае часто можно получить более эффективный
алгоритм с помощью табличной техники, называемой динамическим программированием.
Динамическое программирование, в сущности, вычислительное решение для всех подзадач.
Вычисление идет от малых подзадач к большим, и ответы записываются в таблице. Преимущество
этого метода состоит в том, что раз уж подзадача решена, ее ответ где-то хранится и никогда не
вычисляется заново.
Задачи динамического программирования называются многоэтапными или
многошаговыми.
Задание.
Общий вес ранца заранее ограниченb. Какие предметы положить в ранец, чтобы общая
полезность ci отобранных предметов была максимальна? Вес каждого предмета известен mi.
Решить задачу. Написать программу.
Вар.1
Вар.2
Вар.3.
Вар.4
Вар.5
Вар.6
17
Лабораторная работа № 8(6ч.).
Тема: Нелинейное программирование. Определение экстремума функции при линейных
ограничениях.
Цель работы - Ознакомиться с методами поиска экстремума функции при линейных ограничениях.
Теоретические сведения
Метод золотого сечения.
Метод золотого сечения (МЗС) применяется для поиска минимума унимодальной функции
одной переменной y = F ( x ) , что задана на промежутке [ A , B ]. Алгоритм метода реализуется в виде
последовательности шагов, на каждом из которых осуществляется сужение интервала, что содержит
точку минимума.
В начале вычислений возлагают А{ 0 } = А, B{ 0 } = B.
На s-у шаге определяют величины
L { s } = B{ s } – G (B{ s } – А{ s } )
R{ s } = А { s } + G (B{ s } – А { s } )
где константа G = (√5 – 1 )/2 ≈ 0.618. Подставим
А{ s + 1 }= А{ s } , B{s+1}= R{ s } , если F( L{s}) ≤ F( R{ s } )
А{ s + 1 }= L { s } , B{s+1}= B{ s } , если F( L{s})> F (R { s } ).
Итерации продолжают до тех пор, пока не будет выполняться неравенство
B{ s } – А{ s } ≤ ε ,
где ε > 0 — заданное число, которое определяет погрешность решения задачи.
На каждом шагу МЗП, начиная с 1-го, вычисляется лишь одно значение функции F(x ), потому
что одна из точек золотого перерезу на предыдущем шаге осуществляет золотой перерез промежутка
на следующем шаге.
За приближенное решение задачи принимают
x* = (А { s } + B { s } )/2 , y* = F (x*).
При решении задачи максимизации функции F(x ) необходимо заменить ее на функцию –
F (x ).
Метод случайного поиска.
Метод случайного поиска применяется для нахождения минимума (максимума) произвольной
функции y= F (x ), что задана в любой допустимой области D.
В программе рассматривается реализация данного метода для функции одной переменной.
Произвольная функция F (x ) задана на промежутке [ A , B] . С помощью датчика случайных
чисел, равномерно распределенных на промежутке [0,1] , стр о и тс я последовательность случайных
чисел x{k}, k = 1 ...,N, равномерно распределенных на промежутке [A,B] . В ы чи сл я ю т ся и
сравниваются между собой значения функции F(x) в т о чк ах x{k}. Ми н им ал ь н о е из них
принимается за оценку минимума функции F(x) на пр о м еж ут к е [A,B].
Если N стремится к бесконечности, полученная оценка за вероятностью совпадает к
глобальному минимуму функции, что рассматривается.
При решении задачи максимизации функции F(x ) необходимо заменить ее на функцию –
F (x ).
Метод Фибоначчи.
Метод Фибоначчи (МФ) применяется для поиска минимума унимодальной функции одной
переменной y= F (x ), что задана на промежутке [ A, B].
Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых
осуществляется сужение интервала, что содержит точку минимума.
В начале вычислений возлагают А{ 0 } = А, B{ 0 } = B.
На s-у шаге определяют величины
L { s } = B{ s } – G { s } ( B { s } – А { s } )
R{ s } = А { s } + G{ s } (B { s } – А { s } )
18
где G{s}= Fi(N–s–1)/Fi(N–s), s=0...,N–3, G{N–2} = (1+ε )/2 или (1–ε )/2 , N — заданное число
итераций ε > 0 , Fi(j) — числа Фибоначчи, что задаются рекуррентным соотношением
Fi(j)= Fi(j–1) + Fi(j– 2 ) , j ≥ 2 , Fi(0)= Fi(1)= 1.
Возлагают
А{ s + 1 }= А{ s } , B{s+1}= R{ s } , если F( L{s}) ≤ F( R{ s } )
А{ s + 1 }= L { s } , B{s+1}= B{ s } , если F( L{s})> F (R { s } ).
За приближенное решение задачи принимают
x* = (А { N } + B{ N } )/2 , y* = F (x*).
Для МФ в случае предварительно фиксированного числа итераций длина конечного интервала
поиска минимальная.
При решении задачи максимизации функции F(x ) необходимо заменить ее на функцию –
F (x ).
Метод дихотомии (половинного деления).
Метод дихотомии (МД) применяется для поиска минимума унимодальной функции одной
переменной y= F (x ), что задана на промежутке [ A, B].
Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых
осуществляется сужение интервала, что содержит точку минимума.
В начале вычислений возлагают А{ 0 } = А, B{ 0 } = B.
На s-у шаге определяют величины
L { s } = ( А{ s } + B{ s } – ∆ )/2
R{ s } = (А { s } + B{ s } + ∆ )/2
где ∆ > 0 — достаточно малое число. Возлагают
А{ s + 1 }= А{ s } , B{s+1}= R{ s } , если F( L{s}) ≤ F( R{ s } )
А{ s + 1 }= L { s } , B{s+1}= B{ s } , если F( L{s})> F (R { s } ).
Итерации продолжают до тех пор, пока не будет выполняться неравенство
B{ s } – А{ s } ≤ ε ,
где ε > 0 — заданное число, которое определяет погрешность решения задачи.
За приближенное решение задачи принимают
x* = (А { s } + B { s } )/2 , y* = F (x*).
При решении задачи максимизации функции F(x ) необходимо заменить ее на функцию –
F (x ).
Задание.
Решить методами золотого пересечения, случайного поиска, Фибоначчи и дихотомии задачи
одномерной оптимизации, условия которых задаются модулем с помощью команды «Данные»
главного меню, а также найти наибольшее и наименьшее значение следующих функций на указанных
промежутках:
1)
F(x)= |||x2 – 1 |– 1 |– 1 |
x ∈ [–2, 2];
2)
3)
4)
5)
6)
7)
F(x)= 2x3–3x2–12x+1++ (4 - x 2 )(1 + 2 x 2 )
F(x)= (x+1)2 ln(x+1)+x exp(–x)
F(x)= sin(x) sin(2 x)+ arccos(x 2 )
F(x)= arctg(x) – ln(x) /2
F(x)= x+ x + ехp(x) x2
F(x)= 4 x/(x2 + 4 )– [ x2 (x – 2)] (2/5)
x ∈ [–2, 2];
x ∈ [0, e];
x ∈ [–0.75, 0.75];
x ∈ [0.65, 1.75];
x ∈ [0, 4];
x ∈ [–2, 2].
ЗАДАЧА ВЫПУКЛОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ.
КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД
Постановка задачи нелинейного программирования.
Найти вектор x = (x1. . . , x n ), что минимизирует (максимизирует) функцию
F (x )= F( x1. . . , x n )
(1 8 . 1 )
19
и удовлетворяет систему ограничений
Gi (x1. . . , x n ) Ri 0 , i=1...,m
(18.2)
где символ Ri заменяет один из знаков ≤ , = , ≥ .
Если хотя бы одна из функций F, Gi (i=1...,m) является нелинейной, то указанная постановка
определяет задачу нелинейного программирования (ЗНЛП).
Совокупность точек (векторов) x , которые удовлетворяют (18.2), называется допустимой
областью (множеством) и отражается через D.
Произвольная точка D зовется допустимым решением (точкой, планом, вектором).
Функция F(x ) соотношения (18.1) называется целевой функцией.
Постановка задачи выпуклого программирования.
Найти вектор x = (x1. . . , x n ), что минимизирует целевую функцию
F (x )= F( x1. . . , x n )
(1 8 . 3 )
и удовлетворяет систему ограничений
G i ( x1. . . , x n )≤ 0 , i=1...,m
(18.4)
x j ≥ 0 , j=1...,n
(18.5)
где функции F, Gi (i=1...,m) — выпуклые.
Таким образом, для задачи выпуклого программирования (ЗОП) целевая функция (18.3) —
выпуклая, ограничение (18.4)–(18.5) определяют выпуклое допустимое множество.
Постановка задачи выпуклого квадратичного программирования.
Найти вектор x , что минимизирует целевую функцию
F (x )= x D xТ + c xТ
(18.6)
и удовлетворяет систему ограничений
А xТ ≤ bТ, x ≥ 0
(18.7)
где c = ( c 1 . . . , c n ), x = ( x 1 . . . , x n ), D = | | d k l | | , k,l=1...n, A = | | a i j | | , i=1...,m, j=1...,n,
b = (b 1 . . . , b m ), матрица D симметричная и неотъемлемо определена.
Таким образом, для задачи выпуклого квадратичного программирования (ЗОКП) целевая
функция (18.6) — выпуклая квадратичная, ограничение (18.7) — линейные и определяют выпуклое
многогранное допустимое множество.
Заметим, что для случая n = 2 , m = 1 ЗОКП имеет вид:
d 1 1 x12 + d 2 2 x22 + 2 d12 x1 x2 + c 1 x1 + c 2 x2 → min
a 1 1 x1 + a 1 2 x2 ≤ a 1 0 , x j ≥ 0 , j=1,2
к тому же D = | | d k l | | , k,l=1,2, d12 = d21.
Квадратичный симплекс-метод.
Задача (18.21)–(18.24) решается симплекс-методом.
Если найденный ДБР этой задачи удовлетворяет условиям дополняющей нежесткости
(18.15)–(18.18), то он определяет оптимальное решение исходной ЗВКП. Иначе нужно перейти к
новому ДБР. При этом в базисные включается новая переменная с нулевой оценкой.
Симплекс-метод с условиями (18.15)–(18.18) для решения вспомогательной КЗЛП (18.21)–
(18.24), построенной на основе задачи выпуклого квадратичного программирования (18.6)–(18.7), и
называют квадратичным симплекс-методом (алгоритм обычного симплекс-метода, а также все
связанные с ним определения и утверждения приведены в методических указаниях к лабораторной
работе №2).
Если в оптимальном решении вспомогательной КЗЛП (18.21)–(18.24) все искусственные переменные
z j (j=1...,n) принимают нулевые значения, то, отбрасывая их, получим ДБР системы (18.19)–(18.20).
Та его часть, которая отвечает переменным начальной задачи выпуклого квадратичного
программирования (18.6)–(18.7), и будет ее оптимальным решением.
Если же в оптимальном решении вспомогательной КЗЛП (18.21)–(18.24) значение хотя бы одной из
искусственных переменных отличное от нуля, то система (18.19)–(18.20) решений не имеет, а,
следовательно, множество седловых точек функции Лагранжа начальной задачи выпуклого
квадратичного программирования пустое.
20
Задание.
Решить квадратичным симплекс-методом задачи выпуклого квадратичного программирования,
условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9),
а также следующие задачи.
Во всех задачах выполняются условия: x1 ≥ 0 , x2 ≥ 0 .
1)
x12 + x22 –2 x1 – 4 x2 → min
2 x1 + 3 x2 ≤ 6 ;
2)
–2 x12 – 3 x22 + 4 x1 x2 + 12 x2 → max
3 x1 + 4 x2 ≤ 12;
3)
2 x12 + x22 – x1 x2 – x1 → min
x1 + 2 x2 ≤ 1 ;
4)
x12 + 3 x22 – x1 – 2 x2 →min
x1 + 4 x2 ≤ 7 ;
5)
–2x12 –3x22+16x1+ 24 x2 →max
2 x1 + x2 ≤ 4 ;
6)
x12 + x22 – 3 x1 – 8 x2 → min
x1 +2 x2 ≤ 4 ;
7)
–x12 – x22 + x1 + 2 x2 → max
x1 + 2 x2 ≤ 16;
8)
–x12 – x22 + x1 x2 + 5 x1 + 2 x2 → max
2 x1 +3 x2 ≤ 15 .
Ответы:
1) x * = (0.69; 1.54). 2) x * = (1.23; 2.07). 3) x * = (0.29; 0.14). 4) x * = (0.5; 0.33).
5) x * = (0.57; 2.86). 6) x * = (0.4; 1.8).
7) x* = (0.5; 1).
8) x * = (3.63; 2.58).
21