Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.:Высшая школа, 1986.

2. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем. – М.: Финансы и статистика, 2005.

3. Вагнер Г. Основы исследования операций. М.: Мир, 1972.

4. Исследование операций в экономике/Под ред. Кремер Н.Ш.. – М.: ЮНИТИ, 2003.

5. Экономико-математические методы и модели/Под ред С.И.Макарова. – М.: КНОРУС, 2007.

6. Невежин В.П. Кружилов С.И. Сборник задач по курсу «Экономико-математическое моделирование». – М.: ОАО «Издательский Дом «Городец», 2005.

7. Таха Х.А. Введение в исследование операций. – М.: Издательский дом «Вильямс», 2001.

Содержание

Министерство образования Российской Федерации 1

Математическое программирование. 1

Учебное пособие 1

по изучению дисциплины «Математика» 1

Чебоксары 2008 1

Рецензенты: 2

Обсуждено 2

ВВЕДЕНИЕ 3

1. Целочисленное программирование 4

1.1. Метод Гомори 5

Алгоритм метода Гомори 5

Неравенство 6

1.3 Задачи для самостоятельной работы 15

2. Теория игр 18

2.1. Основные положения теории игр 18

2.2. Решение матричной игры в чистых стратегиях 21

2.4. Игра 22 29

Откуда . Оптимальная стратегия S_в=. 38

2.5. Сведение матричной игры к задаче линейного программирования 39

2.6. Игры с природой 45

1. Критерия Бейеса-Лапласа. 45

2. Критерия Лапласа. 46

3. Критерий Вальда. (минимаксный или максиминный) 46

4. Критерия минимального риска Сэвиджа; 47

5. Критерия Гурвица. 48

По критерию Лапласа оптимальной является стратегия 50

​ 3.1 Линейный межотраслевой баланс (Модель Леонтьева) 55

3.2. Задачи для самостоятельной работы 62

1.Найти объем валового выпуска продукции, при котором конечное потребление достигнет уровня ( 70, 40, 50). 62

Производящие отрасли 62

Прямые межотраслевые потоки 62

Конечные 62

Продукт 62

1 62

2 62

3 62

4 62

1 62

30 62

30 62

50 62

35 62

60 62

2 62

25 62

50 62

40 62

42 62

25 62

3 62

30 62

40 62

35 62

50 62

35 62

4 62

30 62

50 62

50 62

35 62

40 62

2. Найти объем валового выпуска продукции, при котором конечное потребление достигнет уровня ( 50, 30, 45, 60). 62

Производящие отрасли 62

Прямые межотраслевые потоки 62

Конечные 62

Продукт 62

1 62

2 62

3 62

4 62

1 63

25 63

30 63

49 63

35 63

47 63

2 63

36 63

43 63

41 63

42 63

25 63

3 63

42 63

40 63

32 63

50 63

32 63

4 63

30 63

51 63

48 63

35 63

40 63

3. Найти объем валового выпуска продукции, при котором конечное потребление достигнет уровня ( 30, 55, 70, 50). 63

Производящие отрасли 63

Прямые межотраслевые потоки 63

Конечные 63

Продукт 63

1 63

2 63

3 63

4 63

1 63

83 63

93 63

51 63

35 63

28 63

2 63

67 63

46 63

72 63

44 63

46 63

3 63

47 63

40 63

35 63

57 63

57 63

4 63

66 63

54 63

46 63

35 63

41 63

4. Найти объем валового выпуска продукции, при котором конечное потребление достигнет уровня ( 50, 100, 44, 80). 63

Производящие отрасли 63

Прямые межотраслевые потоки 63

Конечные 63

Продукт 63

1 63

2 63

3 63

4 63

1 63

44 63

63 63

79 63

48 63

48 63

2 63

11 63

74 63

95 63

71 63

71 63

3 63

73 63

81 63

43 63

57 63

27 63

4 63

55 63

59 63

57 63

58 63

77 63

4. Нелинейное программирование 63

4.1 Постановка задача нелинейного программирования 63

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

Нелинейное программирование – это математический аппарат для поиска экстремума нелинейных функций при наличии ограничений. 64

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

найти (4.1) 64

при условии 64

(4.2) 64

где или - нелинейные функции переменных . 64

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

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

Решение задачи нелинейного программирования состоит в определении оптимального плана (вектора) такого, что на множестве Х векторов . 64

