Правила оформления ЛР№2 по курсу Методы оптимизации (1013356)
Текст из файла
Дисциплина «Методы оптимизации»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г..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
