Задача Лагранжа

Задача Лагранжа

Содержание

Введение………………………..………………………………………………2

1. Построение модели……………………………………………………..6

2. Задача Лагранжа. Безусловный и условный экстремумы……………7

3. Задача Лагранжа с одним ограничением……………………………..11

4. Смысл множителей Лагранжа………………………………………...15

5. Простейшая модель управления запасами…………………………...18

6. Модель I. Модель Уилсона без ограничений……………………..….26

7. Модель II. Модель Уилсона с ограничениями на складские

помещения……………………………………………………………...33

8. Рацион Робинзона……………………………………………………...38

9. Взаимные экстремальные задачи……………………………………..42

10. Модель потребительского выбора……………………………………44

11. Лабораторные задачи…………………………………………………..47

12. Заключение……………………………………………………………..51

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

Введение

Научная модель является отображением некоторых интересующих нас явлений

(например, определенных объектов, событий, процессов, систем) и

используется в целях управления и предсказания. Основная функция научной

модели заключается не в том, чтобы описать явления, а в том, чтобы

объяснить их. Модель должна помочь выяснить, каким образом некоторые

стороны явления влияют на другие стороны или же на явления в целом. Если

построена достаточно верная модель, то эти вопросы можно выяснить,

производя соответствующие опыты на модели, не меняя характеристик

изучаемого объекта.

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

опыты на самом объекте или невозможны, как, например, в астрономии, или

очень дороги, как в сложных промышленных организациях. Но знание моделей

этих далеко не исчерпывается. В самом дели, в некотором смысле научные

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

потому наука не могла бы существовать без моделей, как она не могла бы

существовать без теории.

Таким образом, модели играют важнейшую роль в исследовательском процессе

и поэтому неизменно возрастает интерес к их изучению. Существующие модели

можно разделить на три типа: изобразительные (модели геометрического

подобия), модели – аналогии и символические (математические).

Изобразительная модель отображает внешние характеристики системы (как

фотография и ли модель самолета). Она подобна оригиналу. Многие фотографии,

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

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

“настоящего” автомобиля. Глобус является изобразительной моделью земного

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

модель в той мере, в какой его свойства совпадают со свойствами оригинала.

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

берётся определенный масштаб. Например, глобус имеет уменьшенный диаметр по

сравнению с земным шаром, хотя форма и относительные размеры континентов,

морей и т.д. приблизительно правильные. Модель атома, наоборот, имеет

увеличенные размеры, чтобы его можно было разглядеть не вооруженным глазом.

Масштаб в модели вводится для экономии и удобства пользователя. В обычных

условиях гораздо легче работать с моделью здания, атома или

производственной системы, чем с самим объектом. Так, с опытным заводом,

который является уменьшенной моделью полного завода, работать гораздо

легче, чем с настоящим заводом.

Изобразительные модели хорошо приспособлены для отображения статического

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

фотография или схема производственных потоков может дать хорошую “картину”

работы завода. Но такие модели не подходят для отображения динамики

явлений, например для отображения рабочих операций, на заводе. Поэтому они

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

Хотя изобразительная модель и подобна оригиналу, она, как и другие типы

моделей, отличается от оригинала и не может отразить всех его свойств. В

ней отображается только свойства оригинала, существенные для задач,

решаемых с помощью данной модели. Этой избирательностью во многом

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

Модель – аналог использует ряд свойств одного явления для отображения

свойств другого явления (например, в некоторых случаях поток воды через

трубы можно принять за аналог “потока” электричества по проводам).

При построении модели различных объектов, событий, процессов или систем

не всегда можно простым изменением масштаба изобразить все интересующие нас

свойства. Например, мы не можем наглядно представить на глобусе

геометрическую структуру Земли. Но мы легко можем представить различные

геометрические формации с помощью разноцветной окраски. При этом мы

производим подмену одного свойства (цвет) другим (геометрическая структура)

в соответствии с некоторыми правилами преобразования. В картографии,

например, такое преобразование является узаконенным, причем правила для

преобразования приводятся в легенде. В легенде на карте приводится также

перечень обозначений: например, сплошная линией обозначается грунтовая

дорога, а пунктирной – шоссейная. Такая модель называется моделью –

аналогом, поскольку в ней совокупность одних свойств представляется с

помощью совокупности других свойств.

Примером простой аналогии является графики. На графиках пользуются

