Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

практикум по математике часть 3

.pdf
Скачиваний:
121
Добавлен:
15.02.2015
Размер:
4.76 Mб
Скачать

Сизов С.Н., Свитачев А.И., Галькова Е.А., Шалагина Е.В.

ПРАКТИКУМ

ПО МАТЕМАТИКЕ

Красноярск 2008

С.Н.Сизов, А.И.Свитачев, Е.А.Галькова, Е.В.Шалагина

Практикум

по математике

в 3-х частях

Часть III

Под редакцией Сизова С.Н.

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

Красноярск 2008

УДК 517+519 ББК 22.11

Сизов С.Н., Свитачев А.И., Галькова Е.А. Шалагина Е.В.

Практикум по математике. В 3-х ч. Ч.III. Учебное пособие для втузов. Под редакцией С.Н.Сизова. Красноярск: КрИЖТ ИрГУПС, 2008.

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

Рецензенты: Ушанов С.В., к.т.н., профессор, зав. каф. «Высшая математика и информатика» Сибирского государственного технологического университета;

Черемисин А.А., д.ф.-м.н., профессор кафедры Ом и ЕНД Красноярского института железнодорожного транспорта ИрГУПС.

©Сизов С.Н., Свитачев А.И., Галькова Е.А., Шалагина Е.В., 2008.

©Красноярский институт железнодорожного транспорта, филиал Иркутского государственного университета путей сообщения, 2008.

Предисловие

Настоящая часть III практикума по математике предназначена для студентов-заочников втузов. Она содержит разделы по математическому программированию: линейное программирование, транспортная задача, нелинейное и динамическое программирование, случайные процессы и теория игр, а также разделы по теории вероятности и математической статистике.

Пособие имеет следующие отличия:

-геометрическое решение задач математического программирования не только изложено, но и объяснено. Для этого была использована геометрическая модель задач в 3-х мерном пространстве;

-произведено «приспособление» функции Лагранжа для решения задач квадратичного программирования; -найдена упрощенная форма уравнения Беллмана, что позволило

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

Учебное пособие соответствует Государственному общеобразовательному стандарту от 2000 года.

Разделы 1-4 написаны Сизовым С.Н. и Гальковой Е.А., раздел 5 – Свитачевым А.И. и Шалагиной Е.В., разделы 6,7 –Сизовым С.Н.

3

ВВЕДЕНИЕ В МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

Математическое программирование– область математики,

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

Функцию, экстремальное значение которой нужно найти в условиях ограниченных возможностей, называют целевой.

Ограниченные возможности формализуются в виде системы ограничений.

Все это составляет математическую модель математического

программирования, которая включает в себя:.

Х = (x1,x2 ,..., x j ,..., xn ),

1.

Совокупность

неизвестных величин

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

2.

Целевая функция F = f (X )= f (x1,x2 ,...,xn ).

 

Экстремальное значение

(min,max) целевой функции позволяет выбрать

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

3. Система ограничений (условий), налагаемых на неизвестные величины. Такими ограничениями могут быть: материальные, финансовые и трудовые ресурсы, возможности технического, технологического и, вообще, научного потенциала. Математические ограничения выражаются уравнениями и неравенствами.

Задача математического программирования формулируется так: найти такие

значения переменных x1,x2 ,..., xn

(оптимальный

план x1,x2,..., xj ,..., xn ),

которые обеспечивают экстремальное значение max(min) целевой функции

max(min)F = f (X )= f (x1,x2 ,...,xn )

(1)

при ограничениях (условиях)

 

 

 

gi (X )= gi (x1,x2 ,..., x j ,..., xn ){,=≥}bi ,

i =1,...,m

(2)

x j 0,

j =1,2,...,n

 

(3)

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

4

Если функции f и gi являются линейными, то задача (1)-(3) относится к линейному программированию. Если хотя бы одна из функций f или gi нелинейная, задача относится к нелинейному программированию.

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

динамическому программированию.

Если параметры, входящие в функции (1), (2), являются случайными,

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

Если при решении задачи выбор оптимального решения производится

вусловиях риска или неопределенности, то задача относится к теории игр.

