Привести к каноническому виду уравнение третьего порядка

Переход к канонической форме ЗЛП

Назначение сервиса . Онлайн-калькулятор предназначен для перехода ЗЛП к КЗЛП. Приведение задачи к канонической форме означает, что все ограничения будут иметь вид равенств, путем ввода дополнительных переменных.
Если на какую-либо переменную x_j не наложено ограничение, то она заменяется на разность дополнительных переменных, x_j = x_j1 — x_j2, x_j1 ≥ 0, x_j2 ≥ 0.

• Шаг №1
• Шаг №2
• Видеоинструкция

Математическая модель ЗЛП называется основной, если ограничения в ней представлены в виде уравнений при условии неотрицательности переменных.

Математическая модель называется канонической, если ее система ограничений представлена в виде системы m линейно независимых уравнений (ранг системы r=m), в системе выделен единичный базис, определены свободные переменные и целевая функция выражена через свободные переменные. При этом правые части уравнений неотрицательны (b_i ≥ 0).

Переменные, входящие в одно из уравнений системы с коэффициентом один и отсутствующие в других уравнениях называются базисными неизвестными, а все другие – свободными.

Решение системы называется базисным, если в нем свободные переменные равны 0, и оно имеет вид:
X_баз = (0, 0; b₁, …, b_m), f(X_баз) = c₀

Базисное решение является угловой точкой множества решений системы, т.е. определяет вершину многоугольника решений модели. Среди таких решений находится и то, при котором целевая функция принимает оптимальное значение.

Базисное решение называется опорным, если оно допустимо, т.е. все правые части уравнений системы (или неравенств) положительны b_i ≥ 0.

Компактная форма канонической модели имеет вид:
AX = b
X ≥ 0
Z = CX(max)

Понятие допустимого решения, области допустимых решений, оптимального решения задачи линейного программирования.
Определение 1 . Вектор X, удовлетворяющий системе ограничений ЗЛП, в том числе и условиям неотрицательности, если они имеются, называется допустимым решением ЗЛП.
Определение 2 . Совокупность всех допустимых решений образует область допустимых решений (ОДР) ЗЛП.
Определение 3 . Допустимое решение, для которого целевая функция достигает максимума (или минимума), называется оптимальным решением.

В каждой задаче ЛП ищутся значения переменных при условии, чтобы:

• эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;
• при этих значениях целевая функция обращалась бы в минимум или максимум.

Одним из универсальных методов ЛП является симплексный метод, который, однако, можно применять, если задача ЛП имеет каноническую форму.

Определение. Задача ЛП имеет каноническую форму, если все ограничения системы состоят только из уравнений (кроме неравенств, выражающих неотрицательность переменных) и целевую функцию необходимо минимизировать.
Примером такой задачи ЛП в канонической форме является задача 1 – сбалансированная транспортная задача с системой ограничений (1) и целевой функцией (2).
Однако в большинстве экономических задач чаще всего в систему ограничений первоначально входят не только уравнения, а и неравенства.

Утверждение. Любая общая задача ЛП может быть приведена к канонической форме.
Приведение общей задачи ЛП к канонической форме достигается путем введения новых (их называют дополнительными) переменных.
Система ограничений (3) этой задачи состоит из четырех неравенств. Введя дополнительные переменные y₁≥ 0, y₂≥ 0, y₃≥ 0, y₄ ≥ 0, можно перейти к системе ограничений:

Эти дополнительные переменные y _i имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i-го вида).
Например, если бы машины первого вида работали все 18 ч, то x + y = 18, следовательно, y ₁ = 0. Но мы допускаем возможность неполного использования времени работы первой машины x + y y = 6, мы можем из системы ограничений (3.9) сделать вывод, что y₁ = y₂ = y₃ = 0, а y₄ = 12 – 6 = 6. Т. е. машины первого, второго, третьего вида используют свое рабочее время полностью. А вот четвертая машина загружена лишь наполовину, 6 часов, и при заданном оптимальном плане простаивает. Возможно, после таких выводов руководителю предприятия захочется загрузить ее другой работой, сдать в аренду на это время и т.д.
Итак, введением дополнительных переменных мы можем любое ограничение типа неравенства привести к уравнению.

