Динамическое программирование и дифференциальное и интегральное исчисление в образах

Прямой ход:

F1(x)=f1(x)

F2(x)=(f2(x)+F1(x))

F3(x)=(f3(x)+F2(x))

F4(x)=(f4(x)+F3(x))

n)Fn(x)= (fn(x)+Fn-1(x))

Прикладные задачи

Производственному объединению из четырех предприятий выделяется банковский кредит в сумме 60 млн. ден. ед. для реконструкции и модернизации производства с целью увеличения выпуска продукции. Значения дополнительного дохода, получаемого на предприятиях объединения в зависимости от выделенной суммы xi, приведены в табл. 2.1. Распределить выделенный кредит между предприятиями так, чтобы дополнительный доход объединения был максимальным

Таблица 2.1 - Значения дополнительного дохода

Решение. Пусть n=1. В соответствии с вычислительной схемой динамического программирования рассмотрим сначала случай n=1, т.е. предположим, что все имеющиеся средства выделяются на реконструкцию и модернизацию одного предприятия. Обозначим через 1(x) максимально возможный дополнительный доход на этом предприятии, соответствующий выделенной сумме x. Каждому значению x отвечает вполне определенное (единственное) значение дополнительного дохода, поэтому можно записать, что:

 (2.1)

В соответствии с формулой (2.1) в зависимости от начальной суммы с поучаем с учетом табл. 2.1 значения 1(с), помещенные в табл. 2.2.

Таблица 2.2 - Значения максимально возможного дополнительного дохода в зависимости от выделенных средств

Пусть теперь n=2, т.е. средства распределяются между двумя предприятиями. Если второму предприятию выделена сумма x, то дополнительный доход на нем составит g2(x). Оставшиеся другому предприятию средства (c-x) в зависимости от величины x (а значит, и c-x) позволят увеличить дополнительный доход до максимально возможного значения 1(c-x). При этом условии общий дополнительный доход на двух предприятиях:

 (2.2)

Оптимальному значению 2(с) дополнительного дохода при распределении суммы с между двумя предприятиями соответствует такое x, при котором сумма (2.2) максимальна. Это можно выразить записью:

 (2.3)

Функциональное уравнение Беллмана для рассматриваемой задачи запишется в следующем виде:

 (2.4)

Очередная задача - найти значения функции (2.3) для всех допустимых комбинаций с и x. Для упрощения расчетов значения x будем принимать кратными 20 тыс. ден. ед. и для большей наглядности записи оформлять в виде таблиц. Каждому шагу будет соответствовать своя таблица. Рассматриваемому шагу соответствует табл. 2.3.

Таблица 2.3 - Значения функции на втором шаге

Для каждого значения (20,40,60) начальной суммы с распределяемых средств в табл. 2.2 предусмотрена отдельная строка, а для каждого возможного значения x (0,20,40,60) распределяемой суммы - столбец. Некоторые клетки таблицы останутся незаполненными, так как соответствуют недопустимым сочетаниям с и x.

В каждую клетку таблицы будем вписывать значение суммы (2.2). Первое слагаемое берем из условий задачи (см.табл.2.1), второе - из табл.2.2. 

В двух последних столбцах таблицы проставлены максимальный по строке дополнительный доход (в столбце ) и соответствующая ему оптимальная сумма средств, выделенная второму предприятию (в столбце ). 

Расчет значений приведен в табл. 2.4. Здесь использована формула, получающаяся из (2.4) при n=3:

Первое слагаемое в табл. 2.4 взято из табл. 2.1, второе из табл. 2.3.

Таблица 2.4 - Значения функции на третьем шаге

Расчёт значений приведен в табл. 2.5. Здесь использована формула, получающаяся из (2.4) при n=4:

Первое слагаемое в табл.2.5 взято из табл.2.1, второе из табл. 2.4.

Таблица 2.5 - Значения функции на четвертом шаге

Составим сводную таблицу, на основе расчетов таблиц, начиная с 2.2.

Таблица 2.6 - Сводная таблица

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

Ответ: максимальный дополнительный доход на четырех предприятиях при распределении между ними 60 млн. ден. ед. составляет 45 млн. ден. ед. и будет получен, если первому и второму предприятию средств не выделять, третьему 40 млн. ден. ед., а четвертому 20 млн. ден. ед.

Простейщая классификация функций

