Операции над векторами и матрицами

Автономная некоммерческая организация высшего образования «Российский новый университет» Налоговый институт Кафедра налогового администрирования Курс лекций по дисциплине математика по направлению подготовки 38.03.01 Экономика профиль налоги и налогообложение Москва 2015 г. Тема №1 Операции над векторами и матрицами Вопросы: 1. Понятие матрицы. 2. Операции над матрицами. 3. Определители и их свойства. 4. Обратная матрица. 5.Система линейных уравнений. Вопрос 1. Понятие матрицы. Любая статистическая таблица это пример матрицы. Таковой является, например следующая таблица: Производство деталей за смену Детали, шт. Бригады I II А 25 35 Б 30 50 В 60 100 Совокупность m·n чисел, расположенных в виде прямоугольной таблицы из m строк и n столбцов, называется прямоугольной матрицей размерности m  n.  Обозначения: Матрицы обозначаются прописными латинскими буквами A, B, C; элементы матрицы обозначаются строчными латинскими буквами, например, aij, i = 1,2,…m; j = 1,2,…n, где i показывает номер строки, j - номер столбца матрицы. Другими словами элемент матрицы aij - это элемент, находящийся на пересечении i–ой строки и j–ого столбца матрицы. Общий вид прямоугольной матрицы записывается как . Матрица называется квадратной матрицей порядка n, если число строк m равно числу столбцов n. При m = 1 матрица содержит одну строку и называется вектором-строкой. При n = 1 матрица содержит один столбец и называется вектором-столбцом. Элементы вектора называются также компонентами или координатами вектора. Если все элементы прямоугольной матрицы нули (aij = 0), то матрица называется нулевой матрицей и обозначается буквой 0. Если в квадратной матрице элементы главной диагонали равны единице (aii = 1), а все остальные элементы – нули (aij = 0, ij), то матрица называется единичной матрицей и обозначается как E. Матрицы A и B равны, если равны все соответствующие элементы этих матриц aij = bij. Вопрос 2. Операции над матрицами. 1. Сумма двух матриц. При сложении двух матриц A и B получается матрица C = A + B, элементы которой определяются как сумму соответствующих элементов этих матриц: cij = aij + bij. Из этого правила следует, что можно сложить только матрицы одинаковой размерности или одинакового порядка. 2. Умножение матрицы на действительное число. При умножении матрицы A на действительное число k получается матрица B = kA, элементы которой определяются умножением всех элементов матрицы B на это число: bij = kaij. 3. Умножение двух матриц. При умножении матриц A и B получается матрица C = AB, элементы которой определяются по правилу ; элемент i-й строки и j-го столбца матрицы C равен сумме произведений i-й строки матрицы A на соответствующие элементы j-го столбца матрицы B. Матрицу А можно умножить на матрицу В только в том случае, когда число столбцов матрицы А равно числу строк матрицы В. Если матрицы A и B квадратные матрицы n–го порядка, то имеет смысл как произведение матриц AB, так и произведение матриц BA, причем полученные матрицы тоже n–го порядка. При этом в общем случае AB  BA, т.е. произведение матриц не коммутативно.  Задача 1. Найти сумму матриц и . Решение: При сложении двух матриц суммируются все соответствующие элементы этих матриц: .  Задача 2. Найти произведение числа 4 и матрицы . Решение: При умножении матрицы на число все элементы матрицы умножаются на это число: .  Задача 3. Найти произведение матриц и . Решение: Элементы матрицы AB определяются сложением произведений элементов первой строки матрицы А с соответствующими элементами первого столбца матрицы В, произведений элементов первой строки матрицы А с соответствующими элементами второго столбца матрицы В и т.д.: .  Задача 4. Найти произведение матриц и . Решение: Элементы полученной матрицы представляют собой суммы произведений элементов строк матрицы А с элементами единственного столбца матрицы В: . Свойства матриц Если A, B и C матрицы, а k и m действительные числа, то выполняются следующие свойства. 1. Сумма матриц обладает свойством коммутативности: A + B = B + A. 2. Сумма трех матриц обладает свойством ассоциативности: (A + B) + C = A + (B + C). 3. Сумма матрицы A и нулевой матрицы 0 равна матрице A: A + 0 = A. 4. Сумма матрицы A и противоположной матрицы – A равна нулевой матрице 0: A – A = 0. 5. Произведение матрицы A и единичной матрицы E равно матрице A: EA = AE = A. При этом выполняется свойство коммутативности. 6. Сумма матриц обладает свойством дистрибутивности относительно действительного множителя (числа): k(A + B) = kA + kB 7. Произведение матрицы с двумя действительными множителями обладает свойством ассоциативности: k(mA) = (km)A. 8. Произведение матриц обладает свойством ассоциативности относительно действительного множителя: k(AB) = (kA)B. 9. Произведение трех матриц обладает свойством дистрибутивности: (AB)C = A(BC), A(B + C) = AB + AC, (A + B)C = AC + BC.  Вопрос 3. Определители и их свойства. Определители Определителем (детерминантом) квадратной матрицы n-го порядка называется число .  Обозначения: detA,  и |A|. Строки и столбцы определителя называются рядами. Определитель второго порядка вычисляется по правилу (1): . (1) Определитель третьего порядка вычисляется по правилу (2): (2). Правило вычисления определителя третьего порядка следующее. Это алгебраическая сумма шести тройных произведений элементов, стоящих в разных строках и разных столбцах. Со знаком плюс берутся произведения, сомножители которых находятся на главной диагонали и в вершинах треугольников с основаниями, параллельными главной диагонали. Со знаком минус берутся произведения, сомножители которых стоят на другой диагонали и в вершинах треугольников с основаниями, параллельными этой диагонали (рис. 1). (+) (-) Рис. 1. Правило вычисления определителя третьего порядка  Задача 1. Найти . Решение: Определитель второго порядка вычисляется по правилу (1): detA = 2·3 – (–3)·4=18.  Задача 2. Найти . Решение: Определитель третьего порядка вычисляется по правилу (2): detA = 1·3·2 + 2·1·0 + 3·2·1 – 3·3·0 – 2·2·2 – 1·1·1 = 3. Минор и алгебраическое дополнение Минором mij некоторого элемента aij определителя n–го порядка называется определитель (n – 1)-го порядка, полученный из исходного определителя путем вычеркивания i-й строки и j-го столбца, на пересечениях которых находится выбранный элемент. Например, минором элемента a11 определителя третьего порядка является . Алгебраическим дополнением называется Aij = (– 1)i+j mij. Если сумма индексов алгебраического дополнения i + j четное число, то алгебраические дополнения и миноры совпадают: Aij = mij, а если – нечетное число, то они отличаются знаком: Aij = – mij. Свойства определителей 1. Если какой-то ряд состоит из одних нулей, то определитель равен 0. 2. Определитель не изменится, если его строки заменить столбцами, и наоборот. 3. При перестановке двух параллельных рядов определитель меняет знак. 4. Определитель, имеющий два одинаковых ряда, равен нулю. 5. Общий множитель элементов какого-либо ряда определителя можно вынести за знак определителя. 6. Если элементы какого-либо ряда определителя представляют собой сумму двух слагаемых, то определитель может быть разложен на сумму двух определителей, с соответствующими слагаемыми этой суммы. 7. Определитель не изменится, если к элементам одного ряда прибавить соответствующие элементы параллельного ряда, умноженные на любое число. 8. Определитель равен сумме произведений элементам некоторого ряда на соответствующие им алгебраические дополнения. Например, определитель третьего порядка равен: detA = a11A11 + a12A12 + a13A13 = a11m11 – a12m12 + a13m13 . (3)  Задача 3. Найти . Решение: Определитель найдем, применяя формулу (3): Ранг матрицы Наибольший порядок отличных от нуля детерминантов (миноров) прямоугольной матрицы m  n, называется рангом матрицы r, причем r  min(m, n). Для квадратной матрицы ранг r  n. Минор, порядок которого определяет ранг матрицы, называется базисным. У матрицы может быть несколько базисных миноров.  Задача 4. Найти ранг матрицы размерности 3  4. Решение: Ранг матрицы r  min(3, 4) = 3. Все детерминанты третьего порядка равны нулю, так как две их строки (вторая и третья) одинаковые (отличаются на постоянный множитель). Отличны от нуля только детерминанты второго порядка, поэтому r = 2. Вопрос 4.Обратная матрица. Квадратная матрица называется невырожденной, если ее определитель отличен от нуля: detA  0. В противном случае матрица называется вырожденной. Матрица A-1 называется обратной матрице А, если выполняется условие A-1A = AA-1 = E. Только у невырожденных квадратных матриц есть обратные матрицы. Обратная матрица вычисляется по формуле (detA  0): . Для матрицы A второго порядка обратная матрица равна: .  Задача 1. Найти A-1, если . Решение: 1. Находим определитель матрицы: . 2. Находим обратную матрицу: .  Задача 2. Найти A-1, если . Решение: 1. Находим определитель матрицы: . 2. Вычисляем алгебраические дополнения: , , , , , , , , . 3. Находим обратную матрицу: . Свойства обратной матрицы 1. Определитель обратной матрицы A-1 равен обратной величине определителя матицы A: det(A-1) = 1/detA 2. Обратная матрица произведения двух матриц равна произведению их обратных матриц: (AB)-1 = B-1A-1 3. При перестановке операций транспонирования и нахождения обратной матрицы результат не изменяется: (A-1)T = (AT)-1. Буква T означает операция транспонирования – операция замены строк столбцами и наоборот. В частности, при транспонировании вектор-столбец превращается в вектор-строку. Вопрос 5.Системы линейных алгебраических уравнений. Вопрос 1. Система линейных алгебраических уравнений, содержащей n уравнений и n неизвестных. Системой линейных алгебраических уравнений, содержащей n уравнений и n неизвестных, называется система вида (1), где aij, i = 1,2,…n; j = 1,2,…n - коэффициенты системы, bi, i = 1,2,…n - свободные члены, xi, i = 1,2,…n - неизвестные, подлежащие нахождению. Более удобной формой записи системы линейных уравнений (1) является матричная форма A·X = B, (2) где А - квадратная матрица n-го порядка, X – вектор столбец из неизвестных xi, i = 1,2,…n, B – вектор-столбец из свободных членов bi, i = 1,2,…n. Система уравнений (1) имеет единственное решение, если матрица А невырожденная, т.е. если определитель матрицы А отличен от нуля:   0. Решение матричного уравнения (2) находится следующим образом: A-1AX = A-1B, EX = A-1B, X = A-1B. (3) Решение X = A-1B справедливо не только для векторов столбцов X и B, но и для произвольных матриц X и B, удовлетворяющих уравнению (2). Формула Крамера Решения системы линейных уравнений (1) определяются формулой Крамера , i=1,2···n, (4) где i получается из определителя  путем замены i-го столбца свободными членами bi. Формула Крамера получается из решения системы X = A-1B. На самом деле, это решение в виде системы записывается как: .  Задача 1. Найти решение системы . Решение: Решение системы уравнений находится с помощью формулы Крамера. 1. Находим определители , , , ;  = 423 + (–1)5(–1) + 231 – 22(–1) – (–1)33 – 451 = 28; 1 = 023 + (–1)5(–2) + 221 – 22(–2) – (–1)23 – 051 = 28; 2 = 423 + 05(–1) + 23(–2) – 22(–1) – 033 – 45(–2) = 56; 3 = 42(–2) + (–1)2(–1) + 031 – 02(–1) – (–1)3(–2) – 421 = – 28. 2. Решение системы равно: , , . Метод последовательных исключений неизвестных (метод Гаусса) С помощью коэффициентов и свободных членов составляется расширенная матрица , над строками которой можно произвести следующие элементарные преобразования. Разрешается изменить порядок строк; прибавлять к элементам произвольной строки элементы другой строки, умноженное на любое отличное от нуля число. При этом нужно стараться свести расширенную матрицу к «треугольному» виду, т.е. к виду, когда все элементы ниже (или выше) главной диагонали равны нулю. Из полученной расширенной матрицы решение находится непосредственно: . т.е. и т.д.  Задача 2. Решить систему уравнений: . Решение: Составляем расширенную матрицу и сводим ее к «треугольному» виду: . После этого нетрудно найти решения: – 14x3 = – 14: x3 = 1; – 3x2 – 2x3 = – 2; x2 = 0; x1 + 2x2 + 3x3 = 2; x1 = –1. Тема №2 Линейные преобразования и квадратичные формы. Вопросы: 1. Система линейных алгебраических уравнений, содержащей m уравнений и n неизвестных. 2. Система линейных однородных уравнений. Вопрос 1. Система линейных алгебраических уравнений, содержащей m уравнений и n неизвестных. Системой линейных алгебраических уравнений, содержащей m уравнений и n неизвестных, называется система вида . Система уравнений называется совместной, если она имеет, хотя бы одно решение, и несовместной, если не имеет ни одного решения. Ответ на совместность системы дает теорема Кронекера-Капелли. Теорема Кронекера-Капелли. Система линейных алгебраических уравнений совместна тогда и только тогда, когда ранг расширенной матрицы равен рангу основной матрицы. Теорема. Если ранг совместной системы равен числу неизвестных, то система имеет единственное решение. Теорема. Если ранг совместной системы меньше числа неизвестных, то система имеет бесконечное множество решение. Решение системы находится следующим образом. Находим ранг матрицы, выбираем какой-либо базисный минор порядка r и r уравнений, с коэффициентами базисного минора (остальные уравнения отбрасываем). Решаем систему выбранных уравнений. Если r = n, то получим единственное решение, а если r < n, то получим бесконечное множество решений.  Задача 3. Найти решение системы . Решение: Ранги основной матрицы и расширенной матрицы равны 2. Поэтому отбрасываем одно уравнение (можно третье уравнение) и решаем полученную систему уравнений: . Обозначив x3 = с, получим решение (2 – с, 1, с). Вопрос 2. Система линейных однородных уравнений. Система линейных уравнений (1) с нулевыми свободными членами b1 = b2 =  = bn = 0 называется системой линейных однородных уравнений. Система линейных однородных уравнений имеет нулевое (тривиальное) решение при   0 и ненулевое бесконечное множество решений при  = 0.  Задача 3. Найти решение системы . Решение: Находим определитель . Так как детерминант равен нулю, то ранг матрицы не равен 3. Легко проверить, что ранг матрицы равен 2. После этого убираем одно из уравнений, например, третье уравнение и решаем полученную систему , т.е. находим x1 и x2 через x3 = с. После подстановки x3 = с получим систему уравнений . Решая эту систему, находим x1 = 2x3 = 2с; x2 = – x3 = – с. Итак, решение системы линейных однородных уравнений имеет вид (2c, – c, c). Тема №3. Векторы и линейные операции над ними. Квадратичные формы. Многочлены и комплексные числа. Вопросы: 1. Понятие вектора. 2. Операции над векторами. 3. Проекция вектора. 4. Комплексные числа. Вопрос 1. Понятие вектора. Отрезок на прямой определяется двумя равноправными точками – его концами. Различают также направленный отрезок, т.е. отрезок, относительно концов которого известно какой из них первый (начало), а какой – второй (конец). Определение: Направленный отрезок (или упорядоченная пара точек) называется вектором. Вектор обычно обозначается символом , где А – начало, а В – конец направленного отрезка, либо одной буквой (в некоторых учебниках буква выделяется полужирным шрифтом; при этом стрелка опускается a). На чертеже вектор изображается стрелкой. Начало вектора называют точкой его приложения. Расстояние между началом и концом вектора называется его длиной. Для обозначения длины вектора (его абсолютной величины) пользуются символом модуля. Так и обозначают длины соответствующих векторов. Вектор единичной длины называют ортом. К векторам будем относить и так называемый нулевой вектор, у которого начало и конец совпадают. Считается, что нулевой вектор не имеет определенного направления и имеет длину равную нулю. Это позволяет обозначать нулевой вектор вещественным числом 0 (нуль). Векторы расположенные либо на одной прямой, либо на параллельных прямых называются коллинеарными. Нулевой вектор считается коллинеарным любому вектору. Среди коллениарных векторов различают одинаково направленные (сонаправленные) и противоположно направленные векторы. Векторы называются компланарными, если они лежат, либо на одной плоскости, либо на прямых, параллельных одной и той же плоскости. Определение: Два вектора называются равными, если они: 1) коллинеарны; 2) равны по длине; 3) одинаково направлены. Следствие: Для любого вектора и для любой точки А, существует, и притом единственная, точка B такая, что . Мы не будем различать двух равных векторов, имеющих разные точки приложения. Такие векторы называются свободными (в отличие от скользящих и связанных векторов, встречающихся в других науках). Понятие равенства векторов обладает следующими свойствами: 1. (рефлексивность). 2. Из того, что , следует (симметричность). 3. Из того, что и , следует (транзитивность). Вопрос 2.Операции над векторами. Определение: Суммой двух векторов и называется вектор, имеющий начало в начале вектора , а конец – в конце вектора , при условии, что вектор приложен к концу вектора . В соответствии с определением слагаемые и и их сумма образуют треугольник (рис.3). Поэтому данное правило сложения двух векторов называют «правилом треугольника». Операция сложения векторов обладает свойствами: 1. (коммутативность); 2. , (ассоциативность); 3. для любого вектора (особая роль нулевого вектора); 4. для каждого вектора существует противоположный ему вектор такой, что (для получения достаточно поменять местами начало и конец вектора ). Вектор противоположный вектору обозначают . Определение: Разностью векторов и называется сумма вектора и вектора противоположного вектору , т.е. . Разность получается из вектора сдвигом его начала в конец вектора , при условии, что векторы и имеют общее начало (рис.3). Очевидно, что для любого вектора . Замечание: Существует еще одно правило сложения векторов, называемое «правилом параллелограмма»: векторы и прикладываются к общему началу О, и на них строится параллелограмм. Суммой будет вектор , расположенный на диагонали параллелограмма. Разностью здесь будет вектор , расположенный на второй диагонали. Векторная алгебра имеет дело с двумя типами величин: векторами и числами. Числа обычно называют скалярными величинами или скалярами. Определение: Произведением вектора на вещественное число λ (скаляр) называется вектор , такой, что 1) ; 2) вектор коллинеарен вектору ; 3) векторы и имеют одинаковое (противоположное) направление, если λ > 0 (λ < 0). Замечание: В случае, когда λ = 0 или произведение  является нулевым вектором. Операция умножения вектора на число обладает следующими свойствами: 1. (ассоциативное свойство сомножителей); Действительно, заметим, что векторы, стоящие обеих частях равенства, имеют одну и ту же длину . Кроме того, они коллинеарны и одинаково направлены, так как их направление совпадает с направлением , если λ и μ одного знака, и противоположно направлению , если λ и μ имеют разные знаки. Если же λ или μ равны нулю, то обе части равенства равны нулю. Свойство доказано. 2. (свойства дистрибутивности). Построим треугольник OAB где и . Построим далее треугольник SPQ, где и . Так как стороны SP, PQ треугольника SPQ параллельны и пропорциональны сторонам OA, AB треугольника OAB, то эти треугольники подобны. Поэтому сторона SQ также параллельна стороне OB и отношение их длин также равно |λ|. Ясно, далее, что и одинаково направлены, если λ > 0. Отсюда следует, что . Но и , а отсюда вытекает первое свойство дистрибутивности. Очевидно, что векторы стоящие в обеих частях второго свойства дистрибутивности коллинеарны. Допустим сначала, что знаки λ и μ одинаковы. Тогда векторы и направлены одинаково и длина их суммы равна сумме их длин, т. е. . Но и следовательно, в этом случае векторы и равны по длине. Направление их совпадает с направлением вектора , если общий знак λ и μ положителен, и противоположно ему, если отрицателен. Допустим теперь, что знаки λ и μ различны, и для определенности будем считать |λ| > |μ|. В этом случае длина суммы равна разности длин, точнее . Но . Следовательно, и в этом случае длина вектора равна длине вектора . Очевидно, что оба эти вектора направлены так же, как . Если же |λ| = |μ| и знаки λ и μ противоположны, то обе части равенства равны нулю. То же обстоятельство имеет место, если равен нулю вектор или оба скаляра одновременно. Теорема: Если вектор коллинеарен ненулевому вектору , то существует вещественное число λ такое, что = λ. Вопрос 3. Проекция вектора. Под углом между векторами понимается угол между векторами равными данным и имеющими общее начало. Если направление отсчета угла не указано, то углом между векторами считается тот из углов, который не превосходит π. Если один из векторов нулевой то угол считается равным нулю. Если угол между векторами прямой то векторы называются ортогональными. Определение: Ортогональной проекцией вектора на направление вектора называется скалярная величина , φ – угол между векторами. Модуль этой скалярной величины равен длине отрезка OA0. Если угол φ острый проекция является положительной величиной, если угол φ тупой – проекция отрицательна, если угол φ прямой – проекция равна нулю. При ортогональной проекции угол между отрезками OA0 и AA0 прямой. Существуют проекции, у которых этот угол отличен от прямого. Проекции векторов обладают следующими свойствами: 1. (проекция суммы равна сумме проекций); 2. (проекция произведения вектора на число равна произведению проекции вектора на число). Базис называется ортогональным, если его векторы попарно ортогональны. Ортогональный базис называется ортонормированным, если его векторы по длине равны единице. Для ортонормированного базиса в пространстве часто используют обозначения . Теорема: В ортонормированном базисе координаты векторов есть соответствующие ортогональные проекции этого вектора на направления координатных векторов. Пример: Пусть вектор единичной длины образует с вектором ортонормированного базиса на плоскости угол φ, тогда . Пример: Пусть вектор единичной длины образует с векторами , и ортонормированного базиса в пространстве углы α, β, γ, соответственно (рис. 5), тогда . Причем . Величины cosα, cosβ, cosγ называются направляющими косинусами вектора Скалярное произведение Определение: Скалярным произведением двух векторов называется число, равное произведению длин этих векторов на косинус угла между ними. Если один из векторов нулевой скалярное произведение считается равным нулю. Скалярное произведение векторов и обозначается через [или ; или ]. Если φ - угол между векторами и , то . Скалярное произведение обладает следующими свойствами: 1. (коммутативность). 2. (скалярный квадрат вектора равен квадрату его длины). 3. Скалярное произведение равно нулю тогда и только тогда, когда сомножители ортогональны или хотя бы один из них нулевой. 4. . 5. . 6. . Векторное произведение Упорядоченная тройка некомпланарных векторов называется правоориентированной (правой), если после приложения к общему началу из конца третьего вектора кратчайший поворот от первого вектора ко второму виден против часовой стрелки. В противном случае упорядоченная тройка некомпланарных векторов называется левоориентированной (левой). Определение: Векторным произведением вектора на вектор называется вектор , удовлетворяющий условиям: 1. где φ – угол между векторами и ; 2. вектор ортогонален вектору , вектор ортогонален вектору ; 3. упорядоченная тройка векторов является правой. Если один из векторов нулевой, то векторное произведение есть нулевой вектор. Векторное произведение вектора на вектор обозначается {либо }. Теорема: Необходимым и достаточным условием коллинеарности двух векторов является равенство нулю их векторного произведения. Теорема: Длина (модуль) векторного произведения двух векторов равняется площади параллелограмма, построенного на этих векторах как на сторонах. Пример: Если – правый ортонормированный базис, то , , . Пример: Если – левый ортонормированный базис, то , , . Пример: Пусть, а ортогонален к . Тогда получается из вектора поворотом вокруг вектора на по часовой стрелке (если смотреть из конца вектора ). Пример: Если дан вектор , то каждый вектор можно представить в виде суммы , где – ортогонален , а – коллинеарен . Легко видеть, что . Действительно, можно заметить, что . Вектор компланарен векторам и , а потому и коллинеарны. Легко видеть (рис. 12), что они одинаково направлены. Векторное произведение обладает следующими свойствами: 1. (антикоммутативность); Действительно, из определения следует, что модуль векторного произведения не зависит от порядка сомножителей. Точно так же вектор коллинеарен вектору . Однако, переставляя сомножители, мы должны изменить направление произведения, чтобы было выполнено условие 3) определения. Действительно, если , , - правая тройка, то , , - левая, а , , - снова правая тройка. 2. ; Если φ - угол между векторами и , то . Векторы, стоящие в обеих частях доказываемого равенства, лежат на прямой, перпендикулярной и . При λ > 0 и вектор и вектор направлены так же, как . Если λ < 0, то кратчайший поворот от к производится навстречу кратчайшему повороту от к . Поэтому и противоположно направлены. Очевидно, что противоположно направлены также и векторы и . Таким образом, при λ ≠ 0 векторы и направлены всегда одинаково, и равенство доказано. При λ = 0 равенство очевидно. 3. ; Если , то доказываемое очевидно. Если , то разложим и в суммы и , где и ортогональны , а и коллинеарны . Поскольку , и вектор ортогонален , а коллинеарен , нам достаточно доказать равенство и (в силу свойства 2) даже равенство , где . Длина вектора равна 1. Выше, в примере, мы видели, что в этом случае умножение на сводится к повороту (ортогонального к ) первого сомножителя на угол 90°. Но при повороте параллелограмм, построенный на и , поворачивается целиком вместе с диагональю. Тем самым равенство доказано. 4. . Пусть в некотором базисе заданы векторы и тогда или Справедливость теоремы следует из предыдущих формул при учете примеров в начале раздела. Чтобы избежать постоянных замечаний об ориентации базиса, мы будем считать, что базис выбирается всегда правый. Векторное произведение используется в основном для решения двух задач: 1. Нахождения вектора перпендикулярного плоскости, в которой расположены два заданных вектора. 2. Вычисление площади S параллелограмма, построенного на векторах и , как на сторонах. В ортонормированном базисе В планиметрии векторное произведение не определено. Но ничто не мешает считать, что изучаемая плоскость помещена в пространство и третий базисный вектор выбран единичным и перпендикулярным плоскости. Тогда векторное произведение имеет одну ненулевую компоненту, а именно третью, и площадь параллелограмма в ортонормированном базисе на плоскости выражается формулой . Вопрос 4.Комплексные числа. Комплексным числом называется выражение вида z = a + bi, где a и b – действительные числа, – мнимая единица. Число а называется действительной частью комплексного числа z и обозначается a = Rez, число b – мнимой частью z: b = Imz. Два комплексных числа z1 = a1 + b1i и z2 = a2 + b2i равны, если a1 = a2 и b1 = b2. Комплексные числа z = a + bi и z = a – bi называются сопряженными. Действия над комплексными числами 1. При сложении двух комплексных чисел отдельно складываются их действительные части и мнимые части: z1 + z2 = (a1 + a2) + (b1 + b2)i. (1) 2. При умножении двух комплексных чисел получается комплексное число: z1z2 = (a1a2 – b1b2) + (a1b2 + a2b1)i, (2). 3. При делении двух комплексных чисел получается комплексное число: , (3).  Задача 1. Найти сумму двух комплексных чисел 2 + 3i и – 4 + 6i. Решение: Комплексные числа суммируются по правилу (1): (2 + 3i) + (– 4 + 6i) = (2 – 4) + (3 + 6)i = – 2 + 9i.  Задача 2. Найти произведение двух комплексных чисел 2 + 3i и – 4 + 5i. Решение: Комплексные числа умножаются по правилу (2): (2 + 3i)·(– 4 + 5i) = (2·(– 4) – 3·5) + (2·5 + 3·(– 4))i = – 23 – 2i.  Задача 3. Найти частное двух комплексных чисел 2 + 4i и 1 + i. Решение: Комплексные числа делятся по правилу (3): . Тригонометрическая форма комплексного числа Всякое комплексное число z = a + bi можно изобразить точкой A(a,b) плоскости, такой что a = Rez, а b = Imz. Тогда a и b можно выразить через полярные координаты r и : a = rcos, b = rsin, где r и  называются модулем и аргументом комплексного числа. Таким образом, комплексное число z = a + bi можно представить в тригонометрической форме . Экспоненциальной формой комплексного числа называется число .  Задача 4. Представить в тригонометрической форме комплексное число . Решение: Так как , то комплексное число представляется в тригонометрической форме в виде . Корни квадратного и биквадратного уравнений Корни квадратного уравнения ax2 + bx + c = 0 с отрицательным дискриминантом D = b2 – 4ac < 0 являются комплексными числами и находятся по формулам . Корни биквадратного уравнения x4 + px2 + q = 0 с отрицательным дискриминантом D = p2 – 4q < 0 являются комплексными числами и находятся по формулам: , .  Задача 5. Решить квадратное уравнение x2 – 4x + 8 = 0. Решение: Дискриминант квадратного уравнения отрицательный: D = 42 – 48 = – 16 < 0 и, следовательно, корни квадратного уравнения равны .  Задача 6. Решить биквадратное уравнение x4 – 4x2 + 16 = 0. Решение: Дискриминант биквадратного уравнения отрицательный: D = 42 – 416 = – 48 < 0. Т.к. и , то и . Тема №4. Элементы аналитической геометрии. Вопросы: 1. Основные задачи аналитической геометрии. 2. Прямая на плоскости. 3. Плоскость в пространстве. 4. Прямая в пространстве. 5. Угол между двумя прямыми в пространстве. 6. Расстояние между прямыми в пространстве. 7. Угол между прямой и плоскостью. 8. Кривые второго порядка. Вопрос 1. Основные задачи аналитической геометрии. Основной метод аналитической геометрии - метод координат. Его сущность: каждой точке М поставлены в соответствие пара или тройка чисел, называемых ее координатами. Каждой фигуре поставлено в соответствие уравнение F(x,у)=0 или F(x,у,z)=0. Отсюда возникают две основные задачи аналитической геометрии: 1) по геометрическому свойству фигуры составить ее уравнение; 2) по уравнению исследовать свойства и форму геометрической фигуры. Вопрос 2. Прямая на плоскости. Постановка задачи Даны точка Мо (x0 , y0) и вектор (A, В) Написать уравнение прямой l, перпендикулярной вектору и проходящей через точку M0. Точка M(x,y) - текущая точка прямой l. тогда и только тогда, когда и (A, В) - ортогональны, следовательно скалярное произведение или А(x-x0)+B(y-y0)=0 Итак, получили уравнение прямой, проходящей через точку M0 и перпендикулярной . Вектор называется нормальным вектором прямой. Последнее уравнение запишем в виде Ax+By+D=0 - оно называется общим уравнением прямой. Другие виды уравнений прямой на плоскости: - уравнение прямой, проходящей через точку М0 (х0 , у0) и параллельной вектору (m, n). у =kx + b - уравнение прямой с угловым коэффициентом к, где k =tg, b - отрезок, отсекаемый прямой на оси OY. у - уо = k(x - хо) - уравнение прямой с угловым коэффициентом k, проходящей через точку М0(х0, у0) - уравнение прямой, проходящей через две точки M1(x1 , y1) и M2(x2 ,y2). - уравнение прямой в отрезках. Между всеми этими уравнениями существует связь, то есть, если задана прямая одним из уравнений, то можно перейти к любому из перечисленных видов. Пример 23. Написать различные виды уравнений прямой, проходящей через две точки М1(2, 0); М2(0, 3). Решение Используя уравнение прямой, проходящей через две точки, находим или Из последнего уравнения с помощью преобразований можно перейти к другим видам уравнений этой же прямой. Уравнение прямой в отрезках: Уравнение прямой с угловым коэффициентом: Общее уравнение прямой: Зх + 2у - 6 = 0, где вектор (3, 2) перпендикулярен данной прямой. Пример 24. Найти уравнение стороны АВ и высоты, опущенной из вершины А в треугольнике АВС, где А(0, 1); В(-2. 3); С(0, 6). Решение Уравнение стороны АВ - это уравнение прямой, проходящей через точки А и В: или Чтобы написать уравнение высоты из вершины А, найдем координаты вектора , который ей перпендикулярен: Используя уравнения прямой, проходящей через точку А и перпендикулярной вектору , находим уравнение высоты: 2(х-0)+3(у-1)=0 или 2х+3у-3=0. Вопрос 3. Плоскость в пространстве. Постановка задачи. Даны точка М0(х0 ,у0 ,z0 ) и вектор (A,B, С). Написать уравнение плоскости, проходящей через точку Мо, перпендикулярно вектору . М(х, у, z) - текущая точка плоскости. Точка М принадлежит искомой плоскости тогда и только тогда, когда вектор то есть, когда скалярное произведение векторов или в координатной форме А(x-y0)+B(y-y0)+C(z-z0)=0. Полученное уравнение является уравнением плоскости, проходящей через точку М0(х0 ,у0 ,z0 ) перпендикулярно вектору (A,B,C). Вектор называется нормальным вектором плоскости. Если в последнем уравнении приведем подобные члены, то получим общее уравнение плоскости: Ax+By+Cz+D=0. Уравнение плоскости в отрезках: Используя условие компланарности трех векторов, можно записать уравнение плоскости, проходящей через точку M0 и параллельную векторам и Уравнение плоскости, проходящей через три точки, имеет вид Пример 25. Найти уравнение плоскости P1, проходящей через три точки M1(1,0,4); М2(-2,1,3); М3(0,7,1) и уравнение плоскости Р2, проходящей через точку Мз, причем Решение Уравнение плоскости р1, проходящей через три точки, имеет вид: Вычисляя определитель, получим 4(х - 1) - 8у - 20(z - 4) == 0; x-2y-5z+ 19=0 - уравнение плоскости Р1. Так как вектор и , , то, используя уравнение плоскости, проходящей через точку М3 перпендикулярно вектору найдем уравнение плоскости Р2 -3(х-0) + 1(у-7) - 1(2-1) = О или 3х-у +z+6=0. Вопрос 4. Прямая в пространстве. Различные виды уравнений прямой Прямую в пространстве можно задать как линию пересечения двух плоскостей: Пусть даны вектор (т ,п , р)и точка М0(х0 , у0 ,z0). Напишем уравнение прямой l, проходящей через точку М0 параллельно вектору . Возьмем на прямой l произвольную (текущую) точку М(х, у, z). Вектор коллинеарен вектору (m, n,p), следовательно: так как , то или Итак, уравнение называется векторным уравнением прямой в пространстве. Вектор (m, n, р) называется направляющим вектором прямой в пространстве. Запишем последнее уравнение в координатной форме; так как r (х, у, z); ro = (х0, у0, z0), то Эти уравнения называются параметрическими уравнениями прямой. Если исключить параметр t в последних уравнениях, то получим каноническое уравнение прямой. Пример 25. Найти каноническое и параметрическое уравнения прямой, заданной как пересечение двух плоскостей р1: 2x-y+z+3=0 и Р2: 3x+y-z+2=0 Решение Проверим, что заданные плоскости не параллельны, то есть их нормальные векторы неколлинеарны. Действительно, (2, -1, 1) и (3, 1, -1) - неколлинеарные векторы (их координаты не пропорциональны) Прямая l, как линия пересечения р1 и Р2 будет перпендикулярна и , поэтому направляющий вектор прямой l равен: Итак, (0,5,5) Из общего уравнения прямой найдем любую точку, принадлежащую данной прямой Пусть z = 0, тогда, решая систему находим х=-1; y= 1 Итак, точка М(-1, 1, 0) принадлежит прямой l. Каноническое уравнение прямой имеет вид параметрические уравнения заданной прямой имеют вид Вопрос 5. Угол между двумя прямыми в пространстве. Углом между двумя прямыми l1 и l2 называют любой из двух смежных углов, образованных прямыми, проведенными через произвольную точку пространства параллельно данным. Один из двух смежных углов между прямыми l1 и 12 равен углу между направляющими векторами и , тогда или В частности, если то тогда m1m2+n1n2+p1p2=0, если то тогда: Вопрос 6. Расстояние между прямыми в пространстве. Рассмотрим две прямые l1 и l2 , возможны три различных случая расположения этих прямых 1) прямые пересекаются, следовательно, они лежат в одной плоскости Уравнения прямых Векторы и , - компланарны, тогда их смешанное произведение·, где =(x2-x1; y2-y1; z2-z1)и расстояние между прямыми d=0. 2) Прямые параллельны, тогда Расстояние между прямыми d можно найти, используя определение векторного произведения. Модуль векторного произведения - это площадь параллелограмма, тогда высота d параллелограмма равна 3) Прямые скрещивающиеся, они не лежат в одной плоскости, тогда искомое расстояние d определяется длиной общего перпендикуляра к этим прямым, то есть это расстояние между параллельными плоскостями, проходящими через прямые l1 и l2. Очевидно, что нормальный вектор к плоскостям есть . Тогда скалярное произведение: где в числителе стоит модуль смешанного произведения, или объем параллелепипеда, построенного на векторах , и , в знаменателе - модуль векторного произведения, то есть площадь параллелограмма, построенного на векторах и . Расстояние d совпадает с высотой данного параллелепипеда. Вопрос 7. Угол между прямой и плоскостью. Углом φ между прямой и плоскостью будем называть любой из двух смежных углов, образованных прямой и ее проекцией на плоскость. Рассмотрим плоскость р: Ах + By + Cz + D = 0, где (A, В, С) - нормальный вектор плоскости; (m, и, р) - направляющий вектор прямой l. Пусть a - угол между векторами и , тогда а = 90- φ, следовательно: cosa=cos(90 - φ) =sina. Из определения скалярного произведения: или или В частности, если l||p, то тогда Ат+Вп+Ср=0, если l p, то , тогда Пример 26. Найти угол между прямыми l: у- 2х + 5 = 0 и l2: 2y+x+3=0 Решение Следовательно, , то есть прямые перпендикулярны. Пример 27. Найти точку пересечения прямой с плоскостью р: х+2у+z - 4=0. Решение Запишем уравнение прямой в параметрическом виде: Подставим в уравнение плоскости Р, получим 2t+1+2(t-5)+t+3-4=0, 5t=10 или t=2, тогда х =5, y=-3, z=5. Точка М (5, -3, 5) является точкой пересечения прямой l с плоскостью Р. Пример 28. Лежит ли прямая в плоскости Р: x-y-z-3=0. Решение Поступаем так же, как в предыдущей задаче, получим 2t+ 1 --(t-5)-(t+3)-3=0, 2t-t-t+1+5-3-3=0; 0t = 0, получили тождество, то есть при любом t мы получим все точки прямой l, следовательно, прямая l принадлежит плоскости Пример 29. Найти угол между прямой и плоскостью Р: х + 2у + z - 4 = 0. Решение. Вектор Вектор тогда тогда Вопрос 8. Кривые второго порядка. Множество точек плоскости, координаты которых удовлетворяют уравнению Ax2+Bxy+Cy2+Dx+Ey+F=O, называется кривой второго порядка, причем хотя бы один из коэффициентов А, В, С отличен от нуля Если А = В = С = 0, то получим уравнение первого порядка, которое определяет прямую на плоскости Если данному уравнению не удовлетворяют координаты ни одной точки плоскости, то имеем так называемую мнимую кривую, например, x2+ у2 = -1 есть уравнение мнимой окружности. В общем случае может оказаться, что уравнение определяет вырожденную кривую - либо пустое множество, либо точку, либо прямую, либо пару прямых (приведите примеры). В дальнейшем рассмотрим только невырожденные кривые. Можно показать, что для таких кривых существует прямоугольная система координат, в которой уравнение этой кривой имеет один из следующих видов. Эти уравнения называются каноническими уравнениями соответственно эллипса, гиперболы и параболы. 2.15.1 Эллипсом называется множество точек на плоскости, сумма расстояний от которых до двух данных есть величина постоянная. Пусть М(х,у) - произвольная (текущая) точка кривой, F1 и F2 -заданные точки. По условию: Пусть тогда F1(-c;0); F2(c,0) Так как и , то Выполним преобразования: Обозначим: а2 -с2 = b2 (а > b, почему ?), тогда b2х2 +a2y2=а2b2 или Итак, получили каноническое уравнение эллипса Параметры а и b называются полуосями (большой и малой) эллипса, начало координат - центром кривой. Точки f1 (-с, 0) и F2 (с, 0) называются фокусами эллипса, где с2 = а2 -b2. Число или называется эксцентриситетам эллипса, оно характеризует «сплюснутость» кривой. В частности, при ε=0, (a=b), имеем или x2+y2=a2 - каноническое уравнение окружности радиуса а с центром в начале координат (фокусы F1 и F2 совпадают с центром). 2.15.2 Гиперболой называется множество точек, абсолютное значение разности расстояний от которых до двух данных точек есть величина постоянная (отличная от нуля). По условию или Выполнив преобразования (сделайте самостоятельно), обозначив a2+b2=с2, получим каноническое уравнение гиперболы где а и b называются полуосями гиперболы, точки (а, 0) и (-а, 0) - ее вершинами, оси симметрии ОХ и OY - соответственно действительной и мнимой осями, точки F1 (-с, 0) и F2( с, 0) -фокусами гиперболы. Число называется эксцентриситетом гиперболы. Прямые (диагонали прямоугольника в центре), уравнения которых , являются асимптотами гиперболы. Гиперболу, каноническое уравнение которой называют сопряженной, график ее имеет следующий вид: 2.15.3 Параболой называется множество точек, равноотстоящих от заданной точки, называемой фокусом, и от заданной прямой, называемой директрисой. Пусть М(х,у) - текущая точка кривой, - заданная точка, фокус; уравнение заданной прямой (директрисы) - расстояние от точки М до директрисы, оно равно По условию или Выполним преобразования: ; окончательно каноническое уравнение параболы: y2=2xp O Число Р называется параметром параболы; точка O(0;0) -вершина параболы; ось ОХ - ось симметрии параболы; прямая - директриса параболы, проходит на расстоянии от вершины параболы. Пример 30. Определить вид кривой, найти ее центр, фокусы и эксцентриситет x2-4x+4y2 =0. Решение: Найдем каноническое уравнение кривой, для этого сделаем преобразования: x2-4x+4-4+4y2=0 (x-2)2+4y2=4 Окончательно Полученное уравнение есть каноническое уравнение эллипса, где а=2; b=1; центр эллипса в точке (2,0). Найдем фокусы, для этого вычислим параметр с: тогда: эксцентриситет эллипса - Тема №5. Неотрицательные матрицы и модели Леонтьева. Вопросы: 1. Общая структура межотраслевого баланса. 2. Статическая межотраслевая модель. 3. Модель межотраслевого баланса затрат труда. 4. Пример расчета межотраслевого баланса. Вопрос 1. Общая структура межотраслевого баланса. Центральным элементом матричных моделей является так называемый межотраслевой баланс. Он представляет собой таблицу, характеризующую связи между различными отраслями экономики страны. Общая структура межотраслевого баланса представлена в таблице 3.1 Таблица 3.1 - Общая структура межотраслевого баланса Производственная сфера экономики представлена в балансе в виде совокупности n отраслей. Баланс состоит из четырех разделов (квадрантов). Первый квадрант представляет собой матрицу, состоящую из (n+1) строки и (n+1) столбца. Этот раздел является важнейшей частью баланса, поскольку именно здесь содержится информация о межотраслевых связях. Величина xij, находящаяся на пересечении i-й строки и j-го столбца, показывает, сколько продукции i-й отрасли было использовано в процессе материального производства j-й отрасли. Величины xij характеризуют межотраслевые поставки сырья, материалов, топлива и энергии, обусловленные производственной деятельностью. В i-й строке величины xi1, xi2,..., xij,..., xin описывают распределение продукции i-й отрасли как средства производства для других отраслей. Величины x1j, x2j,..., xij,..., xnj j-го столбца в этом случае будут описывать потребление j-й отраслью сырья, материалов, топлива и энергии на производственные нужды. Таким образом, первый раздел баланса дает общую картину распределения продукции на текущее производственное потребление всех n отраслей материального производства. В зависимости от того, в каких единицах измеряются потоки продукции в балансе, существуют различные его варианты: в натуральном выражении, в денежном (стоимостном) выражении, в натурально-стоимостном, в трудовых измерителях. Мы рассмотрим баланс в стоимостном выражении, в котором потоки продукции измеряются на основе стоимости произведенной продукции в некоторых фиксированных ценах. Поскольку в этом случае величины xij отражают стоимость продукции, т.е. измеряются в одних и тех же единицах, их можно просуммировать. Величина представляет собой сумму всех поставок i-й отрасли другим отраслям. Сумма по столбцу характеризует производственные затраты j-й отрасли на приобретение продукции других отраслей. На пересечении (n+1) - й строки и (n+1) - го столбца находится величина - так называемый промежуточный продукт экономики. Второй раздел посвящен конечному продукту. Столбец конечного продукта - (n+2) - й столбец. Величина yi - потребление продукции i-й отрасли, не идущее на текущие производственные нужды. В конечную продукцию, как правило, включаются: накопление, возмещение выбытия основных средств, прирост запасов, личное потребление населения, расходы на содержание государственного аппарата, здравоохранение, оборону и т.д., а также сальдо экспорта и импорта. Ко второму разделу относится также столбец валовых выпусков (Xi). В пределах первого и второго разделов справедливо соотношение: (3.1) Третий квадрант межотраслевого баланса отражает стоимостную структуру валового продукта отраслей. В (n+2) - й строке таблицы отражена условно чистая продукция (Vj), представляющая собой разницу между величиной валовой продукции отрасли и суммарными затратами отрасли: (3.2) Условно чистая продукция подразделяется на амортизационные отчисления и чистую продукцию отрасли. Важнейшими составляющими чистой продукции отрасли являются заработная плата, прибыль и налоги. Можно показать, что суммарный конечный продукт равен суммарной условно чистой продукции (). Из соотношений (3.1) и (3.2): Просуммируем первое равенство по i, а второе - по j: Левые части выражений равны, значит равны и правые: откуда что и требовалось доказать. Таким образом, в третьем разделе также фигурирует конечный продукт, но если во втором разделе он разбивается на величины yi, характеризующие структуру потребления, то в третьем разделе величины Vj показывают, в каких отраслях произведена стоимость конечного продукта. Четвертый раздел располагается под вторым. Он характеризует перераспределительные отношения в экономике, осуществляемые через финансово-кредитную систему. В плановых расчетах четвертый раздел, как правило, не используется, и поэтому в пределах нашего курса рассматриваться не будет. Итак, рассмотренный нами межотраслевой баланс - это способ представления статистической информации об экономике страны. Он строится на основе агрегирования результатов деятельности отдельных предприятий. Такой баланс называют отчетным. Кроме этого строятся плановые балансы, предназначенные для разработки сбалансированных планов развития экономики. Вопрос 2. Статическая межотраслевая модель. Статистические межотраслевые модели используются для разработки планов выпуска и потребления продукции и основываются на соотношениях межотраслевого баланса. При построении модели делают следующие предположения: 1) все продукты, производимые одной отраслью, однородны и рассматриваются как единое целое, т.е. фактически предполагается, что каждая отрасль производит один продукт; 2) в каждой отрасли имеется единственная технология производства; 3) нормы производственных затрат не зависят от объёма выпускаемой продукции; 4) не допускается замещение одного сырья другим. В действительности эти предположения, конечно, не выполняются. Даже на отдельном предприятии обычно выпускаются различные виды продукции, используются различные технологии, удельные затраты зависят от объема выпуска и в тех или иных пределах допускается замена одного сырья другим. Следовательно, эти предположения тем более неверны для отрасли. Однако такие модели получили широкое распространение и, как показала практика, они вполне адекватны и применимы для составления планов выпуска продукции. При этих предположениях величина xij может быть представлена следующим образом: (3.3) Величина aij называется коэффициентом прямых материальных затрат. Она показывает, какое количество продукции i-й отрасли идет на производство единицы продукции j-й отрасли. Коэффициенты aij считаются в межотраслевой модели постоянными. Подставляя выражение (3.3) в формулу (3.1), получим: Это соотношение можно записать в матричном виде: X = AX + Y, (3.4) где X = (X1, X2,..., Xn) - вектор валовых выпусков; Y = (y1, y2,..., yn) - вектор конечного продукта; A = - матрица коэффициентов прямых материальных затрат. Коэффициенты прямых материальных затрат являются основными параметрами статической межотраслевой модели. Их значения могут быть получены двумя путями: 1) статистически. Коэффициенты определяются на основе анализа отчётных балансов за прошлые годы. Их неизменность во времени определяется подходящим выбором отраслей; 2) нормативно. Предполагается, что отрасль состоит из отдельных производств, для которых уже разработаны нормативы затрат; на их основе рассчитываются среднеотраслевые коэффициенты. Выражение (3.4) принято называть балансом распределения продукции. Его можно использовать для анализа и планирования структуры экономики. Если известны коэффициенты прямых материальных затрат, то, задав конечный продукт по каждой отрасли, можно определить необходимые валовые выпуски отраслей. В этом заложена основная идея использования матричных моделей для планирования производства. Преобразуем выражение (3.4): X - AX = Y, X (E - A) = Y, X = (E - A) - 1Y, (3.5) где E - единичная матрица. До начала планирования следует выяснить, существует ли матрица, обратная матрице (E-A), и не будут ли получены отрицательные значения выпуска по отраслям. Установим некоторые свойства коэффициентов прямых материальных затрат. 1. Неотрицательность, т.е. aij ≥ 0, Это утверждение следует из неотрицательности величин xij и положительности валовых выпусков Xj. 2. Сумма элементов матрицы A по любому из столбцов меньше единицы, т.е. Доказать это утверждение несложно. Для любой отрасли условно чистая продукция есть величина положительная, поскольку включает в себя заработную плату, амортизацию, прибыль и т.д., т.е. Vj>0. Поэтому, используя соотношение (3.2), можно записать: из соотношения (3.3): откуда безусловно следует: таким образом, утверждение доказано. Можно показать, что при выполнении этих двух условий матрица B = (E - A) - 1 существует и если ее элементы неотрицательны. Говорят, что в этом случае матрица прямых затрат А является продуктивной. Перепишем формулу (3.5): X = BY, (3.6) Матрица В носит название матрицы полных материальных затрат, а ее элементы bij называют коэффициентами полных материальных затрат. Коэффициент bij показывает, каков должен быть валовый выпуск i-й отрасли для того, чтобы обеспечить выпуск единицы конечного продукта j-й отрасли. Можно показать, что B = E + A + A2 + A3 +... (3.7) Умножим обе части на (E - A): B (E - A) = (E + A + A2 + A3 +. .) (E - A), B (E - A) = E + A + A2 + A3 +. - A - A2 - A3 - ..., B (E - A) = E, B = E / (E - A), B = (E - A) - 1. Доказано. Из соотношения (3.7) следует bij ≥ aij, Таким образом, коэффициент полных материальных затрат bij, описывающий потребность в выпуске продукции i-й отрасли в расчете на единицу конечного продукта j-й отрасли, не меньше коэффициента прямых материальных затрат aij, рассчитываемого на единицу валового выпуска. Кроме того, из соотношения (3.7) для диагональных элементов матрицы B следует: bii ≥ 1, Взаимосвязь коэффициентов прямых и полных материальных затрат проще всего проследить на примере: пусть единицей выпуска хлебопекарной промышленности является хлеб (рисунок 3.1). Рисунок 3.1 - Взаимосвязь коэффициентов прямых и полных материальных затрат Полные затраты электроэнергии для нашего примера складываются из прямых затрат и косвенных затрат всех уровней. Косвенные затраты высоких уровней являются незначительными и при практических расчетах ими можно пренебречь. Вопрос 3. Модель межотраслевого баланса затрат труда. Предполагается, что труд выражается в единицах труда одинаковой степени сложности. Обозначим затраты живого труда в производстве j-го продукта через Lj, объем выпущенной продукции, как и прежде, Xj. Тогда коэффициент прямых затрат труда: Определим полные затраты труда, как сумму прямых затрат живого труда и затрат овеществленного труда, перенесенного на продукт через израсходованные средства производства. Формирование полных затрат труда в модели происходит по схеме, представленной на рисунке 3.2 Рисунок 3.2 - Порядок формирования полных затрат труда где Tj - полные затраты труда на единицу j-го продукта; tj - прямые затраты труда на единицу j-го продукта; aijTi - затраты овеществленного труда, перенесенного на j-й продукт через i-е средство производства. Таким образом: Иначе, если известны коэффициенты полных материальных затрат bij, можно записать: Более компактно соотношение можно записать в матричном виде: T = tB, где T = (T1, T2,..., Tn) - вектор-строка коэффициентов полных затрат труда; t = (t1, t2,..., tn) - вектор-строка коэффициентов прямых затрат труда. Аналогично трудовым затратам в межотраслевой модели могут быть учтены показатели фондоемкости изделий. Василий Леонтьев, характеризуя значение балансовых моделей, писал: "Чтобы прогнозировать развитие экономики, нужен системный подход. Экономика каждой страны - это большая система, в которой много различных отраслей, и каждая из них что-то производит - промышленную продукцию, услуги и т.д., которые предлагаются другим отраслям. Каждое звено, компонент системы может существовать только потому, что получает что-то от других. Для производства каждого вида продукции нужно напрямую использовать большое количество других товаров, а еще больше - опосредованно. Мы изучаем одну страну, беря в расчет 600-700 отдельных отраслей, японцы доходят до 2000". Вопрос 4.Пример расчета межотраслевого баланса. Рассмотрим 2 отрасли промышленности: производство угля и стали. Уголь требуется для производства стали и некоторое количество стали в виде инструментов требуется для добычи угля. Предположим, что условия таковы: для производства 1 т. стали нужно 3 т. угля, а для 1 т. угля - 0,1 т. стали. Отрасль Уголь Сталь Уголь 3 Сталь 0.1 Мы хотим, чтобы чистый выпуск угольной промышленности был тонн угля, а стальной промышленность - тонн стали. Если каждая из них будет производить лишь и тонн, то часть продукции будет использоваться в другой отрасли. Для производства тонн стали требуется тонн угля, а для производства тонн угля нужно тонн стали. Чистый выход будет равен: тонн угля и тонн стали. Нам нужно дополнительно производить уголь и сталь, чтобы использовать их в другой отрасли. Обозначим x1 - количество угля, x2 - количество стали. Валовый выпуск каждой продукции найдем из системы уравнений: Решение: (500000; 100000). Для систематического решения задач расчета межотраслевого баланса находят, сколько угля и стали требуется для выпуска 1 т. каждого продукта. x1 = 1,42857 и x2 = 0,14286. Чтобы найти, сколько угля и стали нужно для чистого выпуска т. угля, нужно умножить эти цифры на . Получим: (285714; 28571). Аналогично составляем уравнения для получения количества угля и стали для выпуска 1 т. стали: x1 = 4.28571 и x2 = 1.42857. Для чистого выпуска т. стали нужно: (214286; 71429). Валовый выпуск для производства тонн угля и тонн стали: (285714 + 214286; 28571 + 71429) = (500000; 100000). Тема 6. Линейное программирование. Экономико-математические модели. Вопросы: 1.Функция полезности. Кривые безразличия. Функция спроса. 2. Уравнение Слуцкого. Кривые «доход-потребление». Кривые «цены-потребление». Коэффициенты эластичности. Материальные балансы. 3. Функции выпуска продукции. Производственные функции затрат ресурсов. 4. Задачи линейного программирования. 5. Экономико-математические модели. Вопрос 1. Функции полезности. Кривые безразличия. Функции спроса. Полезность блага – это способность экономического блага удовлетворять одну или несколько человеческих потребностей. Функция полезности – отношение между объемами потребляемых товаров и услуг Q и общей полезности (TU). Функция полезности, возрастая до Qmax, имеет выпуклый вид, так как каждая последующая единица блага увеличивает общую полезность на меньшую величину, чем предыдущая. Функция общей полезности имеет точку максимума, после которой она становится убывающей (рис. 8.1). В максимуме данное количество блага полностью удовлетворяет потребность. Рис. 8.1. Функция полезности и предельная полезность Предельная полезность – это величина добавочной полезности, полученной от прироста величины потребителя на единицу при прочих равных условиях (MU – marginal utility). Предельная потребность представляет собой частную производную общей полезности по объему потребления товара А . Предельная полезность (рис. 5.1) после Qmax становится отрицательной, что означает дальнейшее потребление приносит вред. При покупке товаров на рынке потребитель выбирает набор, который для него является наиболее предпочтительным. Считается, что потребитель хорошо знает потребительские свойства товаров и определяет в соответствии со своими вкусами и предпочтениями полезность каждого товара. Уменьшение количества одного блага в наборе можно компенсировать увеличением некоторого количества другого блага. Существует много наборов, содержащих две товара в различной комбинации и имеющих одинаковую совокупную полезность. Эти наборы представляются точками на кривой безразличия. Кривая так называется потому, что потребителя безразлично, какой набор приобрести. Если обозначить количество товара A буквой x, а количество товара B буквой y, то кривая безразличия имеет вид (рис. 8.2). На рисунке наборы кривой имело общую полезность. При увеличении общей полезности кривая безразличия сдвигается вправо. Рис. 8.2. Кривая безразличия Для товаров совершенных заменителей (например, подсолнечное и кукурузное масла) кривая безразличия является прямой линией. В точках пересечения с осями потребитель покупает только один товар. В других точках потребитель покупает оба продукта в различной пропорции. Удовлетворяет потребности набора A. Часть товара x в наборе B не будет использована для удовлетворения потребностей, поэтому этот набор покупать нецелесообразно. Набор взаимодополняемых товаров с большей общей полезностью u2 находится в угловой точке более высокой кривой безразличия. Кривые безразличия никогда не пересекаются. Кривые безразличия упорядочивают наборы товаров в определенном порядке в соответствии с их полезностью для потребителей. Тем не менее, наглядность графического изображения, сила и убедительность аргументов А.Маршалла были настолько впечатляющими, что с тех пор экономисты всего мира используют именно такое изображение кривых спроса и предложения, объясняя с их помощью механизм рыночного ценообразования. При этом большая часть экономистов отдает себе отчет в том, что кривые спроса и предложения изображаются ими не совсем корректно, показывают эту математическую ошибку, но - так уж принято на протяжении многих десятилетий - ошибку не исправляют. Кривые спроса и предложения в интерпретации А.Маршалла показаны на рисунке 8.3 На нем кривая предложения по традиции обозначена двумя буквами S, а кривая спроса - двумя буквами D. Точка пересечения этих кривых, обозначенная буквой A, характеризует точку рыночного равновесия с равновесной ценой P' и равновесным объемом продаж Q'. Указанная постановка задачи на первых порах затрудняет понимание процесса рыночного ценообразования, особенно для людей со строгими математическими вкусами. Однако в дальнейшем проблемы постепенно исчезают. Рис. 8.3. Кривые спроса и предложения в классической постановке А.Маршалла В настоящей работе такая интерпретация процессов оказывается неприемлемой, поэтому в дальнейшем и математически и графически имеется в виду именно зависимость объемов от цены единицы изделия, то есть будет использоваться математически корректная постановка задачи. Тогда если говорить о кривой спроса, которая характеризует объем приобретения при той или иной цене, а о кривой предложения говорить как о кривой, характеризующей объемы товара, которые продавцы готовы предложить на продажу при изменении цен, то график должен быть иным, а именно таким, как это изображено на рисунке 8.4. Здесь, в отличие от рисунка 8.3, кривая предложения: - во-первых, имеет началом горизонтальную ось, а не вертикальную; - во-вторых, имеет горизонтальную асимптоту, а не вертикальную. Очевидно, что и координаты точки A поменялись местами. Новое расположение кривых спроса и предложения математически, а значит, и методологически более верны, да и смысловую нагрузку имеют достаточно более ясную, чем в случае их изображения на осях рисунка 8.3. Рис. 8.4. Кривые спроса и предложения в математически корректной постановке В такой постановке задачи можно действительно говорить о графическом изображении зависимости объемов от цены и говорить об адекватности ему математических методов, начиная с уравнений кривых спроса и предложения и заканчивая (в специальных случаях) вычислением интегралов. Рисунок 8.4 позволяет получить целый ряд новых результатов, которые невозможно получить при применении рисунка 8.3. В большинстве случаев практикующих экономистов волнует кривая спроса. Графическая модель спроса, показанная на рисунке 1.1.2, основана на предположении о неизменности, статичности рассматриваемого процесса. Если рассмотреть состояние спроса в каждый момент наблюдения на примере какого-либо конкретного рынка, то в подавляющем большинстве случаев мы будем иметь дело с точками, которые лежат не на одной кривой, которая может быть описана моделью с постоянными коэффициентами, а на целом ряде кривых. В подавляющем большинстве случаев каждая новая кривая спроса будет значительно отличаться от предыдущей и от последующей и будет расположена таким образом, что она изменит и уровень своей кривизны, и свои асимптоты. Это означает, что и все параметры математической модели, с помощью которой можно описать кривую спроса, оказываются изменяющимися во времени. Эмпирические опыты показывают, что изменения параметров математической модели, описывающих кривую спроса, как правило, не имеют какой-либо выраженной тенденции. Это означает, что проанализировать и спрогнозировать тенденцию изменения параметров модели (а значит, и тенденцию изменения кривых спроса) нет никакой возможности. Более того, мой собственный практический опыт исследования кривых спроса и предложения на различных фондовых рынках России показывает, что их месторасположение определяется состоянием экономической конъюнктуры и ее конъюнктурообразующих факторов. Часть этих факторов просто неизвестна и не может быть не только спрогнозирована, но даже выявлена. Другая часть не может быть оценена количественно, так как носит явно качественный характер (заявления политиков, например). В то же время, колебания спроса и предложения относительно некоторой постоянной величины под воздействием этих факторов в кратковременной перспективе носит явно выраженный вероятностный характер, поэтому в долговременном аспекте динамика рыночных цен имеет все же некоторый закономерный характер, выявлением и описанием которого занимаются прогнозисты. Поэтому единственно приемлемым путем для прогнозирования спроса остается путь прогнозирования динамики не кривой спроса, а точки равновесия А, ее абсциссы и ординаты. При этом априорно приходится предполагать, что выявленная динамика будет сохраняться и в прогнозируемом периоде, то есть делается предположение о некотором количественном стационарном изменении экономической конъюнктуры. В терминах данной работы под доходом будет пониматься начальный запас блага плюс денежный доход. Этот фактор в работе я обозначил буквой С. Показать предопределяющее влияние дохода на спрос можно графически. Так, на рисунке 8.5 представлен график месторасположения кривой предложения и двух кривых спроса, каждая из которых отличается величиной дохода потребителя. Кривая, отмеченная на рисунке через С1, характеризует спрос потребителя, для которого характерен меньший доход, чем у кривой спроса, отмеченной буквой С2. Рис. 8.5 Кривые спроса при разных состояниях дохода С1 и С2 Как легко убедиться из графика рисунка 8.5, отдельные геометрические характеристики кривой спроса (точки пересечения с осями координат, угол наклона касательной и т.п.) определяются доходом покупателя. Значит именно доход покупателя, существенно влияя на спрос, определяет точку пересечения кривых спроса и предложения, т.е. на равновесную точку. В классической экономической теории предполагается, что доход является фиксированным и рассматривается некоторый абстрактный потребитель с данным доходом. Вопрос 2. Уравнение Слуцкого. Кривые «доход-потребление». Кривые «цены-потребление». Коэффициенты эластичности. Материальные балансы. Коэффициенты эластичности В экономике важным показателем считается эластичность спроса. Коэффициент эластичности спроса по цене показывает, на сколько изменится спрос в процентах при увеличении цены товара на 1%. Коэффициент эластичности спроса по цене определяется как , где Q - спрос. Из-за отрицательного наклона функции спроса p < 0. Факторами, влияющими на эластичность, являются наличие заменителей, размера дохода, качество товара и т.д. Спрос называют эластичным, если p > 1. Когда p < 1, то спрос считается не эластичным. Если 0 < p < 1, то спрос не эластичен, и увеличение (снижение) цены сопровождается снижением (повышением) спроса менее, чем на 1%. Если p > 1, то спрос эластичен, и увеличение (снижение) цены сопровождается снижением (повышением) спроса более, чем на 1%. Если кривая спроса задана линейной функцией Q= a – bp, то .  Задача 1. Найти эластичность спроса Q = 40 – 2p по цене, при p = 4. Решение: p = 4/32(– 2) = – 0,25. В случае, если спрос является функцией двух переменных – цены p и дохода населения R, то коэффициент эластичности спроса по цене определяется как , т.е. с помощью частной производной спроса по цене. Таким же образом определяется коэффициент эластичности спроса по доходу . С ростом доходов покупатель предпочтение дает качественным (и дорогим) товарам, поэтому для качественных товаров спрос увеличивается с ростом доходов, т.е. R > 0. Потребление низкосортных товаров с ростом доходов уменьшается, поэтому R < 0. Высокий положительный коэффициент спроса по доходу в отрасли указывает, что ее вклад в экономический рост больше, чем доля в структуре экономики, и она имеет шансы на расширения и процветание в будущем. Наоборот, если коэффициент эластичности спроса на продукцию отрасли имеет небольшое положительное или отрицательное значение, то ее может ожидать застой и перспективы сокращения производства. Коэффициент эластичности предложения по цене показывает, на сколько изменится предложение в процентах при увеличении цены товара на 1%. Коэффициент эластичности предложения по цене определяется по той же формуле, где Q – предложение. Здесь уже p > 0, т.к. предложение увеличивается при увеличении цены.  Задача 2. Найти коэффициенты эластичности спроса по цене и доходу, для Q = 100 – 2p + 0,1R, при p = 10, R = 1000. Решение: p = 10/180(– 2) = – 0,11; R = 1000/180(0,1) = 0,55 Вопрос 3. Функции выпуска продукции. Производственные функции затрат ресурсов. Производство – важнейшая сфера деятельности фирмы, в которой создается продукция в результате использования производственных факторов. Обычно факторы производства подразделяют на четыре большие категории: труд, капитал, природные ресурсы и предпринимательство. В свою очередь каждая из категорий включает более мелкие группировки. Взаимодействие между вводимыми факторами, производственным процессом и итоговым выходом продукции описывается производственной функцией. Производственная функция описывает технологическую связь между объемом выпускаемой продукции и производственными затратами факторов производства. Будем считать, что выпуск зависит от двух факторов производства – труда L и капитала K. В общем виде производственная функция имеет вид Q = f(K, L). Если независимыми переменными являются затраты, то производственную функцию называют функцией выпуска. Связь между выпуском и затратами факторов соответствует конкретной технологии. В функции находит отражение максимальный объем конечного продукта. В действительности же при любой комбинации факторов можно получить несколько объемов выпуска в зависимости от эффективности организации производства. Производственные функции обладают следующими свойствами. Так как факторы производства являются взаимодополняющими, то отсутствие хотя бы одного из них делает производство невозможным, поэтому f(0, L) = f(K, 0) = 0. Свойство аддитивности отражает тот факт, что объединение двух групп факторов (K1, L1) и (K2, L2) позволяет выпустить по крайней мере такой же объем продукции, как и при раздельном их использовании: f(K1 + K2, L1 + L2)  f(K1, L1) + f(K2, L2). Свойство делимости означает, что любой производственный процесс может осуществляться в сокращенных масштабах: f(K/n, L/n)  f(K, L)/n. Данные свойства не выполняются на малых предприятиях. Один и тот же выпуск можно получить при сочетании факторов (K1, L1), (K2, L2) (Kn, Ln), где n - любое положительное число. Кривая, каждой точке которой соответствует одно из сочетаний факторов и выпуск Q, представляет собой график производственной функции и носит название изокванты (рис. 23). Самая простая производственная функция – линейная с идеально взаимозаменяемыми факторами производства имеет вид Q = aK + bL, где a и b - постоянные. Самая известная производственная функция – это нелинейная функция Кобба-Дугласа Q = AKL1-, где – эластичность выпуска по капиталовложению, а A характеризует эффективность применяемой технологии. Новейшая технология имеет высокую эффективность и обеспечивает больший выпуск по сравнению с ранее применявшейся технологией. Более общую производственную функцию построили К.Эрроу, Х.Чененри, Минхас и Р.Солоу: , где  – эффективность технологии, k - капиталоемкость технологии,  - эластичность замены одного фактора производства другим,  - технологическая отдача от масштаба производства. Производственная функция применяется при минимизации издержек, при максимизации прибыли, при изучении связей и зависимостей процесса производства и т.д. Вопрос 4. Задачи линейного программирования. Фирма выпускает два вида древесно-стружечных плит - обычные и улучшенные. При этом производится две основные операции - прессование и отделка. Требуется указать, какое количество плит каждого типа можно изготовить в течение месяца так, чтобы обеспечить максимальную прибыль при следующих ограничениях на ресурсы (материал, время, затраты): Затраты Партия из 100 плит Имеющиеся ресурсы на месяц обычных улучшенных Материал (фунты) Время на прессование (часы) Время на отделку (часы) Средства (деньги) 20 4 4 30 40 6 4 50 4000 900 600 6000 Прибыль 80 100 max Перейдем к построению математической модели поставленной задачи. Введем следующие обозначения. Пусть х - количество партий в 100 плит обычного вида, изготавливаемых в течение месяца; у - количество партий в 100 плит улучшенного качества, изготавливаемых в течение месяца. Тогда ожидаемую прибыль можно записать так: Требуется найти такие значения х и у, подчиненные условиям для которых Для того, чтобы найти в первой четверти плоскости хОу множество точек, координаты (х, у) которых удовлетворяют указанным выше неравенствам, необходимо сначала построить прямые (по точкам их пересечения с координатными осями) а затем, используя точку начала отсчетаО(0, 0), определить соответствующие полуплоскости. Пересечением полученных полуплоскостей будет четырехугольник ОВМЕ. Наша целевая функция достигает наибольшего значения в одной из вершин четырехугольника. Нам необходимо найти координаты точки М - точки пересечения прямых EF и АВ, для этого надо решить систему уравнений Вычислить значения z в точкахВ(0, 100), Е(150, 0), М(100, 50): Из полученных значений выберем наибольшее и получим ответ: Общая задача линейного программирования В общем случае и число неизвестных , и число ограничений могут достигать десятков, сотен, тысяч и т.д. Однако набор соответствующих условий ничем (кроме количества) от рассмотренных выше примеров не отличается. Это нетрудно заметить уже по общей постановке задачи линейного программирования. Стандартная математическая формулировка общей задачи линейного программирования выглядит так: требуется найти экстремальное значение показателя эффективности (целевой функции) (линейной функции элементов решения ) при линейных ограничительных условиях, накладываемых на элементы решения: где - заданные числа. Что касается существующих методов решения этой задачи с числом переменных, больших двух, то в их основе лежат те же идеи, на которые мы опирались при разработке графического подхода. Конечно, в случае сильного увеличения числа переменных и ограничений техника получения решения заметно усложняется, но она опирается на совершенно стандартные, хорошо разработанные алгоритмы (возникающие трудности связаны лишь с ростом объема необходимых вычислений). Общую постановку задачи линейного программирования можно записать в более компактной форме, если воспользоваться следующим правилом. Правило сокращенного суммирования. Для обозначения суммы чисел : принята такая запись: где ∑ - знак суммирования, а k - индекс суммирования. Это обозначение очень удобно: А вот как выглядит запись общей задачи линейного программирования: Транспортная задача Важный тип задач линейного программирования представляет задача о перевозках. Называется она так потому, что цель этой задачи заключается в минимизации полной стоимости перевозок известного количества товаров со складов к потребителю. Сбалансированная задача - задача о перевозках, в которой общий объем товаров, готовых к отправлению, в точности равен объему товаров, который готовы принять в пунктах назначения. Пример 1. Рассмотрим транспортную задачу, заданную таблицей   В Наличие 1 2 А 1 2 1 2 2 1 20 10 Запрос 16 14 30 Решение. Пусть - искомое число единиц товара, пересылаемого из пункта в пункт . Тогда данные таблицы можно представить в следующем виде: при условии, что Положим и выразим через t остальные переменные: из первого уравнения: , из второго уравнения: , из третьего уравнения: Тогда Из того, что все не отрицательны, получаем, что переменная t должна удовлетворять одновременно следующим четырем неравенствам: Тем самым, мы получили условие . Не трудно заметить, что при t = 16. Ответ: Пример 2. Компания имеет два товарных склада и трех оптовых покупателей. Известно, что общий объем запасов на складах составляет 300 тыс. единиц продукции и совпадает с общим объемом заказов покупателей. Обозначим через количество товара, поставляемого со склада покупателю . Тогда соответствующая транспортная задача может быть сформулирована следующим образом. Минимизировать общую стоимость перевозок: при условии, что Получаем задачу линейного программирования, в которой основные ограничения вследствие того, что транспортная задача сбалансирована, является равенствами. Положим и выразим через u и v остальные переменные. Имеем Учитывая, что все перевозки должны получить неотрицательные значения, мы приходим к задаче которую можно решить графическим методом. Выписанные неравенства определяют на плоскости (u,v) пятиугольник с вершинами (30, 0), (70, 0), (70, 50), (0, 120), (0, 30). Ответ: Симплексный метод Данный метод является методом целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует. Основное содержание симплексного метода заключается в следующем: Указать способ нахождения оптимального опорного решения Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции будет ближе к оптимальному, т.е. указать способ улучшения опорного решения Задать критерии, которые позволяют своевременно прекратить перебор опорных решений на оптимальном решении или следать заключение об отсутствии оптимального решения. Алгоритм симплексного метода решения задач линейного программирования Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее: Привести задачу к каноническому виду Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений) Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода Если выполняется признак единственности оптимального решения, то решение задачи заканчивается Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения Пример решения задачи симплексным методом Пример 26.1 Решить симплексным методом задачу: Решение: Приводим задачу к каноническому виду. Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x6 с коэффициентом +1. В целевую функцию переменная x6 входит с коэффицентом ноль (т.е. не входит). Получаем: Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0. Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6). Вычисляем оценки разложений векторов условий по базису опорного решения по формуле: Δk = CбXk — ck Где: Cб = (с1, с2, ... , сm ) — вектор коэффициентов целевой функции при базисных переменных Xk = (x1k, x2k, ... , xmk ) — вектор разложения соответствующего вектора Ак по базису опорного решения Ск — коэффициент целевой функции при переменной хк. Оценки векторов входящих в базис всегда равны нулю. Опорное решение, коэффиценты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу: Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце "Б" записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов соответствует номерам разрешенных неизвестных в уравнениях ограничениях. Во втором столбце таблицы "Сб" записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце "Сб" оценки единичных векторов, входящих в базис, всегда равных нулю. В последней строке таблицы с оценками Δk в столбце "А0" записываются значения целевой функции на опорном решении Z(X1). Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ1 = -2, Δ3= -9 для векторов А1 и А3 отрицательные. По теореме об улучшении опорного решения, если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше. Определим, введение какого из двух векторов приведет к большему приращению целевой функции. Приращение целевой функции находится по формуле: . Вычисляем значения параметра θ01 для первого и третьего столбцов по формуле: Получаем θ01 = 6 при l = 1, θ03 = 3 при l = 1 (таблица 26.1). Находим приращение целевой функции при введении в базис первого вектора ΔZ1 = — 6*(- 2) = 12, и третьего вектора ΔZ3 = — 3*(- 9) = 27. Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ03 достигается в первой строке (l = 1). Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2) Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения. Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3). Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2. Ответ:max Z(X) = 201 при Х = (0,7,10,0,63). Вопрос 5. Экономико-математические модели. Исследование операций – научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами. Операцией называется совокупность взаимосогласованных действий, направленных на достижение вполне определенной цели. Оперирующей стороной называются определенные лица и коллективы, объединенные организационным руководством и активно стремящиеся к достижению поставленной цели. Стратегиями оперирующей стороны в данной операции называются допустимые способы расходования ею имеющихся активных средств. Здесь слово ”допустимые” следует понимать как «не выходящие за пределы технических, организационных, физических возможностей». Среди допустимых обычно находятся и оптимальные стратегии, превосходящие остальные по каким-либо признакам. Оптимальные (от латинского optimus – наилучший) стратегии должны представлять первоочередной интерес для оперирующей стороны. Критерием эффективности операции называется показатель требуемого, ожидаемого, достигнутого соответствия между результатом предпринимаемых действий и целью операции. Важнейшей функцией критерия является сравнительная оценка различных стратегий до начала их реализации. Его используют также на завершающем этапе операции для характеристики полученных результатов. Как правило, интерес представляют стратегии, позволяющие достичь максимальных значений критерия. Состоянием операции в некоторый момент времени t называется совокупность ее характеристик, проявляющихся в этот момент и отражающих объективно сложившееся положение дел. Всякая операция представляет собой процесс, существующий во времени, проходящий различные этапы развития и завершающийся получением конечного результата, сопоставимого с исходной целью. Математической моделью операции называется формальные соотношения, устанавливающие связь принятого критерия эффективности с действующими факторами операции. Чтобы построить математическую модель, необходимо оценить количественно проявления рассматриваемых факторов и указать группы рассматриваемых параметров, формально представляющие эти факторы. Математические модели могут иметь вид формул, систем уравнений или неравенств, а также таблиц, числовых последовательностей, геометрических образов, отражающих зависимость между критерием эффективности операции и теми параметрами, которые представляют учтенные действующие факторы. Решением, связанным с выбранной математической моделью, называется конкретный набор значений управляемых параметров. Решение можно получить различным путем, с различной степенью точности, в различных предположениях свойств неуправляемых параметров, но независимо от этого оно должно рассматриваться лишь как вспомогательный материал, нуждающийся в осмыслении и сопоставлениях. Определение задачи линейного программирования (ЗЛП), общая, симметричная и каноническая формы записи задачи линейного программирования Определение 1. Задача, в которой требуется найти экстремум функции при ограничениях:     , называется общей задачей линейного программирования (ЗЛП). Задача в краткой записи имеет вид , Определение 2. Задача, в которой требуется найти экстремум функции при ограничениях: , называется задачей линейного программирования, заданной в канонической форме. Определение 3. Задача, в которой требуется найти экстремум функции при ограничениях: , называется задачей линейного программирования заданной в симметричной форме записи. Определение 4. Функция называется целевой функцией ЗЛП. Определение 5. Совокупность чисел  удовлетворяющая ограничениям ЗЛП, называется допустимым решением ЗЛП. Определение 6. Допустимое решение, при котором целевая функция принимает максимальное (минимальное) значение, называется оптимальным решением ЗЛП. Переход от одной формы ЗЛП к другой Переход от неканонической формы ЗЛП к канонической. Теорема 1. Каждому решению  неравенства  соответствует единственное решение  уравнения  и неравенства , и наоборот. Из теоремы следует, что неравенство  можно заменить уравнением  и неравенством . Переменную  называют балансовой переменной. Следовательно, чтобы привести задачу к каноническому виду, нужно заменить каждое неравенство системы ограничений соответствующим уравнением и неравенством , введя в каждое неравенство балансовую переменную с коэффициентом +1, если знак неравенства £, и с коэффициентом -1, если знак неравенства ³. В целевую функцию балансовые переменные вводятся с нулевыми коэффициентами. Если на переменную  не наложено условие на неотрицательность, то эту переменную надо представить в виде разности двух неотрицательных переменных: , где   Переход от канонической формы ЗЛП к симметричной форме. Чтобы перейти от канонической формы ЗЛП к симметричной, нужно найти общее решение системы уравнений: Так как все переменные должны быть неотрицательными, в том числе и базисные, получим систему неравенств: Чтобы исключить базисные переменные из целевой функции, необходимо в целевую функцию вместо базисных переменных подставить их выражения через свободные переменные. Пример 1. Дана ЗЛП: найти наибольшее значение функции  при ограничениях: . Приведем ее к каноническому виду. Канонический вид задачи: найти наибольшее значение функции  при ограничениях: . Пример 2. Перейти от канонического вида задачи к симметричному. Найти наибольшее значение функции  при ограничениях: . Разрешим систему относительно произвольного базиса, система примет вид И так как , отбросив базисные переменные, получим систему неравенств Выразим целевую функцию через свободные переменные: Симметричный вид задачи: найти наибольшее значение функции  при ограничениях: . Математические модели экономических задач Задача об оптимальном использовании ресурсов Предприятие может выпускать определенные виды продукции, используя для этого различные виды ресурсов. Известны затраты каждого вида ресурса на производство единицы каждого вида продукции и прибыль от реализации единицы каждого вида продукции. Требуется составить план выпуска продукции, чтобы при данных запасах ресурсов получить максимальную прибыль. Составим математическую модель данной задачи. Введем обозначения: i - номер i-го вида ресурса, ; bi - запасы i-го вида ресурса, ; j - номер j-го вида продукции, ; aij - затраты i-го вида ресурса на производство единицы j-го вида продукции; cj - прибыль от реализации единицы j-го вида продукции. Все данные занесем в таблицу:   Виды продукции Виды ресурсов 1    2    …     j     …      n Запасы ресурсов 1 2 … i … m a11   a12   …   a1j   …   a1n a21    a22    …   a2j   …   a2n … ai1     ai2   …   aij   …   ain … am1    am2   …   amj   …   amn b1 b2 … bi … bm Прибыль от реализации единицы продукции c1     c2     …    cj    …    cn   Обозначим через xj - планируемый выпуск j-го вида продукции; - план выпуска продукции. Тогда прибыль от реализации всей выпускаемой продукции составит c1x1 + c2x2 +…+cjxj +…+cnxn. Составим ограничения по ресурсам. Найдем расход первого вида ресурса: a11x1+a12x2+…+a1jхj +…+a1nxn. Первый вид ресурса имеется в наличии b1 условных единиц, т.е. получаем ограничение a11x1+a12x2+…+a1jxj +…+a1nxn  b1. Аналогично составляем ограничения по всем остальным видам ресурсов. Кроме того, xj  0, , так как количество продукции не может быть отрицательным числом. Получим ЗЛП: найти наибольшее значение функции при ограничениях: , Таким образом, математической моделью данной задачи является ЗЛП. Задача о диете В продаже имеются различные виды продуктов. Известны содержания питательных веществ в единице каждого вида продукта, цена продуктов, медицинские требования на содержание питательных веществ в суточной диете. Требуется определить, какие продукты и в каком количестве нужно включить в диету, чтобы она соответствовала всем медицинским требованиям и чтобы стоимость диеты была минимальной. Составим математическую модель данной задачи. Введем обозначения: j - номер j-го продукта, ; i - номер i-го питательного вещества, ; aij -содержание i-го питательного вещества в единице j-го продукта; bi - минимальное содержание i-го питательного вещества в суточной диете; cj - цена единицы j-го продукта. Все данные занесем в таблицу: Виды продуктов Виды питательных веществ 1     2     …     j     …     n Медицинские требования к диете 1 2 … i … m a11     a12   …   a1j   …   a1n a21     a22   …   a2j   …   a2n … ai1     ai2   …   aij   …   ain … am1      am2   …   amj   …   amn b1 b2 … bi … bm Цена единицы продукта c1     c2    …    cj    …    cn Пусть xj единиц j-го продукта включается в суточную диету, тогда - суточная диета. Цена диеты: c1x1 + c2x2 +…+cnxn. Если в диету включаем x1, x2, …, xn единиц каждого продукта, то содержание первого питательного вещества в диете составит a11x1+a12x2+…+a1jxj +…+a1nxn, и это должно быть не менее чем b1 единиц, т.е. получаем неравенство a11x1+a12x2+…+a1jxj +…+a1nxn  b1. Аналогично составляем ограничения по всем видам питательных веществ. Кроме того, xj  0, так как количество продуктов не может быть отрицательным числом. Математическая модель задачи: найти минимум функции при ограничениях: , Таким образом, математической моделью данной задачи является ЗЛП.   Задача на оптимальный раскрой материала (по длине) Имеются прутки одинаковой длины, из которых нужно нарезать определенное количество заготовок заданной длины. Прутки можно нарезать на заготовки по различным вариантам. При каждом варианте нарезания прутков остаются концевые отрезки. Требуется определить, какое количество прутков следует разрезать по каждому варианту, чтобы получить заданное количество заготовок различной длины и чтобы общая длина концевых отрезков была минимальной. Составим математическую модель данной задачи. Введем обозначения: i - номер i-го вида заготовки, ; j - номер j-го варианта раскроя прутка, ; aij - количество заготовок i-го вида, получаемых из одного прутка, разрезаемого по j-му варианту; bi  - требуемое число заготовок i-го вида; cj - длина концевого отрезка, оставшегося от одного прутка при разрезании прутка по j-му варианту. Все данные занесем в таблицу: Варианты                     Раскроя Виды заготовок         1     2     …     j     …     n   План по заготовкам 1 2 … i … m a11    a12   …   a1j   …   a1n a21    a22   …   a2j   …   a2n … ai1    ai2   …   aij   …   ain … am1    am2   …   amj   …   amn b1 b2 … bi … bm Длина концевого отрезка c1     c2     …     cj     …     cn   Обозначим через хj - число прутков, разрезаемых по j-му варианту, тогда - план раскроя прутков. Найдем общую длину концевых отрезков. По первому варианту планируем разрезать x1 прутков, концевой отрезок от одного прутка будет иметь длину с1, тогда общая длина концевых отрезков от х1 прутков составит c1x1. Аналогично, общая длина концевых отрезков от х2 прутков, разрезанных по второму варианту, будет равна c2x2 и т.д. Следовательно, общая длина концевых отрезков при разрезании прутков по всем вариантам . Составим ограничения по заготовкам. Заготовок первого вида получают из одного прутка, разрезаемого по первому варианту, a11 штук, а из x1 прутков - a11x1; по второму варианту из одного прутка получают a12 штук, а из x2 прутков - a12x2 и т.д., по n-му варианту - a1nxn штук. Отсюда получаем первое ограничение a11x1+a12x2+…+a1nxn = b1. Аналогично получаем ограничения по всем заготовкам. Кроме того,  так как число прутков не может быть отрицательным. Математическая модель задачи: найти наименьшее значение функции при ограничениях: , Таким образом, математической моделью данной задачи является ЗЛП. Пример 1. Имеются прутки длиной 1 м. Требуется нарезать 200 заготовок длиной 25 см, 250 заготовок длиной 30 см и 150 заготовок длиной 35 см. Количество заготовок, которые можно нарезать из одного прутка по различным вариантам, а также длина концевых отрезков даны в таблице: Варианты    раскроя Виды заготовок 1 2 3 4 5 6 7 8 9 План на заготовки 1 ( 25 см) 4 1 1 2 2 1 200 2 ( 30 см) 3 1 1 1 2 2 250 3 (35 см) 2 2 1 1 1 150 Длина концевого отрезка, см 10 5 10 20 15 5 15   Требуется определить, сколько прутков необходимо разрезать по каждому варианту, чтобы выполнить план по заготовкам и чтобы общая длина концевых отрезков была минимальной. Составим математическую модель задачи. Пусть xj - количество прутков, разрезанных по j-му варианту, , тогда  - план раскроя. Найдем общую длину концевых отрезков, для этого длину концевого отрезка, оставшегося от одного прутка, умножим на количество прутков, разрезаемых по данному варианту. Получим 0х1+10х2+0х3+5х4+10х5+20х6+15х7+5х8+15х9. Тогда целевая функция запишется так: . Составим ограничения по заготовкам, для этого количество заготовок, полученных из одного прутка, умножим на число прутков, разрезаемых по данному варианту, т.е. 4х1     +х4+х5+2х6+2х7+х9, а всего заготовок первого вида требуется 200 штук. Получим уравнение 4х1     +х4+х5+2х6+2х7+х9 = 200. Аналогично получим ограничения по второму и третьему виду заготовок: 3х2+х3             +х5+х6         +2х8+2х9 =250, 2х3+2х4 +х5           +х7 +х8           = 150. Кроме того, , так как число прутков не может быть отрицательным. Математическая модель задачи: найти наименьшее значение функции при ограничениях: . Пример 2. Для производства двух видов продукции используется три вида сырья. Расход сырья на производство единицы каждого вида продукции, запасы, а также прибыль от реализации единиц каждого вида сырья заданы в таблице:     Виды Виды                           продукции сырья 1          2 Запасы сырья, кг 1 2 3 3               8 4               5 9         4 240 200 360 Прибыль от реализации единицы продукции, у.е. 2         3   Составить план выпуска продукции, дающий максимальную прибыль. Для этого составим математическую модель задачи: обозначим через х1, х2 - планируемый выпуск продукции. Найдем прибыль: 2х1 (у.е.) - это прибыль от х1 единиц первого вида продукции и 3х2 ( у.е.) - прибыль от х2 единиц второго вида продукции, а всего 2х1+3х2 - прибыль от реализации х1 единиц первого вида продукции и х2 единиц второго вида продукции. Составим ограничение по первому виду сырья: 3х1+8х2 - расход первого вида сырья на выпуск х1 единиц первого вида продукции и х2 единиц второго вида продукции, а всего первого вида сырья имеется 240, следовательно, получим неравенство 3х1+8х2  240. Аналогично, по второму и третьему видам сырья: 4х1+5х2  200, 9х1+4х2  360. Кроме того, х1 0, х2 0, так как количество выпускаемой продукции не может быть отрицательным числом. Математическая модель задачи: найти наибольшее значение функции при ограничениях: х1 0, х2 0. Графический метод и симплекс-метод решения задач линейного программирования. Графический метод решения ЗЛП Графическим методом можно решать задачи, заданные в неканоническом виде с двумя переменными или сводящиеся к ним. Рассмотрим задачу следующего вида: найти экстремум функции при ограничениях: х1>0, х2>0. Надо построить область допустимых решений системы ограничений. При этом возможны случаи: 1)   область допустимых решений - пустое множество; 2)   область допустимых решений - единственная точка; 3)   область допустимых решений - выпуклый многоугольник; 4)   область допустимых решений - выпуклая неограниченная область. В первом случае ЗЛП не имеет оптимального решения из-за несовместности системы ограничений. Во втором случае - это единственное решение и будет оптимальным решением. В третьем случае, чтобы найти оптимальное решение задачи, можно найти координаты всех угловых точек многоугольника, вычислить значения целевой функции во всех угловых точках. Наибольшее из этих значений и будет максимальным значением целевой функции, а наименьшее - минимальным, а координаты соответствующей угловой точки - оптимальным решением. Существует другой способ, который позволяет графически сразу найти угловую точку, соответствующую оптимальному решению. Пусть с0 - некоторое число. Прямая  является линией уровня целевой функции. В каждой точке этой прямой целевая функция принимает одно и то же значение, равное с0. Вектор - градиент целевой функции перпендикулярен к линиям уровня и показывает направление, в котором эта функция возрастает с наибольшей скоростью. Выбирая из линий уровня, проходящих через область допустимых решений, наиболее удаленную в направлениях вектора  (в случае минимизации - в противоположном направлении), определим угловую точку, в которой целевая функция принимает максимальное (минимальное) значение. Если экстремум достигается в двух угловых точках, то, по теореме об альтернативном оптимуме, оптимальным решением будет любая точка отрезка, соединяющего эти точки: , . В четвертом случае, когда область допустимых решений системы ограничений задачи неограниченная выпуклая область, оптимальное решение находится аналогично описанному выше. В данном случае оптимальное решение может совпадать с одной угловой точкой, с двумя угловыми точками и оптимальное решение может и не существовать из-за неограниченности целевой функции сверху в задаче на максимум или снизу в задаче на минимум. Пример 1. Решить графически следующую задачу: , х1 >0, х2 >0. Построим область допустимых решений системы ограничений: Х2                    90                            40                      30 А                           В                                С                                    D Х1                                                 40   50         80                                                                            l2        l1                                                        l3                   Областью допустимых решений системы ограничений является выпуклый пятиугольник ОАВCD. Построим вектор  и линию уровня, перпендикулярную вектору . Наибольшее значение целевая функция достигает в угловой точке В. Найдем координаты точки В, для этого решим систему из уравнений первой и второй прямой. Решая систему, получим: , . Пример 2. Найти наибольшее и наименьшее значения функции при ограничениях: х1+х2 > 8, -5х1+2х2 < 10, х1-3х2 < 0, х1 >0, х2 >0 Построим ОДР. Областью допустимых решений системы ограничений является выпуклая многоугольная неограниченная область. Наименьшее значение целевой функции достигается в угловой точке А, а наибольшее значение функции найти нельзя, так как функция не ограничена сверху, т.е. max L = ∞. Найдем координаты точки А, для этого решим систему из уравнений первой и третьей прямой: х1+х2 = 8,                                  х1-3х2 =0 х1 = 6,                  х2 = 2. т.е. . Симплексный метод Симплексный метод, или метод последовательного улучшения решения, универсален, им можно решить любую ЗЛП. Пусть ЗЛП задана в канонической форме:                           (1)                (2)                                 (3) Разрешим систему уравнений (2) относительно неотрицательного базиса. Пусть система (2) при этом примет вид                                             (4) Получено опорное решение . .                                     (5) Исключим базисные переменные х1, х2, …,  хr из целевой функции, для этого умножим первое уравнение системы (4) на с1, второе на с2 и т.д., r-е уравнение умножим на сr и все это прибавим к целевой функции. Получим:                              (6) Определение 1. Выражение (6) называется приведенным выражением для целевой функции, коэффициенты при свободных переменных хr+1, …, хj, …, хn называются оценками и обозначаются D. .                                                 (7) Правая часть уравнения (6) , так как . Тогда уравнение (6) примет вид .                                                (8) Запишем систему (5) и выражение (8) в виде одной системы и перейдем ко второму опорному решению:      (9) . Допустим, что вместо xi в базис вводится свободная переменная xj. По правилу прямоугольника найдем значение целевой функции от второго опорного решения.                                                   (10) Сравним  и , так как  fi ³0,  hij > 0, то знак дроби  зависит от знака оценки Dj. 1)   Если Dj > 0, то . 2)   Если Dj < 0, то . 3)   Если Dj = 0, то . Отсюда получаем критерий оптимальности для ЗЛП на максимум: 1)   если все оценки Dj > 0, то найденное решение оптимальное; 2)   если среди оценок имеется хотя бы одно отрицательное число, то найденное решение не оптимально. Пусть Dj < 0, тогда если среди коэффициентов при хj есть хотя бы одно положительное число, хj можно ввести в базис и . Если Dj < 0 и все коэффициенты при хj hij < 0, то хj в базис ввести нельзя. Покажем, что  в этом случае равен бесконечности, для этого из системы (9) выпишем общее решение, всем свободным переменным, кроме хj, придадим значение, равное 0, получим                                                (11) .                                     (12)   Отсюда видно, что если хj придавать сколь угодно большие числовые значения, то решение, полученное из системы (11), будет допустимым, а значение целевой функции (12) будет неограниченно расти, т.е. при х → ∞ ; 3) предположим, что найдено оптимальное решение задачи, т.е. все оценки неотрицательны, и хотя бы одна из оценок свободных переменных равна нулю. Это говорит о наличии в задаче альтернативного оптимума. Если ввести в базис свободную переменную с нулевой оценкой, то получим второе опорное оптимальное решение, а значение целевой функции при этом не изменится. Если нулевых оценок свободных переменных окажется несколько, то введение в базис каждой из этих переменных приводит к получению различных опорных оптимальных решений. Тогда задача имеет множество оптимальных решений, каждое из которых является выпуклой линейной комбинацией опорных оптимальных решений. Алгоритм симплексного метода Решение задач линейного программирования симплексным методом предполагает следующие этапы: 1)   привести задачу к каноническому виду; 2)   найти неотрицательное базисное решение системы ограничений; 3)   найти оценки свободных переменных по формуле и записать полученные оценки в симплексную таблицу; проверить найденное опорное решение на оптимальность: если требуется найти максимум целевой функции, то: а) если все оценки Dj > 0 , то найденное решение оптимально и задача решена; б) если хотя бы одна оценка Dj < 0, а при соответствующей переменной хj нет ни одного положительного коэффициента, то задача не имеет оптимального решения из-за неограниченности целевой функции; в) если хотя бы одна оценка Dj < 0, а при соответствующей переменной хj есть хотя бы один положительный коэффициент, то найденное решение не оптимально и его можно улучшить. Если отрицательных оценок несколько, то в базис вводят переменную с наибольшей по абсолютной величине отрицательной оценкой; 4)   если выполняется случай в), то нужно перейти к следующему опорному решению; 5)   перейти к п. 3. Замечание 1. Критерием оптимальности для ЗЛП на минимум является неположительность оценок, т.е. все  Dj < 0, . Замечание 2. В ЗЛП максимум и минимум целевой функции понимаются как глобальные. Пример 3. Найти наибольшее значение функции при ограничениях:   х1-2х2 - 2х3 +х4 - х5 = 1, -2х2 - х3 +3х4 + х5 = 5, х2 + 8х3+ х4 +3х5 = 20, . Задача задана в каноническом виде. Найдем исходное опорное решение. № п/п Б.п. х1 х2 х3 х4 х5 bi 1 2 3 x1 1 -2 -2 1 -2 -1 8 1 3 1 -1 2 3 1 5 20 1 2 3 x1   x2 1 1 14 15 8 3 5 1 5 8 3 41 45 20 1 2 3 x1 x5 x2 1 1 37/8 15/8 19/8 -1/8 5/8 -7/8 1 103/8 45/8 25/8 . Проверим это решение на оптимальность. № п/п сj Б.п. 1 1 -5 2 1 bi х1 х2 х3 х4 х5 1 2 3 1 1 1 x1 x5 x2 1 1 37/8 15/8 19/8 -1/8 5/8 -7/8 1 103/8 45/8 25/8 D j 111/8 -19/8 173/8 Найденное решение не оптимально, так как D4 < 0. Введем в базис свободную переменную с отрицательной оценкой х4 . № п/п сj Б.п. 1 1 -5 2 1 bi х1 х2 х3 х4 х5 1 2 3 1 2 1 x1 x4 x2 1 1 5 3 5 1 1/5 8/5 7/5 14 9 11 D j 21 19/5 43 . Так как среди оценок нет отрицательных чисел, то второе опорное решение оптимально. , .   Метод искусственного базиса При решении задач линейного программирования симплексным методом необходимо систему ограничений привести к единичному неотрицательному базису. Метод искусственного базиса дает возможность решать задачи без предварительного нахождения опорного решения.   Дана задача: найти наибольшее значение функции при ограничениях:   . Составим расширенную задачу, которую назовем М-задачей. Найти наибольшее значение функции при ограничениях:     . В каждое уравнение, в котором нет базисной переменной, вводим переменную , где , с коэффициентом 1, эти переменные называются искусственными, и они образуют искусственный базис. Искусственные переменные вводятся в целевую функцию с коэффициентами -М, если задача решается на максимум, и +М, если задача решается на минимум, где М сколь угодно большое положительное число. Система ограничений расширенной задачи совместна. Исходное опорное решение  где  , . Между допустимыми решениями исходной и М-задачи есть связь. Если  - допустимое решение М-задачи, то  - допустимое решение исходной задачи, причем . Эти решения называются соответствующими. Теорема. 1. Если в оптимальном решении М-задачи  все искусственные переменные равны 0, то соответствующее ему решение  является оптимальным решением исходной задачи. 2. Если в оптимальном решении М-задачи хотя бы одна из искусственных переменных не равна 0, то система ограничений исходной задачи несовместна. 3. Если М-задача не имеет оптимального решения, то и исходная задача также не имеет оптимального решения.   Алгоритм метода искусственного базиса 1.  Задачу линейного программирования привести к каноническому виду. 2.  Построить М-задачу. 3.  Решить М-задачу симплексным методом, при этом оценки свободных переменных находятся по формуле . Они состоят из двух слагаемых, одно из которых содержит М. Поэтому их будем записывать в двух строках и 4.  Применяя теорему о связи между оптимальными решениями М-задачи и исходной задачи, даем ответ исходной задачи: а) если в оптимальном решении М-задачи все искусственные переменные равны 0, то соответствующее решение исходной задачи является оптимальным и экстремумы целевых функций равны; б) если в оптимальном решении М-задачи хотя бы одна из искусственных переменных не равна 0, то исходная задача не имеет оптимального решения из-за несовместности системы ограничений; в) если М-задача не имеет оптимального решения, то исходная задача также не имеет оптимального решения. Целочисленное программирование   В некоторых экономических задачах (например, при определении оптимального выпуска машин, агрегатов, размещения оборудования) переменные характеризуют физически неделимые единицы и поэтому должны принимать только целые значения. Формулировка задачи целочисленного программирования: найти наибольшее значение функции при ограничениях: , ,  хj - целые, . Если k=n, то задача полностью целочисленная. Если k не равно n, то задача является частично целочисленной. Методы решения задач линейного программирования не гарантируют целочисленности решения. Иногда задачи целочисленного программирования решают приближенно. Отбросив условие целочисленности, решают задачу методом линейного программирования, затем в полученном оптимальном решении округляют переменные до целых чисел. Такой прием можно использовать, если значения переменных достаточно велики и погрешностью округления можно пренебречь. Если значения переменных невелики, то округление может привести к значительному расхождению с оптимальным решением. Существует аналитический метод решения полностью целочисленных задач - метод Гомори. Метод Гомори Основная идея решения целочисленных задач, первоначально предложенная Данцигом, Фулкерсоном и Джонсоном, заключается в том, что задача сначала решается без ограничения целочисленности. Если решение получается целочисленным, то задача решена, если нет, то к задаче присоединяют новое дополнительное ограничение, которое называют сечением. Получают новую задачу, для которой множество допустимых решений будет меньше, чем для исходной задачи, но будет содержать все допустимые целочисленные решения. Дополнительное ограничение отсекает часть области, содержащую нецелочисленное оптимальное решение. Вновь полученную задачу решают методом линейного программирования. Процесс построения сечений и решения задачи повторяется до получения целочисленного оптимального решения. Общий систематический способ построения сечений разработал Гомори в 1958 г.   Алгоритм метода Гомори Пусть дана полностью целочисленная задача линейного программирования: найти максимальное значение функции при ограничениях: , ,  хj - целые, . 1)           Отбросив условие целочисленности, решаем исходную задачу симплексным методом. Если получится целочисленное оптимальное решение, то задача решена. Если в оптимальном решении не все переменные целочисленны, то строим сечения. 2)           Пусть в оптимальном решении переменная xt - дробное число, т.е. xt=ft. Рассмотрим уравнение, в котором xt - базисная переменная. ,                             (1) где J - множество индексов свободных переменных. Разобьем все коэффициенты и свободный член (1) на два слагаемых: целую и дробную часть. Целой частью числа а называется наибольшее целое число, не превышающее а. Дробной частью числа а называется разность между числом а и его целой частью. Целую часть числа обозначим [а], а дробную часть – {а}, т.е. а = [а]+{а}. Тогда уравнение (1) примет вид ,                           (2) или . Для любого целочисленного решения задачи левая часть уравнения (2) есть целое число, следовательно, и правая часть также будет целым числом. Неравенство                                       (3) является сечением Гомори. Покажем, что любое целочисленное решение задачи удовлетворяет этому неравенству, а нецелочисленное решение ему не удовлетворяет. Пусть  - целочисленное решение, и предположим, что оно не удовлетворяет неравенству (3), т.е. , или по условию lj > 0, , отсюда , кроме того, . Получим , или , т.е. является дробным числом. Подставив  в уравнение (2), получим . Правая часть уравнения - дробное число, а левая часть - целое число. Получили противоречие. Следовательно, любое целочисленное решение задачи удовлетворяет неравенству (3). Покажем, что нецелочисленное оптимальное решение не удовлетворяет неравенству (3). Пусть  - нецелочисленное оптимальное решение задачи. Подставим его в неравенство (3): , но Следовательно,  не удовлетворяет неравенству (3). 3)           Присоединяя неравенство (3) к ранее решенной задаче, получим новую задачу линейного программирования, которую вновь решаем симплексным методом; если ее оптимальное решение окажется целочисленным, то оно и будет оптимальным решением исходной задачи. Если снова получится нецелочисленное решение, то строим новое сечение, и т.д. Замечание. Если в оптимальном решении несколько переменных нецелочисленные, то сечение строят по базисной переменной, имеющей наибольшую дробную часть. Пример. Найти наибольшее значение функции при ограничениях: х1 > 0, х2 > 0, х1, х2 - целые. Решим задачу симплексным методом без учета целочисленности, для этого приведем ее к каноническому виду хj > 0, . № п/п сj Б.п. 2 2   x1 x2 x3 x4 bi 1 2 x4 x5 2 -1 -1 2 1 1 7 3 Dj -2 -2 1 2 2 x1 x4 1 -1/2 3/2 1/2 1/2 1 7/2 13/2 Dj -3 1 7 1 2 2 2 x1 x2 1 1 2/3 1/3 1/3 2/3 17/3 13/3 Dj 2 2 20  max L = 20. Решение нецелочисленное, поэтому строим сечение Гомори. Возьмем первое уравнение из последней симплексной таблицы, так как у х1 наибольшая дробная часть . . Сечение примет вид  или , где  х5>0. Присоединив это дополнительное ограничение к ограничениям последней симплексной таблицы, получим новую задачу: Решим эту задачу симплексным методом. № п/п сj Б.п. 2 2   x1 x2 x3 x4 х5 bi 1 2 3 2 2 х1 x2 1 1 2/3 1/3 2/3 1/3 2/3 1/3 -1 17/3 13/3 2/3 1 2 3 2 2 x1 x2 х3 1 1 1 1/2 1/2 1 1/2 -3/2 5 4 1 Dj 1 3 18  max L = 18. Это решение целочисленное, значит исходная задача решена. max L = 18, . Дадим геометрическую иллюстрацию метода Гомори. Областью допустимых решений является четырехугольник ОАВС. Оптимальное решение задачи совпадает с точкой . Построили сечение х1 < 5, оно отсекает нецелочисленное оптимальное решение. Получили область допустимых решений ОАDЕС. Оптимально решение второй задачи будет в точке D (5, 4). Решение получилось целочисленным, следовательно, исходная задача решена.