Строим новый план. Значение целевой функции для этого опорного плана равно: Искомый элемент равен 3 Для этого элемента запасы равны 150, потребности 80. Поскольку минимальным является 80, то вычитаем его. x24 = min (150,80) = 80. 455×1 002 183 150 — 80 = 70 739×50 501 007 080 — 80 = 00Искомый элемент равен 1 Для этого элемента запасы равны 70, потребности 100. Поскольку минимальным является 70, то вычитаем его. x22 = min (70,100) = 70. 455×100x1x370 — 70 = 0739×5 050 100 — 70 = 307 000.
Искомый элемент равен 3 Для этого элемента запасы равны 50, потребности 30. Поскольку минимальным является 30, то вычитаем его. x32 = min (50,30) = 30. 4x5x100x1x30739×50 — 30 = 205 030 — 30 = 7 000.
Искомый элемент равен 4 Для этого элемента запасы равны 100, потребности 50. Поскольку минимальным является 50, то вычитаем его. x11 = min (100,50) = 50. 4x5x100 — 50 = 50x1x30×39×2050 — 50 = 7 000.
Искомый элемент равен 5 Для этого элемента запасы равны 50, потребности 70. Поскольку минимальным является 50, то вычитаем его. x13 = min (50,70) = 50. 4x5x50 — 50 = 0x1x30×39×200 070 — 50 = 2000.
Искомый элемент равен 9 Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его. x33 = min (20,20) = 20. 4x5x0x1x30×39×20 — 20 = 20 — 20 = 1 234.
Запасы14[50]55[50]6 100 221[70]83[80]150 373[30]9[20]1050.
Потребности501 007 080 В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Число занятых клеток таблицы=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][+]610 022[+]1[70][-]83[80]150 373[30][+]9[20][-]1050.
Потребности501 007 080.
Цикл приведен в таблице (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]610 022[20]1[50]83[80]150 373[50]91 050.
Потребности501 007 080.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы 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. Постановка задачи:
Торговый посредник может приобрести для последующей перепродажи товары четырех видов (). Реализация и прибыль (в у.е.) зависят от вида товара и состояния спроса. Спрос в зависимости от макроэкономической ситуации и других факторов (например, сезонность) может принимать одно из трех состояний (). Эти состояния не характеризуются стохастической неопределенностью и не прогнозируются. Определить оптимальные пропорции приобретения товаров по критерию максимума средней гарантированной прибыли при заданной матрице прибыли.
Последовательность выполнения задания:
Используя платежную матрицу игры «с природой» найти нижнюю и верхнюю цены игры и сделать вывод о наличии (отсутствии) седловой точки. Составить пару двойственных задач (с позиции приобретаемых товаров — стратегия закупок; с позиции спроса — стратегия «природа»).Решить эти задачи с использованием стандартного пакета прикладных программ ЗЛП (например, «Поиск решения» в 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.
