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

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ

Институт информационных систем управления

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

Курсовая работа

по учебной дисциплине «Прикладная математика»

Вариант № 7

Исполнитель

Студентка Иванова Кристина                            группы БУ-2-2(в/о)

Руководитель курсовой работы

к.б.н., доцент                                                      _____________                            В.Л. Супоницкий

                                                                                           (подпись)

Москва 2008

Содержание

Задание на курсовую работу

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

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

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

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

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

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

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

Задача формирования оптимального портфеля ценных бумаг

СПИСОК ЛИТЕРАТУРЫ:

Задание на курсовую работу

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

,

компактно записаны в виде

                          c1       c2   c3    c4

                          а11   а12    а13  а14   b1

                          a21   a22   a23  a24   b2            

                          a31   a32   a33  a34   b3     .

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

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

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

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

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

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

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

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

4. Составить математическую модель транспортной задачи по исходным данным из приложения 2, где вектор объемов производства А(a1,..., am), потребления - В (b1,..., bn)   и матрица транспортных издержек   С=(сij), i =;  j = кратко записаны в виде

                                    b1         b2    . . .    bn

                         a1        c11       c12    . . .   c1n

                         a2        c21       c22    . . .   c2n 

                         . . . . . . . . . . . . . . . . . . . .

                         am        cm1      cm2    . . .   cmn            

Если полученная модель окажется открытой, то свести ее к замкнутой и найти оптимальное решение транспортной задачи методом потенциалов (см. раздел 7). Проверить решение транспортной задачи с помощью ЭВМ (приложение 12).

5. Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения (см. раздел 8), располагающего суммой в 700 тыс. руб., по исходным данным, приведенным в приложении 3 (выделяемые суммы кратны 100 тыс.).

16.Провести анализ доходности и риска финансовых операций (см. раздел 12) по исходным данным, приведенным в приложении 7.

17.Решить задачу формирования оптимального портфеля ценных бумаг (см. раздел 13): бумаги первого вида - безрисковые ожидаемой эффективности m0, а второго и третьего вида - некоррелированные рисковые ожидаемых эффективностей  m1, m2  c рисками  s1, s2. Исходные данные взять из приложения 8.

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

Исходные данные

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

                       2  2  3  4                            151

           А =      3  1  0  2                   В=    156               С=(35,41,22,12)

                       1  4  4  0                            162   

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

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

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

                                                 X = (x1, x2, x3, x4)

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

                                  z=35x1+41x2+22x3+12х4max                                                                       (1)

z(x1, x2, x3, x4) = c1x1 + c2x2 + c3x3 + c4x4  max    (z- целевая функция);

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

              2x1 + 2x2 + 3x3 + 4x4   151

                    3x1 + x2 +        + 2x4    156                                                                                                 (2)

              x1 +4x2 + 4x3               162

              a11x1+a12x2+a13x3+a14x4 < в1                      

                      а21х1+а22х2+а23х3+а34х4 < в2;

                       а31х1+а32х2+а33х3+а34х4 < в3

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

               x10, x20, x30, x40                                                                                                        (3)            

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

              2x1 + 2x2 + 3x3 + 4x4  + x5                 = 151

                    3x1 +   x2 +       + 2x4    + x6            = 156                                                                           (4)

             x1 + 4x2 + 4x3                      + x7       = 162

где x5, x6, x7 – остатки соответствующих ресурсов.

x10, x20, x30, x40, x50, x60, x70.                                                                                         (5) 

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

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

               x1=0, x2=0, x3=0, x4=0, x5=151, x6=156, x7=162                                                         (6)

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

                         x1=0, x2=0, x3=0, x4=0                                                                                        (7)

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

         x5=151- 2x1 - 2x2 - 3x3 - 4x4 

        x6=156- 3x1 -   x2 -       - 2x4                                                                                                  (8)   

         x7=162- x1 - 4x2 -  4x3                     

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

         151- 2x2 ≥  0                                x2≤ 75,5

         156-   x2   ≥ 0                               x2≤ 156        т.е.        0≤ x2≤40,5                                         (9)   

        162 - 4x2 ≥   0                               x2≤ 40,5                 

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

    x1=0, x2=40,5, x3=0, x4=0, x5=61, x6=115,5, x7=0                                                                (10)

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

min (bi/ai2>0) = min (151/2,156/1,162/4) = 162/4,

где а32=4 будет разрешающим элементом          разрешающее уравнение – 3

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

  Совершим шаг Гаусса-Жордана, и применив известные формулы исключения, получаем для системы уравнений (4) новый предпочитаемый эквивалент:

2

            3/2x1 +x3  + 4x4 + x5 - 1/2x7  = 70

          11/4x1 - x3 + 2x4  +  x6 - 1/4x7   = 231/2                                                                                  (11)