Рассмотрим задачу о смеси. Система ограничений имеет вид:
Неравенства были обращены в сторону «больше», поэтому вводя дополнительные переменные y ₁, y ₂, y ₃≥ 0, их необходимо вычесть из левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:
Переменные y_i также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y ₁ будет означать количество излишнего вещества А в смеси, y ₂ –количество излишков вещества В в смеси, y₃ – излишки С в смеси.
Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F ввиду очевидности утверждения max F = –min (– F ). Посмотрите на рисунок: если в какой-то точке x= x₀ функция y= F(x) достигает своего максимума, то функция y= –F(x), симметричная ей относительно оси OX, в этой же точке x₀ достигнет минимума, причем F_max = – (–F_min) при x = x₀.

Вывод. Для представления задачи ЛП в канонической форме необходимо:

• неравенства, входящие в систему ограничений задачи, преобразовать в уравнения с помощью введения дополнительных переменных;
• если целевая функция F→max (максимизируется), она заменяется на функцию –F→ min (которая минимизируется).

Пример №1 . Следующую задачу ЛП привести к каноническому виду: F(X) = 5x₁ + 3x₂ → max при ограничениях:
2x₁ + 3x₂≤20
3x₁ + x₂≤15
4x₁≤16
3x₂≤12
Модель записана в стандартной форме. Введем балансовые неотрицательные переменные x₃, x₄, x₅, x₆, которые прибавим к левым частям ограничений-неравенств. В целевую функцию все дополнительные переменные введем с коэффициентами, равными нулю:
В первом неравенстве смысла (≤) вводим базисную переменную x₃. Во 2-ом неравенстве смысла (≤) вводим базисную переменную x₄. В третьем неравенстве вводим базисную переменную x₅. В 4-м неравенстве — базисную переменную x₆. Получим каноническую форму модели:
2x₁ + 3x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ = 20
3x₁ + 1x₂ + 0x₃ + 1x₄ + 0x₅ + 0x₆ = 15
4x₁ + 0x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ = 16
0x₁ + 3x₂ + 0x₃ + 0x₄ + 0x₅ + 1x₆ = 12
F(X) = 5x₁ + 3x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ → max

Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции
— F = -2x₁ + x₂ — 4x₃ +2x₄ → max

4. Соответствующая целевая функция примет вид:
— F = -2x₁ + x₂ — 4(x₈ – x₉) +2(x₁₀ – x₁₁) → max

Пример №2 . Преобразовать следующие задачи ЛП к канонической форме и решить их симплекс-методом.

Математический портал

Nav view search

Navigation

Search

• Вы здесь:
• Home
• Аналитическая геометрия
• Приведение квадратичной формы к каноническому виду.

Приведение квадратичной формы к каноническому виду.

Литература: Сборник задач по математике. Часть 1. Под ред А. В. Ефимова, Б. П. Демидовича.

Метод собственных векторов:

Рассмотрим квадратичную форму $A(x,x) =\sum\limits_^na_x_ix_j$ в евклидовом пространстве $R^n.$ Так как ее матрица $A=(a_ij)$ симметрична, то она может быть представлена в виде $A=UDU^,$ где $D -$ диагональная матрица, на диагонали которой стоят собственные числа матрицы, а $U -$ ортогональная матрица. Столбцы матрицы $U$ являются координатами некоторого ортонормированного базиса $B’=(e_1, . e_n),$ в котором матрица $A$ имеет диагональный вид $D,$ и, следовательно, квадратичная форма — искомый канонический вид. Соответствующие преобразования координат определяются соотношением $$\beginx_1\\\vdots\\x_n\end=U\beginx_1’\\\vdots\\x_n’\end.$$

Пример.

Найти ортогональное преобразование, приводящее следующие формы к каноническому виду, и написать этот канонический вид:

4.213. $11x_1^2+5x_2^2+2x_3^2+16x_1x_2+4x_1x_3-20x_2x_3.$

Решение.

Матрица квадратичной формы имеет вид $$\begin11&8&2\\8&5&-10\\2&-10&2\end.$$

Найдем собственные числа этой матрицы. Для этого запишем характеристическое уравнение:

$$det(A-\lambda E)=\begin11-\lambda&8&2\\8&5-\lambda&-10\\2&-10&2-\lambda\end=$$ $$=(11-\lambda)(5-\lambda)(2-\lambda)+2\cdot 8\cdot (-10)+2\cdot 8\cdot (-10)-$$ $$-2\cdot(5-\lambda)\cdot 2-(11-\lambda)\cdot(-10)\cdot(-10)-8\cdot 8\cdot(2-\lambda)=$$ $$=-\lambda^3+\lambda^2(2+5+11)-\lambda(10+22+55)+110-160-160-20+$$ $$+4\lambda-1100+100\lambda-128+64\lambda=$$ $$=-\lambda^3+18\lambda^2+81\lambda-1458=-\lambda(\lambda^2-81)+18(\lambda^2-81)=$$ $$=(\lambda-9)(\lambda+9)(-\lambda+18)=0.$$

