Лекция: Использовании ресурсов
Взаимно двойственные задачи линейного программирования и их свойства
Вопросы для самопроверки
Задания для самостоятельной работы
Транспортная задача
Решение транспортной задачи
Определение начального решения
Нахождение вводимой в базис переменной
Нахождение выводимой из базиса переменной
Целочисленное линейное программирование
Задачи целочисленного линейного программирования
Метод ветвей и границ
Вопросы для самопроверки
Задания для самостоятельной работы
Метод отсечений (Гомори)
Вопросы для самопроверки
Задания для самостоятельной работы
Динамическое программирование
Задача динамического программирования
Метод решения задач динамического программирования
Решение задачи линейного программирования методом динамического
Программирования
Вопросы для самопроверки
Задания для самостоятельной работы
Нелинейное программирование
Задачи нелинейного программирования
Решение задачи нелинейного программирования методом множителей
Лагранжа
Вопросы для самопроверки
Задания для самостоятельной работы
Список литературы
Предисловие
Управление экономической системой реализуется как процесс, подчиняющийся определенным закономерностям. Их знание помогает определить условия, необходимые и достаточные для осуществления данного процесса. Для этого все параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. При решении конкретной задачи управления предполагается построение экономических и математических моделей и установление критериев эффективности, позволяющих оценивать преимущество того или иного варианта действия. Для применения количественных методов требуется построить математическую модель и количественно выразить критерий эффективности в виде целевой функции.
Математическое программирование включает методы нахождения экстремума (минимума или максимума) целевой функции, область определения которой задается некоторыми ограничениями.
Целевая функция – это экономический показатель, зависящий от некоторых факторов.
Ограничения задают область определения целевой функции с помощью выражений, определяющих диапазоны возможных изменений факторов.
Задачами математического программирования являются оптимизационные математические модели, состоящие из целевой функции от некоторых переменных и ограничений, представляемых выражениями от тех же переменных.
Будем рассматривать класс оптимизационных моделей. Такие задачи возникают при попытке оптимизировать планирование и управление сложными системами, в первую очередь экономическими системами. Оптимизационную задачу можно сформулировать в общем виде: найти переменные удовлетворяющие системе неравенств (уравнений).
(1)
и обращающие в максимум (или минимум) целевую функцию, т.е.
(2)
(Условия неотрицательности переменных, если они есть, входят в ограничения (1) ).
Оптимальным решением задачи математического программирования является соответствующий вектору переменных целевой функции и ограничений вектор чисел, для которого выполняются все ограничения, а целевая функция принимает требуемое экстремальное значение.
Как известно, упорядоченная совокупность значений переменных представляется точкой — мерного пространства. В дальнейшем такую точку будем обозначать а само оптимальное решение
В тех случаях, когда функции и в задаче (1) – (2) хотя бы дважды дифференцируемы, можно применять классические методы оптимизации. Однако применение этих методов весьма ограничено, так как задача определения условного экстремума функции переменных технически весьма трудна: метод дает возможность определить локальный экстремум, а из-за многомерности функции определение ее максимального (или минимального) значения (глобального экстремума) может оказаться весьма трудоемким – тем более, что этот экстремум возможен на границе области решений. Классические методы вовсе не работают, если множество допустимых значений аргумента дискретно или функция задана таблично. В этих случаях для решения задачи (1) — (2) применяются методы математического программирования.
Построение математической модели реального экономического процесса для формирования задачи математического программирования представляет собой скорее искусство, чем науку.
Если показатель эффективности представляет линейную функцию, а функции в системе ограничений (1) также линейны, то такая задача является задачей линейного программирования. Если исходя из содержательного смысла, ее решения должны быть целыми числами, то это задача целочисленного линейного программирования. Если в задаче математического программирования имеется переменная времени и критерий эффективности (2) выражается не в явном виде как функция переменных, а косвенно – через уравнения, описывающие протекание процессов во времени, то такая задача является задачей динамического программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования.
Таким образом, задачи математического программирования могут быть классифицированы:
1) по признаку моделируемых типов процессов,
2) по признаку свойств целевой функции и ограничений.
1)Классификация по признаку моделируемых типов процессов:
1.1) регулирование запасов,
1.2) распределение ресурсов,
1.3) организация обслуживания,
1.4) планирование замены оборудования,
1.5) другие, в т.ч. комбинированные процессы.
2) Классификация по признаку свойств используемых функций:
2.1) задача линейного программирования, когда целевая функция и ограничения задаются линейными функциями;
2.2) задача целочисленного программирования, в которой есть ограничения на целочисленность решения;
2.3) задача динамического программирования, целевая функция которой представляет собой сумму целевых функций каждого этапа ее решения, а ограничения каждого этапа последовательно связаны между собой;
2.4) задача нелинейного программирования, когда целевая функция и ограничения задаются нелинейными функциями.
В пособии нашли отражение основные из приведенных видов задач математического программирования.
Цель курса состоит:
1) в приобретении навыков построения типовых задач математического программирования,
2) в изучении методов решения типовых задач математического программирования.
В создание современного математического аппарата и развитие многих направлений математического программирования большой вклад внесли российские ученые. Особо следует отметить роль академика Л.В.Канторовича, который в 1939 г., занявшись планированием работы агрегатов фанерной фабрики, решил несколько задач: о наилучшей загрузке оборудования, о раскрое материалов с наименьшими потерями, о распределении грузов по нескольким видам транспорта и др. Л.В.Канторович сформулировал новый класс условно-экстремальных задач и предложил универсальный метод их решения, положив начало новому направлению прикладной математики -линейному программированию.
Методы математического программирования, как и любые математические методы, всегда в той или иной мере упрощают, огрубляют задачу. Жизнь богаче любой схемы. Поэтому не следует ни преувеличивать значение количественных методов математического программирования, ни преуменьшать его, ссылаясь на примеры неудачных решений. Уместно привести в связи с этим шутливо-парадоксальное определение этих методов, сделанное одним из их создателей Т. Саати, как “искусства давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами.”
В данном учебном пособии рассматриваются основные оптимизационные модели экономических процессов. Теоретические положения сопровождаются решением практических задач, вопросами для самопроверки и заданиями для самостоятельной работы.