Если множество Х выпукло и функция f выпукла на Х, то задача является задачей выпуклого программирования. 65

Если f – выпуклая функция, то (-f) называется вогнутой функцией. При этом - точка минимума f является точкой максимума (-f) и наоборот. Так как , то достаточно рассмотреть задачи на минимум. 65

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

1. Определение потребности в ресурсах с целью максимизации выпуска продукции для производственной функции f. 65

65

2. Определение потребности в ресурсах с целью максимизации прибыли: 65

65

где - цена продукта, - вектор цен ресурсов. 65

3. Распределение ресурсов между отраслями, производящими потребительские продукты, с целью максимизации уровня их потребления , где - вектор потребления продуктов: 65

65

Предполагается, что и - вогнутые функции. 65

4.2 Решение задач нелинейного программирования с ограничениями-равенствами 65

Основными среди точных методов решения задач нелинейного программирования данного типа является метод множителей Лагранжа. 66

Теорема. Если - точка локального минимума дифференцируемой функции , то при ограничениях , удовлетворяющих некоторому условию регулярности, для функции Лагранжа 66

(4.3.) 66

существует вектор множителей Лагранжа такой, что 66

, (4.4) 66

. (4.5.) 66

Замечания. 1.Множители Лагранжа имеют произвольные знаки. 66

2. Если f ивыпуклы, то необходимые условия (4.4.), (4.5.) являются и достаточными для существования решения задачи (4.1.), (4.2.). 66

3. Требование регулярности связано с существованием решения системы (4.4.), (4.5.). 66

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

Пусть требуется найти 67

(4.6.) 67

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

(4.7.) 67

Составим функцию Лагранжа следующего вида: 67

67

Для того чтобы вектор являлся решением задачи (4.6.), (4.7.) , необходимо существование такого вектора , чтобы пара векторов удовлетворяла системе уравнений: 67

67

Пример 11. В двух цехах предприятия нужно изготовить 20 изделий некоторой продукции. Затраты, связанные с изготовлением х₁ изделий в 1-м цехе, равны руб., а затраты при изготовлении х₂ изделий во 2-м цехе равны руб. Составить план производства изделий в двух цехах с минимальными затратами. 67

Решение. Математическая модель задачи: 68

68

Запишем функцию Лагранжа 68

68

Для данной точки получим в точке экстремума: 68

68

68

Исследуем характер функции f в окрестности точки , для этого находим 68

68

Так как и , то функция выпукла, и точка - точка минимума. 68

Ответ: Оптимальный план изделий. 68

4.3. Решение задач нелинейного программирования с ограничениями-неравенствами 69

Имеется задача нелинейного программирования с ограничениями-неравенствами: 69

(4.8) 69

при условиях 69

(4.9) 69

Допустим, что функции и все , выпуклы по Х. Такая задача носит название выпуклого программирования и множество решений , определяемое условиями (4.9), является выпуклым. Для задачи (4.8), (4.9) справедлива теорема Куна-Таккера. 69

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

(4.10) 69

(4.11) 69

Последнее условие называется условием дополняющей нежесткости. 69

Если функции и - выпуклы по Х, то условия оптимальности (4.10), (4.11) будут не только необходимыми, но и достаточными. В этом случае условие существования решения Х и , удовлетворяющего (4.10), (4.11), которое называют условием регулярности, примет вид 70

для всех . 70

Пользуясь теоремой Куна-Таккера, задачу нелинейного программирования решают следующим образом. 70

Шаг 1. Составляют функцию Лагранжа 70

70

Шаг 2. Составляют систему уравнений вида (4.10), (4.11). 70

Шаг 3. Находят ее решение . В отличие от задачи с ограничениями-равенствами вектор должен в этом случае удовлетворять условию неотрицательности. 70

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

Основные положения теории могут быть легко распространены на этот случай. Тогда к ограничению (4.9) следует добавить следующее ограничение: 70

(4.12) 70

Это ограничение в общем виде можно записать как 70

. 70

Задача представлена в каноническом виде. Применим к ней теорему Куна-Таккера, для чего составим функцию Лагранжа 70

(4.13) 70

где - множители, связанные с ограничениями (4.12). Условия теоремы Куна-Таккера выглядят так: 71

71

Последнее соотношение представляет собой условия дополняющей нежесткости для ограничений неотрицательности. 71

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

71

