Главная Учебники - Разные Лекции (разные) - часть 65
Государственный университет управления Институт заочного обучения Специальность – менеджмент Кафедра прикладной математики по дисциплине: «Прикладная математика» Выполнил студент 1-го курса Группа № УП4-1-98/2 Студенческий билет № Москва, 1999 г. Содержание
1. Линейная производственная задача_____________________________________________ 3 2. Двойственная задача_________________________________________________________ 7 3. Задача о «Расшивке узких мест производства»____________________________________ 9 4. Транспортная задача________________________________________________________ 12 5. Распределение капитальных вложений_________________________________________ 17 6. Динамическая задача управления запасами_____________________________________ 21 7. Анализ доходности и риска финансовых операций________________________________ 26 8. Оптимальный портфель ценных бумаг__________________________________________ 28
Линейная производственная задача – это задача о рациональном использовании имеющихся ресурсов, для решения которой применяют методы линейного программирования. В общем виде задача может быть сформулирована следующим образом: Предположим, предприятие или цех может выпускать Примем следующие обозначения: Таким образом, математическая модель задачи состоит в том, чтобы найти производственную программу
При этом, какова бы ни была производственная программа
А так как компоненты программы – количество изделий, то они не могут быть выражены отрицательными числами, следовательно добавляется еще одно условие:
Предположим, что предприятие может выпускать четыре вида продукции (
Тогда математическая модель задачи будет иметь вид: Найти производственную программу при ограничениях по ресурсам: где по смыслу задачи: Таким образом, получили задачу на нахождение условного экстремума. Для ее решения введем дополнительные неотрицательные неизвестные: Тогда вместо системы неравенств (1.2), получим систему линейных алгебраических уравнений: где среди всех решений, удовлетворяющих условию неотрицательности:
надо найти решение, при котором функция (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
® из базиса. разрешающий элемент = 6 x1
– разрешающая переменная вторая строка – разрешающая разрешающий элемент = При этом каждый элемент симплексной таблицы имеет определенный экономический смысл. Например, во второй симплексной таблице:
Показывают, что увеличение объема сырья первого вида на единицу позволило бы увеличить выпуск продукции третьего вида на
что одновременно потребовало бы Т.к. в последней строке третьей таблицы 1 нет ни одного отрицательного относительного оценочного коэффициента, то производственная программа, при которой получаемая предприятием прибыль имеет наибольшее значение, найдена, т.к., например, коэффициент Таким образом, получили производственную программу:
которая является оптимальной и обеспечивает предприятию наибольшую возможную прибыль:
При этом первый и второй ресурсы будут использованы полностью, т.е. первый и второй ресурсы образуют «узкие места производства»:
а третий ресурс будет иметь остаток:
Помимо этого в третьей симплексной таблице получен обращенный базис, отвечающий оптимальной производственной программе:
тогда можно проверить выполнение соотношения
а т.к. из третьей симплексной таблицы: Задача, двойственная линейной производственной задаче, например, может заключаться в оценке выгоды от продажи сырья, используемого в производстве, на сторону. Например, в предыдущем п.1. рассмотрена линейная производственная задача по выпуску четырех видов продукции с использованием трех видов ресурсов по заданным технологиям. Предположим, некий предприниматель, занимающийся производством других видов продукции с использованием трех таких же видов ресурсов, предлагает «уступить» ему все имеющиеся ресурсы и обещает платить y1
денежных единиц за каждую единицу первого ресурса, y2
денежных единиц за каждую единицу второго ресурса и y3
денежных единиц за каждую единицу третьего ресурса. Возникает вопрос: при каких значениях y1
,y2
, y3
можно согласиться с предложением этого предпринимателя. Т.к. в предыдущей задаче технологическая матрица
значит, для производства, например, первого вида продукции, предприятие должно затратить 3 единицы ресурса первого вида, 4 единицы ресурса второго вида и 4 единицы ресурса третьего вида, за что оно получит прибыль 30 денежных единиц. Следовательно, согласиться с предложением предпринимателя можно, если он заплатит не меньше, т.е. в ценах y1
,y2
, y3
это условие будет иметь вид:
Аналогично и с продукцией второго, третьего и четвертого вида, при этом, за все имеющиеся ресурсы, предприниматель должен заплатить не меньше: Следовательно, предприниматель будет искать такие значения y1
,y2
, y3
, при которых эта сумма была бы как можно меньше. При этом речь идет о ценах, которые зависят не от цен по которым эти ресурсы были когда-то приобретены, а о ценах зависящих от применяемых в производстве технологий, объемов ресурсов и прибыли, которую возможно получить за произведенную продукцию. Таким образом, задача определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок
минимизирующий общую оценку всех ресурсов
при условии, что по каждому виду продукции суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции, т.е.:
причем оценки ресурсов не могут быть отрицательными, т.е.: Решение полученной задачи можно найти с помощью второй теоремы двойственности: дефицитный (избыточный) ресурс, полностью (неполностью) используемый по оптимальному плану производства, имеет положительную (нулевую) оценку, и технология, применяемая с ненулевой (нулевой) интенсивностью, имеет нулевую (положительную) оценку. Т.е. для оптимальных решений
Ранее в п.1. было найдено, что
Но т.к. третий ресурс был избыточным (см. п.1.), то по второй теореме двойственности, его двойственная оценка равна нулю, т.е.
от куда получаем: Таким образом, получили двойственные оценки ресурсов:
тогда общая оценка всех ресурсов равна:
То же самое решение значений двойственных оценок содержится в последней строке симплексной таблицы 1 и имеет определенный экономический смысл: Одновременно технологические оценки из той же строки симплексной таблицы: Задача о «расшивке узких мест производства» заключается в том, что, например, когда в процессе производства происходит изменение объема какого-либо ресурса, используемого в производстве, то, соответственно изменяется план производства и прибыль предприятия, получаемая от реализации готовой продукции. Это может происходить по различным причинам, например: сломался станок, поставщик предлагает сырье в большем количестве и т.п. Поэтому, когда какой-либо ресурс используется полностью, то уменьшение объема этого ресурса, может повлиять на всю структуру плана производства и прибыль предприятия. Следовательно, такой ресурс, образующий «узкие места производства», желательно иметь с некоторым запасом, т.е. заказывать дополнительно, чтобы сохранить структуру плана производства и получить возможность увеличить прибыль предприятия. Для примера возьмем данные и результаты вычислений из п.1. и п.2., где определено, что первый и второй ресурс используются полностью, и, соответственно, именно их нужно заказывать дополнительно. Но в таких объемах, чтобы сохранить структуру ранее найденной программы производства, и с условием, что от поставщика можно получить дополнительно не более одной трети первоначально выделенного объема ресурса любого вида. Следовательно, задача сводиться к нахождению объемов приобретения дополнительных ресурсов, удовлетворяющих указанным условиям, и вычислению дополнительной возможной прибыли. Тогда, пусть
при этом, для сохранения структуры производственной программы, должно выполняться условие устойчивости двойственных оценок:
Т.к.
максимизирующий суммарный прирост прибыли: при условии сохранения структуры производственной программы: предполагая, что можно надеяться получить дополнительно не более одной трети первоначального объема ресурса каждого вида, т.е.: причем дополнительные объемы ресурсов, по смыслу задачи, не могут быть отрицательными, т.е.: Т.к. неравенства (3.2) и (3.3) должны выполняться одновременно, то их можно переписать в виде одной системы неравенств: - - - - - Таким образом, получена задача линейного программирования: максимизировать функцию (3.1) при условиях (3.4) и (3.5). Эту задачу с двумя переменными можно решить графически: На графике видно, что система линейных неравенств (3.4), (3.5), образует область допустимых решений, ограниченную прямыми:
при этом линии уровня функции (3.1) перпендикулярны вектору-градиенту
Координаты этой точки и определяют искомые объемы дополнительных ресурсов. Следовательно, программа «расшивки узких мест производства имеет вид:
и прирост прибыли составит:
Сводка результатов по пунктам 1-3 приведена в таблице 2. Транспортная задача – это задача о минимизации транспортных расходов, связанных с обеспечением пунктов потребления определенным количеством однородной продукции, производимой (хранимой) в нескольких пунктах производства (хранения). В общем виде задача может быть сформулирована следующим образом: Однородный продукт, сосредоточенный в Примем следующие обозначения: Тогда, при наличии баланса производства и потребления:
математическая модель транспортной задачи будет выглядеть следующим образом: найти план перевозок
минимизирующий общую стоимость всех перевозок
при условии, что из любого пункта производства вывозиться весь продукт и любому потребителю доставляется необходимое количества груза причем, по смыслу задачи
Для решения транспортной задачи чаще всего применяется метод потенциалов, при котором вводят обозначение вектора симплексных множителей или потенциалов:
Тогда:
Откуда следует:
При этом один из потенциалов можно выбирать произвольно, т.к. в системе (4.1) и (4.2) одно уравнение линейно зависит от остальных, а остальные потенциалы находятся, что для базисных значений Предположим, что однородный продукт, находящийся в трех пунктах производства (m=3), необходимо доставить в четыре пункта потребления (n=4). При этом матрица Тогда получается, что общий объем продукта в пунктах производства
Для того чтобы превратить открытую модель транспортной задачи в закрытую, необходимо ввести фиктивный пункт потребления с объемом потребления
при этом тарифы на перевозку продукта в этот пункт потребления будут равны нулю, т.к. фактического перемещения продукта не происходит. Тогда, первое базисное допустимое решение легко построить по правилу «северо-западного угла». А т.к. оценки базисных клеток транспортной таблицы равны нулю, то, приняв, что
Т.к. наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 14, то строим цикл пересчета: 14-13-23-24 и производим перераспределение поставок вдоль цикла пресчета: То получаем второе базисное допустимое решение и находим новые потенциалы, полагая
Т.к. теперь наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 22, то строим цикл пересчета: 22‑12‑14‑24 и производим перераспределение поставок вдоль цикла пресчета: Отсюда получаем третье базисное допустимое решение и находим новые потенциалы, принимая
Т.к. наибольшая положительная оценка всех свободных клеток транспортной таблицы, теперь соответствует клетке 21, то строим цикл пересчета: 21-11-14-24 и производим перераспределение поставок вдоль цикла пресчета: Получаем четвертое базисное допустимое решение и находим новые потенциалы, принимая
Т.к. наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 33, то строим цикл пересчета: 33-23-21-11‑14‑34 и производим перераспределение поставок вдоль цикла пресчета: Получаем пятое базисное допустимое решение и находим новые потенциалы, опять принимая
Теперь наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 25, отсюда строим цикл пересчета: 25-23-33- и производим перераспределение поставок вдоль этого цикла пресчета: Получаем пятое базисное допустимое решение и снова находим новые потенциалы, принимая
Находим оценки всех свободных клеток таблицы: Т.к. получили таблицу для которой нет ни одной положительной оценки, следовательно, найдено оптимальное базисное допустимое решение:
при котором транспортные расходы по обеспечению продуктом всех четырех пуктов потребления будут наименьшими. При этом из второго пункта производства товар будет вывезен не полностью, т.е. там останется остаток продукта 28 единиц. Задача о распределении капитальных вложений – это нелинейная задача распределения ресурсов между предприятиями одного производственного объединения или отрасли. Предположим, что указано Примем следующие обозначения: Тогда, задача состоит в том, чтобы найти такие значения
было бы наибольшим, при ограничении общей суммы:
Эту задачу можно решить методом динамического программирования. Для этого необходимо ввести параметр состояния Тогда, если из
Если же k
=1, то:
Допустим, что производственное объединение состоит из четырех предприятий (n
=4). Общая сумма капитальных вложений равна 700 денежных единиц (b
=700), при этом суммы выделяемые предприятиям кратны 100 денежным единицам. Значения функций Для заполнения таблицы 5 необходимо в таблице 4 сложить значения функции Для заполнения таблицы 7 необходимо в таблице 6 сложить значения функции Таблица 6. Теперь, в таблице 8, необходимо сложить значения функции Наибольшее число этой диагонали показывает максимально возможный суммарный прирост прибыли всех четырех предприятий данного производственного объединения, при общей сумме капитальных вложений в 700 денежных единиц, т.е.: причем четвертому предприятию должно быть выделено: Тогда третьему предприятию должно быть выделено (см. табл. 7.): второму предприятию должно быть выделено (см. табл. 5.): на долю первого предприятия остается: Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям: которое обеспечивает производственному объединению наибольший возможный прирост прибыли: Задача управления запасами – это задача о поддержании баланса производства и сбыта продукции предприятия, минимизирующего расходы предприятия на производство и хранение продукции. Предположим, что предприятие, производящее партиями некоторую продукцию, получило заказы на n
месяцев. Размеры заказов значительно меняются от месяца к месяцу, поэтому иногда лучше выполнять заказы сразу нескольких месяцев, а затем хранить готовую продукцию, пока она не потребуется, чем выполнять заказ именно в тот месяц, когда этот заказ должен быть отправлен. Поэтому необходимо составить план производства на эти n
месяцев с учетом затрат на производство и хранение изделий. Примем следующие обозначения: Тогда, задача состоит в том, чтобы найти план производства
и минимизируют суммарные затраты за весь планируемый период:
причем по смыслу задачи Т.к. объем произведенной продукции
Полученную задачу можно решить методом динамического программирования, для чего необходимо определить параметр состояния Тогда, минимальные затраты за один первый месяц (
Следовательно, минимальные затраты при
Если при этом функция затрат на хранение и производство изделий в j-ом месяце имеет вид:
то минимальные затраты за один первый месяц (
если ввести обозначение:
то следовательно, минимальные затраты при
Допустим, что предприятие заключило договора на поставку своей продукции на три месяца. Исходные данные приведены в таблице 9. При этом исходный запас товара на складе составляет две единицы, т.е Предполагается, что затраты на приобретение продукции составляют 5 руб. за каждую единицу для первых трех единиц и 7 руб. за каждую дополнительную единицу, т.е.
Положим
Тогда, т.к. параметр состояния
т.е.
Однако на первом этапе объем производства не может быть меньше одной единицы, т.к. спрос
т.е. каждому значению
Значения функции состояния Положим
Здесь минимум берется по переменной
где верхняя граница зависит от параметра состояния
т.е.
Тогда: ( Наименьшие из полученных значений
причем минимум достигается при
эти значения указываем в результирующей таблице 11. Аналогично: ( ( ( Таким образом: Теперь положим, что
Если оставлять продукцию к концу третьего периода не нужно, тогда параметр состояния принимает единственное значение
а из балансового уравнения следует, что остаток товара на начало третьего месяца
Тогда: ( Следовательно, получаем:
причем минимум достигается при
Таким образом, получили минимальные общие затраты на производство и хранение продукции и последнюю компоненту оптимального решения:
Для нахождения остальных компонент оптимального решения, необходимо воспользоваться обычными правилами динамического программирования. Тогда т.к.
Аналогично т.к.
Следовательно, получен оптимальный план производства, который имеет два варианта:
при этом, каждый вариант оптимального плана производства обеспечивает минимальные общие затраты на производство и хранение продукции в размере 39 денежных единиц. Финансовой называется операция, начальное и конечное состояние которой имеют денежную оценку и цель проведения которой заключается в максимизации дохода в виде разности между конечной и начальной оценками. При этом практически все финансовые операции проходят в условиях неопределенности и, следовательно, их результат невозможно предсказать заранее. Поэтому при проведении финансовой операции возможно получение как прибыли, так и убытка. Поэтому задача анализа доходности и риска финансовой операций заключается в оценке финансовой операции с точки зрения ее доходности и риска. Наиболее распространенным способом оценки финансовой операций является представление дохода операции как случайной величины и оценка риска операции как среднего квадратического отклонения этого случайного дохода. Например, если доход от проведения некоторой финансовой операции есть случайная величина
Т.к. среднеквадратическое отклонение:
это мера разбросанности возможных значений дохода вокруг среднего ожидаемого дохода, то его можно считать количественной мерой риска операции и обозначить как
Допустим, что по четырем финансовым операциям Тогда т.к. Т.к. Тогда, чем правее точка на графике, тем более доходная операция, чем точка выше – тем более она рисковая. Для определения операции оптимальной по Парето, необходимо на графике найти точку, которую не доминирует никакая другая точка. Так как точка Для нахождения лучшей операции можно применить взвешивающую формулу, которая для пар Отсюда видно, что 1-ая финансовая операция – лучшая, а 2-ая – худшая. Задача о формировании оптимального портфеля ценных бумаг – это задача о распределении капитала, который участник рынка хочет потратить на покупку набора ценных бумаг, по различным видам ценных бумаг, удовлетворяющих возможность получения некоторого дохода. Из характеристик ценных бумаг наиболее значимы две: эффективность и рискованность. Т.к. эффективность
Примем следующие обозначения: Тогда, математическое ожидание эффективности портфеля ценных бумаг:
вариация портфеля ценных бумаг:
риск портфеля ценных бумаг:
Следовательно, математическая формализация задачи формирования оптимального портфеля ценных бумаг: Найти такое распределение долей капитала, которое минимизирует вариацию эффективности портфеля, при заданной ожидаемой эффективности портфеля Тогда, если оптимальное решение обозначить как *, то: Если на рынке есть безрисковые ценные бумаги, то решение задачи о формировании портфеля ценных бумаг приобретает новое качество. Пусть: Тогда в рисковую часть портфеля вложена
вариация портфеля ценных бумаг:
риск портфеля ценных бумаг:
Допустим, что задача состоит в нахождении распределения капитала, при формировании оптимального портфеля ценных бумаг заданной эффективности, состоящего из трех видов ценных бумаг: безрисковых эффективности 3 и некоррелированных рисковых, с ожидаемой эффективностью 5 и 9, риски которых равны 4 и 6, т.е.:
Тогда, вариации некоррелированных рисковых ценных бумаг первого и второго вида: Следовательно, матрица Пусть
Тогда значение вектора-столбца
Где: Т.е.: Таким образом, доли рисковых ценных бумаг в оптимальном портфеле:
Следовательно, доля безрисковых ценных бумаг в оптимальном портфеле:
Т.к. необходимость проведения операции “short sale” возникает, когда
|