DM2-pilot2018/2019 — различия между версиями
Vyalyi (обсуждение | вклад) |
Vyalyi (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
====Домашние задания==== | ====Домашние задания==== | ||
| + | |||
| + | '''[https://www.dropbox.com/s/r6tr70f61qk98nm/hw03DM2-pilot.pdf?dl=0 Домашнее задание 3]''' 171 группа - 15 октября; 172 группа - 19 октября | ||
'''[https://www.dropbox.com/s/bbtlhaqxykagxz5/hw02DM2-pilot.pdf?dl=0 Домашнее задание 2]''' 171 группа - 1 октября; 172 группа - 5 октября | '''[https://www.dropbox.com/s/bbtlhaqxykagxz5/hw02DM2-pilot.pdf?dl=0 Домашнее задание 2]''' 171 группа - 1 октября; 172 группа - 5 октября | ||
| Строка 44: | Строка 46: | ||
====Лекции ==== | ====Лекции ==== | ||
| + | |||
| + | '''1 октября''' Введение в симплекс-метод. Грани полиэдров, размерности граней. Грани - множества оптитмальных решений задач ЛП на полиэдре. Общая схема симплекс-метода. Локальное улучшение целевой функции. Критерий оптимальности текущего решения. | ||
'''24 сентября''' Соотношения дополняющей нежесткости. Приложения двойственности ЛП. Задача о максимальном потоке. Теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесия в смешанных стратегиях. | '''24 сентября''' Соотношения дополняющей нежесткости. Приложения двойственности ЛП. Задача о максимальном потоке. Теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесия в смешанных стратегиях. | ||
| Строка 56: | Строка 60: | ||
==== Семинары ==== | ==== Семинары ==== | ||
| − | '''[https://www.dropbox.com/s/ionttln4a8d1d0e/cw04DM2-pilot.pdf?dl=0 Задачи | + | '''[https://www.dropbox.com/s/rf0lzj34plglplo/cw05DM2-pilot.pdf?dl=0 Задачи к 5 семинару]''' |
| + | |||
| + | '''[https://www.dropbox.com/s/ionttln4a8d1d0e/cw04DM2-pilot.pdf?dl=0 Задачи к 4 семинару]''' | ||
'''[https://www.dropbox.com/s/comqfj5ezfzri7a/cw03DM2-pilot.pdf?dl=0 Задачи ко третьему семинару]''' | '''[https://www.dropbox.com/s/comqfj5ezfzri7a/cw03DM2-pilot.pdf?dl=0 Задачи ко третьему семинару]''' | ||
Версия 20:50, 1 октября 2018
Содержание
Дискретная математика на 2-ом курсе ПМИ (пилотный поток)
Лекции проходят по понедельникам в аудитории 205 в 9:00-10:20. Первая лекция 3 сентября.
Лектор:
М.Н. Вялый vyalyi@gmail.com
Семинаристы:
171 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Гайдамашко Даниил Олегович, dogaydamashko@edu.hse.ru
172 Козачинский Александр Николаевич, kozlach@mail.ru, группа в телеграме для вопросов, ассистент Ракитин Денис Романович, drrakitin@edu.hse.ru
Ссылки
Информация о курсе ДМ-2 (правила оценивания)
Конспект лекций о методе резолюций
Консультации
171 группа: М.Вялый по вторникам 15:10-16:40, ком. 219. Первая консультация 11 сентября.
172 группа: Козачинский по понедельникам 13:40-15:00, ком. 617.
Материалы занятий
Домашние задания
Домашнее задание 3 171 группа - 15 октября; 172 группа - 19 октября
Домашнее задание 2 171 группа - 1 октября; 172 группа - 5 октября
Домашнее задание 1 Сроки выполнения: 171 группа - к 17 сентября, 172 группа - к 21 сентября, защита к 26 октября.
Лекции
1 октября Введение в симплекс-метод. Грани полиэдров, размерности граней. Грани - множества оптитмальных решений задач ЛП на полиэдре. Общая схема симплекс-метода. Локальное улучшение целевой функции. Критерий оптимальности текущего решения.
24 сентября Соотношения дополняющей нежесткости. Приложения двойственности ЛП. Задача о максимальном потоке. Теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесия в смешанных стратегиях.
17 сентября Критерий совместности систем линейных неравенств и двойственность. Лемма Фаркаша и ее геометрический смысл. Конечно порожденные и полиэдральные конусы. Двойственная задача ЛП. Теорема двойственности в ЛП.
10 сентября Системы линейных неравенств. Метод исключения переменных Фурье-Моцкина. Геометрические приложения: проекция полиэдра - полиэдр, политоп (выпуклая оболочка конечного числа точек) - полиэдр. Критерий совместности системы линейных неравенств.
3 сентября Примеры задач линейного программирования: задача о составлении раствора, задача о назначениях, транспортная задача. Семантические и синтаксические следствия из систем линейных неравенств. Полиэдры и задача ЛП. Преобразования задач ЛП и систем неравенств. Канонические виды задач ЛП.
