Оптимизация систем управления. Методы многомерной оптимизации.

В этом случае мы имеем дело с неотрицательными решениями системы уравнений.Любая задача линейного программирования с помощью элементарных преобразований может быть приведена к каноническому виду.F(x)=c1x1+c2x2+...+cnxn ->max(min)a11x1+a12x2+...+a1nxn +х n +1 = b1a21x1+a22x2+...+a2nxn+х n +2 = b2 (3).......................am1x1+am2x2+...+amnxn+х n +т = bmxi≥0 (i=1..n),где F(x) – целевая функция; х1,х2,…,хn– базисные переменные; другие переменные именуются свободными.Задача имеет m+n ограничений, среди них m ограничений типа равенства и n ограничений неотрицательности. По определению крайняя точка удовлетворяет n линейно-независимым ограничениям задачи как вернымравенствам.Базисные переменныеСвободные членыX 1X 2…X nX n+1X n+2…Xn+mX n+1b1a 11a 12…a 1n10…0X n+2b2a 21a 22…a 2n01…0…………………………X n+mb ma m1a m2…amn00…1F(x)0-c1-c2…-cn00…0Разберем алгоритм перехода к следующим симплекс-таблицам:1. Находим ключевой столбец. Это столбец соответственный минимально отрицательному (максимально положительному) элементу последней (индексной) строке:Если отрицательных элементов в индексной строке нет, то план оптимальный.2. В ключевом столбце находятся положительные коэффициенты, если таких нет, то задача не имеет решений;3. Выбираем ключевую строку:Среди выбранных коэффициентов столбца, для которых абсолютная величина отношения соответственного свободного члена к этому элементу минимальна.Ключевой элемент – это элемент, расположенный на пересечении ключевого столбца и ключевой строки;4. Базисная переменная из ключевой строки переводится в разряд свободных, а свободная переменная в ключевом столбце переводится в разряд базисных. Строится новая таблица;5. В новой таблице:5.1 Все элементы ключевой строки делятся на ключевой элемент.5.2 Все элементы ключевого столба равны нулю, за исключением ключевого элемента.5.3 Столбец, у которого в ключевой строке имеется ноль, в новой таблице будет таким же.5.4 Строка, у которой в ключевом столбце имеется ноль, в новой таблице будет такой же.5.5 В остальные клетки записывается результат преобразования элементов старой таблицы.6. Переход к шагу 1.Через конечное число итераций либо будет получено решение задачи линейного программирования, либо будет установлено, что решение неограниченно.3.2 Постановка задачи и ее решениеДля производства изделий двух обличий склад может выпустить металла не более 150 кг, причем на изделие первого вида тратится пять килограмм, а на изделие другого вида три килограмма. Требуется планировать производство так, чтобы была обеспечена максимальная прибыль, если изделий первого вида требуется изготовить не более 20 штук, а изделий второго вида не более 25 штук, причем одно изделие первого вида стоит 7 руб., а изделие второго вида стоит 8 руб.Решение поставленной задачиx1 – количество изделий первого вида.x2 – количество изделий второго вида.F(x) – целевая функция.5x1 + 3x2 =150x120x225x1, x2≥0F(x) = 7x1 +8x2 maxПриведем заданную модель к каноническому виду, введя свободные переменные x3, x4, x5, обращающие неравенства в равенства. Переменные x3, x4, x5 входят в уравнение с коэффициентом единица и только один раз:5x1 + 3x2+x3 =150x1+x4=20x2+x5 =25x1, x2, x3, x4, x5≥0F(x)= 7x1 +8x2 +x3 +x4 +x5x3,x4,x5 – базисные переменные; x1,x2 – свободные переменные.Соберем симплекс – таблицу, отвечающую каноническому виду:Таблица2 – Итерация 1БазисСвободные чл.X1X2X3X4X 5X 315053100X 42010010X 52501001F(x)0-7-8000Выстроив первую таблицу, обследуем ее на оптимальность, то есть в последней строке таблицы разыскиваемнаибольший по модулю отрицательный элемент, в нашем случае – это -8. Из данного следует, что столбец х2делается ключевым. Далее в столбце х2 ищем ключевую строку: свободный член делим на элемент столбца х2, находящийся в этой же строке. Из обретенных делений находим минимальное, у нас это будет 25. То есть строка, в которой вышло минимальное частное, будет являться ключевой (строка х5). А элемент, стоящий на пересечении ключевого столбца и ключевой строки будет являться ключевым элементом, в нашей задаче это будет 1.Строим новую таблицу, следуя алгоритму, приведенному выше.Таблица 3 – Итерация 2БазисСвободныеX1X2X3X4X5X3755010-3X42010010X22501001F(x)200-70008Таблицу 3 проверяем на оптимальность таким же способом, что и изначальную таблицу. Находим ключевой элемент в таблице 3, и затем заново пересчитываем новую таблицу.Таблица 4 – Итерация 3БазисСвободныеX1X2X3X4X5X115100,20-0,6X4500-0,210,6X22501001F(x)305001,403,8В нашем случае таблица 4 стала окончательным решением, так как в последней строке нет отрицательных чисел, из этого следует, что мы нашли оптимальный план-решение поставленной задачи.X1=15; X2=25; Fmax=305.Для достижения максимальной прибыли, равной 305 руб., необходимо производить 15 изделий первого вида и 25 изделий второго вида в день.Вычислительная процедура симплекс-метода проявляется итерационным процессом. Если задача хранит несколько переменных и ограничений, то этот процесс очень громоздок. Во многие практические задачи умещаются десятки переменных и ограничений (иногда намного больше), и ясно, что глупо решать эти задачи вручную. Симплекс-метод – это метод для электронно-вычислительных машин. Закономерноформирование теории линейного программирования сошлось по времени с развитием ЭВМ. Без них применениеданной теории имело бы оченьограниченную область приложений.ЗаключениеНынешняя теория математического обоснования принятия решений во многом строится на теории оптимизации, и не может быть изложена довольно стройно без запаса знаний начал математического программирования и изучения операций.В последние годы в прикладной математике немалое внимание уделяется последнему классу задач оптимизации, содержащихся в отыскивании в заданной области точек максимального или минимального значения некоторой функции, зависящей от значительного числа переменных. Это, так именуемые задачи математического программирования, появляющиеся в самых различных сферах человеческой деятельности и прежде всего в экономических изучениях, в практике планирования и организации потребления.В предоставленной курсовой работе было разобраны некоторые виды решение задач оптимизации. Разобраны этапы построения решения данных задач, предложен алгоритм для решения этих задач, а также представлено решение задач.Список использованных источниковТ. М. Попова. Методы многомерной оптимизации: методические указания и задания к выполнению лабораторных работ по дисциплине «Методы оптимизации» для студентов направления «Прикладная математика»/ сост. – Хабаровск : Изд-во Тихоокеан. гос. ун-та, 2012. – 44 с.Вержбицкий В.М. Основы численных методов: Учебник для вузов. М.: Высшая школа, 2002. – 840 с. ISBN 5-06-004020-8Вентцель Е.С. Исследование операций. М.: Высшая школа, 2002. – 255 с.Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.Хемди А. ТахаГлава 3. Симплекс-метод // Введение в исследование операций = OperationsResearch: AnIntroduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8.Акулич И.Л.Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9.