расстоянием для отображения таких свойств, как время, число, проценты, вес,

и многих других. Графики часто удобны для представления количественных

соотношений и дают возможность предсказывать, как изменения одного свойства

сказывается на другом свойстве.

Используя модели – аналоги, мы увеличиваем наши возможности проверять на

модели изменения различных параметров. Обычно проще изменить модель –

аналог, чем изобразительную модель.

Модели – аналоги удобны для отображения динамических процессов или

систем. Можно построить модель, работа которой будет аналогична работе

конвейера на заводе. Или можно отобразить колебания спроса путем

соответствующего изменения некоторой входной величины модели. Однако на

изобразительной модели, например уменьшенной действующей модели цеха, такое

изменение провести трудно.

Другим преимуществом модели – аналога по сравнению с изобразительной

моделью является большая универсальность этой модели. Так, незначительно

изменение модели, можно отобразить различные процессы одного класса.

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

системы (с помощью математического уравнения или системы уравнений).

Элементы модели и их взаимосвязь задаются с помощью символов (обычно

математического или логического характера).

Во многих случаях построения моделей – аналогов затруднительно, поскольку

изучение динамики явления отнимает много времени. Например, чтобы изучить с

помощью аналоговой модели влияния колебания спроса на производственный

процесс, нужно проделать на модели много опытов. Если же системы можно

представить с помощью математического выражения, то влияние изменить какого-

нибудь параметра можно установить с помощью математической дедукции за

несколько шагов. Поэтому мы рассматриваем в основном символические модели.

1. Построение модели

Для постановки задачи необходима анализ системы, исследование её

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

результате такого анализа, является либо изобразительной, либо аналоговой

моделью. Таким образом, первый этап построения модели выполняется в

процессе постановки задачи. После такого анализа системы уточняется

перечень различных вариантов в решения, которые надо оценить. Затем

определяются меры общей эффективности этих вариантов. Следовательно,

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

эффективность системы можно выразить в функции переменных, определяющих

систему. Некоторые из этих переменных в реальной системе можно менять,

другие переменные менять нельзя. Те переменные, которые можно изменить,

назовем “управляемыми”. Различные варианты решения задачи необходимо

выразить с помощью управляемых переменных.

Построение математической (символической) модели системы можно начать с

перечисления всех элементов системы, которые влияют на эффективность работы

системы. Если в качестве меры общей эффективности используется “общие

ожидаемые издержки”, то можно начать с исследования изобразительной или

аналоговой модели, полученной на стадии постановки задачи. Можно выделить

операции и материалы, которым сопоставляется некоторые затраты. При этом

получим, например, следующий исходный список:

1. Производственные затраты:

а) закупочная цена сырья;

б) издержки перевозки сырья;

в) стоимость приемки сырья;

г) стоимость хранения сырья;

д) стоимость планирования производства;

е) стоимость наладочных работ в цехе;

ж) стоимость процесса обработки;

з) стоимость хранения запасов в процессе производства;

и) стоимость завершения производства и передачи готовых изделий на

склад;

к) стоимость анализа результатов работы группой планирования;

л) стоимость хранения готовых изделий.

2. Затраты на сбыт.

3. Накладные расходы.

2. Задача Лагранжа

Безусловный и условный экстремумы

Важное место в математиком аппарате экономики занимают оптимальные задачи

– задачи, которых ищется наилучшее в определенном смысле решение. В

экономической практике требуется использовать имеющиеся ресурс наиболее

выгодным образом. В экономической теории одним из отправных пунктов

является постулат о том, что каждый экономический субъект, имея

определенную свободу выбора своего поведения, отыскивает наилучший со своей

точки зрения вариант. И оптимизационные задачи служат средством описания

поведения экономических субъектов, инструментом исследования

закономерностей этого поведения.

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

которое должен принять субъект, описывается набором чисел х1 ,х2 ,…,хn

(или точкой Х=(х1 ,х2 ,…,хn) n-мерного пространства). Достоинства того или

иного решения определяются значениями функция f(X) = f(х1, х2 ,…,хn) —

целевой функции. Наилучшее решение — это такая точка Х, в которой функция

f(Х) принимает наибольшее значение. Задача нахождения такой точки

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

