Динамическое и линейное программирование

Государственный университет управления

Институт заочного обучения

Специальность – менеджмент

Кафедра прикладной математики

КУРСОВОЙ ПРОЕКТ

по дисциплине: «Прикладная математика»

Выполнил студент 1-го курса

Группа № УП4-1-98/2

Студенческий билет №

Москва, 1999 г.

Содержание

TOC \t “Заголовок 1;2;Заголовок 4;1” 1. Линейная производственная
задача PAGEREF _Toc465690998 \h 3

2. Двойственная задача PAGEREF _Toc465690999 \h 7

3. Задача о «Расшивке узких мест производства» PAGEREF _Toc465691000
\h 9

4. Транспортная задача PAGEREF _Toc465691001 \h 12

5. Распределение капитальных вложений PAGEREF _Toc465691002 \h 17

6. Динамическая задача управления запасами PAGEREF _Toc465691003 \h
21

7. Анализ доходности и риска финансовых операций PAGEREF _Toc465691004
\h 26

8. Оптимальный портфель ценных бумаг PAGEREF _Toc465691005 \h 28

1. Линейная производственная задача

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

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

Примем следующие обозначения:

максимизирующую прибыль:

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

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

удельной прибыли:

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

максимизирующую прибыль:

(1.1)

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

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

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

Тогда вместо системы неравенств (1.2), получим систему линейных
алгебраических уравнений:

(1.3)

где среди всех решений, удовлетворяющих условию неотрицательности:

надо найти решение, при котором функция (1.1) примет наибольшее
значение. Эту задачу будем решать методом последовательного улучшения
плана – симплексным методом.

Воспользуемся тем, что правые части всех уравнений системы (1.3)
неотрицательны, а сама система имеет предпочитаемый вид – дополнительные
переменные являются базисными. Приравняв к нулю свободные переменные x1,
x2, x3, x4, получаем базисное неотрицательное решение:

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

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

Оно соответствует первому уравнению в системе (1.3), и показывает какое
количество изделий третьего вида предприятие может изготовить с учетом
объемов сырья первого вида. Следовательно, в базис вводим неизвестную
x3, а исключаем от туда неизвестную x5. Тогда принимаем первое уравнение
в системе (1.3) за разрешающее, а разрешающим элементом будет a13=6.

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

Полный процесс решения приведен в таблице 1, где в последней строке
третьей таблицы нет ни одного отрицательного относительного оценочного
коэффициента

т.е. выполняется критерий оптимальности для максимизируемой
функции (1.1).

x3 – разрешающая переменная

