![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задача математического программированияСодержание книги Похожие статьи вашей тематики
Поиск на нашем сайте
Методы оптимизации
Математическая модель Математическая модель — описание решаемой задачи в математических терминах. Математическая модель описывает исследуемую систему и позволяет выразить ее эффективность в виде целевой функции W = f (X, Y), где X = (x 1,…, xn) — управляемые переменные, Y = (y 1,…, y m) — неуправляемые переменные(исходные данные). Связь между переменными X и исходными данными Y выражается с помощью ограничений j (X, Y) £ 0. Виды моделей · детерминированные; · вероятностные; · игровые; · неполные (задачи в условиях неопределенности).
Исследованием детерминированных моделей занимается математическое программирование (МП).
Термин «программирование» означает «поиск наилучших планов» (programming – планирование – составление плана или программы действий).
Задача оптимизации (
Задача математического программирования Оптимальным решением задачи (минимизации) называют допустимое решение, минимизирующее f (x) на множестве всех допустимых решений. Задачи математического программирования
История математического программирования Б.Т. Поляк, Институт проблем управления, Москва История математического программирования в СССР: попытка анализа
История математического программирования 1. Леонард Эйлер, 1707-1783, первый ученый, занимавшийся оптимизацией в России 2. Чебышев П.Л., 1821-1894, основы выпуклой оптимизации, решал практические оптимизационные задачи: построение наименее искаженной географической карты, оптимальный раскрой, наилучший выбор параметров механических устройств 3. А.А. Марков, 1856-1922, известны работы в теории чисел и теории вероятностей (Марковские цепи, Марковские процессы) 4. А.М. Ляпунов, 1857-1918, разработал теорию устойчивости для дифференциальных обыкновенных уравнений, тем самым внес огромный вклад в развитие непрерывной оптимизации, предложил инструмент для проверки сходимости численных методов оптимизации История математического программирования 5. Л.В. Канторович, 1912-1986, в 1975г. получил Нобелевскую премию в области экономики, один из основателей численного анализа в нашей стране, одним из первых признал информатику как новую ветвь в математике.
Отец новой науки ОПТИМИЗАЦИИ, которая включает стандартное математическое программирование. С именем Канторовича Л.В.связаны следующие достижения: Линейное программирование, 1939: Опубликована книга (67 стр.), в которой рассматривался новый тип оптимизационных задач. Формы записи этих задач были иными, чем стандартная формулировка задачи ЛП, причем модель, рассматриваемая в западной литературе - частный случай модели Канторовича. Общие условия оптимальности, 1940 Техника функционального анализа, 1939-1948
История математического программирования 6. Г.Ш. Рубинштейн, ученик Канторовича Л.В., учитель д.т.н., проф. УГАТУ Мухачевой Э.А. В 1961г. вышла книга Канторовича Л.В. и Рубинштейна Г.Ш., в которой давались математические формулировки задачи ЛП и приводились численные методы ее решения, были введены понятия двойственных переменных, которые назывались «объектно-обусловленными оценками». 7. В 50-е годы – интенсивные исследования в области ЛП. Стали известны работы западных ученых: Дж. Данцига, Г.Куна, А. Таккера и др. по ЛП. Выпущен первый учебник на русском языке по ЛП Юдиным Д.Б., Гольштейном Е.Г. 8. 60-е годы Появилась общая теория двойственности для задач выпуклой оптимизации (Гольштейн Е.Г.), появились труды по стохастической оптимизации. Литература 1.Канторович Л.В. Математические методы организации и планирования производства. Л.: Изд-во Ленинградский университет, 1939, 64с. 2. Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. М.: Советское радио. 1964, 491с. 3. Карманов В.Г. Математическое программирование. М.: Наука, 1975, 272с. 4. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Изд-во «Наука», Сибирское отделение, 1987, 272с. 5. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение АСУ. М.: Машиностроение, 1984,174с. 6. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов. Уфа: УГАТУ, 1998, 217с. 7. Мухачева Э.А., Валеева А.Ф., Картак В.М. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. Москва: Изд-во МАИ, 2004, 192с.
Задача об оптимальной смеси
Общая форма задачи ЛП Пусть заданы: множества 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,х2, …хn,), (2) удовлетворяющих условиям:
1. хj ³0 для jÎJ2 (3) 2.
Двойственная задача ЛП ЗАДАЧА 1* (двойственная со смешанными ограничениями). Минимизировать линейную функцию
на множестве векторов y= (y1,y2,…..ym), (6) удовлетворяющих условиям: 1. yi ≥ 0 для iÎI2 (7) 2.
Определение. Векторы (2), (6), удовлетворяющие условиям (3), (4) и (7), (8) называются допустимым для задачи 1 и задачи 1* соответственно. Допустимые векторы (2), (6), доставляющие максимум функции (1) и минимум функции (5) соответственно, называются оптимальными. Пример составления двойственной задачи ЛП
Пример составления двойственной задачи ЛП
Связь между задачами 1 и 1*
Связь между парой двойственных задач устанавливает следующая лемма 1: Для любых допустимых векторов х и у в задачах 1 и 1* выполняются неравенства µ(x) £ причем (9) выполняется как равенство в том и только в том случае, если справедливы следующие соотношения:
Связь между задачами 1 и 1* Доказательство. Имеем:
Связь между задачами 1 и 1* Доказательство (продолжение). Имеем:
yi ≥ 0 для iÎI2
Правые части в соотношениях (13) и (15) отличаются лишь порядком суммирования и, следовательно, равны между собой, т.е. выполняется µ(x) £
Доказательство. Пусть вектор х допустимый и существует допустимый вектор у такой, что справедливо (16). Покажем, вектор х оптимальный. Рассмотрим некоторый другой оптимальный вектор х′ в задаче 1 (х′≠х), тогда имеем пару векторов х′ и у. Для этой пары допустимых векторов справедлива лемма 1, т. е. m (х′) ≤ n (у) =m (х)и m (х′) ≤m (х). Отсюда следует что х – оптимальный вектор. Покажем теперь, что вектор у также является оптимальным. Рассмотрим некоторый другой оптимальный вектор у′ в задаче 1 (у′≠у), тогда имеем пару векторов х и у′. Для этой пары допустимых векторов справедливо лемма 1, т. е. n(у′)≥m(х)= n(у) и n(у)≤ n(у′). Отсюда следует что у – оптимальный вектор.▄ Пример применения признака оптимальности в развернутой форме
Как этим признаком пользоваться? Предположим, что мы имеем допустимый вектор х, т.е. хj ≥0 и такие, что Тогда попытаемся найти вектор у из уравнений б), г), д). Эта система совместна и имеет единственное решение, если выполняются следующие условия: 1) Количество уравнений в системе m (совпадает с числом переменных); 2) Матрицы при неизвестных – неособенные
Пример применения признака оптимальности в развернутой форме
Пример применения признака оптимальности в развернутой форме
Пример применения признака оптимальности в развернутой форме
И ее следствия Для разрешимости задачи математического программирования (как и в любой оптимизационной задачи) необходимо, чтобы множество допустимых решений было не пусто, и целевая функция на этом множестве была ограничена сверху (если задача на максимум), либо снизу (если задача на минимум). Теорема двойственности. Каковы бы ни были исходные данные, для задач 1 и 1* имеет место один из следующих взаимоисключающих случаев. 1. В задачах 1 и 1* имеются оптимальные векторы х и у и 2. В задаче 1 существуют допустимые векторы х из некоторого множества Х, но линейная функция 3. В задаче 1* существуют допустимые векторы 4. В задачах 1 и 1* нет допустимых векторов, то есть Базисное множество
Пусть Множество К называют базисным множеством, если отвечающие ему векторы
на множестве n -мерных векторов х = (х1, х2,..., хn), удовлетворяющих условиям 1. 2. Пример. Векторы Лемма 2 Каково бы ни было базисное множество K, для соответствующих векторов х (К) и у (К) имеет место равенство
Доказательство. Так как
что и требовалось показать.▄
Лемма 3 Пусть задано некоторое базисное множество К и отвечающий ему вектор х (К) = (х1, х2,..., хп). Кроме того, для некоторого
Тогда при любом
удовлетворяет условию
Лемма 3 Доказательство. Имеем: После умножения соотношения (18) на Имеем: Складывая (19) и (20), получаем
Следовательно, интересующий нас вектор
Следствие 1 из леммы 3 Вектор Возможны два случая: а). Все коэффициенты gk≤ 0 в б) среди коэффициентов gk имеются положительные Следствие 1. Если имеет место случай а),то векторы Действительно,
По теореме двойственности (слайд 42) в двойственной задаче допустимый вектор не существует, следовательно, вектор х не оптимальный ▄
Следствие 2 из леммы 3 Вектор Случай б) среди коэффициентов gk имеются положительные Следствие 2. Если имеет место случай б),то векторы
причем
Пусть V. Подготовка информации к следующему шагу. В качестве нового допустимого базисного множества принимаем K' = (K\ (k* }) Из базиса удаляется вектор
Вычисляем компоненты соответствующего вектора х (К') = ( по формулам
При этом
Пример решения задачи ЛП с помощью МПУ Прямая задача А Двойственная задача А*
Найдем базис, базисное множество К, построим исходный допустимый вектор x (K)
Векторы α3, α4 – линейно независимы, базисное множество K ={3,4}.
Пример решения задачи ЛП с помощью МПУ I. Определение вектора y (К). Шаг Единственное решение имеет система:
II. Проверка двойственной допустимости ДБМ К
Пример решения задачи ЛП с помощью МПУ III. Вычисление коэффициентов разложения вектора
IV. Определение Определяем, какой вектор удалить из базиса.
Пример решения задачи ЛП с помощью МПУ V. Подготовка информации к следующему шагу. В качестве нового допустимого базисного множества принимаем
k
2 шаг ………………… Методы оптимизации
Математическая модель Математическая модель — описание решаемой задачи в математических терминах. Математическая модель описывает исследуемую систему и позволяет выразить ее эффективность в виде целевой функции W = f (X, Y), где X = (x 1,…, xn) — управляемые переменные, Y = (y 1,…, y m) — неуправляемые переменные(исходные данные). Связь между переменными X и исходными данными Y выражается с помощью ограничений j (X, Y) £ 0. Виды моделей · детерминированные; · вероятностные; · игровые; · неполные (задачи в условиях неопределенности).
Исследованием детерминированных моделей занимается математическое программирование (МП).
Термин «программирование» означает «поиск наилучших планов» (programming – планирование – составление плана или программы действий).
Задача оптимизации (
Задача математического программирования Оптимальным решением задачи (минимизации) называют допустимое решение, минимизирующее f (x) на множестве всех допустимых решений.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-26; просмотров: 1133; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.137.178.186 (0.244 с.) |