f(X) ( max.

Если функция f(X) характеризует отрицательные стороны решения (ущерб,

убытки и т. п.), то ищется точка Х, в которой значение f(X) минимально:

f(X) ( min.

Минимум и максимум объединяются понятием экстремума. Для определенности

мы будем говорить только о задачах максимизации. Поиск минимума не требует

специального рассмотрения, поскольку заменой целевой функции f(X) на -f(Х)

всегда можно “превратить недостатки в достоинства” и свести минимизацию к

максимизации.

Из каких вариантов должен быть выбран наилучший? Иными словами, среди

каких точек пространства нужно искать оптимум. Ответ на этот вопрос связан

с таким элементом оптимизационной задачи, как множество допустимых решений.

В некоторых задачах допустимыми являются любые комбинации чисел х1, х2,…,хn

то есть множество допустимых решений - это все рассматриваемое

пространство.

В других задачах следует принимать во внимание различные ограничения,

означающие, что не все точки пространства доступны при выборе. В

содержательных постановках задач это может быть связано, например, с

ограниченностью располагаемого количества ресурсов.

Ограничения могут быть представлены в форме равенств вида

g(X) = О

или неравенства

g(X) ( О.

Если условия имеют несколько другую форму, скажем, g1(Х) = g2(X) или

g(X) ( A, то их можно привести к стандартному виду, перенеся в функции и

константы в одну из частей равенства или неравенства.

Экстремум, отыскиваемый во всем пространстве, без каких-либо

ограничивающих условий, носит название безусловного. Если целевая функция

непрерывно дифференцируема, то, необходимое условие безусловного экстремума

функции состоит в равенстве нулю всех ее частных производных:

[pic]

Если же заданы ограничения, то экстремум ищется лишь среди точек, которые

удовлетворяют всем ограничениям задачи, так как только такие точки являются

допустимыми. В этом случае экстремум носит название условного.

Рассмотрим задачу поиска условного экстремума:

f(X) ( max

при условиях (2)

g1(Х) = 0; g2(Х) = 0, …, gn(Х) = 0,

все ограничения которой представляют собой равенства.

Если при этом целевая функция и все ограничивающие функции непрерывно

дифференцируемы, то такую задачу мы будем называть задачей Лагранжа.

3. Задача Лагранжа с одним ограничением

Рассмотрим задачу, имеющую следующую структуру:

f(X) ( max

при условии (3)

g(X) = 0.

Рассмотрим пример. По склону горы идет дорога, требуется найти на ней

самую высокую точку. На рис. 1 представлена карта местности с нанесенными

на нее линиями

Рис. 1

равных высот; толстая линия – это дорога. Точка М, в которой дорога

касается одной линий уровня, - это и есть наивысшая точка дороги.

Если Х = (х1, х2) – точка плотности, х1 и х2 – её координаты, то задаче

можно придать следующую форму. Пусть f(Х) — высота точки Х над уровнем

моря, а уравнение g(X) = 0 описывает дорогу. Тогда наивысшая точка дороги -

решение задачи (3).

Если бы дорога проходила через вершину горы, то ее высшая точка была бы

самой высокой точкой местности, и ограничение можно было бы не принимать во

внимание.

Если же дорога не проходит через вершину, то, немного отклонившись от

дороги, можно было бы подняться выше, чем двигаясь строго по дороге.

Отклонение от дороги соответствует попаданию в такие точки, где g(X)

( 0; при малых отклонениях достижимую при этом высоту можно приближенно

считать пропорциональной отклонению.

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

попытаться “исправить” рельеф местности так, чтобы отклонение от дороги не

давало преимуществ в достижении высоты. Для этого нужно заменить высоту

f(Х) функцией.

L(X) = f(X) - (g(Х),

где множитель ( подбирается таким образом, чтобы участок склона в

окрестности точки М стал горизонтальным (слишком малое ( не устранит

преимуществ отклонений от дороги, а слишком большое – придаст преимущество

отклонениям в противоположную сторону).

Теперь, поскольку рельеф L(X) делает площадку в окрестности точки

оптимума горизонтальной, эта точка удовлетворяет равенствам

[pic]

а так как точка лежит на дороге, то – и ограничению g(X) = 0.

[pic]рис.2

Пример с горой и дорогой — лишь иллюстрация идеи; точно так же двумерный

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

было бы рассуждать и в общем, n-мерном случае.

Справедливо следующее утверждение:

Если f(х1,…,хn) и g(х1,…,хn) - непрерывно дифференцируемые функции всех

своих аргументов, то решение задачи

f(х1,…,хn) ( max

при условии

g(х1,…,хn) = 0

удовлетворяет равенствам

[pic]

где

L(х1,…,хn;() = f(х1,…,хn) — (g(х1,…,хn).

Функция L(X; () получила название функции Лагранжа (или лагранжиана)

задачи (3), а коэффициент ( — множителя Лагранжа.

Заметим, что равенство (5) — это представленное в другой форме

ограничение g(Х) = 0.

Приведенные выше рассуждения, разумеется, не являются доказательством

сформулированного здесь утверждения; они лишь помогают понять существо

метода: составляющая (g(Х) в составе функции Лагранжа должна уравновешивать

возможное увеличение максимального значения функции g(Х) от нуля. Это

обстоятельство в дальнейшем будет весьма полезно при обсуждении смысла

множителя Лагранжа.

Рассмотрим чрезвычайно простой пример. Веревкой длины А требуется

огородить на берегу моря прямоугольный участок наибольшей площади (берег

считается прямолинейным).

Рис.3[pic]к задаче Дидона

Обозначим стороны прямоугольника х1 и х2 (см. рис. 3). Решим сначала

задачу без использования метода Лагранжа.

Очевидно, х2 = А - 2 х1 и площадь прямоугольника равна

S = х1х2 = x1(А - 2х1). Рассматривая ее как функцию одного

аргумента х1, нетрудно найти его значение, при котором площадь максимальна:

х1 = А/4. Отсюда х2 = А/2. Максимальная площадь равна S* = А2/8.

Теперь рассмотрим эту же задачу в форме задачи Лагранжа:

х1х2 ( max

при условии

2 х1 + х2 - А = 0

Лагранжиан этой задачи равен

L(х1,х2; () = х1х2 - ((2х1 + х2 - А),

и условия экстремума имеют вид

[pic]

так что

х2 = 2(

х1 = (

2 х1 + х2 = А

Подставляя значения х1 и х2 из первого и второго равенств в третье,

находим, что 4( = А, откуда

( = А/4; х1 = А/4; х2 =А/2,

как и при решении первым способом.

Этот пример показывает распространенный способ решения задачи Лагранжа.

Соотношения (4) и (5) образуют систему уравнений относительно х1,…,хn и (,.

Система состоит из n + 1 уравнения - n уравнений вида (4) и одно уравнение

вида (5). Число уравнений равно числу неизвестных. Из уравнений вида (4)

можно попытаться выразить каждую из неизвестных х1,…,х2 через (, то есть

решить ее как систему из n уравнений, рассматривая ( как параметр.

Подставляя получившиеся выражения в уравнение (5) – нам известно, что оно

совпадает с ограничением, - получаем уравнение относительно (. Решая его,

находят (, после чего определяются исходные неизвестные х1,…,хn.

4. Смысл множителей Лагранжа

При решении задачи Лагранжа мы интересовались значениями х1,…,хn; кроме

того, нас могло интересовать экстремальное значение целевой функции f(X).

Но в процессе решения попутно было определено значение еще одной величины -

множителя Лагранжа.

Оказывается, множитель Лагранжа — весьма существенная характеристика

решаемой задачи. Чтобы смысл ее стал яснее, несколько изменим формулировку

ограничения, ничего не изменяя по существу.

Типичная экономическая ситуация характеризуется тем, что приходится

искать наиболее выгодное решение при ограниченном количестве некоторого

ресурса. Если r - заданное количество ресурса, а функция h(X) характеризует

потребное его количество для достижения точки Х, то ограничению естественно

придать форму

h(X) ( r.

По характеру задачи часто бывает ясно, что для достижения оптимума ресурс

нужно использовать полностью, так что ограничение может быть записано в

виде равенства

h(X) = r. (6)

Это условие можно представить в форме g(X) = h(Х) - r = 0. Но значительный

интерес представляет максимально достижимый уровень функции f(x) в

зависимости от имеющегося количества ресурса r. Обозначим

F(r) = max (f(X) ( h(X) = r(.

В правой части - принятое обозначение условного экстремума: после

вертикальной черты выписывается условие.

Вспомним, что при обсуждении структуры лагранжиана мы интерпретировали

Страницы: 1, 2, 3