Прикладные модели оптимизации

ВВЕДЕНИЕ Прикладные модели оптимизации 2 Оптимизация  целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях;  процесс нахождения экстремума функции, т. е. выбор наилучшего (в определенном смысле) варианта из множества возможных. 5 Исследование операций  «Исследование операций – это экспериментальная и прикладная наука, занимающаяся наблюдением, пониманием и предсказанием поведения целенаправленных человеко-машинных систем, а поэтому практических проблем правительства, бизнеса и общества». Американское общество исследования операций, 6 1952 Основные этапы научного метода  Определение проблемы.  Формулировка гипотезы.  Проведение эксперимента.  Создание модели.  Проверка модели. 7 Модель Модель – это некоторый материальный или абстрактный объект: 8  находящийся в определенном объективном соответствии с исследуемым объектом,  несущий о нем определенную информацию,  способный замещать его на определенных этапах исследований. Виды моделей 1  Вербальная модель: любая словесная формулировка задачи.  Физическая модель: имеет ту же физическую природу, что и исследуемый объект, но отличается от неё размерами, весом и пр.  Аналоговые модели: имеют иную физическую природу, чем рассматриваемый объект. 9 Виды моделей 2  Знаковые модели – абстрактные модели явления или процесса в форме графиков, схем, рисунков, формул химических или ядерных реакций, математических соотношений.  Математическая модель – важнейший класс знаковых моделей.  Количественная модель – математическая или 10 вербальная модель явления или процесса, реализованная в форме компьютерной программы. Математическая модель  Математическая модель (знаковая) – это модель объекта или системы, заданная в виде формул, функций, уравнений, отображений и других математических (в т.ч. алгоритмических) соотношений. Общая схема решения проблемы: Вербальная модель → математическая модель → → количественная модель 11 Создание математической модели оптимизации  Понять проблему, составить описательную модель      12 задачи. Идентифицировать основные переменные задачи Выбрать некоторую количественную меру эффективности для целевой функции. Представить эту меру эффективности как функцию относительно основных переменных. Идентифицировать и представить все ограничения как выражения относительно основных переменных. Собрать количественные данные или сделать соответствующие оценки для всех параметров модели. КЛАССИФИКАЦИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ Оптимизационная задача нет Одно лицо да да Одна цель нет нет Многокритериальная оптимизация Определенность Принятие решения в условиях неопределенности да Линейность нет Нелинейное программирование да нет Целочисленность Теория игр Линейное программирование 13 да Целочисленное программирование Тема 1. Линейное программирование Лекция 1 14 Линейное программирование – раздел математического программирования. Математическое программирование изучает проблемы принятия решений, которые могут быть математически сформулированы как задачи нахождения максимума (минимума) некоторой, вообще говоря, нелинейной функции (целевой функции) многих переменных, при заданной системе ограничений на переменные решения. 15 Задача линейного программирования (ЗЛП) — это задача нахождения наибольшего (наименьшего) значения линейной функции многих переменных при линейных ограничениях типа равенств (неравенств), когда на переменные задачи есть (нет) ограничений на знак. 16 Основные проблемные ситуации, в которых используются модели ЛП  Определение производственного задания.  Распределение и назначение.  Составление проектов сложных систем.  Производственный график и планирование работ.  Смеси (например, нефтяных продуктов). 17 Основные области применения линейного программирования  В физических и социальных науках.  В технике, сельском хозяйстве и военном деле.  В бизнесе, а именно:  в задачах планирования (в т.ч. бюджетном и финансовом планировании);  при оценке проектов;  в маркетинге;  в менеджменте. 18 Пример 1. Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступает 195 бревен длиной 6 м. Определите план распила, обеспечивающий максимальное число комплектов. 19 Пример 1. Способ распила Число полученных брусков длиной 1,2 м 3м 5м 1 5 - - 2 2 1 - 3 - 2 - 4 - - 1 xi – число брёвен, распиленных способом i, 20 x i  1,..., 4 – число комплектов Пример 2. Сформулирован перечень задач, решаемых на первом этапе автоматизации. Время, требуемое на разработку задач, превышает заданный срок ввода первой очереди в эксплуатацию. Возникает проблема составления титульного списка, т.е. возникает необходимость ограничения перечня задач, автоматизируемых на первом этапе. 21 Пример 2. Задача: требуется сформировать перечень задач, подлежащих автоматизации (титульный список) на первом этапе, с учетом имеющихся материальных, трудовых, временных и прочих ресурсов. 22 Экономическая интерпретация ЗЛП (Л. В. Канторович, 1938) Задача планирования производства x1 x2 – объем выпуска продукции 1-го вида в плановый период, (ед. измер.) – объем выпуска продукции 2-го вида в плановый период, (ед. измер.) План выпуска (производственный план): Функция прибыли: Цель: 23 L  c1 x1  c2 x2 max L  max c1 x1  c2 x2  x1 , x2  Экономическая интерпретация ЗЛП aij – количество ресурса типа i, необходимое для производства единицы продукции вида j, i  1,2,3; j  1,2 Количество ресурса типа 1, необходимое для реализации производственного плана x1 , x2  : a11x1  a12 x2 b1 – доступное количество ресурса типа 1 a11x1  a12 x2  b1 a21 x1  a22 x2  b2 24 a31 x1  a32 x2  b3 x1  0, x2  0 Математическая модель задачи планирования производства max L  max c1 x1  c2 x2  a11x1  a12 x2  b1 a21 x1  a22 x2  b2 a31 x1  a32 x2  b3 x1  0, x2  0 25 Математическая постановка ЗЛП (в общем виде) n max L  max  c j x j min L  min  p j x j n n n j 1 j 1 a x j 1 ij  bi , i  1, j n a x j 1 ij j , m1 ,  bi , i  m1  1, x j  0, j  1,, n. 26 q x j  ri , i  1,..., m1 , q x j  ri , i  m1  1, j 1 n , m, j 1 ij ij x j  0, j  1,, n. , m, Определения Целевая функция – величина, которая количественно характеризует цель, которую хотим достичь n L  c jx j j 1 Переменные решения (основные) – величины, которые мы можем изменять и от которых зависит целевая функция x1 , x2 ,..., xn 27 Определения Параметры модели – числа, которые в ходе решения остаются неизменными. Изменение параметров может вызвать изменение решения. Ограничения – условия, ограничивающие изменение переменных в процессе поиска экстремума; записываются с помощью уравнений или неравенств. 28 Ограничения, параметры n max L  max  c j x j j 1 n a x j 1 ij j  bi , i  1, j  bi , i  m1  1, n a x j 1 ij , m1 , x j  0, j  1,, n. 29 , m, Допустимое и оптимальное решения ЗЛП Допустимое решение - любой набор переменных решения (т.е. вектор X  ( x1 , x2 ,..., xn ) ), удовлетворяющих ограничениям. Оптимальное решение ЗЛП – допустимое решение доставляющее максимум (минимум) целевой функции при заданных ограничениях: X  ( x1 , x2 ,..., xn ), * 30 * * * Значение ЗЛП Наибольшее (наименьшее) значение целевой функции – значение ЗЛП: L  X *   L( x1* , x2* ,..., xn* )  L* Решить задачу ЛП – означает найти оптимальное решение этой задачи и ее значение. 31