Методы оптимизации (стр. 1 )

Методы оптимизации

Математическая модель

Математическая модель — описание решаемой задачи в математических терминах.

Математическая модель описывает исследуемую систему и позволяет выразить ее эффективность в виде целевой функции

W = f(X,Y),

где X = (x1,…, xn) — управляемые переменные,

Y = (y1,…, ym) — неуправляемые переменные (исходные данные).

Связь между переменными X и исходными данными Y выражается с помощью ограничений

j (X, Y) £ 0.

Виды моделей

·  детерминированные;

·  вероятностные;

·  игровые;

·  неполные (задачи в условиях неопределенности).

Исследованием детерминированных моделей занимается математическое программирование (МП).

Термин «программирование» означает «поиск наилучших планов» (programming – планирование – составление плана или программы действий).

Задача оптимизации

(

)

Задача математического программирования

Оптимальным решением задачи (минимизации) называют допустимое решение, минимизирующее f(x) на множестве всех допустимых решений.

Задачи математического программирования

История математического программирования

, Институт проблем управления, Москва

История математического программирования в СССР: попытка анализа

История математического программирования

1.  Леонард Эйлер, , первый ученый, занимавшийся оптимизацией в России

2.  , , основы выпуклой оптимизации, решал практические оптимизационные задачи: построение наименее искаженной географической карты, оптимальный раскрой, наилучший выбор параметров механических устройств

3.  , , известны работы в теории чисел и теории вероятностей (Марковские цепи, Марковские процессы)

4.  , , разработал теорию устойчивости для дифференциальных обыкновенных уравнений, тем самым внес огромный вклад в развитие непрерывной оптимизации, предложил инструмент для проверки сходимости численных методов оптимизации

История математического программирования

5. Л.В. Канторович, , в 1975г. получил Нобелевскую премию в области экономики, один из основателей численного анализа в нашей стране, одним из первых признал информатику как новую ветвь в математике.

Отец новой науки ОПТИМИЗАЦИИ, которая включает стандартное математическое программирование.

С именем связаны следующие достижения:

Линейное программирование, 1939:

Опубликована книга (67 стр.), в которой рассматривался новый тип оптимизационных задач. Формы записи этих задач были иными, чем стандартная формулировка задачи ЛП, причем модель, рассматриваемая в западной литературе - частный случай модели Канторовича.

Общие условия оптимальности, 1940

Техника функционального анализа,

История математического программирования

6. Г.Ш. Рубинштейн, ученик , учитель д. т.н., проф. УГАТУ

В 1961г. вышла книга и , в которой давались математические формулировки задачи ЛП и приводились численные методы ее решения, были введены понятия двойственных переменных, которые назывались «объектно-обусловленными оценками».

7. В 50-е годы – интенсивные исследования в области ЛП.

Стали известны работы западных ученых: Дж. Данцига, Г. Куна, А. Таккера и др. по ЛП.

Выпущен первый учебник на русском языке по ЛП ,

8. 60-е годы

Появилась общая теория двойственности для задач выпуклой оптимизации (), появились труды по стохастической оптимизации.

История математического программирования

Велись разработки ПО для реализации симплекс – метода для решения задачи ЛП (, , и др, доцент УГАТУ ).

Появились численные методы решения специальных классов задач ЛП:

транспортная задача, методы декомпозиции, итеративные методы ЛП.

Практическое применение ЛП для социалистической экономики.

9. 70-80-е годы

Вводится новое понятие сложности оптимизационной задачи: установлены нижние границы для различных классов оптимизационных задач ( и др.).

Было установлено: если метод имеет сложность, совпадающую с нижней границей, то он оптимален, т. е. не существует методов, которые решают все задачи класса быстрее (в отношении порядка).

Построен итеративный метод решения задачи ЛП, для которой была доказана полиномиальная сходимость ()

Литература

1.Канторович методы организации и планирования производства. Л.: Изд-во Ленинградский университет, 1939, 64с.