1.ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1.1.Краткие сведения из теории

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

x1, x2 ,..., xn , которые доставляют максимум (минимум) целевой функции

 

n

 

F = c1x1 + c2 x2 +... + cn xn = c j x j

(1.1)

 

j=1

 

при условиях

 

 

n

(i =1,...,m),

 

aij x j {,=,}bi

(1.2)

j=1

 

 

x j 0, j =1,2,..., n

 

(1.3)

где c j , aij , bi (i =1,2,...,m ; j =1,2,...,n ) – заданные числа.

Задача линейного программирования называется канонической, если ограничения задачи (1.2) состоят из системы уравнений и условий неотрицательности всех n переменных.

Если в ограничениях (1.2) находятся неравенства– задача называется

симметричной.

Поскольку min F = −max(F ), задачу минимизации функции F формально можно свести к задаче максимизации противоположной функции (F ). Найдя максимальное значение функции ( F ), нужно ее знак заменить на противоположный и тем самым определится минимальное значение исходной функции F .

Алгоритм составления модели задачи линейного программирования, заданной в текстовой форме.

Для этого необходимо:

5

1.ввести обозначения для неизвестных задачи;

2.проанализировать и зафиксировать ограничения для них;

3.составить систему ограничений задачи;

4.составить целевую функцию и установить вид экстремума.

Рассмотрим два метода решения задач линейного программирования: геометрический метод и симплекс-метод.

1.1.1. Геометрический метод

Геометрический метод решения задач математического программирования применяется для решения задач, имеющих две переменные x1 и x2 как в целевой функции, так и в функциях системы

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

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

В математической модели присутствуют функции двух переменных: f = f (x1,x2 )– целевая функция и gi (X )= gi (x1, x2 ), i =1,...,m – функции в системе ограничений. Каждая из этих функций геометрически представляется в виде поверхности: линейные функции–плоскостями, функции второго порядка– кривыми поверхностями второго порядка и т.д..

Рассмотрим

решение

задачи

 

 

линейного

программирования

геометрическим методом.

 

 

 

 

 

 

 

 

 

Пусть дана задача:

 

 

 

 

 

 

 

 

 

 

max(min)F = c1x1 + c2 x2 ,

(1.4)

 

 

a11x1 + a12 x2 b1

 

 

 

a

21

x

+ a

22

x

2

b

 

 

 

 

1

 

 

2

 

при условии

 

a31x1 + a32 x2 b3

(1.5)

 

a

 

x

+ a

 

x

 

b

 

 

 

41

1

 

42

 

2

4

 

 

 

a

51

x

+ a

52

x

2

b

 

 

 

 

1

 

 

5

 

 

0, x2

0

x1

Найти такие решения (x1, x2 ), которые обеспечивали бы максимальное

(минимальное) значение целевой функции (1.4) при соблюдении условий ограничительной системы неравенств (1.5).

6

Представим геометрическую интерпретацию данной модели.

Целевая функция (1.4) есть плоскость, проходящая через начало координат. При пересечении с координатной плоскостью F = 0 она образует прямую c1x1 + c2 x2 = 0

Ограничительная система неравенств (1.5) представляет собой объемное тело, ограниченное боковой поверхностью прямой призмы, в сечении которой плоскостью F = 0 находится пятиугольник ABCDE. Эти геометрические фигуры представлены на рис. 1.1.

Рис.1.1.

Если плоскость (1.4) не вызывает сомнения, то тело ограниченное боковой поверхностью прямой призмы (1.5) требует пояснений.

Если каждое неравенство, входящее в (1.5), преобразовать в равенство, то геометрически оно представляется вертикальной плоскостью (параллельной координате F ), т.к. в уравнении отсутствует переменная F . При пересечении с координатной плоскостью F = 0 имеем прямую, аналитическое выражение которой совпадает с аналитическим выражением для нашей вертикальной плоскости.

При возвращении к неравенству меняется и геометрическое представление. Рассмотренная ранее вертикальная плоскость делит трехмерное пространство на два полупространства. Одно из них есть геометрическое место (множество) точек, каждая из которых своими

