Математические методы (стр. 1 из 3)

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

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

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

Вариант 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

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

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

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

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

II. 3у₁+4у₂ ≤ 13

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

у₂= -13/4 у₁=13/3

III. -у₁+2у₂ ≤ 3

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

у₂=3/2 у₁= -3

IV. 2у₁-3у₂ ≤ 6

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

у₂= -2 у₁=3

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

F_A=9 - max

F_B=4/9*6=8/3=2*2/3 - min

Ответ: по теореме двойственности F_max= Z_min= 9

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

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

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

· способ определения какого – либо первоначального допустимого базисного решения задачи;

· правило перехода к лучшему (точнее, не худшему) решению;

· критерий проверки оптимальности найденного решения.

IIIЗадание: Решить задачу симплексным методом.

Z(x)=x₁-x₂+x₃ → max

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

4x₁+2x₂+x₃ ≥ 6

-x₁+x₂+x₃ = 1

x₁-x₂+4x₃ ≤ 24

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

x_j ≥ 0 , j=1,2,3

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