2. , Гольштейн и методы линейного программирования. М.: Советское радио. 1964, 491с.

3. Карманов программирование. М.: Наука, 1975, 272с.

4. , Рубинштейн программирование. Новосибирск: Изд-во «Наука», Сибирское отделение, 1987, 272с.

5. Мухачева раскрой промышленных материалов. Применение АСУ. М.: Машиностроение, 1984,174с.

6. , , Мартынов и методы расчета раскроя-упаковки геометрических объектов. Уфа: УГАТУ, 1998, 217с.

7. , , Картак двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. Москва: Изд-во МАИ, 2004, 192с.

Главные научные центры по математическому программированию

Москва: МГУ, Центральный экономико-математический институт, Вычислительный центр

Киев: Институт кибернетики им.

Новосибирск: Институт математики им. Сибирского отделения РАН, Новосибирский государственный университет

Ленинград: Ленинградский государственный университет

Задача планирования производства

Вид сырья Нормы расхода сырья (кг) на одно изделие Общее количество сырья на складе (кг) А В I II III 12 4 13 4 4 12 300 120 252 Прибыль от реализации одного изделия (у. е.) 30 40

Учитывая, что изделия А и В могут производиться в любых соотношениях (сбыт обеспечен), требуется составить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий будет максимальной. Предположим, что предприятие изготовит х1 изделий вида А и х2 изделий вида В. Поскольку производство продукции ограничено имеющимся в распоряжении предприятия сырьем каждого вида, и количество изготовленных изделий не может быть отрицательным, должны выполняться следующие условия: 1) х1, х2 ³ 0 2) 12х1 + 4 х2 £ 300 4 х1 + 4 х2 £ 120 3 х1 + 12 х2 £ 252 Максимальная прибыль от реализации х1 изделий вида А и х2 изделий вида В составит m(х) = max (30 х1 + 40 х2 ) x

Задача об оптимальной смеси

Цель – подобрать оптимальный состав коктейля из трех компонентов: коньяка, шампанского и сока. Стоимости ингредиентов смеси соответственно: с1=50, с2=100, с3=20; Содержание в них алкоголя: а1=0,4; а2=0,5; а3=0,0; Вкусовые качества в баллах: в1=4, в2=8, в3=10.

Пусть хi (i = 1,2,3) – доля каждого компонента в коктейле (все расчеты ведем на единицу объема). Стоимость коктейля определится функцией: f1(x1, x2, x3)= с1 x1+ с2 x2+ с3 x3 Крепость коктейля определится функцией: f2(x1, x2, x3)= a1 x1+ a2 x2+ a3 x3 Вкус коктейля определится функцией: f3(x1, x2, x3)= в1 x1+ в2 x2+ в3 x3 Естественное желание – получить коктейль минимальной стоимости, максимальной крепости и максимального вкуса (противоречивые критерии!)

Задача об оптимальной смеси (продолжение)

Выберем критерий – оптимизация стоимости, а остальные критерии ограничим на требуемом уровне:

Крепость ограничим долей алкоголя в 0,2, а вкус – 8 баллами.

При этом должны выполняться следующие условия:

1) хi ≥ 0 (i = 1,2,3)

2) 0,4 x1+ 0,5 x2+ 0 x3 ≥ 0,2

4 x1+ 8 x2+ 10 x3 ≥ 8

x1+ x2+ x3 =1

Минимальная стоимость составит

m(х) =min (50 x1+ 100 x2+ 20 x3)

x

Некоторые определения

Выпуклой комбинацией n точек x1, x2,…,xn называется любая линейная комбинация вида λ1x1+λ2x2+…+λnxn=x, где λj≥0, λ1+λ2+…+λn=1, j=1,2,…,n.

Некоторые определения

Некоторые определения

1. Пусть М = {a1 , a2, ..., аm} – множество вещественных чисел R

Подмножество М на­зывают ограниченным сверху, если все его элементы не пре­восходят некоторого с R, где с называют верхней границей для М.