при условиях: 71

, 71

а функции и дифференцируемы и выпуклы по Х. Вектор является оптимальным решением задачи тогда и только тогда, когда существует такой вектор , что пара является седловой точкой функции Лагранжа , т.е. выполняются следующие условия: 71

71

Пример 12. Предприятие выпускает два вида изделий А и Б. Норма расхода на производство каждого вида изделий приведены в таблице. При этом известно, что сырья имеется 12 т, а оборудования - 30 станко-часов. 72

Ресурсы 72

Норма расхода ресурсов 72

на 1 изделие 72

Запас 72

ресурсов 72

Изделие А 72

Изделие Б 72

Сырье, т 72

3 72

2 72

12 72

Оборудование, станко-час 72

5 72

6 72

30 72

Оптовые цены, руб. 72

9 72

7 72

Определить оптимальный план реализации продукции, если себестоимость одного изделия соответственно равна руб. и руб., где и - план выпуска изделий вида А и Б. 72

Решение. 72

Математическая запись задачи. Прибыль предприятия при плане равна 72

. 72

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

72

72

Функция Лагранжа получит вид 72

. 73

Для данной функции в точке экстремума получим: 73

73

При решении данной системы уравнений рассмотрим четыре случая. 73

1. Этот случай соответствует предположению о том, что - внутренняя точка Х. Тогда 73

73

Откуда 73

Но эта точка не принадлежит Х, так как условие (4.9) не выполняется, т.е. 73

2. Из и условия (4.8) следует, что точка лежит на границе . Получаем систему линейных уравнений вида 73

73

Решив данную систему уравнений, получаем 74

74

3. Случай невозможен. 74

4. Случай невозможен. 74

Ответ. Оптимальный план изделий. 74

4.4. Задачи для самостоятельной работы 74

1. Определить методом множителей Лагранжа условные экстремумы функций: 74

1) при условии , 74

2) при условии . 74

2. Найти оптимальный набор продуктов , максимизирующий функцию полезности при заданных ценах и продуктов и и доходе М. 74

3. Предприятие выпускает изделия двух видов А₁ и А₂, при изготовлении которых используется сырье I и II. Известны запасы сырья , нормы его расхода на единицу изделия , оптовые цены за единицу изделия и себестоимость . Составить план выпуска изделий, дающий предприятию максимальную прибыль. 74

4. Найти оптимальное распределение ресурсов объемом не более 100 единиц между 4 потребителями, если прибыль при выделении i-му потребителю единиц ресурса равна млн. руб. При . 74

5. Динамическое программирование 75

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

Решение задач методом динамического программирования проводится на основе сформулированного Р.Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения. 75

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

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

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

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния S и переменную управления Х. Переменная Sопределяет, в каких состояниях может оказаться система на данном k-м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Применение управления X на k-м шаге приносит некоторый результат и переводит систему в некоторое новое состояние . Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление такое, что результат, который достигается за шаги с k-го по n-й оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана и зависит от номера шага k и состояния системы S. 76

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

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

В общем виде задача динамического программирования формулируется следующим образом: требуется определить такое управление , переводящее систему из начального состояния в конечное состояние , при котором целевая функция принимает наибольшее (наименьшее) значение. 77

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

1) задача оптимизации формулируется как конечный многошаговый процесс управления; 77

2) целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага: ; 77

3) выбор управления на каждом шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги (нет обратной связи); 77

4) состояние системы после каждого шага управления зависит только от предшествующего состояния системы и этого управляющего воздействия (отсутствие последействия) и может быть записано в виде уравнения состояния: ; 77

5) на каждом шаге управления зависит от конечного числа управляющих переменных, а состояние системы зависит от конечного числа параметров; 77

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

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

Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге: 78

. 78

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления Х. 78

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S₀), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге , применение которого переведет систему в состояние , зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага. 78

5.1 Задача об оптимальном распределении инвестиций. 79

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

79

79

… 79

79

… 79

79

79

79

79

… 79

79

… 79

79

79

79

79

… 79

79

… 79

79

79

… 79

… 79

… 79

79

… 79

… 79

79

79

79

… 79

79

… 79

79

где - прибыль i-го предприятия при вложении в него средств. 79

Математическая модель задачи будет следующей. 79

Определить вектор , удовлетворяющий условиям 79

, 79

И обеспечивающий максимум целевой функции 79

