- •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 стратегии.
1. Предмет и задачи курса. Экономико-математическая модель задачи линейного программирования. Пример.
Математическое программирование – дисциплина, занимающаяся изучением экстремальных задач (max/min), разработкой методов их решения.
Математическое программирование делится на задачи линейного и нелинейного программирования (целочисленное, выпуклое, динамическое, параметрическое). Многие инженерно-экономические задачи можно с достаточной степенью точности описать с помощью линейной целевой функции и системы линейных ограничений. Раздел, изучающий такие задачи, называется линейным программированием.
Этапы линейного программирования:
постановка задачи (словесная формулировка), формулировка условий задачи, выбор критериев оптимальность
сбор необходимых данных, составление исходной матрицы
построение экономико-математической модели
решение задачи одним из математических методов
анализ полученных результатов
Экономико-математическая модель.
Для производства 3 видов изделий (A,B,C) используется 3 вида различного сырья в количестве 180, 210, 244 единицы. Нормы затрат каждого вида сырья на производство единицы продукции данного вида приведены в таблице:
I |
4 |
2 |
1 |
II |
3 |
1 |
3 |
III |
1 |
2 |
5 |
Цена от реализации изделий:
A |
B |
C |
10 |
14 |
12 |
Определить план выпуска продукции, при котором прибыль максимальна. Составить математическую модель.
Решение: пусть предприятие производит x1 изделий вида А, x2 изделий вида B и x3 изделий вида С. Так как производство ограничено имеющимся сырьем и количеством изготовляемых изделий, то должны выписываться условия:
4х1+2х2+х3
3х1+х2+3х3
х1+2х2+5х3
все x0,
Z = 10x1+14x2+12x3 (max).
Методы решения:
графический (быстро и наглядно решает простейшие задачи)
симплекс-метод (универсальный метод)
метод потенциалов (им решаются транспортные задачи)
Необходим контроль, анализ решений, корректировка оптимального плана.
2. Общая постановка задачи линейного программирования. Каноническая форма задачи линейного программирования.
Найти совокупность значений x1, x2, … , xn, удовлетворяющим условию и доставляющим функции Z экстремальное значение.
n
∑aijxj (<=, =>,=)bi - ограничения (1,1)
i=1
xj=>0 - условия неотрицательности (1,2)
i=1,m
j=1,n
n
Z = ∑cjxj - целевая функция (1,3)
i=1
Совокупность значений переменных x1, x2, … , xn, удовлетворяющих условиям 1.1-1.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
все xi =>0, i=1,n j=1,m
Z=c1x1+c2x2+…+cnxn (max)
Приведение задачи к каноническому виду:
переход от ограничений-неравенств к ограничениям-равенствам (ограничение-неравенство вида сводится к ограничению-равенству добавлением к его левой части дополнительной (балансовой) неотрицательной переменной, а вида - вычитанием)
замена переменных, которые не подчинены условию неотрицательности
переход задачи min к max (Z = Z)