Отсюда находим собственные числа:

$$\lambda_1=9,\quad \lambda_2=-9, \quad\lambda_3=18.$$

Далее находим собственные вектора:

Собственный вектор для собственного числа $\lambda_1=9$ найдем из системы $$(A-\lambda E)X=0, X\neq 0, \Rightarrow (A-9E)X=0, X\neq 0$$

Решим однородную систему уравнений:

Вычислим ранг матрицы коэффициентов $A=\begin2&8&2\\8&-4&-10\\2&-10&-7\end$ методом окаймляющих миноров:

Фиксируем минор отличный от нуля второго порядка $M_2=\begin2&8\\8&-4\end=-8-64=-72\neq 0.$

Таким образом ранг матрицы $A$ равен двум.

Выберем в качестве базисного минор $M=\begin2&8\\8&-4\end=-72\neq 0.$ Тогда, полагая $x_3=c,$ получаем: $$\left\<\begin2x_1+8x_2+2c=0\\ 8x_1-4x_2-10c=0\end\right.\Rightarrow\left\<\begin2x_1+8x_2=-2c\\8x_1-4x_2=10c\end\right.$$

По правилу Крамера находим $x_1$ и $x_2:$

Таким образом, общее решение системы $X(c)=\beginc\\-c/2\\c\end.$

Из общего решения находим фундаментальную систему решений: $E=X(1)=\begin1\\-1/2\\1\end.$

Собственный вектор для собственного числа $\lambda_2=-9$ найдем из системы $$(A-\lambda E)X=0, X\neq 0, \Rightarrow (A+9E)X=0, X\neq 0$$

Решим однородную систему уравнений:

Вычислим ранг матрицы коэффициентов $A=\begin20&8&2\\8&14&-10\\2&-10&11\end$ методом окаймляющих миноров:

Фиксируем минор отличный от нуля второго порядка $M_2=\begin20&8\\8&14\end=280-64=216\neq 0.$

Таким образом ранг матрицы $A$ равен двум.

Выберем в качестве базисного минор $M=\begin20&8\\8&14\end=216\neq 0.$ Тогда, полагая $x_3=c,$ получаем: $$\left\<\begin20x_1+8x_2+2c=0\\ 8x_1+14x_2-10c=0\end\right.\Rightarrow\left\<\begin20x_1+8x_2=-2c\\8x_1+14x_2=10c\end\right.$$

По правилу Крамера находим $x_1$ и $x_2:$

Таким образом, общее решение системы $X(c)=\begin-c/2\\c\\c\end.$

Из общего решения находим фундаментальную систему решений: $E=X(1)=\begin-1/2\\1\\1\end.$

Собственный вектор для собственного числа $\lambda=18$ найдем из системы $$(A-\lambda E)X=0, X\neq 0, \Rightarrow (A-18E)X=0, X\neq 0$$

Решим однородную систему уравнений:

Вычислим ранг матрицы коэффициентов $A=\begin-7&8&2\\8&-13&-10\\2&-10&-16\end$ методом окаймляющих миноров:

Фиксируем минор отличный от нуля второго порядка $M_2=\begin-7&8\\8&-13\end=91-64=27\neq 0.$

Таким образом ранг матрицы $A$ равен двум.

Выберем в качестве базисного минор $M=\begin-7&8\\8&-13\end=27\neq 0.$ Тогда, полагая $x_3=c,$ получаем: $$\left\<\begin-7x_1+8x_2+2c=0\\ 8x_1-13x_2-10c=0\end\right.\Rightarrow\left\<\begin-7x_1+8x_2=-2c\\8x_1-13x_2=10c\end\right.$$

По правилу Крамера находим $x_1$ и $x_2:$

Таким образом, общее решение системы $X(c)=\begin-2c\\-2c\\c\end.$

Из общего решения находим фундаментальную систему решений: $E=X(1)=\begin-2\\-2\\1\end.$

Таким образом, мы нашли вектора