. 79

Процесс оптимизации разобьем на n шагов, на k-м шаге будем оптимизировать инвестирование не всех предприятий, а только предприятий с k-го по n-е. При этом на них расходуются не все средства, а некоторая меньшая сумма , которая и будет являться переменной состояния системы. Переменной управления на k-м шаге назовем величину средств, вкладываемых в k-е предприятие. В качестве функции Беллмана на k-м шаге в этой задаче можно выбрать максимально возможную прибыль, которую можно получить с предприятий с k-го по n-е при условии, что на их инвестировании осталось средств. При вложении в k-е предприятие средств получим прибыль , а система к (k+1)-му шагу перейдет в состояние , т.е. на инвестирование предприятий с (k+1)-го до n-го останется средств. 79

Таким образом, на первом шаге условной оптимизации при k=n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может выделяться количество средств , . Чтобы получить максимум прибыли с этого последнего предприятия, надо вложить в него все эти средства, т.е. и . 80

На каждом из последующих шагов для вычисления функции Беллмана следует использовать результаты предыдущего шага. Максимально возможная прибыль, которая может быть получена предприятиями с k-го по n-е, равна 80

, . 80

Максимум этого выражения достигается на некотором значении , которое и является оптимальным управлением на k-м шаге для состояния системы . Аналогично можно отыскать функции Беллмана и оптимальные управления вплоть до шага . 80

Функция Беллмана представляет собой максимально возможную прибыль со всех предприятий (с 1-го по n-е), а значение , на котором достигается максимум прибыли, является оптимальным количеством средств, которое необходимое вложить в 1-е предприятие. Для всех последующих шагов вычисляется величина и оптимальным управлением на k-м шаге является то значение , которое доставляет максимум прибыли при соответствующем состоянии системы . 81

Пример 13. Распределить T=40 ден. ед. по трем предприятиям с целью получения максимальной суммарной прибыли. Прибыль с предприятий задается таблицей 81

Х 81

81

81

81

0 81

0 81

0 81

0 81

10 81

17 81

21 81

19 81

20 81

23 81

25 81

24 81

30 81

34 81

30 81

29 81

40 81

40 81

37 81

32 81

Решение: 81

I этап. Условная оптимизация 81

I-й шаг. k=3. Предполагаем, что все средства 40 ден. ед. переданы на инвестирование третьего предприятия. В этом случае максимальная прибыль составит . 81

Таблица 2. 81

81

81

81

81

0 82

10 82

20 82

30 82

40 82

0 82

0 82

- 82

- 82

- 82

- 82

0 82

0 82

10 82

- 82

19 82

- 82

- 82

- 82

19 82

10 82

20 82

- 82

- 82

24 82

- 82

- 82

24 82

20 82

30 82

- 82

- 82

- 82

29 82

- 82

29 82

30 82

40 82

- 82

- 82

- 82

- 82

32 82

32 82

40 82

2-й шаг. k=2. Определяем оптимальную стратегию инвестирования во второе и третье предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид 82

. 82

На его основе рассчитываются данные 82

Таблица 3. 82

82

82

82

82

0 82

10 82

20 82

30 82

40 82

0 82

0+0 82

- 82

- 82

- 82

- 82

0 82

0 82

10 82

0+19 82

21+0 82

- 82

- 82

- 82

21 82

10 82

20 82

0+24 82

21+19 82

25+0 82

- 82

- 82

40 82

10 82

30 82

0+29 82

21+24 82

25+19 82

30+0 82

- 82

45 82

10 82

40 82

0+32 82

21+29 82

25+24 82

30+19 82

37+0 82

50 82

10 82

3-й шаг. k=1. Определяем оптимальную стратегию инвестирования в первое и остальные предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид 82

. 82

На его основе находим данные. 82

Таблица 4. 83

83

83

83

83

0 83

10 83

20 83

30 83

40 83

0 83

0+0 83

- 83

- 83

- 83

- 83

0 83

0 83

10 83

0+21 83

17+0 83

- 83

- 83

- 83

21 83

0 83

20 83

0+40 83

17+21 83

23+0 83

- 83

- 83

40 83

0 83

30 83

0+45 83

17+40 83

23+21 83

34+0 83

- 83

57 83

10 83

40 83

0+50 83

17+45 83

23+40 83

34+21 83

40+0 83

63 83

20 83

