Решение оптимизационных экономических задач методами линейного программирования

 

 

 

 

РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ  ЭКОНОМИЧЕСКИХ ЗАДАЧ МЕТОДАМИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

 

 

СОДЕРЖАНИЕ

 

Введение Основная часть 2.1 Общая постановка задачи линейного программирования (ЛП) 2.2 Примеры экономических  задач, приводящихся к задачам  ЛП 2.3 Геометрический (графический) метод решения задач ЛП 2.4 Пример решения задачи ЛП геометрическим методом 2.5 Симплексный метод решения задач ЛП 2.6 Пример решения задачи ЛП симплексным методом 2.7 Теоремы двойственности и их использование в задачах ЛП 2.8 Пример решения двойственной задачи 2.9 Транспортная задача и ее решение методом потенциалов 2.10 Пример решения  транспортной задачи 2.11 Решение задач ЛП с использованием программы «Maple 15» Заключение Список литературы

4 стр. 9 стр. 9 стр. 12 стр. 17 стр. 20 стр. 24 стр. 30 стр. 34 стр. 37 стр. 43 стр. 48 стр. … стр. … стр. … стр.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

Математика служит людям  издавна и успешно. Потребности  всей практической деятельности людей, естествознания, техники постоянно  ставили и ставят перед математикой новые задачи, стимулируя ее развитие. В свою очередь прогресс в математике делал математические методы более эффективными, расширял сферу их применения и, тем самым, способствовал общему научно-техническому прогрессу и развитию производительных сил. В противовес историческому мифу можно без преувеличения сказать, что мир стоит не на трех китах, а на двух - математике и экономике. Математика - основа всех точных наук, а экономика в двух своих ипостасях - как хозяйственная система и как наука - создает материальные условия для существования людей и помогает им понять «что почем» в окружающей их жизни.

Многовековой опыт ведения  хозяйства показывает, что результативность этого вида человеческой деятельности во многом зависит от умения считать. Существенно возрастает роль счета по мере становления стабильной рыночной экономики. Для принятия обоснованных и своевременных решений субъектами хозяйствования предпринимателями, менеджерами, работниками экономических служб и руководителями предприятий, банков, бирж и т.п. - без определенных экономико-математических знаний, без вычислительной техники и без навыков практического их использования уже не обойтись.

Каждый человек ежедневно, не всегда осознавая это решает  проблему: как получить наибольший эффект, обладая ограниченными средствами.  Наши средства и ресурсы всегда  ограничены.  Жизнь  была  бы  менее интересной , если бы это было не так.  Не  трудно  выиграть  сражение,  имея армию в 10 раз большую, чем у противника; Ганнибалу,  чтобы  разбить  римлян при Каннах, командуя вдвое меньшей армией,  нужно было  действовать очень обдуманно.

Чтобы достичь наибольшего  эффекта, имея ограниченные средства, надо составить  план,  или  программу  действий.  Раньше  план  в  таких  случаях составлялся «на глазок».  Но в  середине  XX века был создан специальный математический аппарат,  помогающий  это  делать «по науке».  Соответствующий  раздел  математики  называется математическим программированием. Слово «программирование» здесь и в  аналогичных  терминах («линейное программирование, динамическое программирование» и т.п.)  обязано отчасти  историческому   недоразумению,   отчасти   неточному   переводу   с английского. По-русски лучше было  бы  употребить  слово  «планирование».  С программированием для ЭВМ  математическое  программирование  имеет  лишь  то общее,  что  большинство  возникающих  на  практике  задач   математического программирования слишком  громоздки  для  ручного  счета,  решить  их  можно только с помощью ЭВМ, предварительно составив программу.

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

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

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

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

Один из разделов математического  программирования называется - линейным программированием. 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ОСНОВНАЯ ЧАСТЬ

 

1. Общая постановка задачи линейного программирования (ЛП)

 

Линейное программирование – направление математики, изучающее  методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными  и линейным критерием оптимальности.

Несколько слов о самом  термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий.

К математическим задачам  линейного программирования относят  исследования конкретных производственно-хозяйственных  ситуаций, которые в том или  ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

· задача об оптимальном использовании ресурсов при производственном планировании;

·  задача о смесях;

· задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах;

· транспортные задачи.

Линейное программирование является наиболее разработанным и широко применяемым разделом математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

· математические модели большого числа экономических задач линейны относительно искомых переменных;

· данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;

· многие задачи линейного программирования, будучи решенными, нашли широкое применение;

· некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования.

Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

В общем виде модель записывается следующим образом:

· целевая функция:

= c1x1 + c2x2 + ... + cnxn → max(min);

(1.1)

· ограничения:

a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1,  a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2, ...             am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm;

(1.2)

· требование неотрицательности:

xj ≥ 0,

(1.3)

При этом a_ij, b_i, c_j (   ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3).

Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми.

Вектор  , удовлетворяющий ограничениям (1.2) и (1.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (1.1) достигает своего максимального (минимального) значения, называется оптимальным.

Подавляющее большинство  известных методов решения задач  линейного программирования предназначены  для канонических задач. Поэтому  начальный этап решения всякой общей задачи линейного программирования обычно связан с приведением ее к некоторой эквивалентной канонической задаче.

Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:

• ограничения в виде неравенств преобразуются в уравнения за счет добавления фиктивных неотрицательных переменных , которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;
• переменные, на которые не наложено условие неотрицательности, представляются в виде разности двух новых неотрицательных переменных:

• переменные, на которые наложено условие неположительности, представляются в виде новой неотрицательной переменной помноженной на -1:

Нетрудно заметить, что  «платой» за переход от общей формы задачи линейного программирования к канонической является рост ее размерности, что, при прочих равных условиях, является фактором, усложняющим процесс решения.

 

 

 

 

 

 

 

 

 

2. Примеры экономических  задач, приводящихся к задачам  ЛП

 

Приведем примеры некоторых типовых задач, решаемых при помощи методов линейного программирования. Такие задачи имеют реальное экономическое содержание.

 

1. Задача об оптимальном использовании ресурсов при производственном планировании.

Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b₁, b₂,..., b_m условных единиц.