Анализ экономических задач симплексным методом (183273)

Посмотреть архив целиком

Введение.

Многие задачи, с которыми приходится иметь дело в повседнев­ной практике, являются многовариантными. Среди множе­ства возможных вариантов в условиях рыночных отно­шений приходится отыскивать наилучшие в некотором смысле при ограничениях, налагаемых на природные, эко­номические и технологические возможности. В связи с этим возникла необхо­димость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику? Такие методы объединяются под общим названием — математическое программирование.

Математическое программирование — область мате­матики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограниче­ниями, т. е. задач на экстремум функции многих пере­менных с ограничениями на область изменения этих переменных.

Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием опти­мальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет матема­тическую модель. Математическая модель задачи — это отражение ори­гинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает:

  1. совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.);

  2. целевую функцию (функцию цели, показатель эф­фективности, критерий оптимальности, функционал зада­чи и др.). Целевая функция позволяет выбирать наилуч­ший вариант -из множества возможных. Наилучший ва­риант доставляет целевой функции экстремальное значе­ние. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень об­служивания или дефицитности, число комплектов, отходы и т. д.;

Эти условия следуют из огра­ниченности ресурсов, которыми располагает общество в любой момент времени, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Ограниченными являются не только материальные, финансовые и трудовые ресурсы. Таковыми могут быть возможности технического, техноло­гического и вообще научного потенциала. Нередко по­требности превышают возможности их удовлетворения. Математически ограничения выражаются в виде уравне­ний и неравенств. Их совокупность образует область до­пустимых решений (область экономических возможно­стей). План, удовлетворяющий системе ограничений зада­чи, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, на­зывается оптимальным. Оптимальное решение, вообще говоря, не обяза­тельно единственно, возможны случаи, когда оно не су­ществует, имеется конечное или бесчисленное множество оптимальных решений.

Один из разделов математического программирования - линейным программированием. Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполните­лям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспек­тивного, текущего и оперативного планирования и управ­ления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах раз­вития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т. д. Особенно широкое применение методы и модели линейного програм­мирования получили при решении задач экономии ресур­сов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспорт­ных и других задач.

Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Кан­торовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в эконо­мике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексного метода (ме­тода последовательного улучшения плана) для решения ЗЛП состоит в следующем:

  1. умение находить начальный опорный план;

  2. наличие признака оптимальности опорного пла­на;

  3. умение переходить к нехудшему опорному плану.

















§1.Задача линейного программирования и свойства ее решений.


1.1 Понятие линейного программирования. Линейное про­граммирование—раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополни­тельных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на уни­версальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного про­граммирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.

Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с на­хождением экстремумов функции во внутренней точке области допустимых значений. Отсюда — необходимость разработки новых методов.


Формы записи задачи линейного программирования:

Общей задачей линейного программирования называют задачу

(1)

при ограничениях

(2)

(3)

(4)

(5)

- произвольные (6)

где - заданные действительные числа; (1) – целевая функция; (1) – (6) –ограничения;

- план задачи.


1.2 Свойства решений.

Пусть ЗПЛ представлена в следующей записи:

(7)

(8)

(9)

Чтобы задача (7) – (8) имела решение, системе её ограничений (8) должна быть совместной. Это возможно, если r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r= n система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки много­гранных решений. Пусть r. В этом случае система векторов содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линей­ная комбинация. Базисов, вообще говоря, может быть несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r век­торам базиса, называют, как известно, базисными и обо­значают БП. Остальные n – r переменных будут свобод­ными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свобод­ными будут переменные .

Если свободные переменные приравнять нулю, а базис­ные переменные при этом примут неотрицательные значе­ния, то полученное частное решение системы (8) назы­вают опорным решением (планом).


Теорема. Если система векторов содер­жит m линейно независимых векторов , то допустимый план (10) является крайней точкой многогранника планов.

Теорема. Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения бо­лее чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой ли­нейной комбинацией.


§2.Графический способ решения ЗЛП.

Геометрическая интерпретация экономических задач дает возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования бо­лее сложных свойств. ЗЛП с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в простран­ствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практиче­ского значения, однако его рассмотрение проясняет свой­ства ОЗЛП, приводит к идее ее решения, делает геомет­рически наглядными способы решения и пути их практи­ческой реализации.

Пусть дана задача

(11)

(12)

(13)

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (12), (13) задает на плоскости некоторую полуплоскость. Полу­плоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множест­вом. Отсюда следует, что область допустимых решений задачи (11) — (13) есть выпуклое множество.

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — не­пустое множество, например многоугольник .


Выберем произвольное значение целевой функ­ции . Получим . Это уравнение пря­мой линии. В точках прямой целевая функция сохра­няет одно и то же постоянное значение . Считая в ра­венстве (11) параметром, получим уравнение семей­ства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Найдём частные производные целевой функции по и

(14)

(15)

Частная производная (14) ((15)) функции пока­зывает скорость ее возрастания вдоль данной оси. Следо­вательно, и скорости возрастания соответст­венно вдоль осей и . Вектор называ­ется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор — указывает направление наискорейшего убывания целевой функции. Его называют антигра­диентом.

Вектор перпендикулярен к прямым семейства

Из геометрической интерпретации элементов ЗЛП вы­текает следующий порядок ее графического решения.

  1. С учетом системы ограничений строим область до­пустимых решений

  2. Строим вектор наискорейшего возра­стания целевой функции — вектор градиентного направ­ления.

  3. Проводим произвольную линию уровня

  4. При решении задачи на максимум перемещаем ли­нию уровня в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем по­ложении (крайней точке). В случае решения задачи на минимум линию уровня перемещают в антиградиентном направлении

  5. Определяем оптимальный план и экстре­мальное значение целевой функции