II этап. Безусловная оптимизация 83

I-й шаг. По данным таблицы 4 максимальный доход при распределении 40 ден. ед. между тремя предприятиями составляет . При этом первому предприятию нужно выделить ден.ед. 83

2-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего предприятий: 83

ден. ед. 83

По данным таблицы 3 находим, что оптимальный вариант распределения денежных средств размером 20 ден. ед. между вторым и третьим предприятиями составляет ден. ед. при выделении второму предприятию ден. ед. 83

3-шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю третьего предприятия: 83

ден. ед. 83

Из таблицы 2 находим и ден. ед. 83

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

ден. ед. 83

5.2 Задача инвестирования 84

Предположим, что в начале каждого из следующих n лет необходимо сделать инвестиции Р₁, Р₂, …,Р_n. Вы имеет возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент r₁, а второй – r₂. Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы. Премиальные меняются от года к году, и для i-го года равны и в первом и втором банках соответственно. Они выплачиваются в конце года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находится там до конца рассматриваемого периода. Необходимо разработать стратегию инвестиций на следующие n лет. 84

Элементы модели динамического программирования таковы. 84

1. Этапы i представляется порядковым номером года i, i=1, 2, …, n. 84

2. Вариантами решения на i-м этапе (для i-го года) являются суммы и инвестиций в первый и второй банк соответственно. 84

3. Состоянием на i-м этапе является сумма денег на начало i-го года, которые могут быть инвестированы. 84

По определению . Следовательно, 84

84

(5.1) 84

где Сумма денег , которые могут быть инвестированы, включает лишь новые деньги и премиальные проценты за инвестиции, сделанные на протяжении (i-1)-го года. 85

Пусть - оптимальная сумма инвестиций для интервала от i-го до n-го года при условии, что в начале i-го года имеется денежная сумма . Обозначим через накопленную сумму к концу n-го года при условии, что и - объемы инвестиций на протяжении i-го года в первый и второй банк соответственно, . 85

Сформулируем задачу в следующем виде: 85

Максимизировать 85

где 85

85

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

В данном случае рекуррентное уравнение для обратной прогонки в алгоритме динамического программирования имеет вид 85

85

где выражается через в соответствии с формулой (5.1), а . 85

Пример 14. Необходимо инвестировать 4000 долл. сейчас и 2000 долл. в начале каждого года, от второго до четвертого, считая от текущего года. Первый банк выплачивает годовой сложный процент 8% и премиальные на протяжении следующих четырех лет в размере 1,8; 1,7; 2,1 и 2,5% соответственно. Годовой сложный процент, предлагаемый вторым банком, на 0,2% ниже, чем предлагает первый банк, но его премиальные на 0,5% выше. Задача состоит в максимизации накопленного капитала к концу четвертого года. 86

Решение. Используя обозначения, имеем следующее. 86

долл., долл., 86

86

86

86

Этап 4. 86

86

где . 86

Функция является линейной по I₄ в области , и, следовательно, ее максимум достигается при из-за отрицательного коэффициента при I₄. Следовательно, оптимальное решение для этапа 4 может быть представлено в следующем виде. 86

Состояние 86

Оптимальное решение 86

86

86

86

1,108 86

0 86

Этап 3. 87

87

где 87

87

. 87

Следовательно, 87

87

Состояние 87

Оптимальное решение 87

87

87

87

2216+1,1909 87

0 87

Этап 2. 87

87

где 87

87

. 87

Следовательно, 87

88

Состояние 88

Оптимальное решение 88

88

88

88

4597,8+1,27996 88

88

Этап 1. 88

88

где 88

88

. 88

Следовательно, 88

88

Состояние 88

Оптимальное решение 88

88

88

88

7157,7+1,38349 88

88

При вычислениях в обратном направлении получаем следующее. 88

долл., 89

долл., 89

долл. 89

Следовательно, оптимальное решение будет записано следующим образом. 89

Год 89

Оптимальное 89

решение 89

Решение, принимаемое 89

инвестором 89

Накопления 89

1 89

89

Инвестировать долл. 89

в первый банк 89

долл. 89

2 89

89

Инвестировать долл. 89

в первый банк 89

долл. 89

3 89

89

Инвестировать долл. 89

во второй банк 89

долл. 89

4 89

89

Инвестировать долл. 89

во второй банк 89

долл. 89

Всего 89