2. Для каждого ограниченного сверху непу­стого множества MR среди его верхних границ имеется минимальная, которую называют супремумом множества М и обозначают через sup M. Если же множество MR не является ограниченным сверху, то пишут sup M=+.

Множество М R называют ограниченным снизу, если все его элементы не меньше некоторого числа с R.

Соответствующие с R называют нижними грани­цами, а наибольшую из них — инфимумом множества М, который обозначают через inf M.

Если же множество MR не является ограниченным снизу, то пишут

inf M =-.

Некоторые определения

3. Не каждое ограниченное сверху множество MR имеет наибольший элемент, обозначаемый обычно через max М. Однако если такой элемент существует, то max М = sup М.

Если в множестве MR име­ется наименьший элемент, обозначаемый через min M, то это множество является ограниченным снизу и при этом min М= inf M.

5. Система векторов x1, x2,…,xr, r≥2, называется линейно зависимой, если хотя бы один из векторов системы является линейной комбинацией остальных, и линейно независимой – в противном случае.

6. Максимальное число линейно независимых векторов в n-мерном пространстве равно n.

7. Любая совокупность n линейно независимых векторов n-мерного пространства образует базис n-мерного пространства.

Некоторые определения

8. Какова бы ни была прямоугольная матрица

,

максимальное число линейно независимых строк (т. е. со­ответствующих n-мерных векторов) совпадает с максималь­ным числом линейно независимых столбцов (т. е. соответ­ствующих m-мерных векторов). Это число называется ран­гом матрицы А. При этом квадратную матрицу

порядка m называют неособенной, если ее ранг r совпадает с m. Если отвечающая системе линейных уравнений квадратная матрица А является неособенной, то эта система имеет единственное решение при любых свободных членах .

Некоторые определения

Задачи выпуклого программирования: целевая функция f и все функции

(а следовательно, и множество допустимых решений Q) являются выпуклыми; любой локальный минимум является глобальным.

Задачи линейного программирования: все функции f и

являются линейными, так что множество допустимых решений Q оказывается выпуклым линейным многогранным множеством.

Рассмотренные задачи (слайды 8-10) - являются задачами линейного программирования (ЛП).

Любой вектор Х, удовлетворяющий ограничениям задачи ЛП, называется допустимым вектором.

Допустимый вектор, доставляющий max или min целевой функции задачи ЛП, называется оптимальным вектором.

Геометрическая интерпретация задач линейного программирования

Задача планирования производства m(х) = max (30 х1 + 40 х2 ) x 1) х1, х2 ³ 0 2) 12х1 + 4 х2 £ 300 4 х1 + 4 х2 £ 120 3 х1 + 12 х2 £ 252

Основные этапы графического метода решения задач ЛП 1.  Строятся прямые, уравнения которых получаются в результате замены в ограничениях 1) и 2) знаков неравенств на знаки точных равенств. 2.  Находятся полуплоскости, определяемые каждым из ограничений задачи 3.  Определяется область допустимых решений - ОДР (многоугольник решений) 4.  Строится вектор С =(С1;С2) (C1 и C2 – коэффициенты при неизвестных в целевой функции m(x)) 5.  Строится линия уровня – как перпендикуляр к вектору С, проходящая через ОДР 6.  Линия уровня передвигается в направлении вектора С (если задача поставлена на max) или в противоположном направлении (если задача поставлена на min). В результате находится либо точка оптимума (граничная точка линии уровня с ОДР), либо устанавливается неограниченность функции на множестве допустимых решений. 7.  Определяются координаты точки оптимума, и вычисляется значение целевой функции в этой точке.

Геометрическая интерпретация задач линейного программирования

Графический метод решения задач ЛП

При нахождении решения задачи ЛП графическим методом могут встретиться следующие случаи:

Целевая функция m принимает Целевая функция m принимает max в любой

max в единственной точке А точке отрезка АВ

