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