12691,7 долл. 89

5.3 Задачи для самостоятельной работы 89

1. Имеются четыре предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятиях в зависимости от выделенных средств Х представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции. 89

Х 90

90

90

90

90

20 90

14 90

19 90

33 90

41 90

40 90

48 90

45 90

59 90

81 90

60 90

37 90

38 90

33 90

52 90

80 90

48 90

58 90

77 90

73 90

100 90

64 90

67 90

61 90

92 90

2. Фермер имеет 2 овец. В конце года он принимает решение, сколько овец продать и сколько оставить. Прибыль от продажи одной овцы в 1-й год равна 100 долл., во 2-й - 130 долл., в 3-й год – 120 долл. Количество овец в конце каждого года удваивается. Фермер планирует в конце третьего года полностью продать овец. 90

3. Найти оптимальное распределение средств между 3 предприятиями при условии, что прибыль , полученная от каждого предприятия, является функцией от вложенных в него средств х. Вложения кратны 1, а функции заданы в таблице. Начальные средства равны 9 ден ед. 90

х 90

1 90

2 90

3 90

4 90

5 90

6 90

7 90

8 90

9 90

90

5 90

9 90

12 90

14 90

15 90

18 90

20 90

24 90

27 90

90

7 90

9 90

11 90

13 90

16 90

19 90

21 90

22 90

25 90

90

6 90

10 90

13 90

15 90

16 90

18 90

21 90

22 90

25 90

6. Контрольные задания 90

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

Х 103

103

103

103

103

20 103

16 103

14 103

15 103

15 103

40 103

30 103

32 103

36 103

25 103

60 103

49 103

50 103

45 103

22 103

80 103

51 103

48 103

57 103

36 103

100 103

72 103

60 103

70 103

51 103

Х 103

103

103

103

103

20 103

10 103

14 103

14 103

19 103

40 103

16 103

14 103

15 103

15 103

60 103

30 103

32 103

36 103

25 103

80 103

45 103

43 103

47 103

36 103

100 103

60 103

50 103

55 103

53 103

Х 103

103

103

103

103

20 103

42 103

40 103

25 103

24 103

40 103

34 103

52 103

36 103

45 103

60 103

47 103

50 103

46 103

32 103

80 103

51 103

48 103

57 103

36 103

100 103

62 103

60 103

67 103

54 103

Х 103

103

103

103

103

20 103

22 103

17 103

18 103

35 103

40 103

43 103

39 103

33 103

42 103

60 103

49 103

51 103

45 103

55 103

80 103

61 103

75 103

57 103

68 103

100 103

82 103

79 103

67 103

81 103

Х 103

103

103

103

103

20 103

9 103

11 103

14 103

8 103

40 103

19 103

14 103

20 103

15 103

60 103

30 103

32 103

16 103

25 103

80 103

36 103

30 103

38 103

33 103

100 103

48 103

44 103

52 103

36 103

Х 103

103

103

103

103

20 103

12 103

24 103

10 103

20 103

40 103

21 103

17 103

16 103

25 103

60 103

20 103

21 103

25 103

22 103

80 103

30 103

38 103

22 103

23 103

100 103

42 103

35 103

18 103

41 103

Х 103

103

103

103

103

20 103

19 103

14 103

20 103

25 103

40 103

36 103

32 103

36 103

53 103

60 103

51 103

52 103

47 103

66 103

80 103

72 103

61 103

72 103

70 103

100 103

81 103

79 103

80 103

84 103

Х 104

104

104

104

104

20 104

14 104

17 104

22 104

20 104

40 104

26 104

20 104

21 104

33 104

60 104

35 104

32 104

37 104

46 104

80 104

52 104

61 104

67 104

30 104

100 104

61 104

72 104

58 104

42 104

Х 104

104

104

104

104

20 104

19 104

48 104

42 104

45 104

40 104

36 104

32 104

56 104

53 104

60 104

54 104

62 104

67 104

66 104

80 104

72 104

81 104

82 104

70 104

100 104

88 104

95 104

98 104

84 104

Х 104

104

104

104

104

20 104

12 104

15 104

11 104

10 104

40 104

23 104

27 104

21 104

19 104

60 104

30 104

29 104

34 104

36 104

80 104

42 104

46 104

45 104

47 104

100 104

58 104

61 104

58 104

54 104

Х 104

104

104

