Понятие канонической и стандартной задач линейного программирования.

Date: 2015-10-07; view: 410.

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

Кривой второго порядка на плоскости А² называется множество точек М(х;у), координаты которых удовлетворяют уравнению вида а11х²+2а12ху+а22у² +2а10х+2а01у+а00=0, где а11, а12, а22, а10, а01, а00 – некоторые действительные числа неравные нулю одновременно.

Каноническое уравнение эллипса: x²/a²+y²/b²=1, a³b (b²=a²-c², a>0)

Каноническое уравнение параболы: y²=2px

Каноническое уравнение гиперболы: x²/a²-y²/b²=1, b= (c²-a²)

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

Общая форма задачи имеет вид: найти при условиях

где

Здесь и далее нам удобнее считать с и а_і вектор - строками, а x и b=(b₁,...,b_m)^T - вектор столбцами.

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

т.е. все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае I₂ = 0, а в другом - I₁ = 0.

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

	(2.1)
	(2.2)

(2.3)

Задача ЛП в стандартной форме:

В обоих случаях А есть матрица размерности m x n, i-я строка которой совпадает с вектором а_i.

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

Квадратичная форма имеетнормальный вид, если все коэффициенты при квадратах по модулю равны 1. Наиболее простой способ приведения квадратичных форм к нормальному виду – метод Лагранжа.

30. Первая теорема двойственности.

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