Учебное пособие. — Л.: ВИКИ им. А.Ф. Можайского, 1989. — 87 с.: ил.
Учебное пособие посвящено изложению материала по теме лекции
«Линейное программирование» (раздел «Специальные главы математики»
по дисциплине «Высшая математика»).
В этом учебном пособии подробно описан метод разрешающих множителей и вытекающий из него симплекс-метод для решения задач линейного программирования (ЛП), приведенных к стандартной форме. Многие проблемы в экономике, технике и в других областях деятельности приводят к задачам ЛП, которые при учете особенностей задачи решаются более короткими путями (также на основе использования разрешающих множителей) по сравнению с теми, которые необходимо было бы пройти после приведения задачи к стандартной форме. Один из примеров такого учета особенностей — решение транспортной задачи, которая рассматривается без привлечения симплекс-метода. Учебное пособие содержит большое количество примеров решения задач, упражнений и рисунков, облегчающих понимание изложенного материала. Подробно излагается графический способ решения соответствующей задачи ЛП.
Учебное пособие написано замечательным советским и российским математиком, доктором физико-математических наук, профессором Хаимом Львовичем Смолицким — специалистом в области дифференциальных и интегральных уравнений, теории надежности и вычислительной математики. Постановка задачи линейного программирования (Общая задача математического программирования. Линейное программирование. Примеры проблем планирования производства, приводящих к задачам ЛП).
Общая форма задачи ЛП (Формулировка задачи в общей форме. Замечания).
Стандартная форма задачи ЛП (Расширенный план. Стандартная форма задачи ЛП).
Матричная запись задачи ЛП. Опорный план. Невырожденная задача (Определения, обозначения, матричная запись задачи ЛП. Активные и пассивные номера относительно плана X. Сжатые матрицы и векторы. Опорный план. Невырожденная задача ЛП. Упражнения).
Геометрический смысл задачи ЛП в случае n=3.
Графическое решение стандартной задачи в случае n=m+2 (Многоугольник планов. Опорные планы-вершины. Вырожденные задачи. Учет целевой функции. Оптимальные планы. Пример. Упражнения).
Двойственная (сопряженная) задача. Разрешающие множители (Определение двойственной (сопряженной) задачи. Соотношение между линейными формами основной и двойственной задачи. Разрешающие множители. Достаточное условие оптимальности плана основной задачи).
Необходимое условие оптимальности плана (Постановка вопроса. Существование разрешающего плана для оптимального плана. Графический способ решения задачи ЛП в случае m=2. Упражнения).
Признак неограниченности целевой функции. Переход к улучшенному опорному плану (Постановка вопроса. Признак неограниченности целевой функции. Переход к улучшенному опорному плану. Последовательность операций для решения задачи ЛП).
Симплекс-метод (Z-матрица, отвечающая опорному плану. Обработка Z-матрицы. Переход к улучшенному опорному плану. Упражнения).
Метод искусственного базиса: нахождения исходных опорного плана и Z-матрицы (Предварительная обработка системы уравнений. Вспомогательная задача. Анализ оптимального плана вспомогательной задачи. Упражнения).
Примеры (Первый пример. Второй пример).
Транспортная задача (Задание транспортной задачи. Матрица A. Опорные планы. Невырожденные задачи. Разрешающие множители (потенциалы). Контрольная таблица. Признак оптимальности опорного плана. Переход к улучшенному опорному плану. Метод северо-западного угла. Замечание о несбалансированной транспортной задаче. Упражнения).
Заключение.
Историческая справка.
Ответы
В этом учебном пособии подробно описан метод разрешающих множителей и вытекающий из него симплекс-метод для решения задач линейного программирования (ЛП), приведенных к стандартной форме. Многие проблемы в экономике, технике и в других областях деятельности приводят к задачам ЛП, которые при учете особенностей задачи решаются более короткими путями (также на основе использования разрешающих множителей) по сравнению с теми, которые необходимо было бы пройти после приведения задачи к стандартной форме. Один из примеров такого учета особенностей — решение транспортной задачи, которая рассматривается без привлечения симплекс-метода. Учебное пособие содержит большое количество примеров решения задач, упражнений и рисунков, облегчающих понимание изложенного материала. Подробно излагается графический способ решения соответствующей задачи ЛП.
Учебное пособие написано замечательным советским и российским математиком, доктором физико-математических наук, профессором Хаимом Львовичем Смолицким — специалистом в области дифференциальных и интегральных уравнений, теории надежности и вычислительной математики. Постановка задачи линейного программирования (Общая задача математического программирования. Линейное программирование. Примеры проблем планирования производства, приводящих к задачам ЛП).
Общая форма задачи ЛП (Формулировка задачи в общей форме. Замечания).
Стандартная форма задачи ЛП (Расширенный план. Стандартная форма задачи ЛП).
Матричная запись задачи ЛП. Опорный план. Невырожденная задача (Определения, обозначения, матричная запись задачи ЛП. Активные и пассивные номера относительно плана X. Сжатые матрицы и векторы. Опорный план. Невырожденная задача ЛП. Упражнения).
Геометрический смысл задачи ЛП в случае n=3.
Графическое решение стандартной задачи в случае n=m+2 (Многоугольник планов. Опорные планы-вершины. Вырожденные задачи. Учет целевой функции. Оптимальные планы. Пример. Упражнения).
Двойственная (сопряженная) задача. Разрешающие множители (Определение двойственной (сопряженной) задачи. Соотношение между линейными формами основной и двойственной задачи. Разрешающие множители. Достаточное условие оптимальности плана основной задачи).
Необходимое условие оптимальности плана (Постановка вопроса. Существование разрешающего плана для оптимального плана. Графический способ решения задачи ЛП в случае m=2. Упражнения).
Признак неограниченности целевой функции. Переход к улучшенному опорному плану (Постановка вопроса. Признак неограниченности целевой функции. Переход к улучшенному опорному плану. Последовательность операций для решения задачи ЛП).
Симплекс-метод (Z-матрица, отвечающая опорному плану. Обработка Z-матрицы. Переход к улучшенному опорному плану. Упражнения).
Метод искусственного базиса: нахождения исходных опорного плана и Z-матрицы (Предварительная обработка системы уравнений. Вспомогательная задача. Анализ оптимального плана вспомогательной задачи. Упражнения).
Примеры (Первый пример. Второй пример).
Транспортная задача (Задание транспортной задачи. Матрица A. Опорные планы. Невырожденные задачи. Разрешающие множители (потенциалы). Контрольная таблица. Признак оптимальности опорного плана. Переход к улучшенному опорному плану. Метод северо-западного угла. Замечание о несбалансированной транспортной задаче. Упражнения).
Заключение.
Историческая справка.
Ответы