Алгоритмы численного решения задач
Графоаналитический метод решения задач. Получение задачи линейного программирования в основном виде. Вычисление градиента и поиск экстремумов методом множителей Лагранжа. Параболоид вращения функции. Поиск решения на основе условий Куна-Таккера.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 13.09.2010 |
| Размер файла | 139,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
9
Решить графоаналитическим методом.
Задача 1
max (X) = - 2x1 + x2 + 5x3
при 4x1 + 2x2 + 5x3 12
6x1 - 3x2 + 4x3 = 18
3x1 + 3x2 - 2x3 16
Х ? 0
Здесь число n = 3 и число m = 3.
Выразим из ограничений и х3:
? 0
Подставим его в целевую функцию
max (X) =
Получим новые ограничения:
х ? 0
Получили задачу линейного программирования в основном виде для n = 2
Вычисляем градиент :
= =
Рисунок 1
Прямые a, c, d и e пересекаются и образуют четырехугольник ACDE. Определим max ц (Х), который удовлетворяет условию Х>=0:
Это точка D (0,7; 4,7; 0).
Функция ц (Х*) в точке D:
ц (Х*) = 38,3
Найти экстремумы методом множителей Лагранжа
Задача 2
extr ц (X) = 4x1 - x22 - 12
при x12 + x22 = 25
Составим функцию Лагранжа:
L (X,л) = 4x1 - x22 - 12 + л (x12 + x22 - 25)
h (X) = x12 + x22 - 25 = 0 - функция ограничения.
Составим систему уравнений из частных производных и приравняем их нулю.
Решим данную систему уравнений:
2x2 (л - 1) = 0
Предположим, что x2 ? 0, тогда л = 1 подставим в первое уравнение системы.
4 - 2x1 = 0
2x1 = - 4
x1 = 2
Подставим x1 в третье уравнение системы.
4 +x22 - 25 = 0
x22 - 21 = 0
x22 = 21
x2 = ±4,5826
Параболоид вращения функции h (x).
В двухмерной проекции график выглядит так:
Рисунок 2.
На рис.2 видно, что в точках А1 и А2 функция ц (X) = h (X). В этих точках функция ц (X) равна минимальному значению.
|
(X*,л*) N |
X1* |
X2* |
л* |
ц (X*) |
Примечание |
|
|
1 |
2 |
4,5826 |
1 |
-24,25 |
Min |
|
|
2 |
2 |
-4,5826 |
1 |
-24,25 |
Min |
Решить обобщенным методом множителей Лагранжа или на основе условий Куна-Таккера.
Задача 3
extr ц (X) = 9 (x1 - 5) 2 + 4 (x2 - 6) 2 =
при 3x1 + 2x2 >= 12
x1 - x2 <= 6
Решим задачу на основе условий Куна-Таккера.
Составим функцию Лагранжа.
L (X,л) = + л1 (3x1 + 2x2 - 12) + л2 (x1 - x2 - 6) =
Составим систему уравнений из частных производных и приравняем их нулю.
Решим систему уравнений.
1) Предположим, что л2 ? 0, тогда из уравнения (d) получим
x2 = х1 - 6
Пусть л1 = 0 и x1 ? 0, тогда из уравнения (а) получим
18x1 - 90 - л2 = 0, л2 = 18х1 - 90
Пусть x2 ? 0, тогда из уравнения (b) получим
8x2 - 48 - л2 = 0
Подставив в уравнение выражения для x2 и л2, получим
x1 = 4
x2 = - 2
x1* = 4; x2* = - 2; ц (Х) * = 265
Трехмерный график целевой функции для данной задачи
Двухмерная проекция
Рисунок 3
На рис.3 видно, что в точке А функция b (X) = a (X), которые находятся в параболоиде вращения целевой функции.
В этой точке функция ц (X) равна максимальному значению.
2) Предположим, что л2 = 0 и x2 ? 0, тогда из уравнения (b) получим
8x2 - 48 + 2л1 = 0
x2 =
x2 = 6 -
Предположим, что x1 ? 0, тогда из уравнения (а) выразим x1.
18х1 - 90 + 3л1 = 0
18 = 90 - 3л1
х1 =
х1 = 5 -
Подставим выражения для x1 и x2 в уравнение (с) системы.
а) = 0, x1 = 5; x2 = 6
б) = 15
x1 = 2,5; x2 = 2,25
Подставив корни x1 = 5; x2 = 6 в целевую функцию получим ц (Х) = 0, а корни x1 = 2,5; x2 = 2,25 - получим ц (Х) = 112,49
Таким образом:
x1* = 5; x2* = 6; ц* (Х) = 0
На рис.4 видно, что в точке В функция ц (X) = a (X). В этой точке функция ц (X) равна минимальному значению.
Рисунок 4
|
X* N |
X1* |
X2* |
ц (X*) |
Примечание |
|
|
1 |
5 |
6 |
0 |
Min |
|
|
2 |
4 |
-2 |
265 |
Max |
Получить выражение вектор-функции и матрицы Якоби системы и составить алгоритм численного решения задачи на основе условий Куна-Таккера.
Задача 4
max ц (X) = - x12 - x22 +2х2
при x1 + x2 >= 18
x1 + 2 x2 >= 14
Х>=0
Найдем выражение вектор-функции системы.
Составим функцию Лагранжа.
L (X,л) = - x12 - x22 + 2х2 + л1 (x1 + x2 - 18) + л2 (x1 + 2x2 - 14)
Вектор-функция системы:
Составим матрицу Якоби.
Составим алгоритм численного решения задачи:
Рисунок 5.
Подобные документы
Построение пространства допустимых решений. Нахождение оптимального решения с помощью определения направления убывания целевой функции. Нахождение оптимальной точки. Поиск экстремумов методом множителей Лагранжа. Условия экстремума Куна-Таккера.
контрольная работа [396,2 K], добавлен 13.09.2010Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Формулировка общей задачи математического программирования. Классификация задач нелинейного программирования. Понятие о функции Лагранжа. Задача теоремы Куна-Таккера. Экономическая интерпретация множителей Лагранжа, формулирование условий оптимальности.
презентация [669,1 K], добавлен 25.07.2014Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ.
презентация [441,5 K], добавлен 19.10.2014Число линейно независимых уравнений. Отрицательная базисная переменная. Симплекс-метод решения задач линейного программирования. Экстремальное значение целевой функции. Метод северо-западного угла. Задачи нелинейного программирования. Функция Лагранжа.
контрольная работа [257,5 K], добавлен 29.09.2008Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.
дипломная работа [2,4 M], добавлен 13.08.2011Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
курсовая работа [232,4 K], добавлен 01.06.2009Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009