Графический метод решения задач ЛП

При нахождении решения задачи ЛП графическим методом могут встретиться следующие случаи:

Целевая функция не ограничена сверху Система ограничений задачи несовместна

на множестве допустимых решений (некорректная постановка задачи). Нет ОДР

Общая форма задачи ЛП

Пусть заданы: множества I={1,2…m} и J={1,2…n}, причем I= I1U I2, I1 Ç I2 = Æ, J= J1UJ2, J1Ç J2 = Æ, вещественные числа аij, iÎI, jÎJ; bi , iÎI, сj, jÎJ.

ЗАДАЧА 1 (прямая со смешанными ограничениями)

Максимизировать линейную функцию

(1)

на множестве векторов х=( х1,х2, …хn,), (2)

удовлетворяющих условиям:

1.  хj ³0 для jÎJ2 (3)

2. (4)

Двойственная задача ЛП

ЗАДАЧА 1* (двойственная со смешанными ограничениями).

Минимизировать линейную функцию

(5)

на множестве векторов y=(y1,y2,…..ym), (6)

удовлетворяющих условиям:

1. yi ≥ 0 для iÎI2 (7)

2. (8)

Определение.

Векторы (2), (6), удовлетворяющие условиям (3), (4) и (7), (8) называются допустимым для задачи 1 и задачи 1* соответственно.

Допустимые векторы (2), (6), доставляющие максимум функции (1) и минимум функции (5) соответственно, называются оптимальными.

Правила составления двойственной задачи ЛП

  В задаче 1 имеется n-переменных и m - ограничений типа (4). В задаче 1* имеется m –переменных и n-ограничений типа (8). Это значит, что каждой переменной в задаче 1 соответствует ограничение в задаче 1* и каждому ограничению в задаче 1 соответствует переменная в задаче 1*.

  В задаче 1 требуется максимизировать целевую функцию на множестве заданных ограничений больше 0. В задаче 1* требуется минимизировать целевую функцию на множестве заданных ограничений меньше 0.

  Коэффициенты сj линейной функции (1) в задаче 1 являются свободными членами ограничений (8) задачи 1*, свободные члены bi ограничений (4) в задаче 1 являются коэффициентами линейной функции (5) задачи 1*.

  Коэффициенты при неизвестных аij в задачах 1 и 1* одни и те же, но матрицы из этих коэффициентов транспонированы по отношению друг к другу.

  В задаче 1 все неравенства типа ³ , а в задаче 1* все неравенства типа £.

  Если на переменную задачи 1 налагается условие неотрицательности, то соответствующее ограничение в двойственной задаче является неравенством, а если условия неотрицательности на переменную нет, то соответствующее ограничение в задаче 1* является уравнением. И наоборот.

Пример составления двойственной задачи ЛП

Пример 1. Записать двойственную задачу к следующей задаче линейного программирования. ЗАДАЧА1. Найти х = (х1, х2, х3, х4), удовлетворяющий условиям:

Решение. Заметим, что т. е все переменные связаны условием неотрицательности, и все ограничения выполняются как неравенства. Двойственная задача имеет вид: ЗАДАЧА 1* Найти удовлетворяющие условиям:

Пример составления двойственной задачи ЛП

Пример 2. ЗАДАЧА 1. Требуется мак­симизировать линейную функцию =2x1 — х2 + Зх3 + х4 — 5x5 на множестве пятимерных векторов х = (х1, х2, х3, х4, х5), удовлетворяющих условиям , , , Зх1 + 2х2 - 5х3 + х5 - 7 0, 3х2 - 4х3 - 2х4 + 1 = 0, 2х1 + 2х3 - 3х4 + х5 0.

Решение. ЗАДАЧА 1* Требует­ся минимизировать линейную функцию на множестве трехмерных векторов, удовлетворяющих условиям , , 3y1 + 2y3 + 2 0, 2y1 + 3y2 -1 = 0, - 5y1 + 4y2 + 3y3 + 3 0, - 2y2 - 3y3 +1 0, y1 + y3 - 5 = 0.

