Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования. Характеристика графических методов решения задачи линейного программирования, сущность их геометрической интерпретации и основные этапы.
Аннотация к работе
Линейное программирование - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Для решения задач линейного программирования потребовалось создание специальных методов.Линейное программирование - математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их. Термин «программирование» нужно понимать в смысле «планирования».Даны линейная функция Z=С1х1 С2х2 ... CNXN (1.1) и система линейных ограничений a11x1 a22x2 ... Найти такие неотрицательные значения х1, х2, ..., xn, которые удовлетворяют системе ограничений (1.2) и доставляют линейной функции (1.1) минимальное значение. Минимизировать линейную функцию Z = СХ при ограничениях А1х1 А2x2 ... Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А0Х0, где С = (с1, с2, ..., CN) - матрица-строка; А = (aij) - матрица системы; Х =(xij)-матрица-столбец, А0 = (аі) матрица-столбец Минимизировать линейную функцию Z = Cjxj при ограниченияхПод ним подразумевается множество некоторых элементов (именуемых векторами или точками), для которых заданы операции сложения и умножения на вещественное число (скаляр), причем элементы, являющиеся результатом выполнения операций, также в соответствии с определением должны принадлежать исходному пространству. Вектор ?1a1 ?2a2 … ?mam называется линейной комбинацией векторов а1 а2,..., ам с коэффициентами ?1, ?2, ?m, Система векторов линейного пространства а1 а2,..., ам называется линейно зависимой, если существуют такие числа ?1, ?2, ?m не равные одновременно нулю, что их линейная комбинация ?1a1 ?2a2 … ?mam равняется нулевому вектору (вектору, все компоненты которого равны нулю). В противном случае систему а1, а2,..., ам называют линейно независимой, т. е. линейная комбинация данных векторов может быть равна нулевому вектору только при нулевых коэффициентах ?1, ?2, …, ?m Максимально возможное количество векторов, которые могут образовывать линейно независимую систему в данном линейном пространстве, называют размерностью пространства, а любую систему линейно независимых векторов в количестве, равном размерности, - базисом пространства. Множество Н, получаемое сдвигом некоторого линейного подпространства L € Rn на вектор a € Rn: H=L a, называется аффинным множеством (пространством).Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования , которую можно дать для случаев n = 2 и n = 3. Пусть нам задана задача линейного программирования в стандартной форме Возьмем на плоскости декартову систему координат и каждой паре чисел (x1,x2)поставим в соответствие точку на этой плоскости. Рассмотрим теперь, какие области соответствуют неравенствам вида a1 x1 a2 x2 ? b. Сначала рассмотрим область, соответствующую равенству a1 x1 a2 x2 = b.Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой аі1х1 аі2х2 ? bi i = 1, m. Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми x1 = 0; х2 = 0.. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых составляют решение данной системы. Если в системе ограничений (**) - (***) n = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого аі1х1 аі2х2 аі3х1 ? bi, а условия неотрицательности - полупространства с граничными плоскостями соответственно xi = 0 (i = 1, 2, 3).Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Пусть задача линейного программирования задана в двумерном пространстве, т. е. ограничения содержат две переменные. Неосновной случай ? получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. Рассмотрим теорию на конкретном примере: Найти допустимую область задачи линейного программирования, определяемую ограничениями Беря x1 = x2 = 0, получим, что-0 0<1 и поэтому интересующая нас полуплоскость лежит ниже прямой, изображенной на рис.Составить такой план выпуска продукции, при котором прибыль предприятия от реализации продукции будет максимальной при условии, что изделие В надо выпустить не менее, чем
План
ОГЛАВЛЕНИЕ
Введение 3
I. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ 4
1.1 Линейное программирование. 4
1.2 Формулировка задачи. 5
1.3 Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования. 7
1.4 Математические основы решения задачи линейного программирования графическим способом. 9
1.4.1 Математический аппарат. 9
1.4.2 Геометрическая интерпретация задачи линейного программирования. 11
1.4.3 Этапы решения графического метода задач линейного программирования 13