Математические методы

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ  НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ КОЛЛЕДЖ УПРАВЛЕНИЯ ИНФОРМАТИКИ И СЕРВИСА (ИМСИТ) 
 
 
 
 
 
 
 
 
 

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

по  дисциплине «МАТЕМАТИЧЕСКИЕ  МЕТОДЫ» 

Вариант 3. 
 
 
 
 
 

             Выполнил:

студент группы ПО-3-3

   специальности 230105

                       «Программное обеспечение

        вычислительной техники и

    автоматизированных систем»

Горбунов  Дмитрий Валерьевич 

Проверил:

                  Шихина В. А. 
 
 
 
 
 

Краснодар, 2006 

СОДЕРЖАНИЕ 
 
 

Введение …  … … … … … … … …  … … … … … … … …  … … … … … … … …  .  2 Графический метод решения задач … … … … … … … … … … … … … … … … 3

Теория двойственности … … … … … … … …  … … … … … … … …  … … … ... 6

Симплексный метод  … … … … … … … … … … … … … … … … … … … … … .. 10

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

Список использованной литературы … … … … … …  … … … … … … … …  … …  24 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ

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

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

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

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

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

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

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

      Z(X) = c₁x₁ + c₂x₂  → max (min)

       a₁₁x₁ + a₁₂x₂ ≤ (≥) b₁,

      a₂₁x₁ + a₂₂x₂ ≤ (≥) b₂,

      ……………………………..

      a_m1x₁ + a_m2x₂ ≤ (≥) b_m

      x₁≥0, x₂≥0

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

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

      Областью  решений линейного неравенства a_i1x₁ + a_i2x₂ ≤b_i является одна из двух полуплоскостей, на которые прямая a_i1x₁ + a_i2x₂ = 0, соответствующая данному неравенству, делит всю координатную плоскость. Для того, чтобы определить, какая из полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство: если оно удовлетворяется, то областью решений является полуплоскость, содержащая эту точку, если не удовлетворяется – то полуплоскость, не содержащая данную точку .

      Для нахождения среди допустимых решений  оптимального используют линии уровня и опорные прямые. Линией уровня  называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение линии уровня имеет вид c₁x₁ + c₂x₂ = L , где L = const. Все линии уровня параллельны между собой. Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с областью допустимых решений и по отношению к  которой эта область находиться в одной из полуплоскостей. Важное свойство линии уровня: при параллельном смещении линии в одну сторону уровень возрастает, а в другую сторону – убывает. 
 

I   Задание:   Решить графическим методом задачу с двумя переменными. 

   

        Z(x)=2х₁+3х₂ → max 

     -6х₁+х₂ ≥ 3

     -5х₁+9х₂ ≤ 45

         х₁-3х₂ ≤ 3 

          х₁ ≥ 0  ,  х₂ ≥ 0 
 
 

Найдем  точки пересечения прямых с осями  координат: 
 
 

I.   -6х₁+х₂=3

        1)х₁=0                 2)х₂=0

          х₂=3                     х₁= -1/2 

II.  -5х₁+9х₂=45

        1)х₁=0                 2)х₂=0

           х₂=5                    х₁= -9 

III.  х₁-3х₂=3

        1)х₁=0                2)х₂=0

           х₂= -1                  х₁=3 
 
 
 
 
 
 
 
 
 

Построим  область решения данной системы: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Найдем  вектор направленности целевой функции 
 

Z(х)=2х₁+3х₂=0

   1)х₁=0                     2)х₁=3

      х₂=0                         х₂= -2 

Z(х)=2х₁+3х₂=6

   1)х₁=0                     2)х₂=0

      х₂=2                         х₁=3 
 
 
 
 

Ответ: Целевая  функция принимает максимальное

значение в  точке (0;0),   при х₁=0 и х₂=0.

Теория  двойственности. 

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

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

1. Привести все неравенства ограничений исходной задачи к единому смыслу: если в исходной задаче ищется максимум линейной функции, то все неравенства системы ограничений привести к виду «≤», а если минимум – к виду «≥». Для этого неравенства, в которых данное требование не выполняется, умножить на  -1.
2. Составить расширенную матрицу системы – А , в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.
3. Найти матрицу А`  транспонированную к матрице А
4. Сформулировать двойственную задачу на основании полученной матрицы А` и условия неотрицательности переменных.

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

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

II  Задание:    Решить графическим методом задачу с двумя переменными. 

   

Z(х)=4х₁+13х₂+3х₃+6х₄ → min 

При ограничениях:

       -5х₁+3х₂-х₃+2х₄+х₅ = -1

      9х₁-4х₂+2х₃-3х₄+х₆ = 6

          

Учитывая условия неотрицательности:

           х_j ≥ 0  , j=1,2,3,4. 

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

     -5х₁+3х₂-х₃+2х₄+х₅ ≥ -1

    9х₁-4х₂+2х₃-3х₄+х₆ ≥ 6 

Составим  расширенную матрицу системы уравнений 
 

            -5    3   -1    2    1    0   -1

     А =   9   -4    2   -3    0    1    6

              4   13    3    6    0    0    Z 
 

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

              -5    9    4

             3   -4   13

               -1    2    3

     А′ =  2   -3    6

               1    0    0

                0    1    0

             -1    6    F 
 
 
 

Составим  новую систему ограничений 
 

    F(y)= -у₁+6у₂ → max 

         -5у₁+9у₂ ≤ 4

          3у₁+4у₂ ≤ 13

          -у₁+2у₂ ≤ 3

          2у₁-3у₂ ≤ 6

           у₁ ≤ 0

           у₂ ≤ 0

         у₁ ≥ 0 ;  у₂ ≥ 0 
 
 
 

Найдем  точки пересечения прямых с осями координат: 
 
 

1. -5у₁+9у₂ ≤ 4

  1)у₁=0             2)у₂=0

   у₂=4/9              у₁= -4/5 

2. 3у₁+4у₂ ≤ 13