Связь между задачами 1 и 1*

Связь между парой двойственных задач устанавливает следующая лемма 1:

Для любых допустимых векторов х и у в задачах 1 и 1* выполняются неравенства

µ(x) £(у), (9)

причем (9) выполняется как равенство в том и только в том случае, если справедливы следующие соотношения:

(10)

(11)

Связь между задачами 1 и 1*

Доказательство. Имеем:

хj ³0 для jÎJ2

(12)

Суммируя полученные соотношения, получим с учетом того, что (13)

Связь между задачами 1 и 1*

Доказательство (продолжение). Имеем:

yi ≥ 0 для iÎI2

(14)

(15)

Правые части в соотношени­ях (13) и (15) отличаются лишь порядком суммирова­ния и, следовательно, равны между собой, т. е. выполняется µ(x) £(у) (9). Для достижения равенства в (9), очевидно, не­обходимо и достаточно, чтобы достигались равенства во всех неравенствах (13) и (15). Последнее эквива­лентно выполнению соотношений (10) и (11) ▄

Признак оптимальности в краткой форме

Для оптимальности допустимого вектора х=( х1,х2, …хn,) в задаче 1 достаточно существования допустимого вектора y=(y1,y2,…..yn) в задаче 1*, удовлетворяющего условию

m(х)= n(у) (16)

Тогда допустимый вектор y=(y1,y2,…..yn) также является оптимальным в задаче 1*.

Доказательство.

Пусть вектор х допустимый и существует допустимый вектор у такой, что справедливо (16). Покажем, вектор х оптимальный.

Рассмотрим некоторый другой оптимальный вектор х′ в задаче 1 (х′≠х), тогда имеем пару векторов х′ и у. Для этой пары допустимых векторов справедлива лемма 1, т. е. m(х′)≤ n(у) =m(х) и m(х′)≤m(х). Отсюда следует что х – оптимальный вектор.

Покажем теперь, что вектор у также является оптимальным.

Рассмотрим некоторый другой оптимальный вектор у′ в задаче 1 (у′≠у), тогда имеем пару векторов х и у′ . Для этой пары допустимых векторов справедливо лемма 1, т. е. n( у′)≥m(х)= n(у) и n(у)≤ n( у′). Отсюда следует что у – оптимальный вектор.▄

Признак оптимальности в развернутой форме

Для оптимальности допустимого вектора х=(х1,х2…,хn,) в задаче 1 достаточно существование m-мерного вектора у=(у1,у2,у3,…,уm), удовлетворяющего условиям:

а) уi і 0, iОI2

б) еaijyi + cj = 0, jОJ1,

iОI

в) еaijyi + cj, £ 0, jОJ2,

iОI

г) еaijyi + cj, = 0, если хj >0 для jОJ2,

iОI

д) уi = 0, если еaijxj + bi >0, iОI2 ,

jОJ

тогда вектор у является оптимальным в задаче 1*.

Пример применения признака оптимальности в развернутой форме

Как этим признаком пользоваться?

Предположим, что мы имеем допустимый вектор х, т. е. хj ≥0 и такие, что , .

Тогда попытаемся найти вектор у из уравнений б), г), д). Эта система совместна и имеет единственное решение, если выполняются следующие условия:

1)  Количество уравнений в системе m (совпадает с числом переменных);

2)  Матрицы при неизвестных – неособенные

Пример применения признака оптимальности в развернутой форме

Проверить вектор на оптимальность в следующей задаче ЛП: Максимизировать при условиях:

Решение. Решение задачи необходимо начинать с проверки допустимости данного вектора . Подставляя значения компонент вектора в ограничении I0 и 20, убеждаемся, что все они выполняются. Для проверки остальных условий признака оптимальности составляем двойственную задачу: Требуется найти вектор , удовлетворяющий условиям:

Пример применения признака оптимальности в развернутой форме