Реферат: Линейное программирование 3

БАЛТИЙСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ

РЫБОПРОМЫСЛОВОГО ФЛОТА РФ

ИНСТИТУТ ПРИКЛАДНОЙ ЭКОНОМИКИ И МЕНЕДЖМЕНТА

КАФЕДРА «МЕНЕДЖМЕНТ»

Контрольная работа

По дисциплине: «Моделирование и математические методы в экономике »

На тему: 1. «Задачи математического программирования»

2. «Свойства задачи линейного программирования»

Выполнил:

Студент группы Эзс 3

Специальность:

Основы менеджмента

Шифр: 08 Эзс 1530

Данилов Ю.С.

Проверил:

Дерендяева Т.М.

г. Калининград, 2010

Содержание

Введение -----------------------------------------------------------------------стр. 3

1. Задачи математического программирования------------------------стр. 5

2. Свойства задачи линейного программирования--------------------стр. 8

Задача----------------------------------------------------------------------------стр. 10

Список использованной литературы--------------------------------------стр. 11

Введение.

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

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

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

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

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

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

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

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

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

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

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

Задачи математического программирования

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

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

Математическое программирование включает в себя такие разделы математики как линейное, нелинейное и динамическое программирование. Сюда же обычно относят стохастическое программирование, теорию игр, теорию массового обслуживания, теорию управления запасами и некоторые другие.

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

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

Математическое программирование возникло в 30-е годы XX века. Венгерский математик Б.Эгервари в 1931 году решил задачу, называемую проблемой выбора. Американский ученый Г.У. Куй обобщил этот метод, после чего он получил название венгерского метода. В 1939 году российский ученый Л.В. Канторович разработал метод разрешающих множителей решения задач линейного программирования. Большой вклад в развитие математического программирования внесли американские ученые. В 1949 году американский ученый Дж. Данциг опубликовал один из основных методов решения задач линейного программирования, получивший название симплексный.Составление математической модели экономической задачи включает следующие этапы:

1) выбор переменных задачи;

2) составление системы ограничений;

3) выбор целевой функции.

Переменными задачи называются величины х₁ ,х₂ ,х₃ ....х _n , которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора Х=( х₁ ,х₂ ,х₃ ....х _n )

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

f (х₁ х₂ , х₃ ...., х _n ) → max f (х₁ х₂ , х₃ ...., х _n ) → min (a)

и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений

g₁ (x₁ , x₂ , x₃ ....x_n ) = 0 (b)

g_m ( x ₁ , x ₂ , x ₃ .... x_n ) = 0 (c)

Если целевая функция (a) и система ограничений (b), (c) являются линейными, то задача математического программирования называется задачей линейного программирования.

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

Z(x) = c₁ x₁ +c₂ x₂ +…. + c_n x_n → max ( min ) (d)

a₁₁ x₁ + a₁₂ x₂ + … + a_1n x_n = b₁

a_i1 x₁ + a_i2 x₂ + … + a _in x_n ≤ b_i

a_(i+1)1 x₁ +a_(i+1)2 x₂ +…+a_(i+1)n x_n ≤ b_i+1 (e)

a_m1 x₁ +a_m2 x₂ +…+a_mn x_n ≤ b_m

x_i ≥ 0, i =1,2,… t ; t ≤ n (f)

Это позволяет найти экстремум целевой функции задачи (d) и соответствующие ему переменные Х=(х ₁ ,х ₂ ,х ₃ ,...., х _n ) при условии, что эти переменные удовлетворяют системе ограничений (e) и условиям неотрицательности (f).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор Х=(х ₁ ,х ₂ ,х ₃ ,...., х _n ), удовлетворяющий системе ограничений и условиям неотрицательности.

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

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

Но если все c_i = 0, то и Z = 0, т.е. экстремум функции не обнаруживается. Связано это с тем, что производную можно использовать для определения экстремума только во внутренних точках области решений, а в данном случае экстремум, как будет показано ниже, находится на границах области. Отсюда и возникает необходимость разработки специальных методов поиска экстремума

Свойства задачи линейного программирования

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

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

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

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

max(min)Z = (1)

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

( i =1,2…. m ) (2)

( i = m ₁ +1,..., m ₁ ) (3)

( i = m ₂ +1,..., m ₂ ) (4)

x_j ≤ 0 ( j =1,2….. n ₁ ) (5)

x_j -произвольные ( j = n ₁ +1,….. n ) (6)

где с _j ,а _ij , b_i ;- заданные действительные числа;

(1) - целевая функция;

(2) - (6) -ограничения;

х = (х,;...;х _n ) –план задачи.

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

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

mах Z = сх (7)

А₁ х₁ ,+А₂ х₂ +... + А_n х_n =А₀ (8)

х₁ ≥ 0, х₂ ≥ 0,…….х_n ≥ 0 (9)

Чтобы задача (7) - (8) имела решение, системе её ограничений (8) должна быть совместной. Это возможно, если rэтой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r= n система имеетединственное решение, которое будет при х_j ≥ 0 (j=1,...,n) оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n, вэтом случае система векторов А₁ ,А₂ ,...,А_n содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, может быть несколько, но не более с. Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n — rпеременных будут свободными, их обозначают СП. Будем считать, что базис составляют первые m векторов А₁ ,А₂ ,...,А_m . Этому базису соответствуют базисные переменные х₁ ,х₂ ,...,х_m , а свободными будут переменные х_{m +1} ,х_{m +2} ,….х_n .

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

Задача

Зависимость доходов фирмы R и издержек I в зависимости от объёма производства x задётся функциями следующего вида: R(x)=2/3x³ – 18x² – 17x ; C(x)=1/3x³ – 10x² +150. производственные мощности позволяют производить до 30 единиц продукции. При каком объёме производства прибыль максимальна?

Решение

R(x) = 2/3x³ – 18x² – 17x

C(x) = 1/3x³ – 10x² +150

P(x) = R(x) – C(x)

P(x) =2/3x³ – 18x² – 17x – 1/3x³ + 10x² –150

P(x) =1/3x³ – 8x² – 17x –150

Решая кубическое уравнение по теореме Кордано получаем 3 значения х.

x ₁ =27

x ₂ = 3

x ₃ = – 5 (не имеет экономической силы)

Ответ: 27

Список использованной литературы

1. Замков О.О., Толстопятенко А.В, Математические методы в
экономике, Дело и сервис, 2001

2. Коршунова Н.И., Плясунов В.С. Математическая экономика. М.: Вита-
Пресс, 1996

3. Пинегина М.В. Математические методы и модели в экономике. М.:
Издательство «Экзамен» 2002

4. Бережков Л.Н. Теория оптимального управления экономическими
системами. СПб.:«Знание», 2002