- •1. Предмет и задачи курса. Экономико-математическая модель задачи линейного программирования. Пример.
- •2. Общая постановка задачи линейного программирования. Каноническая форма задачи линейного программирования.
- •3. Система линейных алгебраических уравнений (слау). Метод Гаусса. Пример.
- •4. Матрицы.
- •5. Обратная матрица.
- •6. Неопределенная система лау. Базисные.
- •7. Множества. Выпуклые линейные комбинации.
- •8. Выпуклый n-мерный многогранник является выпуклой линейной комбинацией своих угловых точек.
- •9. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
- •10. Теорема об экстремальном значении целевой функции.
- •13. Нахождение исходного опорного решения.
- •14. Симплексный метод.
- •16. Приращение целевой функции
- •17, 18. Критерии оптимальности
- •19. Метод невязок.
- •20. Двойственные задачи.
- •24. Теоремы двойственности. Основное неравенство двойственности.
- •28. Теорема о ранге матрицы коэффициентов тз
- •29. Нахождение исходного опорного решения транспортной задачи
- •30. Переход к новому опорному решению тз
- •32. Метод потенциалов.
- •33. Теорема об эквивалентных преобразованиях матрицы затрат.
- •35. Оценка свободной клетки.
- •36. Критерий оптимальности. Переход к оценочной матрице.
- •37.Открытая модель транспортной задачи.
- •38. Распределительный метод
- •39. Постановка задачи цп.
- •40.Метод Гомори.
- •41. Понятие об игровых моделях
- •42. Приведение экономических задач к теоретико-игровой форме.
- •43. Парная конечная игра. Платежная матрица. Maxmin/minmax стратегии.
3. Система линейных алгебраических уравнений (слау). Метод Гаусса. Пример.
Система м линейных уравнений с н переменными имеет вид:
а11х1+ а12х2+ …+а1jхj+..+a1nxn=b1
а21х1+ а22х2+…+ а2jхj+..+a2nxn=b2
аi1х1+ аi2х2+…+ аijхj+..+ainxn=bi
аm1х1+ аm2х2+…+ аmjхj+..+amnxn=bm
где аij, bi (i=1,n j=1,m) - произвольные числа при переменных, называемые коэффициентами при переменных и свободныи членами уравнений.
В более краткой записи с помощью знаков суммирования систему можно записать:
n
∑aijxj =bi
j=1
Решение такой системы – это набор чисел, при подстановке которых в эту систему каждое уравнение превращается в тождество. Совместной СЛАУ называется такая система, которая имеет хотя бы одно решение. Если система решений не имеет, то она называется несовместной.
Метод Гаусса.
Метод последовательного исключения переменных заключается в том, что с помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого вида, из которой последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.
Ход решения
умножая 1-ое уравнение на подходящие числа и прбавляя полученные уравнения соответственно ко второму, третьему ,… m-му уравнению системы, исключим переменную х1 из всех последующих уравнений, начиная со второго.
Предположим что а22 <>0 умножая второе уравнение на подходящие числа и прибавляя полученные уравнения соответственно к третьему, четвертому,…, m-му уравнению системы, исключим переменную х2 из всех последующих уравнений, начиная с третьего.
4. Матрицы.
Матрицей размера м*н называется прямоугольная таблица чисел, содержащая м строк и н столбцов. Числа составляющие матрицу называются ее элементами.
Матрица состоящая из одной строки, называется матрицей (вектором) – строк, а из одного столбца – матрицей –столбцом
Матрица называется квадратной, если число ее строк = числу ее столбцов. Элементы матрицы, у которых номера столбца = номеру строки (i=j), называются диагональными и образуют главную диагональ матрицы. Если все недиоганальные элементы квадратной матрицы =0, то матрица назыв диагональной. Если у диагональной матрицы все диагональные элементы = 1, то матрица назыв единичной матрицей. Матрица любого порядка назыв нулевой, если все ее эл-ты = 0
Операции над матрицами.
Умножение матрицы на число. Все эл-ты матрицы умножаем на это число. Произведением матрицы А на число № назыв матрица В=№А.
Сложение матриц. Сумма 2х матриц одинакового размера назыв матрица С=А+В, эл-ты которой cij=aij+bij
Вычитание. А-В=А+(-1)*В
Умножение матриц. Умножение матрицы А на матрицу В определено, когда число столбцов 1ой матрицы =числу строк второй. Тогда произведением матриц А*В назыв такая матрица С, каждый элемент которой сij равен сумме произведений элементов i-ой строки матрицы А на соответствующие элементы j-го столбца матрицы В.
Транспонирование. Переход от матрицы А к матрице А’, в которой строки и столбцы поменялись местами с сохранением порядка.
Возведение в степень. Целой положительной степенью А в степени м (м>1)квадратной матрицы А называется произведение м матриц, равных А.
В матрице А размера m x n вычеркиванием каких-либо строк и столбцов можно вычленить квадратные подматрицы k-го порядка, где k≤min(m;n). Определители таких подматриц называются минорами k-го порядка матрицы А.
Ранг матрицы – наивысший порядок отличных от нуля миноров матрицы.