Прикладная математика

СОДЕРЖАНИЕ: 

                                                                                                                                 стр.

1. Задание на курсовую работу         3
2. Линейная производственная задача       6
3. Двойственная задача         13
4. Задача о «расшивке узких мест производства»     15
5. Транспортная задача линейного программирования    17
6. Динамическое программирование. Распределение капитальных

   вложений           21

7. Матричная игра как модель конкуренции и сотрудничества  24
8. Анализ доходности и риска финансовых операций    28

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ 

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

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

А=         В=        С=(30, 28, 9, 23)                            

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

    В последней симплексной таблице  указать обращенный базис Q^-1, соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения

                                                    H= Q^-1B

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

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

    Применить найденные двойственные оценки ресурсов к решению следующей задачи.

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

    По  пунктам 1, 2, 3 составить сводку результатов.

3. Составить математическую модель транспортной задачи, где в исходных данных А(а1,а2,а3) – вектор объема производства, В(b1, b2, b3, b4) - вектор объема потребления, С(с_ij), i = 1,2,3; j = 1,2,3,4 – матрица транспортных издержек.

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

4. Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб. Выделяемые суммы кратны 100 тыс. руб.
5. Рассмотреть матричную игру как модель сотрудничества и конкуренции. Найти графически решение игры. Указать, как проявляется конкуренция между игроками и сотрудничество между ними.
6. Провести анализ доходности и  риска финансовых операций.

ЛИНЕЙНАЯ  ПРОИЗВОДСТВЕННА  ЗАДАЧА 

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

    А=         В=        С=(30, 28, 9, 23)                             (1)

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

    Математическая  модель задачи:

    Найти производственную программу

                                 (x1, x2, x3, x4)

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

                             z=30x1+28x2+9x3+23x4                                             (2)

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

                            ,                                        (3)

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

                             x1≥0,  x2≥0, x3≥0, x4≥0.                                      (4)

    Получили  задачу на условный экстремум. Для ее решения систему неравенств (3) при  помощи дополнительных неотрицательных  неизвестных х5, х6, х7, заменим системой линейных алгебраических уравнений

                             ,                     (5)                    

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

     x1≥0, x2≥0, x3≥0, x4≥0, x5≥0, x6≥0, x7≥0,                   (6)

надо  найти то решение, при котором  функция (2) примет наибольшее значение.

     Воспользуемся тем, что правые части всех уравнений  системы (5) неотрицательны, а сама система  имеет предпочитаемый вид – дополнительные переменные являются базисными. Приравняв к нулю свободные переменные х1, х2, х3, х4, получаем базисное неотрицательное решение

     х1=0, х2=0, х3=0, х4=0, х5=110, х6=126, х7=114,                (7)

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

          х1=0, х2=0, х3=0, х4=0,                         (8)

по которой  мы пока ничего не производим.

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

       (9)

     Сохраняем пока в общем решении х2=х3=х4=0 и увеличиваем только х1. При этом значения базисных переменных должны оставаться неотрицательными, что приводит к системе неравенств 

            или      

         т.е. 0 ≤ х1 ≤ 42

     Дадим х1 наибольшее значение х1=42, которое она может принять при нулевых значениях других свободных неизвестных, и подставим его в (9). Получаем для системы уравнений (5) частное неотрицательное решение

     х1=42, х2=х3=х4=0, х5=68, х6=0, х7=30          (10)

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

     min ,

разрешающим элементом будет  =3. Применив формулы исключения, получаем для системы уравнений (5) новый предпочитаемый эквивалент 

                   (11)

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

              х1=42, х2=0, х3=0, х4=0.                 (12)

Исследуем, является ли эта программа наилучшей, т.е. обеспечивает ли она наибольшую прибыль. Для этого выразим функцию  прибыли (2) через новые свободные  переменные х2, х3, х4, х6. И второго  уравнения системы (11) выразим базисную переменную х1 через свободные и подставляем в (2). Получаем 

          z = 30(42-2х2-4/3х4-1/3х6)+28x2+9x3+23x4,

           z = 1260 - 32х2+9х3 -17х4-10х6                             (13) 

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

Найдем разрешающее уравнение

               min

Это третье уравнение системы (11).

Прежде  чем преобразовывать систему  (11) представим соотношение (13) в виде уравнения   

             32х2-9х3 +17х4+10х6 = 1260 – z                  (14)

и припишем его к системе (11). Получим 
 
 

                                                                         (15)

Затем преобразуем всю вспомогательную систему (15) по формулам исключения, исключив х3 из всех уравнений кроме третьего. Эта система преобразуется к виду 

                                           (16)

Первые  три уравнения системы (15) представляют некоторые предпочитаемый эквивалент системы уравнений (5) и определяют базисное неотрицательное решение  системы условий рассматриваемой задачи

х1=42, х2=0, х3=30, х4=0, х5=8, х6=0, х7=0          (17),

т.е. определяют производственную программу 

      х1=42, х2=0, х3=30, х4=0                                  (18)

и остатки  ресурсов:

    первого вида    х5=8

    второго вида    х6=0                                      (19)

    третьего вида   х7=0 

    В последнем уравнении системы (16) среди коэффициентов при неизвестных в левой части уравнения нет ни одного отрицательного. Если из этого уравнения выразить функцию цели через остальные неотрицательные переменные

       z= 1530-32x2-20x4-4x6-9x7,                          (20)   

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

      х2=0, х4=0, х6=0, х7=0.                                   (21)               

