- •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 стратегии.
40.Метод Гомори.
Метод решения задачи, предложенный Гомори, основан на симплексном методе и состоит в следующем. Симплексным методом находится оптимальный план задачи без учета условия целочисленности. Если оптимальный план целочисленный, то вычисления заканчивают; если же оптимальный план содержит хотя бы одну дробную компоненту Xi, накладывают дополнительное ограничение, учитывающее целочисленность компонент плана, и вычисления симплексным методом продолжают до получения нового оптимального плана . Если и он является нецелочисленным, то составляют следующее ограничение, учитывающее целочисленность. Процесс присоединения дополнительных ограничений повторяют до тех пор, пока либо будет найден целочисленный оптимальный план, либо доказано, что задача не имеет целочисленных планов. Это наблюдается в случае, если для дробного Xi все Xij в этой строке окажутся целыми.
Недостатком метода Гомори является требование целочисленности для всех переменных: как основных, выражающих единицы продукции, так и для дополнительных, выражающих величину неиспользованных ресурсов, которые могут быть и дробными.
41. Понятие об игровых моделях
Если имеется несколько конфликтующих сторон, каждая из которых принимает некоторое решение, определяемое заданным набором правил, и каждой из этих сторон известно возможно конечное состояние конфликтной ситуации с заранее определенными для каждой из сторон платежами, то говорят, что имеет место игра. Ситуация называется конфликтной, если в ней участвуют стороны, интересы которых частично или полностью противоположны. Игра – это конфликт, в котором имеется по крайней мере два участника или игрока, каждый из которых стремится к достижению своих целей.
Задача теории игр состоит в выборе такой линии поведения игрока, отклонения от которой могут лишь уменьшить его выигрыш. При этом предполагается, что все игроки ведут себя рационально.
Допустимые действия каждого из игроков, направленные на достижение некоторых целей, называются правилами игры. Количественная оценка результатов игры называется платежом. Ход – это выбор игроком одного из действий, предусмотренных правилами игры. Ходы бывают личными и случайными. Однозначные описания выбора игрока в каждой из возможных ситуаций, при которой он должен сделать личный ход, называется стратегий игрока. Стратегия игрока называется оптимальной, если при многократном повторении игры она обеспечивает игроку максимальный возможный средний выигрыш.
Классификация игр.
1. Возможность образований коалиций.
Если правила игры разрешают объединение группы участников для получения ими лучших результатов по сравнению с теми, которых они бы добились, действуя самостоятельно, то такая игра называется кооперативной. В противной случае игра называется бескоалиционной или некооперативной.
2. По количеству стратегий.
Если у каждого игрока имеется в распоряжении конечное чило стратегий, то игра называется конченой, в противном случае - бесконечной.
3. По числу игроков.
В зависимости от числа участников они делятся на игры с двумя, тремя и более игроками. Игра с двумя игроками называется парной.
4. По свойствам выигрыша.
Игра называется игрой с нулевой суммой, если в любой партии сумма выигрышей всех игроков равна нулю, т.е. каждый игрок может выиграть лишь за счет проигрыша других игроков. Если это условие не выполнено, то такая игра называется игрой с ненулевой суммой. В парной игре с нулевой суммой выигрыш одного игрока всегда равен проигрышу другого. Такая игра называется антагонистической.
5. По количеству имеющейся априорной информации.
Различают игры с полной информацией о состоянии игры, о стратегиях действий сторон и о платежной матрице; игры с неполной (вероятностной) информацией о функциях выигрыша, о стратегиях сторон, об осведомленности сторон (каналах наблюдения); игры в условиях полной неопределенности.