Основные понятия и определения линейного программирования

ЛЕКЦИЯ 3. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ. СЛОЖНЫЕ ОБЪЕКТЫ. ТИПЫ МОДЕЛИРОВАНИЯ. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. УКАЗАНИЯ К ЛР-1 Составитель: д.т.н. Колесникова С.И. skolesnikova@yandex.ru ПОНЯТИЕ МОДЕЛИ. КЛАССИФИКАЦИЯ ВИДОВ МОДЕЛИРОВАНИЯ Модель – это физический или абстрактный образ моделируемого объекта, удобный для проведения исследований и позволяющий адекватно отображать интересующие исследователя физические свойства и характеристики объекта. Зачем? Легкость, доступность получения информации, сокращение сроков исследования и уменьшение материальных затрат на исследование и др. Моделирование процесс замещения объекта исследования некоторой его моделью и проведение исследований на модели с целью получения необходимой информации об объекте. Моделирование систем Физическое Математическое Аналитическое Численное Имитационное Компьютерное Статистическое Классификация видов моделирования систем ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ МОДЕЛИ Будут ли следующие зависимости линейными? — зависимость веса человека от его роста? — длительность ожидания в очереди в магазине? — посещаемость поликлиники в период гриппа? — количество человек, ожидающих поезда на станции метро (во времени )? Постановка линейной задачи: Y= b⋅X+ ℇ Постановка нелинейной задачи: Y= f(X, b, ℇ) где вид , f – нелинейный. Линейные модели? 1) Чем дальше в лес, тем больше дров 2) По доходу и расход 3 ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ МОДЕЛИ Нелинейная модель Статистически линейная модель (линейный тренд в среднем) Статистически нелинейная модель (логарифмический тренд в среднем) 4 МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Арсенал математических методов, которые объединиют под названием – методы разработки оптимальных решений (или исследования операций): - Теория управления запасами. - Теория массового обслуживания. - Теория игр. - Теория статистических решений. – - Сетевые методы планирования и управления. – - Математическое программирование Математическое (оптимальное) программирование включает в себя: o линейное, o нелинейное, o целочисленное, o динамическое, o дискретное, o выпуклое программирование. 5 ЗАДАЧИ ЛИНЕЙНОГО/НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Нелинейное программирование – раздел математического программирования, изучающий задачи отыскания глобального экстремума фиксированной (целевой) функции при наличии ограничений в ситуации, когда целевая функция и ограничения имеют общий характер (не предполагаются линейными). Стандартная форма задач ЛП и НЛП в матричной записи. ) Cx → extr ; Леонид Витальевич Канторович (1912—1986) f ( x) F ( x ) → extr ; f ( x= = Найти минимум линейной функции на Ax = b; выпуклом множестве. (Нобелевская b. Φ ( x) = премия по экономике). x ≥ 0. Задачи на условный экстремум функции. Условный экстремум функции – экстремум функции, аргументы которой удовлетворяют дополнительным условиям-ограничениями, уравнениями связи. ПРИМЕРЫ. Задачи нелинейного программирования. 1) затраты изменяются не пропорционально количеству закупленных/произведенных товаров; 2) расход определенных видов сырья и ресурсов происходит нелинейно, а скачкообразно (в зависимости от объема производства); 3) среди замкнутых плоских кривых, имеющих заданную длину, найти кривую, охватывающую максимальную площадь; 4) среди тел равного объема найти с наименьшей поверхностью; 5) .............................. 6 КЛАССИФИКАЦИЯ ЗАДАЧ И МЕТОДОВ ЛП (ЗЛП) 7 ДВОЙСТВЕННОСТЬ ЗАДАЧ ЛП. Правила перехода к двойственной ЗЛП Прямая задача Двойственная задача 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 8 ФОРМЫ ЗАДАЧ ЛП Каноническая Стандартная Общая 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 – правые части ограничений. Любая ЗЛП может быть сведена к канонической, стандартной или общей задаче 9 ЗАДАЧИ ЛП (ЗЛП). ПРИМЕР Составить экономико-математическую модель задачи: для выпуска изделий двух типов А и В на заводе используют сырье четырех видов (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. Формализация данных задачи как данных ЗЛП: 10 ЗАДАЧИ ЛП (ЗЛП). ПРИМЕР 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 11 ЗАДАЧИ ЛП . ПРИМЕР 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 независимых нулей. 12 ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ДЛЯ ЗАДАЧ ЛП Вещественное ЛП - 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. 14