2015-05-14
304
1. Предмет прикладной математики в экономике. Этапы решения задач о принятии решений.
2. Примеры конкретных практических задач с экономическим содержанием и их математическая формулировка: задача о раскрое; задача о ресурсах; задача о диете; задача об инвестициях; транспортная задача, задача о загрузке оборудования.
3. Решение систем линейных уравнений методом полного исключения неизвестных (методом Жордана-Гаусса). Вывод формул пересчета коэффициентов системы. Базисные неизвестные. Свободные неизвестные. Общее решение. Частное, базисное решение. Геометрическая интерпретация базисного решения.
4. Разложение векторов по векторам базиса. Теорема о единственности разложения. Переход от одного базиса к другому.
5. Основная задача линейного программирования. План, оптимальный план.
6. Стандартная задача ЛП. Каноническая задача ЛП. Опорный план. Приведение основной задачи ЛП к каноническому виду.
7. Выпуклые множества. Внутренние, граничные, крайние (угловые) точки. Выпуклый многоугольник, многогранник, опорная плоскость.
8. Объединение множеств, пересечение множеств, лемма о пересечении выпуклых множеств.
9. Теорема о представлении выпуклого многогранника через угловые точки.
10. Геометрическая интерпретация задачи ЛП.
11. Теорема о выпуклости планов задачи ЛП.
12. Теорема о достижении оптимума в угловой точке многогранника решений. Альтернативный оптимум.
13. Теорема о соответствии угловой точки многогранника решений линейно независимой системе векторов.
14. Теорема о соответствии линейно независимой системы векторов угловой точке многогранника решений.
15. Графический метод решения стандартной задачи ЛП с двумя переменными.
16. Графический метод решения канонической задачи ЛП, где число переменных больше двух.
17. Идея симплекс-метода. Построение опорных планов. Вывод формулы пересчета коэффициентов.
18. Теорема о возможности улучшения плана для задачи на минимум. Критерий оптимальности.
19. Теорема о возможности улучшения плана для задачи на максимум. Критерий оптимальности.
20. Алгоритм симплекс-метода, алгебра симплекс-метода.
21. Составление первой симплекс-таблицы, переход к последующим, контроль за ведением таблиц.
22. Геометрический и экономический смысл симплекс-метода.
23. Поиск начального опорного плана методом искусственного базиса. Признак неразрешимости задачи ЛП.
24. Задачи со смешанными ограничениями и методы их решения.
25. Понятие о двойственных задачах ЛП. Примеры построения двойственных задач, имеющих экономическое содержание.
26. Основная задача ЛП и двойственная к ней (правила построения двойственных задач).
27. Несимметричные двойственные задачи. Первая теорема двойственности.
28. Вторая теорема двойственности. Условия дополняющей нежесткости.
29. Определение решения двойственной задачи, используя оптимальную симплекс-таблицу прямой задачи (по первой теореме двойственности).
30. Определение оптимального решения прямой задачи по решению двойственной, используя условия дополняющей нежесткости.
31. Общая постановка транспортной задачи по критерию стоимости и ее математическая модель. Допустимый план. Оптимальный план. Вырожденность. Закрытая транспортная задача. Открытая модель.
32. Теорема о допустимости и разрешимости закрытой транспортной задачи.
33. Теорема о ранге системы ограничений-уравнений закрытой транспортной задачи.
34. Определение цикла. Примеры построения циклов. Теорема о четности вершин в цикле. Означенный цикл. Цикл пересчета.
35. Методы построения начального плана транспортной задачи: «северо-западного угла», «минимального элемента», «двойного предпочтения», «метод Фогеля».
36. Критерий оптимальности транспортной задачи. Метод потенциалов (теоретическое обоснование).
37. Сетевая постановка транспортной задачи по критерию стоимости. Опорные планы. Требования, предъявляемые к опорному плану.
38. Метод потенциалов для транспортной задачи на сети. Вычисление потенциалов. Условия оптимальности. Переход от одного плана к другому.
39. Постановка задачи «о разборчивой невесте», ее математическая формулировка (запрет на многомужество, многоженство и однополые браки).
40. Метод потенциалов для задачи «о разборчивой невесте». Решение проблемы вырожденности. Критерий оптимальности.
41. Определение эквивалентности матриц. Теорема Эгервари.
42. Венгерский метод для решения задач о назначениях, «о разборчивой невесте».
43. Двойственный симплекс-метод. Правила выбора ведущего элемента.
44. Целочисленное программирование. Метод Гомори. Вывод формулы отсекающей гиперплоскости.