7

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

Исследуя, таким образом, каждое неравенство (1.5) приходим к выводу, что система неравенств образует бесконечное тело, ограниченное боковой поверхностью прямой призмы, в сечении которой плоскостью F = 0 лежит пятиугольник ABCDE.

При пересечении тела, ограниченного боковой поверхностью призмы и наклонной плоскости F = c1x1 + c2 x2 получается наклонный пятиугольник

A1B1C1D1E1 . Иными словами, плоскость F,ограниченная пятиугольником A1B1C1D1E1 есть геометрическое место точек одновременно принадлежащих и плоскости F = c1x1 + c2 x2 , т.е. целевой функции и рассмотренному выше

телу, т.е. системе ограничений (1.5).

Задача линейного программирования– отыскание решения (x1, x2 ), которые обеспечивали бы max(min)F (1.4) при соблюдении ограничений

(1.5) в геометрической интерпретации будет сформулирована так: найти такие точки (множество точек) на плоскости x1Ox2 , которые обеспечивали

бы max(min)F на наклонной плоскости, и одновременно принадлежали бы

телу, ограниченному боковой поверхностью призмы. На рис.1.1 это точки A

и C.

Вточке A имеем минимум целевой функции : min F(x1A , x2 A )= A1 A .

Вточке С имеем максимум целевой функции : max F(x1C , x2C )= C1C .

На рис.1.1 наглядно видно решение рассматриваемой задачи. Но решать ее подобным образом ( строить геометрические тела в трехмерном пространстве) достаточно не просто. Реально задачу линейного программирования геометрическим методом решают на плоскости x1Ox2 .

Прямая c1 x1 + c2 x2 = 0 , проведенная на плоскости x1Ox2 одновременно является линией уровня плоскости F = c1 x1 + c2 x2 = 0 , т.к. все точки на этой линии имеют равные аппликаты в данном случае равные нулю. Одновременно эта линия показывает значение целевой функции равной нулю. Изменение местоположения линии уровня показывает изменение значения целевой функции.

Нас интересует увеличение значения F до максимально возможной величины, т.е. перемещение линии уровня по наклонной плоскости подальше от начала координат. Из теории скалярного поля известно, что если F = F(x1, x2 )– скалярная функция, как в нашем случае, то градиент

 

 

 

F

 

 

F

 

 

 

 

 

F

 

F

 

 

 

 

 

 

 

 

 

 

 

 

 

скалярного поля F

grad F =

i +

 

j

 

 

 

,

 

укажет

x

x

 

 

или grad F =

x

x

 

 

 

 

 

1

 

 

 

2

 

 

 

 

 

1

 

 

2

 

 

направление наинтенсивнейшего изменения (наискорейшего возрастании) этой функции в точке, где он определен. Вектор grad F всегда перпендикулярен линиям уровня.

8

В нашем случае: F = c1x1 + c2 x2 ; grad F = F i + F j = c1i + c2 j .

x1 x2

Вектор grad F стационарен, т.е. он не изменяется ни по модулю, ни по

направлению в любой точке плоскости. Это важное обстоятельство показывает, что увеличение целевой функции происходит только в одном направлении. С другой стороны это значит: чтобы увеличить значение целевой функции от F = 0 и более линию уровня– прямую F = 0 нужно

перемещать по плоскости параллельно самой себе в направлении grad F . На рис. 1.1 показан процесс перемещения прямой F = 0 параллельно

самой себе по плоскости в направлении grad F . При пересечении с боковой поверхностью прямой призмы в точке A1 эта прямая покажет значение целевой функции min F = A1 A, а двигаясь дальше при пересечении с поверхностью призмы в точке C1 – max F = C1C .

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

Система ограничений (1.5) будет иметь такое же аналитическое выражение как и прежде, но геометрически будет выражаться многоугольником ABCDE (рис.1.1 и 1.2).

Рис.1.2.

Вектор grad F = F i + F j остается неизменным.

x1 x2

Параллельное перемещение прямых– линий уровня по плоскости F проектируется в такое же параллельное перемещение прямой F = 0 но

9