В базисе $B’=(e_1′, e_2′, e_3′)$ заданная квадратичная форма имеет вид $$A(x, x)=9x_1^2-9x_2^2+18x_3^2,$$ а соответствующее преобразование координат:

Ответ: $A(x, x)=9x_1^2-9x_2^2+18x_3^2;$

76. Приведение квадратичных форм к каноническому виду

Рассмотрим некоторое линейное преобразование А с матрицей .

Это симметрическое преобразование можно записать в виде:

Y1 = a11x1 + a12x2

Y2 = a12x1 + a22x2

Где у1 и у2 – координаты вектора в базисе .

Очевидно, что квадратичная форма может быть записана в виде

Ф(х1, х2) = х1у1 + х2у2.

Как видно, геометрический смысл числового значения квадратичной формы Ф в точке с координатами х1 и х2 – скалярное произведение .

Если взять другой ортонормированный базис на плоскости, то в нем квадратичная форма Ф будет выглядеть иначе, хотя ее числовое значение в каждой геометрической точке и не изменится. Если найти такой базис, в котором квадратичная форма не будет содержать координат в первой степени, а только координаты в квадрате, то квадратичную форму можно будет привести к каноническому виду.

Если в качестве базиса взять совокупность собственных векторов линейного преобразования, то в этом базисе матрица линейного преобразования имеет вид:

.

При переходе к новому базису от переменных х1 и х2 мы переходим к переменным и . Тогда:

Тогда .

Выражение называется Каноническим видом квадратичной формы. Аналогично можно привести к каноническому виду квадратичную форму с большим числом переменных.

Теория квадратичных форм используется для приведения к каноническому виду уравнений кривых и поверхностей второго порядка.

Пример. Привести к каноническому виду квадратичную форму

Ф(х1, х2) = 27.

Коэффициенты: а11 = 27, а12 = 5, а22 = 3.

Составим характеристическое уравнение: ;

(27 — l)(3 — l) – 25 = 0

Пример. Привести к каноническому виду уравнение второго порядка:

17×2 + 12xy + 8y2 – 20 = 0.

Коэффициенты а11 = 17, а12 = 6, а22 = 8. А =

Составим характеристическое уравнение:

(17 — l)(8 — l) — 36 = 0

136 — 8l — 17l + l2 – 36 = 0

L2 — 25l + 100 = 0

Итого: — каноническое уравнение эллипса.

Пример. Используя теорию квадратичных форм, привести к каноническому виду уравнение линии второго порядка. Схематично изобразить график.

Решение: Составим характеристическое уравнение квадратичной формы : при

Решив это уравнение, получим l1 = 2, l2 = 6.

Найдем координаты собственных векторов:

Полагая m1 = 1, получим n1 =

Полагая m2 = 1, получим n2 =

Собственные векторы:

Находим координаты единичных векторов нового базиса.

Имеем следующее уравнение линии в новой системе координат:

Каноническое уравнение линии в новой системе координат будет иметь вид:

Пример. Используя теорию квадратичных форм, привести к каноническому виду уравнение линии второго порядка. Схематично изобразить график.

Решение: Составим характеристическое уравнение квадратичной формы : при

Решив это уравнение, получим l1 = 1, l2 = 11.

Найдем координаты собственных векторов:

Полагая m1 = 1, получим n1 =

Полагая m2 = 1, получим n2 =

Собственные векторы:

Находим координаты единичных векторов нового базиса.

Имеем следующее уравнение линии в новой системе координат:

Каноническое уравнение линии в новой системе координат будет иметь вид:

Пример. Используя теорию квадратичных форм, привести к каноническому виду уравнение линии второго порядка. Схематично изобразить график.

4ху + 3у2 + 16 = 0

Коэффициенты: a11 = 0; a12 = 2; a22 = 3.

Характеристическое уравнение:

Корни: l1 = -1, l2 = 4.

Для l1 = -1 Для l2 = 4

M1 = 1; n1 = -0,5; m2 = 1; n2 = 2;

= (1; -0,5) = (1; 2)

Получаем: — каноническое уравнение гиперболы.

При использовании компьютерной версии “Курса высшей математики” возможно запустить программу, которая решает рассморенные выше примеры для любых начальных условий.

Для запуска программы дважды щелкните на значке:

В открывшемся окне программы введите коэффициенты квадратичной формы и нажмите Enter.

Примечание: Для запуска программы необходимо чтобы на компьютере была установлена программа Maple (Ó Waterloo Maple Inc.) любой версии, начиная с MapleV Release 4.