Это означает, что производственная программа (18) является наилучшей и обеспечивает предприятию наибольшую прибыль 

                 .

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

    Запишем процесс решения задачи в виде симплексной таблицы 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

В данной симплексной таблице обращенным базисом Q^-1, соответствующим оптимальному набору базисных неизвестных является матрица

                                                    Q^-1=

Проверим  выполнение соотношения

                                   H= Q^-1B,

где В=

По определению  произведением матрицы Q^-1 размером (3×3) на матрицу В размером (3×1) является матрица Н размером (3×1), где 

h₁₁=1*110+1*126+(-2)*114=8

h₂₁=0*110+1/3*126+0*114=42

h₃₁=0*110+(-2/3)*126+1*114=30, т.е.

Н= , что соответствует матрице Н в третьем столбце последней симплексной таблицы. Таким образом, соотношение H= Q^-1 B выполняется.

Графический способ решения

    Воспользуемся тем, что в оптимальной производственной программе х2=0 и х4=0. Предположим, что вторую и четвертую продукции  мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Решим задачу графически. Математическая модель задачи будет выглядеть следующим образом:

                                                  (22)

            z = 30x1+9x3→max                                (23)

                                                              (24)  →   

             x1 ≥ 0, x3 ≥ 0                                       (25) 

     Система линейных неравенств (24) и (25) определяет выпуклый многоугольник OPQRS допустимых решений. Линии уровня функции z перпендикулярны вектору-градиенту grad z = (30; 9) и образуют семейство параллельных прямых. Наибольшего значения функция z достигает в точке Q. Координаты этой точки определяют оптимальный план производства х1=42, х3=30, а максимальная прибыль будет равна 1530.

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

     (х1=0, х3=0)→(х1=42, х3=0)→(х1=42, х3=30)

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

    ДВОЙСТВЕННАЯ  ЗАДАЧА 

    Технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С  имеют вид:

          А=         В=        С=(30, 28, 9, 23)                            

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

                                                 (у1, у2, у3),

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

                                           f=110у1+126у2+114у3                        (1)

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

                                                                    ,                                   (2)

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

                       у1≥0, у2≥0, у3≥0.                                (3)

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

              (х1, х2, х3, х4) и (у1, у2, у3) пары двойственных задач необходимо и достаточно выполнение условий

    Ранее было найдено, что в решении исходной задачи х1>0, x3>0. Поэтому

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

                                      у1=0,

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

откуда  следует

                           у2=4, у3=9.

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

                       У1=0, у2=4, у3=9.

    Общая оценка всех ресурсов равна

                     f=110*0+126*4+114*9

                     f=1530.

ЗАДАЧА  О «РАСШИВКЕ УЗКИХ МЕСТ ПРОИЗВОДСТВА» 

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

    T(t1, t2, t3) – вектор дополнительных объемов ресурсов.

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

                                 Н+Q^-1T ≥ 0.

    Необходимо  найти вектор T(0, t2, t3),

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

                                   W = 4t2 + 9t3                                                 (1)

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

                                                     (2)

    Мы  можем получить дополнительно не более 1/3 первоначального объема ресурса  каждого вида

                                                              (3),

    причем  t2 ≥ 0, t3 ≥ 0.                                                 (4)

    Перепишем неравенства (2) и (3) в виде:

                                                                                         (5)

                            t2 ≤ 126/3, t3 ≤ 114/3,

                            t2 ≤ 42, t3 ≤ 38.                                          (6)

    Приходим  к задаче линейного программирования:

    максимизировать W = 4t2 + 9t3 при условиях (4), (5), (6).

    Решим задачу графически: 
 
 
 
 
 
 
 
 
 
 
 
 

    Наибольшего значения функция W достигает в точке М(42, 25). Таким образом, программа расшивки имеет вид:

                                   t1 = 0, t2 = 42, t3 = 25

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

              W = 4*42+9*25

              W = 393.

Результаты  запишем в виде таблицы:

ТРАНСПОРТНАЯ  ЗАДАЧА ЛИНЕЙНОГО  ПРОГРАММИРОВАНИЯ 

    Однородный  продукт, сосредоточенный в трех пунктах производства в количествах а1, а2, а3 единиц, необходимо распределить между четырьмя пунктами потребления, которым необходимо соответственно b1, b2, b3, b4 единиц. Стоимость перевозки единицы продукта  из i-го пункта отправления в j-й пункт назначения равна с_ij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были бы минимальными.

    Обозначим через х_ij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления

                                                                            (1)

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

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

                             Х= (х_ij)_,           i=1,2,3;          j=1,2,3,4,

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

                                          L =                                  (2)

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

                                                  i=1,2,3                         (3)

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

                                                  j=1,2,3,4                       (4)

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

                            х₁₁ > 0,…, x_mn > 0.                                                        (5)

    Исходные  данные задачи имеют вид

    А(а1, а2, а3)=(65, 40, 70);    В(b1, b2, b3, b4)=(30, 58, 32, 43);  

    C=

    Общий объем производства ∑а_i =65+40+70=175 больше, чем требуется всем потребителям ∑b_j=30+58+32+43=163, то есть мы имеем открытую модель транспортной задачи. Решим задачу с помощью метода потенциалов. Для превращения задачи в закрытую модель вводим фиктивный пункт потребления с объемом потребления 175-163=12 единиц. Тарифы на перевозку в этот пункт условимся считать равными нулю.

    Первое  базисное допустимое решение построим по правилу «северо-западного угла».

      Транспортная таблица 1