x3 ( в базис.

первая строка – разрешающая

x5 ( из базиса.

x1 – разрешающая переменная

вторая строка – разрешающая

1290

0 7 0 9 6 3 0

При этом каждый элемент симплексной таблицы имеет определенный
экономический смысл. Например, во второй симплексной таблице:

единицы сырья третьего вида.

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

Таким образом, получили производственную программу:

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

При этом первый и второй ресурсы будут использованы полностью, т.е.
первый и второй ресурсы образуют «узкие места производства»:

а третий ресурс будет иметь остаток:

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

а т.к. из третьей симплексной таблицы:

выполняется.

2. Двойственная задача

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

Например, в предыдущем п.1. рассмотрена линейная производственная задача
по выпуску четырех видов продукции с использованием трех видов ресурсов
по заданным технологиям. Предположим, некий предприниматель,
занимающийся производством других видов продукции с использованием трех
таких же видов ресурсов, предлагает «уступить» ему все имеющиеся ресурсы
и обещает платить y1 денежных единиц за каждую единицу первого ресурса,
y2 денежных единиц за каждую единицу второго ресурса и y3 денежных
единиц за каждую единицу третьего ресурса. Возникает вопрос: при каких
значениях y1, y2, y3 можно согласиться с предложением этого
предпринимателя.

удельной прибыли имели вид:

значит, для производства, например, первого вида продукции, предприятие
должно затратить 3 единицы ресурса первого вида, 4 единицы ресурса
второго вида и 4 единицы ресурса третьего вида, за что оно получит
прибыль 30 денежных единиц. Следовательно, согласиться с предложением
предпринимателя можно, если он заплатит не меньше, т.е. в ценах y1, y2,
y3 это условие будет иметь вид:

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

денежных единиц.

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

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

минимизирующий общую оценку всех ресурсов

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

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

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

, тогда:

. Тогда переходим к новой системе уравнений:

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

тогда общая оценка всех ресурсов равна:

То же самое решение значений двойственных оценок содержится в последней
строке симплексной таблицы 1 и имеет определенный экономический смысл:

Показывает, что добавление одной единицы второго ресурса обеспечит
прирост прибыли в 3 денежные единицы.

Одновременно технологические оценки из той же строки симплексной
таблицы:

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

3. Задача о «Расшивке узких мест производства»

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

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

Для примера возьмем данные и результаты вычислений из п.1. и п.2., где
определено, что первый и второй ресурс используются полностью, и,
соответственно, именно их нужно заказывать дополнительно. Но в таких
объемах, чтобы сохранить структуру ранее найденной программы
производства, и с условием, что от поставщика можно получить
дополнительно не более одной трети первоначально выделенного объема
ресурса любого вида. Следовательно, задача сводиться к нахождению
объемов приобретения дополнительных ресурсов, удовлетворяющих указанным
условиям, и вычислению дополнительной возможной прибыли.

– вектор дополнительных объемов ресурсов:

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

, то задача состоит в том, чтобы найти вектор:

максимизирующий суммарный прирост прибыли:

(3.1)

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

(3.2)

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

(3.3)

причем дополнительные объемы ресурсов, по смыслу задачи, не могут быть
отрицательными, т.е.:

(3.4)

Т.к. неравенства (3.2) и (3.3) должны выполняться одновременно, то их
можно переписать в виде одной системы неравенств:

(

(3.5)

Таким образом, получена задача линейного программирования:
максимизировать функцию (3.1) при условиях (3.4) и (3.5).

Эту задачу с двумя переменными можно решить графически:

График 1.

На графике видно, что система линейных неравенств (3.4), (3.5), образует
область допустимых решений, ограниченную прямыми:

пересечения прямых:

Координаты этой точки и определяют искомые объемы дополнительных
ресурсов. Следовательно, программа «расшивки узких мест производства
имеет вид:

и прирост прибыли составит:

Сводка результатов по пунктам 1-3 приведена в таблице 2.

0 7 0 9

4. Транспортная задача

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

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

Примем следующие обозначения:

Количество груза, планируемого к перевозке от i-го пункта отправления
в j-ый пункт назначения

Тогда, при наличии баланса производства и потребления:

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

найти план перевозок

минимизирующий общую стоимость всех перевозок

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

(4.1)

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

(4.2)

причем, по смыслу задачи

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

Тогда:

Откуда следует:

объемов продукта, необходимых пунктам потребления, имеют вид:

Тогда получается, что общий объем продукта в пунктах производства

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

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

единиц,

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

, первая транспортная таблица и потенциалы имеют вид:

Т.к. наибольшая положительная оценка всех свободных клеток транспортной
таблицы, соответствует клетке 14, то строим цикл пересчета: 14-13-23-24
и производим перераспределение поставок вдоль цикла пресчета:

Т.к. теперь наибольшая положительная оценка всех свободных клеток
транспортной таблицы, соответствует клетке 22, то строим цикл пересчета:
22-12-14-24 и производим перераспределение поставок вдоль цикла
пресчета:

Т.к. наибольшая положительная оценка всех свободных клеток транспортной
таблицы, теперь соответствует клетке 21, то строим цикл пересчета:
21-11-14-24 и производим перераспределение поставок вдоль цикла
пресчета:

EMBED Equation.3

Т.к. наибольшая положительная оценка всех свободных клеток транспортной
таблицы, соответствует клетке 33, то строим цикл пересчета:
33-23-21-11-14-34 и производим перераспределение поставок вдоль цикла
пресчета:

Теперь наибольшая положительная оценка всех свободных клеток
транспортной таблицы, соответствует клетке 25, отсюда строим цикл
пересчета: 25-23-33- и производим перераспределение поставок вдоль этого
цикла пресчета:

Находим оценки всех свободных клеток таблицы:

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

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

5. Распределение капитальных вложений

Задача о распределении капитальных вложений – это нелинейная задача
распределения ресурсов между предприятиями одного производственного
объединения или отрасли.

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

Примем следующие обозначения:

, при которых значение суммарного прироста прибыли или мощности всей
отрасли:

принимают только целые неотрицательные значения, т.е.:

, чтобы увеличение прибыли или мощности k предприятий было бы
максимальным, т.е.:

Если же k=1, то:

приведены в таблице 3:

100 30 30 72* 88 101 110 119 125

200 49 49 91* 107* 120 129 138

300 63 63 105 121* 134* 143*

400 68 68 110 126 139

500 69 69 111 127

600 65 65 107

700 60 60

100 22 22 64 94* 113* 129* 143 156

200 37 37 79 109 128 144* 158*

300 49 49 91 121 140 156

400 59 59 101 131 150

500 68 68 110 140

600 76 76 118

700 82 82

, т.е. заполнить только одну диагональ:

100 50

194

200 68

197*

300 82

195

400 92

186

500 100

172

600 107

149

700 112 112

Наибольшее число этой диагонали показывает максимально возможный
суммарный прирост прибыли всех четырех предприятий данного
производственного объединения, при общей сумме капитальных вложений в
700 денежных единиц, т.е.:

денежных единиц

причем четвертому предприятию должно быть выделено:

денежных единиц

Тогда третьему предприятию должно быть выделено (см. табл. 7.):

денежных единиц

второму предприятию должно быть выделено (см. табл. 5.):

денежных единиц

на долю первого предприятия остается:

денежных единиц

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

которое обеспечивает производственному объединению наибольший возможный
прирост прибыли:

денежных единиц

6. Динамическая задача управления запасами

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

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

Примем следующие обозначения:

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

и минимизируют суммарные затраты за весь планируемый период:

должна удовлетворять ограничениям:

Если при этом функция затрат на хранение и производство изделий в j-ом
месяце имеет вид:

, где

если ввести обозначение:

) 1 1 1

Предполагается, что затраты на приобретение продукции составляют 5 руб.
за каждую единицу для первых трех единиц и 7 руб. за каждую
дополнительную единицу, т.е.

, тогда:

может принимать значения на отрезке:

соотношением:

, поэтому:

, тогда:

приведены в таблице 10.:

, тогда:

, где:

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

, который принимает значения на отрезке:

соотношением:

Тогда:

, т.е.:

эти значения указываем в результирующей таблице 11.

Аналогично:

Таким образом:

, тогда:

, где:

может изменяться в пределах:

связан с объемом производства соотношением:

Тогда:

Следовательно, получаем:

, т.е.:

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

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

, следовательно, из таблицы 11.:

, следовательно, из таблицы 10.:

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

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

7. Анализ доходности и риска финансовых операций

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

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

Т.к. среднеквадратическое отклонение:

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

, то средний ожидаемый доход каждой операции имеет вид:

, то риски каждой финансовой операции имеют вид:

каждой операции на плоскость (см. график 2.).

Тогда, чем правее точка на графике, тем более доходная операция, чем
точка выше – тем более она рисковая.

Для определения операции оптимальной по Парето, необходимо на графике
найти точку, которую не доминирует никакая другая точка.

, то из графика 2. видно, что 3-ая операция доминирует 2-ую операцию, а
1-ая операция доминирует 3-ую и 2-ую операции. Но 1-ая и 4-ая операции
несравнимы, т.к. доходность 4-ой операции больше, но и риск ее тоже
больше, чем доходность и риск 1-ой операции, следовательно, 1-я операция
является оптимальной по Парето.

, тогда:

Отсюда видно, что 1-ая финансовая операция – лучшая, а 2-ая – худшая.

8. Оптимальный портфель ценных бумаг

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

, т.е.:

Примем следующие обозначения:

Эффективность портфеля (набора) ценных бумаг

Тогда, математическое ожидание эффективности портфеля ценных бумаг:

вариация портфеля ценных бумаг:

риск портфеля ценных бумаг:

Следовательно, математическая формализация задачи формирования
оптимального портфеля ценных бумаг:

Тогда, если оптимальное решение обозначить как *, то:

Означает возможность проведения операции “short sale”, т.е.
краткосрочного вложения доли капитала в более доходные ценные бумаги

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

Пусть:

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

вариация портфеля ценных бумаг:

риск портфеля ценных бумаг:

Допустим, что задача состоит в нахождении распределения капитала, при
формировании оптимального портфеля ценных бумаг заданной эффективности,
состоящего из трех видов ценных бумаг: безрисковых эффективности 3 и
некоррелированных рисковых, с ожидаемой эффективностью 5 и 9, риски
которых равны 4 и 6, т.е.:

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

ожидаемой эффективности рисковых видов ценных бумаг имеют вид:

– двухмерный вектор-столбец, компоненты которого равны 1, т.е.:

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

Где:

Т.е.:

EMBED Equation.3

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

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

– PAGE 27 –