Общий вид задач линейного программирования, основная задача линейного программирования.

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

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

Формы записи задачи линейного программирования:

Общей задачей линейного программирования называют задачу:

max(min)Z = (1)

при ограничениях:

(i=1,2….m) (2)

(i= m1+1,..., m1) (3)

(i= m2+1,..., m2) (4)

xj≤0

(j=1,2…..n1) (5)

xj-произвольные (j= n1+1,…..n) (6)

где сj,аij,

bi;- заданные действительные числа;

(1) - целевая функция;

(2) - (6) -ограничения;

х = (х,;...;хn) –план задачи.

Свойства решений.

Пусть ЗЛП представлена в следующей записи:

mах Z = сх (7)

А1х1,+А2х2+... + Аnхn=А0 (8)

х1 ≥ 0, х2 ≥ 0,…….хn ≥ 0 (9)

Чтобы задача (7) - (8) имела решение, системе её ограничений (8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r= n система имеет единственное решение, которое будет при хj ≥ 0 (j=1,...,n) оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n, вэтом случае система векторов А1,А2,...,Аn содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, может быть несколько, но не более с. Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n — r переменных будут свободными, их обозначают СП. Будем считать, что базис составляют первые m векторов А1,А2,...,Аm. Этому базису соответствуют базисные переменные х1,х2,...,хm, а свободными будут переменные хm+1,хm+2,….хn.

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

9. Метод половинного деления решения уравнений.
Пусть уравнение F(x)=0 на отрезке [a;b] имеет единственный корень и при этом ф-я f(x) на этом отрезке непрерывна. Раздели отрезок (a;b) пополам точкой с. с=a+b/2. Возможны 2 случая: Ф-я f(x) меняет знак на отрезке [a;с], либо на [c;d], выбирая в каждом случае тот из отрезков, на котором ф-я меняет знак и продолжает процесс половинного деления. Можно дойти до сколь угодно малого отрезка, содерж. Корень уравнения. Метод половинного деления это метод решения уравнения с заданной точностью (длина отрезка соответствует точности)

 

12. Алгоритм вычисления определителя по методу Гаусса.
Для реализации данного метода нужно провести следующие действия:
1. Умножить первую строку исходного определителя на число обратное первому элементу. В результате значение определителя также умножается на данное число. Первый элемент первой строки станет равным единице.
2. Умножить первую строку на число, равное первому элементу второй строки. Первый элемент первой строки станет равным первому элементу второй строки.
3. Вычесть из второй строки первую строку. На первом месте второй строки окажется 0. Вычитание строк не изменяет значение определителя.
4. Вычесть из третьей и всех последующих строк первую строку. Тогда на первом месте первого столбца будет 1 а на остальных местах ноль.
5. Заменить первую строку полученного определителя первой строкой исходного определителя. В результате полученный определитель с нулями в первом столбце начиная со второго элемента станет равным исходному определителю. Этот определитель будет иметь элементы всех строк отличные от элементов исходного определителя, за исключением первой строки.
6. Вычеркнуть первую строку и первый столбец из полученного определителя на этапе 5.
7. К полученному определителю на единицу меньшего порядка применить действия по пунктам 1-5 Метода Гаусса.
8. Повторить пункт 7 ко всем минорам более низкого порядка.
9. В результате выполнения пунктов 1-8 мы получим определитель равный данному, но имеющий диагональную матрицу. Определитель диагональной матрицы равен произведения диагональных элементов.

15. Задача аппроксимации функций.
В вычислительной математике нередки случаи, когда одну функцию приходится заменить другой более простой. Такую задачу называют аппроксимацией функции. Поводом для аппроксимации функции может послужить, в частности, табличный способ её задания. Под аппроксимацией в математике понимается операция нахождения неизвестных численных значений какой-либо величины по известным её значениям и, может быть, численным значениям других величин, связанных с рассматриваемой. Способ построения приближающей функции, при котором в узлах х0х1х2…хn значения приближаемой и приближающей переменной совпадают называется интерполяционной. Приближение, при котором точка, в которой ищется значение приближающей функции находится за пределами отрезка интерполяции называется экстраполяцией. Уравнение функции можно найти с помощью интерполяционного многочлена Лагранжа.