Линейное программирование - Программирование, компьютеры и кибернетика контрольная работа

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Минимизировать функцию f(x) на всей числовой оси методом Ньютона. Критерием достижения требуемой точности считать выполнение неравенства .
Найдем первую и вторую производные исходной функции:
Выберем начальное приближение . И осуществим вычисления по формуле
Далее мы заканчиваем вычисления, потому что данная точность достигнута. В результате мы получаем: и .
Осуществим проверку при помощи встроенной функции Minimize:
Выписать матрицу Q квадратичной функции f(x), найти ее градиент в точке и убедиться в выпуклости f(x) в .
Запишем исходную функцию в следующем виде:
Найдем градиент в точке по формуле , где r - вектор-столбец и равен :
Подставляя в полученную матрицу , мы получаем следующее значение градиента в данной точке:
Теперь убедимся в выпуклости f(x) в . Для того, чтобы исходная функция была выпуклой в , достаточно, чтобы матрица Q была положительно определена. Для этого найдем угловые миноры матрицы Q и если они будут больше нуля, то функция f(x) будет выпуклой в .
Так как , ,то функция f(x) выпукла в .
Проверка на выпуклость и нахождение градиента в точке x0
Ответ: градиент равен и функция f(x) будет выпуклой в .
Минимизировать квадратичную функцию методом наискорейшего спуска, заканчивая вычисления при , .
Тогда производные исходной функции будут иметь вид:
Выберем начальное приближение . Тогда
Для нахождения точки минимума функции найдем нули ее производной:
Зная , мы определим следующим образом:
И так далее по выше описанной цепочке.
Реализуем решение данной задачи в математическом пакете Mathcad.
Возьмем следующие начальное приближение и :
В результате получаем искомое решение и функцию :
Минимизировать функцию f(x) методом сопряженных направлений, заканчивая вычисления при , .
Тогда частные производные исходной функции будут иметь вид:
Решение будем искать по следующему алгоритму:
Для нахождения точки минимума функции используем метод перебора:
Для нахождения точки минимума функции используем метод перебора:
Для нахождения точки минимума функции используем метод перебора:
следовательно требуемая точность достигнута и
Решить задачу линейного программирования графическим методом.
Изобразим на плоскости наш многоугольник ABCDE (красного цвета) и одну из линий уровня (розового цвета).
Линии AB соответствует уравнение , BC соответствует , CD соответствует , DE соответствует и EA соответствует
Направление убывания функции указывает вектор . Совершая параллельный перенос линии уровня вдоль направления , находим ее крайнее положение. В этом положении прямая проходит через вершину многоугольника ABCDE. Поэтому целевая функция принимает минимальное значение в точке , причем
Решить задачу линейного программирования в каноническом виде графическим методом.
Матрица системы будет иметь следующий вид:
Ранг этой матрицы равен . Тогда число свободных переменных равно , поэтому для решения задачи можно использовать графический метод. Решив систему ограничений - равенств относительно базисных переменных , , получим:
Исключая с помощью полученной системы переменные , из выражения для целевой функции, получаем:
С учетом условия неотрицательности , , и последних равенств получаем следующую задачу:
Изобразим на плоскости наш многоугольник ABCDEJ (красного цвета) и одну из линий уровня (розового цвета).
Линии AB соответствует уравнение , BC соответствует , CD соответствует , DE соответствует , EJ соответствует и JA соответствует .
Направление убывания функции указывает вектор . Совершая параллельный перенос линии уровня вдоль направления , мы видим, что целевая функция содержит сторону AB многоугольника ABCDEJ. Таким образом, все точки отрезка AB являются точками минимума функции . Так как концы A и B имеют координаты и соответственно, то найдем отсюда координаты и :
Тогда любая точка минимума представима в виде
где . Минимальное значение целевой функции
Ответ: бесконечное множество решений
Решить задачу линейного программирования симплекс - методом, находя начальную угловую точку методом искусственного базиса.
Ее ранг равен 3. Введем дополнительные переменные и запишем условие вспомогательной задачи линейного программирования для рассматриваемого случая:
Считая дополнительные переменные базисными, запишем симплекс таблицу этой задачи, соответствующую угловой точке :
Произведем преобразования исходной симплекс-таблицы симплекс-методом следующим образом:
1) смотрим на нижнюю строку - выбираем тот столбец, в котором нижний элемент отрицательный, если таких столбцов несколько, то выбираем любой (в нашем случае выбираем первый столбец );
2) далее смотрим на последний и выбранный столбцы - сравниваем отношения элементов последнего и выбранного столбцов (в выбранном столбце берем только положительные числа), и выбираем тот элемент выбранного столбца, где отношение элементов будет наименьшим (в нашем случае 9/3 и 0/1, так как второе отношение наименьшее, следовательно, опорным элементом будет 1);
3) меняем местами переменные и , остальные переменные оставляем на своих местах;
4) на место опорного элемента ставим отношение 1/(опорный элемент);
5) на остальных местах разрешающей строки записываем соответствующие элементы исходной таблицы, деленные на опорный элемент;
6) на свободные места разрешающего столбца ставим со знаком минус соответствующие элементы исходной таблицы, деленные на опорный элемент;
7) оставшиеся свободные места в новой симплекс-таблице заполняем построчно следующим образом: из строки элементов исходной таблицы вычитаем произведение ее элемента из разрешающего столбца на уже заполненную разрешающую строку новой таблицы.
Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц:
В нижней строке последней симплекс-таблицы нет отрицательных элементов, следовательно, минимум вспомогательной целевой функции достигнут и есть угловая точка допустимого множества исходной задачи линейного программирования, тогда
Решить полностью целочисленную задачу линейного программирования методом Гомори.
Введем дополнительные переменные и запишем условие вспомогательной задачи линейного программирования для рассматриваемого случая:
Считая дополнительные переменные базисными, запишем симплекс таблицу этой задачи, соответствующую угловой точке :
Произведем преобразования исходной симплекс-таблицы симплекс-методом следующим образом: смотрим на нижнюю строку - выбираем тот столбец, в котором нижний элемент отрицательный, если таких столбцов несколько, то выбираем любой (в нашем случае выбираем первый столбец ); далее смотрим на последний и выбранный столбцы - сравниваем отношения элементов последнего и выбранного столбцов (в выбранном столбце берем только положительные числа), и выбираем тот элемент выбранного столбца, где отношение элементов будет наименьшим (в нашем случае 9/3 и 0/1, так как второе отношение наименьшее, следовательно, опорным элементом будет 1); меняем местами переменные и , остальные переменные оставляем на своих местах; на место опорного элемента ставим отношение 1/(опорный элемент); а остальных местах разрешающей строки записываем соответствующие элементы исходной таблицы, деленные на опорный элемент; на свободные места разрешающего столбца ставим со знаком минус соответствующие элементы исходной таблицы, деленные на опорный элемент; оставшиеся свободные места в новой симплекс-таблице заполняем построчно следующим образом: из строки элементов исходной таблицы вычитаем произведение ее элемента из разрешающего столбца на уже заполненную разрешающую строку новой таблицы. Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц:
Как видим, в последней строке таблицы все элементы положительны, то есть получаем решение и . Но это решение не удовлетворяет условию целочисленности, поэтому дополняем последнюю симплекс-таблицу строкой, используя следующие правила: среди нецелых элементов выбирается произвольный элемент , по r -ой строке симплекс-таблицы составляется дополнительное ограничение вида (здесь мы полагаем, что свободные переменные имеют номера m +1,…, n ). С помощью вспомогательной переменной это ограничение представляется в виде равенства и вводится в симплекс-таблицу дополнительной строкой
где фигурные скобки означают дробную часть.
Таким образом, мы получаем следующую таблицу:
Так как , то после дополнения строкой симплекс-таблица перестает соответствовать допустимому базисному решению задачи линейного программирования, которую она описывает.
Для перехода к допустимому базисному решению производятся следующие операции:
а) строка с отрицательным свободным членом считается разрешающей;
б) если все коэффициенты , то задача не имеет решения, в противном случае номер l разрешающего столбца находится из условия:
в) совершается преобразование симплекс-таблицы с опорным элементом
Если в новой таблице по-прежнему есть хотя бы один отрицательный свободный член, то описанная процедура повторяется, начиная с операции а), необходимое число раз.
Применяя данные правила к нашей симплекс-таблице, мы получаем следующие преобразования:
Полученная симплекс-таблица не только соответствует допустимому базисному решению, но и дает решение рассматриваемой задачи:
Решить задачу дробно - линейного программирования.
Знаменатель целевой функции положителен при всех x из допустимого множества U, так как .
и получаем следующую задачу линейного программирования:
Неизвестные параметры мы можем уже из этих выражений найти:
Решить задачу квадратичного программирования.
Матрица нашей квадратичной функции положительно определена. Наша исходная задача имеет вид:
На основании теоремы Куна-Таккера точка минимума целевой функции из (1) на допустимом множестве (2) и (3) может быть найдена как решение следующей системы уравнений с дополнительными переменными ; :
удовлетворяющее условию неотрицательности:
Применяя выше описанные условия, мы преобразуем исходную задачу в следующий вид:
Будем искать угловую точку множества, определяемого этой системой, методом искусственного базиса. Введем дополнительные переменные и в 3-е и 4-ое уравнения выше написанной системы, считая базисными переменными начальной угловой точки , , и .
Вспомогательную целевую функцию выразим через свободные переменные , , , , и с помощью двух первых уравнений выше написанной системы.
Последовательность симплекс-таблиц, приводящих к решению задачи, приведена ниже. Рамками обведены опорные элементы, а те свободные переменные, которые на данном шаге нельзя переносить в базисные из-за условий , обведены кружками.
Как видим, в последней строчке нет отрицательных чисел, следовательно, мы нашли решение и оно имеет вид и .
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции. курсовая работа [1,1 M], добавлен 21.03.2012
Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели. курсовая работа [581,5 K], добавлен 13.10.2008
Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы. курсовая работа [1,7 M], добавлен 05.01.2015
Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания. контрольная работа [2,0 M], добавлен 02.05.2012
Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь. задача [390,4 K], добавлен 10.11.2010
Решение задачи линейного программирования симплекс-методом. Нахождение оптимального плана по критерию максимума прибыли. Транспорт - определение плана перевозок грузов на предприятие, которое обеспечивает минимальные совокупные транспортные издержки. контрольная работа [2,0 M], добавлен 11.05.2008
Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом. курсовая работа [263,5 K], добавлен 27.03.2011
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Линейное программирование контрольная работа. Программирование, компьютеры и кибернетика.
Контрольная работа: Товар как экономическое отношение. Стоимость, полезность, ценность и цена товара
Реферат: Особенности управления предприятиями, основанными на различных формах собственности
Лекция по теме Финансовый менеджмент
Контрольная работа: Ведение ссудных счетов, начисление процентов по кредитам
Реферат: «система оценивания и сравнительный анализ результатов обучения»
Курсовая работа по теме Технология социальной работы как мастерство специалиста социальной работы
Участие Третьих Лиц В Гражданском Процессе Курсовая
Итоговая Контрольная Работа 5 Класс Никольский
Реферат: Contributions Of The Philosophes Essay Research Paper
Культура Японии Реферат Скачать
Реферат На Тему Основные Положения, Правила И Оценка Соответствия Однородной Продукции
Промежуточная Контрольная Работа По Технологии
Добро Побеждает Зло Сочинение Для 3
Дипломная работа по теме Вмешательство государственной структуры в механизм регулирования экспортной политики страны
Дипломная Работа Анализ
Как Заполнить Дневник Педагогической Практики
Контрольная Работа По Теме Прекрасно Было Летом
Контрольная работа по теме Развитие инновационной деятельности
Сочинение Мое Любимое Растение 6 Класс
Сочинение Сравнение Пророк Пушкина И Лермонтова
Цыпленок табака (гарнир - отварной картофель) - Кулинария и продукты питания контрольная работа
Порядок назначения инвалидности, компенсационных выплат в РФ - Государство и право дипломная работа
Разработка стратегии организации - Менеджмент и трудовые отношения курсовая работа