Методы поиска у задачах условной оптимизации

Строим новый план. Значение целевой функции для этого опорного плана равно: Искомый элемент равен 3 Для этого элемента запасы равны 150, потребности 80. Поскольку минимальным является 80, то вычитаем его. x24 = min(150,80) = 80. 455x1002183150 - 80 = 70739x50501007080 - 80 = 00Искомый элемент равен 1 Для этого элемента запасы равны 70, потребности 100. Поскольку минимальным является 70, то вычитаем его. x22 = min(70,100) = 70. 455x100x1x370 - 70 = 0739x5050100 - 70 = 307000Искомый элемент равен 3 Для этого элемента запасы равны 50, потребности 30. Поскольку минимальным является 30, то вычитаем его. x32 = min(50,30) = 30. 4x5x100x1x30739x50 - 30 = 205030 - 30 = 07000Искомый элемент равен 4 Для этого элемента запасы равны 100, потребности 50. Поскольку минимальным является 50, то вычитаем его. x11 = min(100,50) = 50. 4x5x100 - 50 = 50x1x30x39x2050 - 50 = 007000Искомый элемент равен 5 Для этого элемента запасы равны 50, потребности 70. Поскольку минимальным является 50, то вычитаем его. x13 = min(50,70) = 50. 4x5x50 - 50 = 0x1x30x39x200070 - 50 = 2000Искомый элемент равен 9 Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его. x33 = min(20,20) = 20. 4x5x0x1x30x39x20 - 20 = 00020 - 20 = 0001234Запасы14[50]55[50]6100221[70]83[80]150373[30]9[20]1050Потребности501007080В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Число занятых клеток таблицы=6. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 4; 0 + v1 = 4; v1 = 4u1 + v3 = 5; 0 + v3 = 5; v3 = 5u3 + v3 = 9; 5 + u3 = 9; u3 = 4u3 + v2 = 3; 4 + v2 = 3; v2 = -1u2 + v2 = 1; -1 + u2 = 1; u2 = 2u2 + v4 = 3; 2 + v4 = 3; v4 = 1v1=4v2=-1v3=5v4=1u1=04[50]55[50]6u2=221[70]83[80]u3=473[30]9[20]10Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij(2;1): 2 + 4 > 2; ∆21 = 2 + 4 - 2 = 4 (3;1): 4 + 4 > 7; ∆31 = 4 + 4 - 7 = 1 max(4,1) = 4 Выбираем максимальную оценку свободной клетки (2;1): 2 Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 1234Запасы14[50][-]55[50][+]610022[+]1[70][-]83[80]150373[30][+]9[20][-]1050Потребности501007080Цикл приведен в таблице (2,1 → 2,2 → 3,2 → 3,3 → 1,3 → 1,1). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 1234Запасы14[30]55[70]610022[20]1[50]83[80]150373[50]91050Потребности501007080Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 4; 0 + v1 = 4; v1 = 4u2 + v1 = 2; 4 + u2 = 2; u2 = -2u2 + v2 = 1; -2 + v2 = 1; v2 = 3u3 + v2 = 3; 3 + u3 = 3; u3 = 0u2 + v4 = 3; -2 + v4 = 3; v4 = 5u1 + v3 = 5; 0 + v3 = 5; v3 = 5v1=4v2=3v3=5v4=5u1=04[30]55[70]6u2=-22[20]1[50]83[80]u3=073[50]910Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят:Таким образом, из 1-го склада необходимо груз направить в 1-й магазин (30), в 3-й магазин (70). Из 2-го склада необходимо груз направить в 1-й магазин (20), в 2-й магазин (50), в 4-й магазин (80). Из 3-го склада необходимо весь груз направить в 2-й магазин. Применение информационных технологий для решения задачи условной оптимизацииКак упоминалось выше, в теории оптимальных решений не существует универсальных алгоритмов для решения задач оптимизации, но существуют методы, которые могут применяются, как вспомогательные в данной области. Рассмотрим пример решения задачи теории игр средствами линейного программирования с использованием возможностей табличного процессора Excel.Постановка задачи:Торговый посредник может приобрести для последующей перепродажи товары четырех видов (). Реализация и прибыль (в у.е.) зависят от вида товара и состояния спроса. Спрос в зависимости от макроэкономической ситуации и других факторов (например, сезонность) может принимать одно из трех состояний (). Эти состояния не характеризуются стохастической неопределенностью и не прогнозируются.Определить оптимальные пропорции приобретения товаров по критерию максимума средней гарантированной прибыли при заданной матрице прибыли.20161214181010128121410Последовательность выполнения задания:Используя платежную матрицу игры «с природой» найти нижнюю и верхнюю цены игры и сделать вывод о наличии (отсутствии) седловой точки.Составить пару двойственных задач (с позиции приобретаемых товаров – стратегия закупок; с позиции спроса – стратегия «природа»).Решить эти задачи с использованием стандартного пакета прикладных программ ЗЛП (например, «Поиск решения» в Excelили QSB).Сравнить полученные решения и сделать необходимые проверки.Представить ответ в развернутом виде.Решение:Найдем нижнюю и верхнюю цены игры для определения наличия седловой точки. Для этого определим минимальные значения по строкам и максимальные значения по столбцам матрицыmin201612121418101010128812141010max201812верхняяценаигры ;нижняя цена игры Так как , то данная игра имеет седловую точку и имеет решение в чистых стратегиях.Цена игры=12.Сведем рассматриваемую задачу к прямой и двойственной задаче линейного программирования. Рассмотрим задачу с позиции спроса.Разделимобе части ограничений системы на V:Выполним замену Приведем задачу к канонической форме:Решение задачи линейного программирования средствами MSExcelПостановка задачиИтерации решения задачиОтчет о решении задачиВычислим среднюю цену игры по формуле:С позиции приобретаемых товаров получим следующую постановку задачи:Решение задачи средствами MSExcelПостановка задачиИтерацииРезультаты вычисленииТаким образом, значения целевой функции двойственных задач совпадают и равны 0,08.заключениеВ настоящее время большое количество технических задач требует поиска экстремума некоторой целевой функции на строго заданной области определения, то есть применяется условная оптимизация.Существующие методы решения оптимальных задач отличаются своей многогранностью и широким спектром применения. При этом эффективность выбранного метода в том или ином случае зависит от направления анализа предложено в задаче математической модели.В данном исследовании были изучены вопросы использования различных методов оптимальных решений для решения задач условной оптимизации. Каждый из представленных в работе методов имеет свои особенности и область применения, но многие из них могут быть использованы для решения задач различной направленности, а также в сочетании с другими методами для достижения максимального результата.В ходе исследования рассмотрено практическое применение методов линейного программирования для решения задач условной оптимизации, а также использование для этих целей средств информационных технологий.Список использованной литературыАоки М. Введение в методы оптимизации. М.: Наука, 1977. 334 с. Банди Б. Методы оптимизации // М.: Радио и связь, 1988.– 128 с.Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, Гл. ред. физ.-мат. лит., 2012.– 824 c. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985. 509 c. Данко П. Е., Попов А. Г., Кожевникова Т. Я. Высшая математика в упражнениях и задачах. В 2-х ч. Ч I: Учеб. пособие для втузов. – 5-е изд., испр. – М.: Высш. шк. 2012. – 304 с.: ил. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 2012. 432 с. Мину М. Математическое программирование. Теория и ал- горитмы. М.: Наука. Гл. ред. физ.-мат. лит., 2013. 488 c. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оп- тимизации. М.: Наука. Гл. ред. физ.-мат. лит., 2013. 352 c. Орлянская И.В. Современные подходы к построению методов глобальной оптимизации // Электронный журнал «Исследовано в России». –С. 2097-2108. http://zhurnal.ape.relarn.ru/articles/2002/189.pdf (19.05.2009).Пшеничный Б.Н., Данилин Ю.М. Численные методы в экс- тремальных задачах. М.: Наука, 2011. – 320 с. Партыка Т. Л., Попов И. И. Математические методы. – Учебник. – М.: ФОРУМ: ИНФРА-М, 2013. – 464 с. (Профессиональное образование).Савин А.Н., Шараевский Ю.П., Тимофеева Н.Е. Модификация комплексного метода условной оптимизации Бокса для определения размеров замедляющих систем по заданным электродинамическим характеристикам // 15-я Международная Крымская конференция «СВЧ-техника и телекоммуникационные технологии», 2013. –С. 779-780.Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации: Учеб. пособие. — 2-е изд. — М.: ФИЗМАТЛИТ, 2012. 368 с. Таха, Хемди А. Введение в исследование операций, 7-издание,: Пер. с англ. – М.: Издательский дом «Вильямс», 2011. – 912 с.: ил. – Парал. Тит. англ. Фиакко А., Мак-Кормик Г. Нелинейное программирова- ние. Методы последовательной безусловной минимизации. М.: Мир, 1972. 240 с. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975. 536 c