104

104

20 104

19 104

33 104

29 104

35 104

40 104

26 104

43 104

36 104

45 104

60 104

35 104

52 104

49 104

56 104

80 104

47 104

60 104

62 104

72 104

100 104

68 104

79 104

82 104

94 104

Х 104

104

104

104

104

20 104

22 104

24 104

28 104

25 104

40 104

38 104

32 104

46 104

33 104

60 104

45 104

44 104

57 104

46 104

80 104

52 104

56 104

67 104

58 104

100 104

51 104

69 104

70 104

68 104

Х 104

104

104

104

104

20 104

12 104

24 104

25 104

18 104

40 104

23 104

32 104

36 104

22 104

60 104

33 104

40 104

44 104

32 104

80 104

45 104

48 104

47 104

36 104

100 104

52 104

60 104

57 104

35 104

Х 104

104

104

104

104

20 104

6 104

4 104

5 104

8 104

40 104

107 104

12 104

16 104

15 104

60 104

24 104

25 104

24 104

22 104

80 104

21 104

24 104

27 104

31 104

100 104

32 104

30 104

37 104

45 104

Х 105

105

105

105

105

20 105

2 105

6 105

8 105

5 105

40 105

8 105

3 105

6 105

9 105

60 105

12 105

5 105

10 105

14 105

80 105

11 105

8 105

7 105

13 105

100 105

20 105

10 105

17 105

15 105

Х 105

105

105

105

105

20 105

12 105

10 105

16 105

19 105

40 105

30 105

32 105

36 105

25 105

60 105

44 105

54 105

34 105

22 105

80 105

51 105

48 105

47 105

36 105

100 105

62 105

56 105

57 105

48 105

Х 105

105

105

105

105

20 105

16 105

12 105

15 105

24 105

40 105

30 105

36 105

36 105

22 105

60 105

49 105

34 105

45 105

32 105

80 105

51 105

47 105

57 105

41 105

100 105

72 105

57 105

70 105

59 105

Х 105

105

105

105

105

20 105

12 105

14 105

15 105

13 105

40 105

36 105

32 105

36 105

33 105

60 105

34 105

50 105

45 105

35 105

80 105

47 105

48 105

57 105

37 105

100 105

57 105

60 105

70 105

47 105

Х 105

105

105

105

105

20 105

29 105

24 105

22 105

25 105

40 105

36 105

33 105

36 105

35 105

60 105

48 105

22 105

44 105

46 105

80 105

52 105

46 105

53 105

49 105

100 105

58 105

39 105

68 105

38 105

Х 105

105

105

105

105

20 105

9 105

14 105

10 105

15 105

40 105

26 105

22 105

23 105

18 105

60 105

35 105

28 105

27 105

16 105

80 105

32 105

38 105

32 105

20 105

100 105

41 105

46 105

48 105

34 105

Х 105

105

105

105

105

20 105

12 105

26 105

31 105

32 105

40 105

49 105

30 105

46 105

45 105

60 106

45 106

59 106

64 106

56 106

80 106

82 106

56 106

82 106

87 106

100 106

86 106

89 106

90 106

84 106

Х 106

106

106

106

106

20 106

11 106

24 106

12 106

35 106

40 106

26 106

22 106

28 106

33 106

60 106

31 106

32 106

37 106

36 106

80 106

42 106

41 106

47 106

40 106

100 106

58 106

59 106

53 106

54 106

Х 106

106

106

106

106

20 106

12 106

10 106

16 106

19 106

40 106

26 106

22 106

28 106

33 106

60 106

51 106

52 106

48 106

56 106

80 106

42 106

41 106

47 106

40 106

100 106

68 106

71 106

58 106

54 106

Х 107

107

107

107

107

20 107

12 107

14 107

20 107

29 107

40 107

36 107

32 107

36 107

33 107

60 107

34 107

42 107

27 107

46 107

80 107

49 107

56 107

32 107

50 107

100 107

55 107

59 107

38 107

44 107

Х 107

107

107

107

107

20 107

11 107

14 107

12 107

15 107

40 107

24 107

32 107

39 107

25 107

60 107

34 107

50 107

40 107

22 107

80 107

27 107

48 107

37 107

36 107

100 107

37 107

60 107

47 107

57 107

МЕТОДИЧЕСКОЕ ИЗДАНИЕ

Санаева Татьяна Александровна