Правила оформления ЛР№2 по курсу Методы оптимизации (Методические указания, правила оформления и вопросы к лабораторным работам)

Дисциплина «Методы оптимизации»8 факультет 3 курсЛАБОРАТОРНАЯ РАБОТА №2«ПРИКДАДНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ»РЕШАЕМЫЕ ЗАДАЧИ:• Задача об аренде партии верблюдов• Задача о выборе транспортных средствСОДЕРЖАНИЕ И ПРАВИЛА ОФОРМЛЕНИЯ ОТЧЕТА ПО ЛАБОРАТОРНОЙ РАБОТЕ:1. Отчет по лабораторной работе выполняется после выполнения лабораторной работы в отдельнойтетради вручную.

Отчет должен быть у каждого студента, даже если работа выполнялась бригадой.2. Обложка тетради, должна содержать наименование лабораторной работы, наименованиедисциплины, фамилию и группу студента.3. По каждой решенной в работе задаче в отчете должны содержать следующие разделы:(1) Текстовая постановка прикладной задачи.(2) Выбранные параметры.(3) Математическая модель задачи.(4) Графическое решение, если задача имеет 2 переменные (графическое решениевыполняется вручную на миллиметровке формата A4 (масштаб по осям 1:1).

(См.алгоритм и примеры)На графике должны быть: подписаны оси координат; указаны единицы масштаба; выделено цветом множество допустимых решений; построен вектор градиента в точке (0,0) (не схематично, а с соблюдением координат имасштаба); построена линия уровня целевой функции, проходящая через точку (0, 0); обоснованно указано решение задачи на основании графика, с приведением координатоптимального решения и оптимального значения функции.(5) Подготовка задачи к решению (переход к канонической задаче, переход к М-задаче и т.д.).(6) Решение табличным симплекс методом и/или методом Гомори (приводимое решениедолжно содержать все таблицы и комментарии к ним).

Таблицы могут быть распечатаны ивклеены в отчет.(7) Соответствующая двойственная задача к прямой задаче максимизации (без учетацелочисленности) и ее решение, а в случае когда двойственная задача имеет двепеременные, дополнительно графическое решение двойственной задачи (графическоерешение выполняется вручную на миллиметровке формата А4 (масштаб по осям 1:1).(8) Выводы и рекомендации.ПРОЦЕДУРА ЗАЩИТЫ ЛАБОРАТОРНОЙ РАБОТЫ1.

Индивидуальная беседа по отчету.2. Заключительное тестирование (к тестированию допускаются студенты по итогам беседы поотчету).УСЛОВИЯ ЗАЩИТЫ: оценка хорошо или отлично за заключительный тест.Кафедра 805, 2013г.Дисциплина «Методы оптимизации»8 факультет 3 курсАЛГОРИТМ ГРАФИЧЕСКОГО РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГОПРОГРАММИРОВАНИЯ1. Построить множество допустимых решений, задаваемое ограничениями.2. Построить градиент целевой функции в точке (0, 0)T .3. Построить линию уровня целевой функции, проходящую через точку (0, 0)T .Если, построенная линия уровня не имеет общих точек с множеством допустимых решений,то, используя параллельный перенос, построить еще одну линию уровня функции,пересекающую множество допустимых решений.

Линию уровня, имеющую общие точки смножеством допустимых решений, отметим ⊕ .4. Для поиска максимума целевой функции переносить, используя параллельный перенос,построенную линию уровня ⊕ в направлении градиента до последнего касания смножеством допустимых решений. В точке (точках) касания достигается условныймаксимум. Если множество допустимых решений в направлении градиента неограниченное,то максимума в задаче нет.Для поиска минимума целевой функции аналогично переносить построенную линию уровня⊕ в направлении, противоположном градиенту, до последнего касания с множествомдопустимых решений. В точке (точках) касания достигается условный минимум. Еслимножество допустимых решений в направлении, противоположномградиенту,неограниченное, то минимума в задаче нет.Пример 1.Дано:f ( X ) = − x1 + 3 x2 → extr− x1 + x2 ≤ 1 ,2 x1 + x2 ≤ 4 ,x1 , x2 ≥ 0 .Найти решение задачи графически.(1)(2)(3)Решение:1.

Для графического решения задачи построим множество допустимых решений, задаваемоеограничениями (1)-(3).Ограничение (1) в задаче определяется прямой− x1 + x2 = 1 , проходящей через точки:x1x201−10Множество допустимых решений в задаче будет ограничено этой прямой и будет содержатьточку (0, 0)T , так как при подстановке координат этой точки в ограничение (1) получаетсяверное неравенство: −0 + 0 ≤ 1 .Кафедра 805, 2013г.Дисциплина «Методы оптимизации»Ограничение (2) в задаче определяется прямой8 факультет 3 курс2 x1 + x2 = 4 , проходящей через точки:x1x20420Множество допустимых решений в задаче будет ограничено этой прямой и будет содержатьточку (0, 0)T , так как при подстановке координат этой точки в ограничение (2) получаетсяверное неравенство: 2 ⋅ 0 + 0 ≤ 4 .Ограничения (3) в задаче задают 1-ю четверть координатной плоскости.Множество допустимых решений включает все точки, в которых ограничения выполняютсяодновременно.

Отметим крайние точки получившегося множества: О, A, B, С (рис. 1.).Рис. 1.2. Построим градиент функции ∇f ( X ) = (−1, 3)T в точке (0, 0)T (рис. 1.).3. Построим линию уровня функции f ( X ) = C , проходящую через точку (0, 0)T . Для этогонайдем значение константы C , подставив координаты точки в целевую функцию:Кафедра 805, 2013г.Дисциплина «Методы оптимизации»8 факультет 3 курсC = −0 + 3 ⋅ 0 = 0 , и затем построим прямую − x1 + 3 x2 = 0 . Заметим, что построенная прямаяперпендикулярна градиенту (рис. 1.).Построенная линия уровня пересекает множество допустимых решений, отметим ее ⊕ (рис.1.).4.

Будем искать точку максимума функции как последнюю точку касания линии уровня имножества допустимых решений при параллельном переносе линии ⊕ в направленииградиента функции. Как видно из чертежа, это точка B = (1, 2)T (соответствующая линияуровня изображена штриховой линией). Таким образом, получено решение задачи поискамаксимума функции:x1* = 1 ,x2* = 2 ,*f ( X max) = −1 + 3 ⋅ 2 = 5 .Будем искать точку минимума функции как последнюю точку касания линии уровня имножества допустимых решений при параллельном переносе линии ⊕ в направлении,противоположном градиенту функции.

Как видно из чертежа, это точка C = (2, 0)T(соответствующая линия уровня изображена штриховой линией). Таким образом, полученорешение задачи поиска минимума функции:x1* = 2 ,x2* = 0 ,*f ( X min) = −2 + 3 ⋅ 0 = −2 .Пример 2.Дано:f ( X ) = 4 x1 + x2 → extr− x1 + x2 ≤ 1,2 x1 + x2 ≥ 4,(1)(2)x1 , x2 ≥ 0 .Найти решение задачи графически.(3)Решение:1. Для графического решения задачи построим множество допустимых решений, задаваемоеограничениями (1)-(3).Ограничение (1) в задаче определяется прямой − x1 + x2 = 1 , проходящей через точки:x1x201−10Множество допустимых решений в задаче будет ограничено этой прямой и будет содержатьточку (0, 0)T , так как при подстановке координат этой точки в ограничение (1) получаетсяверное неравенство: −0 + 0 ≤ 1 .Ограничение (2) в задаче определяется прямой2 x1 + x2 = 4 , проходящей через точки:Кафедра 805, 2013г.Дисциплина «Методы оптимизации»8 факультет 3 курсx102x240Множество допустимых решений в задаче будет ограничено этой прямой и НЕ будетсодержать точку (0, 0)T , так как при подстановке координат этой точки в ограничение (2)получается неверное неравенство: 2 ⋅ 0 + 0 ≥ 4 .Ограничения (3) в задаче задают 1-ю четверть координатной плоскости.Множество допустимых решений включает все точки, в которых ограничения выполняютсяодновременно.

Отметим крайние точки получившегося множества: A, B (рис. 2.).Рис. 2.2. Построим градиент функции ∇f ( X ) = (4, 1)T в точке (0, 0)T (рис. 2.).Кафедра 805, 2013г.Дисциплина «Методы оптимизации»8 факультет 3 курс3. Построим линию уровня функции f ( X ) = C , проходящую через точку (0, 0)T . Для этогонайдем значение константы C , подставив координаты точки в целевую функцию:C = 4 ⋅ 0 + 0 = 0 , и затем построим прямую 4 x1 + x2 = 0 . Заметим, что построенная прямаяперпендикулярна градиенту (рис. 2.).Построенная линия уровня не имеет общих точек с множеством допустимых решений.Используя параллельный перенос, построим еще одну линию уровня функции,пересекающую множество допустимых решений, и отметим ее ⊕ (рис.

2.).4. Будем искать точку максимума функции как последнюю точку касания линии уровня имножества допустимых решений при параллельном переносе линии ⊕ в направленииградиента функции. Как видно из чертежа, такой точки не существует, так как множестводопустимых решений в направлении градиента неограниченное, следовательно, максимума взадаче нет.Будем искать точку минимума функции как последнюю точку касания линии уровня имножества допустимых решений при параллельном переносе линии ⊕ в направлении,противоположном градиенту функции.

Как видно из чертежа, это точка A = (1, 2)T(соответствующая линия уровня изображена штриховой линией). Таким образом, полученорешение задачи поиска минимума функции:x1* = 1 ,x2* = 2 ,*f ( X min) = 4 ⋅1 + 2 = 6 .Кафедра 805, 2013г..