Алгоритмы численного решения задач

Графоаналитический метод решения задач. Получение задачи линейного программирования в основном виде. Вычисление градиента и поиск экстремумов методом множителей Лагранжа. Параболоид вращения функции. Поиск решения на основе условий Куна-Таккера.

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 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

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.