Предмет и задачи математического программирования. Экономические примеры. Постановка общей задачи МП.
Задача ЛП и различные формы ее мат. записи (общая, каноническая, симметричная). Преобразование одной формы записи ЗЛП в другую.
Целевая функция и ее свойства, интерпретация. Основные понятия планов: допустимый, базисный, оптимальный. Область допустимых решений задачи ЛП.
Графический метод решения ЗЛП.
Опорные планы ЗЛП. Соответствие между опорными планами и вершинами многогранника планов.
Основная теорема ЛП. Принципиальная схема решения ЗЛП, вытекающая из этой теоремы.
Симплексный метод решения ЗЛП. Общая идея симплекс-метода. Геометрическая иллюстрация.
Признак оптимальности опорного плана ЗЛП
Нахождение начального опорного плана ЗЛП.
Нахождение оптимального опорного плана ЗЛП
Признак неограниченности целевой функции на множестве планов и геометрическая иллюстрация.
Признак бесконечности множества оптимальных планов (альтернативный оптимум) и геометрическая иллюстрация.
Признак неразрешимости ЗЛП и геометрическая иллюстрация
Алгоритм симплекс-метода.
Понятие двойственности в ЛП. Симметричные двойственные задачи и их экономическая интерпретация. Двойственные оценки.
Несимметричные двойственные задачи. Связи между элементами моделей задач двойственной пары. Соответствие между переменными двойственных задач (двойственные переменные).
Теорема двойственности (основная теорема двойственности) и ее – экономическая интерпретация. Нахождение оптимального плана двойственной задачи по решению прямой.
Теорема об оценках и ее экономическая интерпретация
Свойства двойственных оценок и их применение при анализе решений ЗЛП.
Формулировка и математическая модель транспортной задачи по критерию стоимости. Особенности модели как ЗЛП.
Транспортная задача с открытой и закрытой моделью. Преобразование открытой модели в закрытую.
Условие разрешимости транспортной задачи. Условия целочисленности оптимального плана.
Теорема о ранге матрицы системы ограничительных уравнений транспортной задачи и ее прикладное значение.
Циклы в транспортной таблице. Свойства циклов.
Способы построения начального опорного плана транспортной задачи (северо-западного угла, наименьшего элемента, Фогеля).
Процедура преобразования опорного плана транспортной задачи в новый опорный план.
Оценка (характеристика) свободной клетки транспортной таблицы, ее вычисление и экономический смысл.
Признак оптимальности опорного плана транспортной задачи. Неединственность оптимального плана.
Потенциалы поставщиков и потребителей и их вычисление.
Связь между оценками свободных клеток, и потенциалами.
Алгоритм метода потенциалов.
Основное неравенство теории двойственности.
Теорема существования оптимальных планов пары двойственных задач.
Теорема о существовании плана транспортной задачи.
Теорема о ранге матрицы транспортной задачи.
Постановка и решение задачи об оптимальных назначениях.
Ассортиментно-распределительные задачи, постановка и решение.
Алгоритм построения опорного плана симплекс-методом. Привести пример.
Алгоритм построения оптимального плана симплекс-методом. Привести пример.
Теорема о выборе разрешающего элемента задачи, решаемой симплекс-методом.
Теорема об оптимальном плане задаче, решаемой симплекс-методом.
Вырожденность и ее устранение при решении задач симплексным методом.
Случай бесчисленного множества оптимальных планов. Геометрическая иллюстрация.
Постановка и математическая модель задачи целочисленного линейного программирования. Идея решения задачи методом отсечений и его геометрическая иллюстрация.
Метод Гомори решения полностью целочисленной задачи ЛП.
Метод ветвей и границ решения целочисленных задач.
Понятие о динамическом программировании. Особенности решения задач. Принцип оптимальности Беллмана. Вычислительная схема метода динамического программирования
Задача о выборе кратчайшего пути на сети дорог и решение ее методом динамического программирования.
Задача об оптимальном распределении средств между предприятиями на расширение производства и решение ее методом динамического программирования.
Графический метод решения задач дробно-линейного программирования. Привести пример.
Постановка задачи НЛП. Понятие выпуклой и вогнутой функции
Графический метод решения задач НЛП.
Метод Лагранжа решения задач НЛП.
Градиентный метод решения задач НЛП.
Метод искусственного базиса решения задач линейного программирования симплексным методом.
Симплексный метод решения задач дробно-линейного программирования.
Постановка задачи параметрического линейного программирования. Симплексный метод решения параметрических задач.
Простая ссылка:
Html ссылка:
ВВ ссылка: