Оптимизационные математические модели

Лекция № 4 Оптимизационные математические модели 3. Литература: 1. Зайцев М.Г., Варюхин С.Е. Методы оптимизации и принятия решений: примеры, задачи, кейсы: учебное пособие. - М.: Издательский дом «Дело», 2011. 2. Кучков А.Ф., Лукашевич Н.Ф., Попов Г.П., Шумов В.В. Математическое моделирование служебно-боевых действий пограничных войск: Учебник. - М.: ФПС России, 1996. 3. Врачинская Т.И. Математические методы в управленческой деятельности: Курс лекций. - Калининград: ФГОУ ВПО ФСБ России, 2013. 4. Королев Г.Д. Математические методы в решении профессиональных задач: Электронный курс лекций. - Калининград: ФГОУ ВПО ФСБ России, 2013. 4. Учебные вопросы и расчет времени Содержание Время, мин Вступительная часть 5 Учебные вопросы (основная часть) 80 1. Модели оптимизации. 10 2. Задача линейного программирования. 40 3. Графическое решение задачи линейного программирования. 30 Заключительная часть 5 Текст лекции № 4 1. Модели оптимизации К оптимизационным математическим методам относятся методы решения задач с применением моделей математического программирования. К ним относятся задачи, решаемые с помощью следующих моделей: 1. Модели линейного программирования. Их разновидности: a. Одноиндексные модели линейного программирования. b. Двухиндексные модели линейного программирования. c. Целочисленные модели линейного программирования. d. Булевые модели линейного программирования. 2. Модели нелинейного программирования. 3. Модели динамического программирования. Все перечисленные модели находят широкое применение при решении задач профессиональной деятельности. Решение этих задач сводится к поиску оптимального решения по целевой функции с учетом ограничений при известных исходных данных (внешних параметрах). 2. Задача линейного программирования 2.1. Постановка задачи линейного программирования Линейное программирование является составной частью задач матема­тического программирования, в которых критерий оптимальности задается в виде линейной функции от входящих в него переменных, кроме того, на эти пе­ременные накладываются некоторые ограничения в форме линейных равенств и неравенств. Общей задачей линейного программирования называется задача, кото­рая состоит в определении максимального (минимального) значения функции F(x) = c1 x1 + с2 х2 + ... + сn хn (2.1) при условиях (2.2) где aij, bi, cj - заданные постоянные величины (числа), к ≤ т. Функция (2.1) называется целевой функцией задачи линейного програм­мирования, а условия (2.2) - системой ограничений данной задачи. Стандартной (симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального (мини­мального) значения функции (2.1) при выполнении условий (2.2), где к = т и 1 = п. Таким образом, в стандартной задаче система ограничений состоит только из неравенств. В краткой записи стандартная задача линейного программирования имеет вид: при ограничениях Основной (канонической) задачей линейного программирования назы­вается задача, которая состоит в определении максимального (минимального) значения функции (2.1) при выполнении условий (2.2), где k = 0 и l = п. Таким образом, в основной задаче система ограничений состоит из равенств и условий неотрицательности переменных. Совокупность чисел х = (х1, х2, ..., хп), удовлетворяющих ограничениям задачи (2.2) называется допустимым решением (допустимым планом). Допустимое решение, при котором целевая функция принимает свое мак­симальное (минимальное) значение, называется оптимальным. 2.1. Решение задачи линейного программирования в табличном процессоре MS Excel 1. Постановка задачи Руководство фирмы предполагает производить продукцию двух моделей А1 и А2. Их производство ограниченно наличием сырья, временем эксплуатации оборудования и денежными кредитами. Для каждого изделия модели А1 требуется 0,3 м3 древесины, 0,2 часа работы станков и затратить 1,6 денежных единиц, а для изделия модели А2 - 0,4 м3 древесины, 0,5 часа работы станков и 1 ден. ед. Фирма может получить от своих поставщиков до 170 м3 древесины в неделю и использовать оборудование в течение 160 часов. На финансирование проекта предполагается выделять 800 ден. ед. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А1 должно приносить 2 ден. ед. прибыли, а каждое изделие модели А2 - 4 ден. ед. прибыли? 2. Формулировка математической модели 2.1. Обозначения х1 - количество выпущенных за неделю изделий модели А1, х2 - количество выпущенных за неделю изделий модели А2. W - доход предприятия 2.2. Целевая функция max W = 2 х1 + 4 х2 2.3. Составление системы ограничений Ограничение на расход древесины 0,3 х1 + 0,4 х2  170, Ограничение на время использование оборудования 0,2 х1 + 0,5 х2  160, Ограничение на использование финансов 1,6 х1 + 1,0 х2  800, Объём выпускаемых изделий (в неделю) х1  0, х2  0 3. Решение задачи средствами Excel Расчетные формулы в таблице п. 3.2 =C41*$C$54 =D41*$D$54 =C50+D50 =C42*$C$54 =D42*$D$54 =C51+D51 =C43*$C$54 =D43*$D$54 =C52+D52 =C44*$C$54 =D44*$D$54 =C53+D53 Результаты расчета 3.4. Составление отчетов 3.4.1. Отчет по результатам 3.4.2. Отчет по устойчивости 3.4.3. Отчет по пределам 3. Графическое решение задачи линейного программирования Графически могут решаться задачи, заданные в стандартной форме и со­держащие не более двух переменных (или сводящиеся к ним). Найдем решение задачи, состоящее в определении максимального значе­ния функции (2.1) при условиях: (2.3) Решение задачи выполняется в два этапа: • построение области допустимых решений, • нахождение в этой области оптимального решения. Каждое неравенство системы ограничений (2.3) геометрически определя­ет полуплоскость с граничными прямыми. Если система неравенств (2.3) совместна (т. е. имеет хотя бы одно реше­ние), то ее решение - это множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоско­стей - выпуклое, то областью допустимых решений задачи является выпуклое множество, которое называется многоугольником решений. Оптимальное решение достигается в одной из вершин этого многоуголь­ника (если оно есть и единственно). Алгоритм решения ОЗЛП графическим методом 1. Построить прямые, являющиеся границами многоугольника реше­ний. Уравнения этих прямых получают из системы ограничений заменой зна­ков неравенств на знаки равенств. 2. Найти полуплоскости, определяемые каждым из ограничений задачи. 3. Найти многоугольник решений. 4. Построить вектор N, с началом в точке О (0; 0) и концом в точке, координатами которой являются коэффициенты целевой функции. 5. Построить линию уровня (линию, перпендикулярную данному век­тору N). 6. Передвинуть линию уровня в направлении вектора N при нахож­дении максимума (или в противоположном направлении при нахождении ми­нимума) до последней точки многоугольника решений. 7. Определить координаты точки максимума (или минимума) целевой функции. Для этого надо решить систему уравнений. 8. Вычислить значение целевой функции в точке максимума (мини­мума). Пример. Для производства единиц техники и вооружения 1-го и 2-го ти­пов (продукция) требуются три типа ресурсов: железо, пластик и трудозатраты. Потребности в ресурсах для производства одного единица каждого вида, запа­сы ресурсов, а также прибыль от реализации одной единицы техники и воору­жения каждого вида, заданы в следующей таблице: Необходимо найти план выпуска продукции, позволяющий получить наибольшую прибыль. Решение. Если обозначить х1 - выпуск (число единиц) продукции 1-го ти­па, а х2 - выпуск (число единиц) продукции 2-го типа, то, в соответствии с таблицей условия, неизвестные х1 и х2 будут удовлетворять следующей сис­теме ограничений: (2.4) По условию задачи необходимо найти оптимальный план производства продукции, т.е. такой план (х1 , х2), который доставляет максимум функции прибыли: Для того чтобы решить поставленную задачу графическим методом, изо­бразим на координатной плоскости область, заданную системой ограничений (2.4): Эта область лежит в первом квадранте координатной плоскости, а её граница задается системой уравнений: (2.4) в которой каждое уравнение является уравнением прямой линии. Прямая l1, заданная уравнением {х1 + 3х2 =24}, проходит через точки (24; 0) и (0; 8); прямая l2, заданная уравнением {4х1 + х2 = 24}, проходит через точки (6; 0) и (0; 24); прямая 13, заданная уравнением {Зх1 + 2х2 = 23}, проходит - через точки (23/3; 0) и (0; 23/2). Таким образом, область, заданная системой (2.4), является пятиугольником OABCD. Рассмотрим теперь вектор N = (2;3) с началом в точке 0(0;0); параллельный вектору (200; 300), и построим линию нулевого уровня прибыли z = 0, т.е. прямую 200х1 + 300х2 =0. Эта прямая проходит через точку 0(0;0) и перпендикулярна вектору . Заметив, что каждая из линий уровня z= const является прямой, параллельной линии нулевого уровня z= 0, будем передвигать линию нулевого уровня z- 0 параллельно самой себе в направлении вектора N = (2;3) до тех пор, пока она пересекается с точками пятиугольника OABCD. Очевидно, что последними точками, в которых передвигаемая линия пересекается с пятиугольником OABCD, могут быть только вершины пятиугольника. Найдем координаты вершин пятиугольника. Координаты точки В удовлетворяют системе уравнений: . Решая эту систему, находим, что В (5; 4). Координаты точки С удовлетворяют системе уравнений: Решая эту систему уравнений, находим, что С (3; 7). Координаты остальных вершин пятиугольника нам уже известны: А (6; 0), D(0; 8), О (0; 0). Подсчитаем теперь значения, которые принимает функция прибыли в вершинах пятиугольника: z(0) = z(0;0) = 200  0 + 300  0 = 0; z(A) = z(6;0) = 200  6 + 300  0 = 1200; z(B)= z(5;4) = 200  5 + 300  4 = 2200; z(C) = z(3;7) = 200  3 + 300  7 = 2700; z(D)= z(0;8) = 200  0 + 300  8 = 2400. Таким образом, наибольшая прибыль достигается в точке С (3; 7), и оптимальный план имеет вид {х1,х2) = (3; 7). Наибольшая прибыль 2700 рублей достигается при выпуске 3-х единиц техники и вооружения 1-го типа и 7 единиц 2-го типа. Вопросы и задания для проверки 1. Перечислите модели оптимизации. 2. Приведите определение модели линейного программирования (ЛП). 3. Приведите запись целевой функции в общем виде. 4. Приведите запись ограничений в общем виде. 5. Что называется общей задачей линейного программирования? 6. Что называется стандартной задачей линейного программирования? 7. Что называется основной задачей линейного программирования? 8. Что называется допустимым решением в задаче ЛП? 9. Что называется оптимальным решением в задаче ЛП? 10. Приведите порядок решения задачи ЛП графическим методом.