Линейное программирование: понятия; сложные объекты, типы моделирования

ЛЕКЦИЯ 1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ. СЛОЖНЫЕ ОБЪЕКТЫ. ТИПЫ МОДЕЛИРОВАНИЯ. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. УКАЗАНИЯ К ЛР-1 Составитель: д.т.н. Колесникова С.И. [email protected] ПОНЯТИЕ МОДЕЛИ. КЛАССИФИКАЦИЯ ВИДОВ МОДЕЛИРОВАНИЯ Модель – это физический или абстрактный образ моделируемого объекта, удобный для проведения исследований и позволяющий адекватно отображать интересующие исследователя физические свойства и характеристики объекта. Зачем? Легкость, доступность получения информации, сокращение сроков исследования и уменьшение материальных затрат на исследование и др. Моделирование процесс замещения объекта исследования некоторой его моделью и проведение исследований на модели с целью получения необходимой информации об объекте. Моделирование систем Физическое Математическое Аналитическое Численное Имитационное Компьютерное Статистическое Классификация видов моделирования систем Физическое моделирование: 1) сама исследуемая система (например, производственный эксперимент), 2) другая система с подобной физической природой (макет: продувка моделей самолетов в аэродинамических трубах). Математическое моделирование - процесс установления соответствия данной реальной системы некоторой математической модели и исследование этой модели, позволяющее получить характеристики реальной системы. Математическое моделирование Аналитическое: алгебраические, интегральные, разностные соотношения Компьютерное Численное Имитационное Статистическое Компьютерное моделирование - математическая модель системы представлена в виде программы на ЭВМ, позволяющей проводить с ней вычислительные эксперименты. Численное моделирование - использование методов вычислительной математики в численном решении некоторых математических уравнений при заданных значениях параметров и начальных условиях. Имитационное моделирование – воспроизведение на ЭВМ элементарных явлений, составляющих реальный исследуемый процесс, с сохранением последовательности протекания событий во времени. Статистическое моделирование – это вид моделирования для получения статистических данных о процессах в моделируемой системе. ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ МОДЕЛИ Будут ли следующие зависимости линейными? — зависимость веса человека от его роста? — длительность ожидания в очереди в магазине? — посещаемость поликлиники в период гриппа? — количество человек, ожидающих поезда на станции метро (во времени )? Постановка линейной задачи: Y= b⋅X+ ℇ Постановка нелинейной задачи: Y= f(X, b, ℇ) где вид , f – нелинейный. Линейные модели? 1) Чем дальше в лес, тем больше дров 2) По доходу и расход 4 ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ МОДЕЛИ Нелинейная модель Статистически линейная модель (линейный тренд в среднем) Статистически нелинейная модель (логарифмический тренд в среднем) 5 ЛИНЕАРИЗАЦИЯ НЕЛИНЕЙНЫХ МОДЕЛЕЙ НЕЛИНЕЙНОСТЬ ОБЪЕКТОВ И ЯВЛЕНИЙ – В СОВРЕМЕННОЙ НАУКЕ, ОБРАЗОВАНИИ «... истинные законы не могут быть линейными» А. Эйнштейн «... Создание общей теории нелинейных систем вряд ли возможно» Р. Фейнман Все реальные системы являются нелинейными, многомерными и многосвязными, в которых протекают сложные переходные процессы и возникают критические и хаотические режимы. ОТВЕТ НА ЛЮБОЙ ВОПРОС УЖЕ СУЩЕСТВУЕТ. НАДО ТОЛЬКО ПРАВИЛЬНО ПОСТАВИТЬ ВОПРОС, ЧТОБЫ ПОЛУЧИТЬ ЕГО Формализовать цель исследования Николис Г., Пригожин И. Самоорганизация в неравновесных системах. –М.: Мир, 1979. 7 ОБЪЕКТЫ ИССЛЕДОВАНИЙ КАК ДИНАМИЧЕСКИЕ ОБЪЕКТЫ СИСТЕМЫ ДИФФЕРЕНЦИАЛЬНЫХ, РАЗНОСТНЫХ УРАВНЕНИЙ – математические модели динамических объектов Состояние (совокупность переменных) детерминированной динамической системы (ДС) изменяется во времени по некоторому заданному закону. Регулярные ДС – устойчивые (малые возмущения со временем затухают, ДС возвращается к исходному регулярному (стационарному) поведению. Хаотические ДС обладают экспоненциальной чувствительностью к начальным условиям (изменение в начальных условиях усиливается экспоненциально во времени). Примеры хаотического поведения: броуновское движение, изменения погоды, колебания орбит астрономических тел, поведение фондовой биржи, биологические процессы в организме человека, криптографические системы. Объекты исследований: открытые сложные нелинейные системы с обратными связями. 8 ОСНОВНЫЕ ПОНЯТИЯ ОТНОСИТЕЛЬНО ДИНАМИЧЕСКИХ ОБЪЕКТОВ Система (от греч. systema – целое, составленное из частей, соединение) – множество элементов, находящихся в отношениях и связях друг с другом, образующих определенную целостность, единство. Любая система может быть охарактеризована некоторым набором величин. Величины, которые можно измерить, называют физическими: «длина», «температура», «цена», скорость,... Все величины можно разделить на параметры и переменные. Переменные – это величины, которые могут изменяться при рассмотрении процесса; параметры – постоянные величины в рамках рассматриваемой задачи. Независимые переменные – переменные (времяи, пространственные координаты), изменяющиеся независимо от рассматриваемой системы (в рамках данной задачи). Зависимые переменные - зависят от независимых и изменяются с изменением независимых величин. Пример. «Температура» и «давление» зависимые переменные; время - независимая переменная. Мир линейных функций утомительно однообразен: линейная зависимость не обладает избирательностью,... не может описывать ни резонансных всплесков, ни насыщения, ни колебаний – ничего, кроме равномерного неуклонного роста или столь же равномерного и столь же неуклонного убывания. Данилов Юлий Александрович (1936-2003) – русский физик, математик, историк науки, педагог, переводчик и просветитель 9 Одно и то же математическое описание – модель для разных процессов-явлений. катастрофические события разной природы могут развиваться по одним законам (Г.Г. Малинецкий) Фондовый рынок: зависимость логарифма индекса Доу-Джонса от времени перед Великой депрессией в 1929г. Геологический объект: концентрации ионов хлора в родниках перед землетрясением в Кобе в 1995г. 10 ПРИМЕРЫ ОПИСАНИЙ. МОДЕЛЬ ПРОДОЛЬНОГО ДВИЖЕНИЯ СА Задача синтеза системы управления продольным движением СА: определение вектора управления u(x) как функции координат состояния системы, обеспечивающего полет СА с заданными: скоростью ( x1 ) V0 , высотой ( x4 ) H0 и углом тангажа ( x5 ) ϑ0 − g sin x5 + a1u1 + z1 , x1 (t ) = − g cos x5 + a2 u2 + z2 , x2 (t ) = x3= (t ) a3u3 + z3 , = x4 (t ) x1 sin x5 + x2 cos x5 , x5 (t ) = x3 , = x6 (t ) x1 cos x5 − x2 sin x5 . x1 - горизонтальная скорость, м/с, x2 - вертикальная скорость, м/с, x3 - угловая скорость, рад/с; x4 - высота, м, x5 - угол тангажа, град; x6 - дальность полета, м, z1 , z2 , z3 - неизвестные возмущения, u1 , u2 , u3 - управляющие воздействия. 11 ЭКОНОМИЧЕСКИЕ ОБЪЕКТЫ: МОДЕЛЬ РЫНКА ОДНОТИПНОЙ ПРОДУКЦИИ Исходный объект (дискретное описание) X= X i (αC0 − µβ X X iYi ), i +1 Аналог уравнения (5) Фейгенбаума Yi += A(αC0 − µβY X iYi ). 1 (В.И.Шаповалов) A – количественная характеристика X i , Yi – объемы продаж однотипной государственных нужд в этом виде продукции, реализуемых частным X и продукции; государственным Y предприятиями, β X , βY – цены на товары у соответственно, в i-й период; C0 – средний доход покупателя в предприятий; α , µ – коэффициенты регионе; пропорциональности. Примеры объектов и задач управления X= X i (αC0 − µβ X X iYi ), i +1 (6) Yi += ui (αC0 − µβY X iYi ). 1 ui - закон изменения государственных X= X i (α C0 − µβ x X iYi ), i +1 Yi +1 = A(α C0 − µβ y X iYi ) + ui . ui - закон изменения объемов (7) нужд в этом типе продукции производимой продукции данного типа Цель управления: устойчивое достижение множества желаемых состояний, 0, i ∈ Ν заданного аналитически ( X i , Yi ) : ψ ( X i , Yi ) = { } 12 Сложный динамический объект (по Л.А. Растригину) • НЕСТАЦИОНАРНОСТЬ • МНОГОМЕРНОСТЬ • МНОГОСВЯЗНОСТЬ • НЕЛИНЕЙНОСТЬ •ХАОТИЧНОСТЬ •СЛАБАЯ ФОРМАЛИЗУЕМОСТЬ И УПРАВЛЯЕМОСТЬ Свойства (и/или): 1) объект не имеет полного аналитического описания и полностью описывающей его модели, т.е. для построения его адекватной модели недостаточно априорной информации; 2) нестационарность описывающего его случайного процесса, (слабопредсказуемость); 3) нелинейность имеющихся моделей описания; 4) многомерность, многосвязность; X (t ) = ( x1(t ) ⋅ swf1(t ),..., xm (t ) ⋅ swfm (t ) ) , swf j (t ) - переключательная функция: x j (t ) ↑↓ , включения/выключения компоненты. ДИНАМИЧЕСКАЯ МОДЕЛЬ ФЕЙГЕНБАУМА xt=αxt-1(1-xt-1), t=1,2,… СОВРЕМЕННЫЕ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЯ СЛОЖНЫХ ОБЪЕКТОВ Построение алгоритмов силового ВОЗДЕЙСТВИЯ на объект Исследование процессов естественной самоорганизации Синергетика Кибернетика Пассивное наблюдение за природными явлениями Синергетическая теория управления (СТУ) Активное воздействие на искусственные и природные системы СТУ: выявление устойчивых законов поведения объекта (инвариантов) и их энергоэффективное достижение 15 МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Арсенал математических методов, которые объединиют под названием – методы разработки оптимальных решений (или исследования операций): - Теория управления запасами. - Теория массового обслуживания. - Теория игр. - Теория статистических решений. – - Сетевые методы планирования и управления. – - Математическое программирование Математическое (оптимальное) программирование включает в себя: o линейное, o нелинейное, o целочисленное, o динамическое, o дискретное, o выпуклое программирование. 16 ЗАДАЧИ ЛИНЕЙНОГО/НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Нелинейное программирование – раздел математического программирования, изучающий задачи отыскания глобального экстремума фиксированной (целевой) функции при наличии ограничений в ситуации, когда целевая функция и ограничения имеют общий характер (не предполагаются линейными). Стандартная форма задач ЛП и НЛП в матричной записи. ) Cx → extr ; Леонид Витальевич Канторович (1912—1986) f ( x) F ( x ) → extr ; f ( x= = Найти минимум линейной функции на Ax = b; выпуклом множестве. (Нобелевская b. Φ ( x) = премия по экономике). x ≥ 0. Задачи на условный экстремум функции. Условный экстремум функции – экстремум функции, аргументы которой удовлетворяют дополнительным условиям-ограничениями, уравнениями связи. ПРИМЕРЫ. Задачи нелинейного программирования. 1) затраты изменяются не пропорционально количеству закупленных/произведенных товаров; 2) расход определенных видов сырья и ресурсов происходит нелинейно, а скачкообразно (в зависимости от объема производства); 3) среди замкнутых плоских кривых, имеющих заданную длину, найти кривую, охватывающую максимальную площадь; 4) среди тел равного объема найти с наименьшей поверхностью; 5) .............................. 17 КЛАССИФИКАЦИЯ ЗАДАЧ И МЕТОДОВ ЛП (ЗЛП) 18 ДВОЙСТВЕННОСТЬ ЗАДАЧ ЛП. Правила перехода к двойственной ЗЛП Прямая задача Двойственная задача m n min : f (Y ) = ∑ bi yi max : Z ( X ) = ∑ c j x j , i =1 j =1 n ∑a x j =1 ij j ≤ bi , i = 1,..., m x j ≥ 0, j = 1,..., n max Z ( X ) g i ( X ) ≤ bi , i = 1, m m yi ∑a y i =1 ij i ≥ cj , j = 1,..., n xi 1,...m yi ≥ 0, i = Переход к двойственной min f (Y ) r j (Y ) ≥ c j , j = 1, n 19 ФОРМЫ ЗАДАЧ ЛП Каноническая Стандартная Общая 1. Ограничения Уравнения n ∑ aij x j = bi , i = 1; m j =1 Неравенства Уравнения и неравенства ≤  a x ∑ ij j   bi , i = 1; m j =1 ≥  ≤    aij x j =  bi , i = 1; m ∑ j =1 ≥    n n 2. Условия неотрицательности Все переменные Все переменные Часть переменных x j ≥ 0 , j = 1; n x j ≥ 0 , j = 1; n x j ≥ 0 , j = 1; s , s < n 3. Целевая функция n Z = ∑ c j x j (max или min) j =1 Здесь: x j – переменные задачи; c j – коэффициенты при переменных в целевой функции; aij – коэффициенты при переменных в основных ограничениях задачи; bi – правые части ограничений. Любая ЗЛП может быть сведена к канонической, стандартной или общей задаче 20 ЗАДАЧИ ЛП (ЗЛП). ПРИМЕР Составить экономико-математическую модель задачи: для выпуска изделий двух типов А и В на заводе используют сырье четырех видов (I, II, III, IV). Для изготовления изделий необходимо: А: С1(А) ед. сырья вида I, С2(А) ед. вида II, С3(А) ед. вида III и С4(А) ед. вида IV. В: С1(В) ед. сырья вида I, С2(В) ед. вида II, С3(В) ед. вида III, С4(В) 1 ед. вида IV. Запасы сырья: I вида – К1 ед., II вида – К2 ед., III вида – К3 ед., IV вида – К4 ед. Выпуск одного изделия приносит прибыль типа А – П1 усл.ед. типа В – П2 усл.ед. Составить план производства, обеспечивающий наибольшую прибыль. Решение. 1. Сведение данных в таблицу: Сырье Кол-во сырья на ед. Запас сырья, продукции, ед. ед. А В I С1(А) С1(В) К1 II С2(А) С2(В) К2 III С3(А) С3(В) К3 IV С4(А) С4(В) К4 Прибыль от ед. П1 П2 продукции, усл.ед. 2. Формализация данных задачи как данных ЗЛП: 21 ЗАДАЧИ ЛП (ЗЛП). ПРИМЕР 1 1. Сведение данных в таблицу: Сырье Кол-во сырья на продукции, ед. А В С1(А) С1(В) С2(А) С2(В) С3(А) С3(В) С4(А) С4(В) ед. П1 П2 ед. Запас сырья, ед. I К1 II К2 III К3 IV К4 Прибыль от продукции, усл.ед. 2. Формализация данных задачи как данных ЗЛП: Обозначим x1 , x2 – количество изделий типа А и В соответственно, планируемое к выпуску ( x1 ≥ 0 , x2 ≥ 0 ). Прибыль: П1 ⋅ x1 + П2 ⋅ x2 , Целевая функция задачи: Z П1 ⋅ x1 + П2 ⋅ x2 → max . = Составляя неравенства по каждому виду сырья, получим систему: Z = П1 ⋅ x1 + П2 ⋅ x2 → max; Z =3 x1 + 2 x2 → max С1( А ) ⋅ x1 + С1( B ) ⋅ x2 ≤ K1 С1( А ) ⋅ x1 + С1( B ) ⋅ x2 ≤ K1 2 x + 3 x ≤ 21 1 2    С2 ( А ) ⋅ x1 + С2 ( B ) ⋅ x2 ≤ K2 С2 ( А ) ⋅ x1 + С2 ( B ) ⋅ x2 ≤ K2  x1 + x2 ≤ 8 ⇒ Модель задачи ЛП ⇒ ⇒   С3 А x С3 B x K3 ⋅ + ⋅ ≤ x x С3 А ⋅ + С3 B ⋅ ≤ K3 ( ) 2 ( ) 2  ( ) 1  ( ) 1 2 x1 + x2 ≤ 12 С4 А ⋅ x + С4 B ⋅ x ≤ K4 С4 А ⋅ x + С4 B ⋅ x ≤ K4  x1 ≤ 5 ( ) 2 ( ) 2  ( ) 1  ( ) 1 x1 ≥ 0, x2 ≥ 0 22 ЗАДАЧИ ЛП . ПРИМЕР 2. ЗАДАЧА О НАЗНАЧЕНИЯХ Имеется n (i = 1, , n) работ и m ( j = 1, , m) потенциальных их исполнителей. Известны затраты cij на выполнение j-м исполнителем i-й работы. Требуется назначить каждого исполнителя на одну работу так, чтобы минимизировать суммарные затраты на выполнение всех работ. Методы решения задачи о назначениях основаны на двух простых утверждениях: 1) решение задачи не изменится, если к любому столбцу или строке матрицы затрат прибавить некоторую константу; 2) если все cij ≥ 0 и найдется план X такой, что Z = n m = c x ∑∑ =i 1 =j 1 ij ij 0, то X – оптимальный план. Здесь n = m . Основанный на упомянутых утверждениях, алгоритм поиска решения заключается в преобразовании матрицы затрат cij в матрицу с нулевыми элементами, образующими систему из n независимых нулей. 23 ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ДЛЯ ЗАДАЧ ЛП Вещественное ЛП - Simplex-метод. Целочисленное ЛП не имеет общепринятого универсального математического подхода к решению (математические пакеты). Python, пакет для научных расчетов scipy. Функция scipy.optimize.linprog - для решения только задач вещественного ЛП. Задачу целочисленного ЛП в Python можно решить с помощью любой из множества дополнительных библиотек, таких как PuLP, Pyomo, cvxopt и др. MatLab Функция linprog - для задачи вещественного ЛП. матрично-векторная форма записи ограничений. Функция (начиная с версии R2014a) intlinprog - для решения задач смешанного ЛП. Функция solve - универсальная функция, ограничения и целевую функцию можно задать символьно. ЛИТЕРАТУРА Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990. Дэннис. Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений: Пер.с англ. М.: Мир, 1988. Карманов В.Г. Математическое программирование: Учебное пособие. М.: Наука, 1989. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1991. Аоки М. Введение в методы оптимизации. М.: Наука, 1988. Полак Э. Численные методы оптимизации. Единый подход. М.: Мир, 1994. Уайлд Д. Дж. Методы поиска оптимума. М.: Наука, 1997. Габбасов Р., Кириллова Ф.М. Методы оптимизации. Минск: Изд во БГУ, 1988. Бахвалов Н.С. Численные методы. М.: Наука, 1989. Гилл Ф. и др. Практическая оптимизация. М.: Мир, 1992. 25