DM2-pilot2017/2018 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 51: Строка 51:
  
 
====Лекции  ====
 
====Лекции  ====
 +
 +
'''02 октября'''  Введение в симплекс-метод. Итерации, направление улучшения целевой функции. Грани, опорная грань. Улучшение целевой функции вдоль грани. Критерий того, что целевая функция постоянна на опорной грани. Выбор направления итерации, когда целевая функция постоянна на опорной грани: невырожденный случай.
  
 
'''25 сентября''' Соотношения дополняющей нежесткости. Приложения двойственности ЛП: задача о максимальном потоке, двойственная к ней и теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесных стратегий и цены игры.  
 
'''25 сентября''' Соотношения дополняющей нежесткости. Приложения двойственности ЛП: задача о максимальном потоке, двойственная к ней и теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесных стратегий и цены игры.  

Версия 21:16, 2 октября 2017

Дискретная математика на 2-ом курсе ПМИ (пилотный поток)

Лекции проходят по понедельникам в аудитории 509 в 9:00-10:20. Первая лекция 4 сентября.

Лектор:

М.Н. Вялый vyalyi@gmail.com

Семинаристы:

161 Вялый Михаил Николаевич, vyalyi@gmail.com, ассистент Умаров Рустам, rustam.umarov96@gmail.com

162 Козачинский Александр Николаевич, kozlach@mail.ru, ассистент Стороженко Андрей Андреевич, storozhenkoaa@yandex.ru

Ссылки

Информация о курсе ДМ-2 (правила оценивания)

Литература по курсу ДМ-2

Записки по материалам курса.

Конспект лекций о линейном программировании для основного потока. Содержит только то, что рассказывалось или будет рассказано на лекциях основного потока. Зато в этом конспекте изложение по возможности упрощено и улучшено.

Конспект лекций о методе резолюций

Консультации

161 группа: М.Вялый по вторникам 15:10-16:40, ауд. 313. Возможны изменения! Следите за объявлениями.

161 группа: Р. Умаров по понедельникам, 15:10-16:30, ауд. 311.

162 группа: по вторникам 16:40 - 18:00 в ауд. 511 (Козачинский)

Материалы занятий

Домашние задания

Оценки за домашние задания (группа 162)

Оценки за домашние задания (группа 161)


Внимание: домашние задания нужно сдавать преподавателю перед началом семинара. Поэтому сроки сдачи домашних заданий теперь различаются в разных группах.

Домашнее задание 3 Срок выполнения: 161 группа к 16 октября; 162 группа к 17 октября (на листке написано неверно)

Домашнее задание 2 Срок выполнения: 161 группа ко 2 октября; 162 группа к 3 октября

Домашнее задание 1 Срок выполнения: к 18 сентября.

Лекции

02 октября Введение в симплекс-метод. Итерации, направление улучшения целевой функции. Грани, опорная грань. Улучшение целевой функции вдоль грани. Критерий того, что целевая функция постоянна на опорной грани. Выбор направления итерации, когда целевая функция постоянна на опорной грани: невырожденный случай.

25 сентября Соотношения дополняющей нежесткости. Приложения двойственности ЛП: задача о максимальном потоке, двойственная к ней и теорема Форда-Фалкерсона. Матричные игры с нулевой суммой. Существование равновесных стратегий и цены игры.

18 сентября Двойственность. Лемма Фаркаша. Конечно порожденные конусы и полиэдральные конусы - одно и то же. Двойственные задачи в ЛП. Теорема двойственности.

11 сентября Исключение переменной в системе линейных неравенств. Проекция полиэдра - полиэдр. Решение систем линейных неравенств и задачи ЛП методом исключения переменных. Достижимость максимума в задаче ЛП с ограниченной целевой функцией. Политопы. Политоп - это полиэдр. Синтаксические следствия линейных неравенств. Критерий совместности системы линейных неравенств.

4 сентября Примеры задач линейного программирования: задача о составлении раствора, задача о назначениях, транспортная задача. Полиэдры и задача ЛП. Преобразования задач ЛП и систем неравенств. Канонические виды задач ЛП.

Семинары

Задачи к семинару 25 сентября

Задачи к семинару 18 сентября

Задачи к семинару 11 сентября

Задачи к семинару 4 сентября