Функция у = f(x) называется четной, если ее область определения симметрична и выполняется равенство

Из симметричности области определения и из того, что наряду с точкой (х,у) графику функции принадлежит точка (- x,y), следует, что график четной функции симметричен относительно оси ординат.

Например, у = х2 функция четная, так как

а область определения R (множество всех действительных чисел) симметричное.

Функция y=f(x) называется нечетной, если область ее определения симметрична и выполняется равенство для всех х из области определения.

Из симметричности области определения и из того, что вместе с точкой (х,у) графику функции принадлежит точка (-х,-у), следует, что график нечетной функции симметричен относительно начала координат (т.е. не изменяется при вращении его относительно начала координат на 180°.

Функция у = f(x) называется периодической, если существует число такое, что для каждого значения аргумента х из области ее значения имеет место равенство.

Число Т называют периодом функции.

Из определения следует, что числа (k = 0,±1,±2,...) также являются периодами.

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

Ограниченность функции

Функция у = f(х) называется ограниченной сверху в области своего задания X, если существует такое положительное число М, что для всех выполняется неравенство

Пример. Функция у = - х2 ограничена сверху, так как для всех ,то есть 0 = М.

Функция у = f(x) называется ограниченной снизу, если существует такое число М, что для всех х из области определения функции выполняется неравенство

Монотонность функции

Функция у = f(х) называется возрастающей на некотором промежутке, если для любых двух значений х из этого промежутка

следует, что

Функция у = f(x) называется убывающей на некотором промежутке, если для любых двух значений х из этого промежутка следует,

что

Возрастающие и убывающие функции обычно называют монотонными.

Линейная функция y = kx + b.

la. Рассмотрим вначале частный случай функций y = kx + b при b = 0.

Функция определена при всех

Областью значения является множество R (так как уравнение kx = c имеет решение при всех с).

Функция является нечетной, f(--x) = - kx = - f(x).

Функция не является периодической, так как k(x+T) = kx =>kx + kT = kx =>кТ= 0 =>Т = 0.

Функция не ограничена.

Функция монотонная (прик > 0 возрастающая, k< 0 убывающая).

Если у = 0, то х = 0.

1 б. Рассмотрим частный случай функции y = kx + b при k = 0.

у = b.

Эта функция определена при всех

· Областью значения является одна точка b.

· Функция четная.

· Функция периодическая (периодом является любое число, основного периода нет).

· Функция ограничена.

· Функция постоянная

1 в. Функция y = kx + b.

Функция y = kx + b является суммой двух функций y = kx и у = b.Следовательно область определения R (множество действительных чисел).

· Область значения R.

· Функция общего вида при

· Функция не является периодической.

· Функция не ограничена.

· Функция монотонна (k> 0 возрастающая, k< 0 убывающая).

· График функции получается из графика функции y = kx сдвигом

· по оси ординат на величину b.

Дробно - линейная функция

28 Глава, 1. Задачи управления многошаговыми процессами

Размещено на http://www.allbest.ru/

а, b, с, d - постоянные, причем (иначе мы имели бы линейную функцию) и (иначе произошло бы сокращение и мы получили бы постоянную функцию).

la. В начале рассмотрим функцию

Функция определена всюду, кроме х = 0, то есть область определения интервалы .

Область значения также интервалы .

Функция нечетная, так как

Функция убывающая (прик > 0) и возрастающая (при k< 0) на интервалах .

Функция неограниченная.

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

1б. Общий случай

Полагая получаем

Следовательно график функции легко получить из графика функции с помощью сдвига на - т вдоль оси Ох и на n единиц вдоль оси Оу.

Свойства функции получаемые свойств функции

Степенная функция у = хn.

1а. Рассмотрим случай n = 2k.

Функция определена на всей числовой оси.

Функция четная, так как

Функция не является периодической.

На интервале (-; 0) функция убывает,на интервале (0; +) функция возрастает.

Функция ограничена снизу.

Обратная функция

Пусть на некотором множестве Х задана функция у = f(x) и Y - область значения данной функции.

Возьмем некоторое число . Тогда найдется такое число (возможно не единственное), что Таким образом, каждому значению поставлено в соответствие число (возможно не единственное). Если такое число - единственное, то говорят, что задана функция х = g(y).

Графики функции у = f(х) и обратной для нее функции х = g(y) совпадают, только аргумент обратной функции рассматривается на оси Оу.

Но если, следуя нашим привычкам, аргумент обозначить буквой х и откладывать его на оси Ох, то есть вместо х = g(y) писать у = g(x), то график функции у = g(x) отличается от графика функции у = f(х).

Легко показать, что графики функции у = f(x) и обратной к ней функции

у = g(x) симметричны относительно биссектрисы I и III координатных углов.

Заметим, что и свойства прямой, и обратной функций связаны между собой.

1. Область определения функции у = f(х) Х является областью значений функции .

Область значения функции у = f(x)Y является областью определения функции .

3. Если функция у =f(х) возрастает (убывает),то функция y = g(x) возрастает (убывает).

4. Если функция у = f(х) дифференцируема в точке , то функция у = g(x) дифференцируема в точке

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

Функция, определяемая равенством

,

где а - постоянное положительное число не равное единице.

Свойства показательной функции непосредственно вытекают из свойств степени.

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

2. a0 = 1, при любом основании.

3. При а > 1, аx> 1 для х > 0 и аx< 1 для х < 0.

4. При 0 < a < 1, аx< 1 для х > 0 и аx> 1 для х < 0.

5. Область изменения (значений) функции у = аxявляется множество положительных чисел, то есть интервал (0;).

6. Функция монотонна

6.1. Если а > 1, тоаxвозрастающая.

6.2. Если 0<а< I,тоаx убывающая.

7. Если а <b, то аx<bxпри х > 0и аx< bx при х < 0.

8. Производная функции у = аx

Используя вышеперечисленные свойства, получаем график функции у = аx.

Логарифмическая функция

Показательная функция монотонна на всей области определения, следовательно, она имеет обратную. Так как монотонная функция определяет взаимно - однозначное отображение.

Определение. Функция, обратная показательной функции у = аx, называется логарифмической функцией и обозначается

у = logax.

Свойства логарифмической функции следуют из свойств показательной функции.

1. Областью определения является множество положительных чисел, то есть (0;).

2. Областью значений является множество действительных чисел, то есть

(-;+).

3. loga 1 = 0 при любом a.

4. Функция logax монотонна.

4.1. Приа > 1 функция возрастает.

4.2. При 0<а < 1 функция убывает.

5. Если а > 1, то loga х> О при х > 1 и loga х < V при 0 <х < 1.

6. Еслиа < 1, то loga х < 0 при х > 1 и loga х > 0 при 0 <х <1.

7. Производная функции у =loga х

Последовательности

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

x1 , x2 , ..., xn , ...,

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

xn = f(n)

Определим одно из важнейших понятий математического анализа - предел последовательности, или, что то же самое, предел переменной величины xn , пробегающей последовательность x1 , x2 , ..., xn , ... ..

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

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

последовательности , начиная с некоторого.

Теорема (о единственности предела). Если -- предел последовательности и -- предел последовательности , то .Доказательство. Предположим, что . Возьмем . Найдется такой номер , что

также существует

Возьмем , которое больше и . Тогда

Обозначение. есть предел :

,

-- стремится (сходится) к ,

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

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

Последовательности (строго) возрастающая и (строго) убывающая называются (строго) монотонными.

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

Теорема. Всякая сходящаяся последовательность ограничена.

Доказательство. Пусть -- предел последовательности . Тогда найдется такой номер , что

Тогда .

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

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

Числовые ряды.

Числовым рядом называется

Например,

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

конечна.

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

Если предел не существует либо бесконечен, то ряд расходится.

Теорема 1: Необходимое условие сходимости ряда.

Если ряд сходится, то (при ).

Обратное утверждение неверно, у ряда общий член

, но ряд расходится.

Простейшие свойства числовых рядов.

1. Линейность.

Если ряды и сходятся (и их суммы соответственно равны и ), то линейная комбинация тоже сходится (к сумме ).

Это свойство вытекает из линейности предела:

2. На сходимость ряда не влияет изменение первых членов ряда:

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

Дело в том, что частичные суммы при этих рядов отличаются на постоянную величину: (при ). Следовательно, если имеет предел, то и имеет его (и наоборот).

Знакоположительные числовые ряды.

Рассмотрим один из частных случаев числовых рядов так называемые знакоположительные числовые ряды. Для них верно следующее неравенство.

Теорема 2: Критерий сходимости знакоположительных рядов.

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

Теорема 3: Первый признак сравнения.

Пусть . Тогда:

1. Если сходится, то сходится.

2. Если расходится, то расходится.

Теорема 4: Второй признак сравнения.

Пусть и - знакоположительные ряды, причём при . Тогда эти два ряда сходятся или расходятся одновременно.

Теорема 5: Признак Даламбера.

Пусть . Тогда:

1. Если , то ряд сходится.

2. Если , то ряд расходится.

Теорема 6: Радикальный признак Коши.

Пусть и существует предел . Тогда:

1. Если , то ряд сходится.

2. Если , то ряд расходится.

Теорема 7: Интегральный признак Коши.

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

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

(или ), где .

Ряды, не являющиеся знакопостоянными ( или ) называются знакопеременными.

Ряд называется абсолютно сходящимся, если сходится.

Ряд называется условно сходящимся, если он сходится, но не является абсолютно сходящимся.

Теорема 8: Абсолютно сходящийся ряд сходится.

Теорема9: Признак Лейбница.

Пусть монотонно невозрастает и . Тогда ряд сходится.

Ряд, членами которого являются степенные функции аргумента x, называется степенным рядом :

Часто рассматривается также ряд, расположенный по степеням (x ? x0), то есть ряд вида

где x0 ? действительное число.

Интервал и радиус сходимости

Рассмотрим функцию . Ее областью определения является множество тех значений x, при которых ряд сходится. Область определения такой функции называется интервалом сходимости. 

Если интервал сходимости представляется в виде , где R > 0, то величина R называется радиусом сходимости. Сходимость ряда в конечных точках интервала проверяется отдельно. 

Радиус сходимости можно вычислить, воспользовавшись радикальным признаком Коши, по формуле

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

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

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

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

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

? задача о смесях (планирование состава продукции);

? задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

? транспортные задачи (анализ размещения предприятия, перемещение грузов).

3.1.1 Симплекс-метод

Для производства двух видов изделий P1, P2 использует 3 вида сырья. Запасы сырья ограничены: предприятия обеспеченно сырьем первого вида в количестве S1 (кг), сырьем второго вида S2 (кг), сырьем третьего вида S3 (кг). На производство одного изделия P1 необходимо затратить сырья первого вида А1 (кг), сырья второго вида А2 (кг), сырья третьего вида А3 (кг). На производство одного изделия P2 необходимо затратить сырья первого вида В1 (кг), сырья второго вида В2(кг), сырья третьего вида В3 (кг).

Прибыль от реализации одного изделия P1 составляет С1 руб., а изделия P2 составляет С2 руб. Составить план производства изделий P1 и P2 , так чтобы предприятие получило наибольшую прибыль от их реализации. Решить задачу симплексным методом.

Решение:

1) Допустим, что предприятие планирует выпустить х1 единиц изделий первого вида Р1 и х2 единиц изделий второго вида Р2 . Количество числа х1 не должно превышать его запасы:

5х1 + 8х2 ? 6390

4х1 + 9х2 ? 6750

4х1 + 5х2 ? 4440

х1 ? 0; х2 ? 0

Реализация х1 изделия Р1 и х2 единиц изделий Р2, будет соответствовать

17х1 и 26х2 руб. прибыли.

2) Суммарная прибыль х0 =17х1 + 26х2 (max)

Таким образом математическая модель имеет вид:

5х1 + 8х2 ? 6390

4х1 + 9х2 ? 6750 (1) - система ограничения

4х1 + 5х2 ? 4440

х1 ? 0; х2 ? 0 (2) -условие неотрицательности

3) От системы (1) ограничений в виде неравенств переходим к системе ограничений в виде уравнений, обозначив:

х3 = 6390 - 5х1 - 8х2

х4 = 6750 - 4х1 - 9х2 (3)

х5 = 4440 - 4х1 - 5х2

Тогда система ограничений в виде неравенств заменяется системой ограничений в виде уравнений:

5х1 + 8х2 + х3 = 6390

4х1 + 9х2 + х4 = 6750 (4)

4х1 + 5х2 + х5 = 4440

Целевую функцию удобно записать в виде уравнения в неявном виде:

х0 - 17х1 - 26х2 = 0 (5)

4) Система разрешима относительно новых переменных х3, х4 , х5 - эти переменные будут базисными, а х1 и х2 - свободные.

х1 =0

х2=0

х3=6390

х4=6750

х5=4440

Базисное решение является опорным, так как все базисных переменных не отрицательны, значения целевой функции х0 =0

5) Составим симплексную таблицу.

(таб. 3.1.1)

6) Проверяем критерий оптимальности.

В нулевой строке целевой функции есть отрицательные элементы, поэтому полученное опорное решение не является оптимальным.

7)Выбираем разрешенный столбец: необходимо взять тот столбец, у которого в ноль строке стоит наибольший отрицательный элемент: (-17).

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

6390 : 5 = 1278;

3750 : 4 = 1687,5;

4440 : 4 = 1110

Наименьшее из этих отношений min

9)Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки: 4

Выполним преобразования однократного замещения. В результате базисная переменная х5 переводится в свободную.

Составляем новую симплексную таблицу. Делим все элементы разрешающей строки на 4.

= 1110; 1; 0; 0;

=

=

=

=

(таб. 3.1.2)

2310 : 4 = 557,5

1110 :

В ноль строке есть отрицательный элемент: , значит решение не оптимальное.

0

1

0

0

Составим симплексную таблицу.

(таб 3.1.3)

Это опорное решение является оптимальным, так как в ноль строке нет отрицательных элементов.

Ответ: предприятие получит максимальную прибыль от реализации продукции, если первого изделия будет выпущено 480 изделий, а второго 510 изделий, то максимальная прибыль составит:

х0 = 17 510 + 26 480 = 21150

3.1.2 Графический метод

Пусть предприятие планирует выпустить х изделий Р1, а тогда у единиц изделий Р2.

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

5х + 8у ? 6390

4х + 9у ? 6750

4х + 5у ? 4440

х ? 0; у ? 0

Целевая функция х0 = 17х + 26у (max)

Переходим от системы неравенств к системе равенств

5х + 8у = 6390 (1)

4х + 9у =6750 (2)

4х + 5у = 4440 (3)

х=0 (4)

у=0 (5)

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

1) 5х + 8у= 6390; у =

2)4х + 9у = 6750; 9у = 6750 - 4х; у =

3) 4х + 5у = 4440; 5у = 4440 - 4х; у =

Область допустимых значений решений пятиугольника ABCDE (в нем ищем max или min) х0 = 17х + 26у; (17;26); 17х + 26у = С; С = 0; 17х = -26у;

(l)

Проведем прямую l параллельно самой себе вдоль и достигнем точки, в которой последний раз наша прямая пересекает область значений (max) получаем точку D. Находим координаты точки D.

4х + 5у = 4440 (-5)

5х + 8у = 6390 (4)

-20х - 25у = -22200

20х + 32у = 25560

7у = 3360;

у = 480;

4х + 5у = 4440;

4х + 5480 = 4440;

4х = 4440 - 2400;

4х = 2040;

х = 510

Заключение

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

- решать и преобразовывать матрицы СЛАУ

- находить производные различных функций

- решать приделы

- изучили дифференциальное и интегральное исчисления

- решать задачи по теории вероятности

- решать задачи различного типа с помощью аналитического и графического метода

- решать: задачи симплекс-методом; транспортные задачи; модели Леонтьева.

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

динамическое программирование дифференциальное интегральное исчисление

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

1. Письменный Д.Т Конспекты лекций по высшей математике - 9-e изд. - Айрис-пресс, 2009. - 608 с.

2. Вентцель Е.С. "Элементы динамического программирования" М.: Наука, 2002. - 176с.

3. Дифференциальное и интегральное исчисления. В 2т. Т.2_Пискунов Н.С_2003 -560 с.

4. Савицкая, Г.В. Анализ хозяйственной деятельности предприятий АПК: учеб.пособие / Г.В. Савицкая. - 5-е изд., испр. и доп. - Мн. : Новое знание, 2005. - 390 с.

5. Солодовников, А.С. Математика в экономике: Учебник / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов: В 3-х ч. Ч. 1. - М.: Финансы и статистика, 1998. - 111 с.

6. http://bse.sci-lib.com/article079816.htmlhttp://bse.sci-lib.com/article079816.html

7. http://www.aup.ru/books/m157/4_3_3.htm // Административно-управленческий портал //http://www.aup.ru/books/m157/4_3_3.htm // Административно-управленческий портал //

Размещено на Allbest.ru