programma_MOR

f (x1, x2 )

8. ПРИМЕРНЫЕ ВОПРОСЫ К ЭКЗАМЕНУ

1.Виды математических моделей, используемых в экономике.

2.Принятие решений на основе моделей оптимизации.

3.Выпуклые множества и их свойства.

4.Метод множителей Лагранжа с ограничениями типа равенств.

5.Метод множителей Лагранжа с ограничениями типа неравенств.

6.Постановка задачи ЛП.

7.Геометрическое решение ЗЛП.

8.Симплексный метод решения ЗЛП.

9.Двойственные задачи ЗЛП.

10.Транспортная ЗЛП. Методы составления опорных планов.

11.Проверка оптимальности плана ЗЛП. Метод потенциалов.

12.Основные понятия матричной теории игр: стратегия, выигрыш, нижняя цена игры, верхняя цена игры, платежная матрица.

13.Решения антагонистических игр.

14.Решения игр с природой.

15.Критерии выбора решений в условиях неопределенности.

9. ПОНЯТИЙНО-ТЕРМИНОЛОГИЧЕСКИЙ СЛОВАРЬ ДИСЦИПЛИНЫ

НЕЛИНЕЙНЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ.

Математическая модель задачи нелинейного программирования с двумя неизвестными имеет вид: L max(min) при ограничениях gi (x1 , x2 ) C, i 1, m .

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

Лангранжа			L(x1	, x , )	f (x1, x2 )		(g(x1, x2 )	C) ,	где λ	– множитель	Лагранжа.
				2
Нахождение			локального		экстремума целевой				функции	L f (x1 , x2 ) при условии
g(x1 , x2 )		C		требует		решения		следующей		системы	уравнений
Lx	f x	(x1 , x2 )		g x (x1 , x2 )		0,
1	1			1
Lx2	f x2 (x1 , x2 )			g x2 (x1 , x2 )		0,
L	g(x1 , x2 ) C 0.

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Линейное программирование – это наука о методах исследования и нахождения

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

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

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

			n
L(x)				c j x j	max(min)
			j	1
n aij x j
				( )bi ,	x j 0, i 1, m, j 1, n.
j 1

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

			n
L(x)				c j x j	max(min)
			j	1
n aij x j
				bi , x j	0, i 1, m, j 1, n.
j 1

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

11

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

X (x1 , x2 ,...xn ) , удовлетворяющий системе ограничений.

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

обозначается Х опт .
Неравенство вида			ai1 x1	ai2 x2 bi ( )0 определяет полуплоскость двухмерного
пространства.
Уравнение вида ai1x1			ai2 x2	bi 0 называется граничной прямой.

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

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

Точка В называется граничной точкой выпуклой области, если в любой окрестности этой точки содержатся как точки данной области, так и не принадлежащие к ней.

Точка С называется угловой точкой выпуклой области, если она является граничной и не лежит внутри отрезка, соединяющего две другие точки этой области.

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

Ограниченной называется область, если существует такое число M			0 , что модуль радиуса-
вектора x , соединяющего начало координат с любой точкой			области, по абсолютной
величине меньше М.

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

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

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

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

Область	решения			системы,	удовлетворяющая	условиям	неотрицательности
(x j 0,	j 1, n) , называется областью допустимых решений.

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

определении минимума.

Нулевая

линия

уровня

линейной

целевой

функции

L(x ; x )

c x

c x

max(min) задается уравнением

c x

c

2

x

2

0 .

1

2

1

1

2

2

1

1

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

L(x1, x2 )

называется вектор, координаты которого равны

соответствующим частным производным в точке (0,0) gradL

L

;

L

c ; c

.

2

x1

x2

1

Двойственная задача. Если исходная задача линейного программирования имеет вид

n

L(x)

c j x j

max(min)

j

1

n aij x j

( )bi ,

x j 0, i 1, m, j 1, n,

j 1

12

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

			m bi yi
S( y)				min(max)
			i 1
m aij yi
			( )c j ,	yi 0, i 1, m, j 1, n.
i 1

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

оптимальное решение,

причем для любых оптимальных решений X

и Y выполняется

равенство L(x)

max

S( y)

min

.

Если одна из двойственных задач неразрешима ввиду того, что

(или

L(x)max

S ( y)min

), то другая задача не имеет допустимых решений.

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

достаточно, чтобы они удовлетворяли системе уравнений

m

xоптj

aij yоптi

c j

0,

i 1

n

yоптi

aij xоптj

bi

0.

j

1

Транспортная задача линейного программирования – это задача определения рационального плана транспортирования груза xij от поставщиков ai к потребителям b j с учетом тарифа сij и имеющего минимальную стоимость L( X ) min .

ТРАНСПОРТНАЯ ЗАДАЧА.

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

L( X )

m n	cij xij	min,
i 1 j	1

n xij		m xij bj ,	m ai	n bj , xij 0, i		, j		.
	ai ,				1, m		1, n
j 1		i 1	i 1	j 1

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

L( X )

m n	cij xij	min,
i 1 j	1

n xij		m xij bj ,	m ai	n bj , xij 0, i		, j		.
	ai ,				1, m		1, n
j 1		i 1	i 1	j 1

Оптимальным решением транспортной задачи линейного программирования является матрица X опт xij m n , удовлетворяющая системе ограничений и доставляющая минимум

целевой функции.

Метод северо-западного угла – распределение груза начинается с верхней левой клетки и продолжается вниз и вправо.

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

Потенциалами ui и v j называют	числа, удовлетворяющие равенству ui	v j cij для
занятых клеток и неравенству ui v j	cij 0 для свободных клеток в оптимальном решении.
В опорном решении, не являющимся оптимальным, неравенство ui v j cij		0 хотя бы в

одной из свободных клеток не выполняется.

Переход от одного опорного решения к другому проводится на основе перемещения груза по циклу, построенного таким образом, что одна из вершин замкнутого многоугольника

13

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

ТЕОРИЯ ИГР Теория игр – раздел математики, в котором рассматриваются задачи построения

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

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

Задача первого игрока – максимизировать свой выигрыш, задача второго игрока –

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

Игру можно представить в виде матрицы, в которой строки – стратегии первого игрока, столбцы – стратегии второго игрока, а элементы матрицы – выигрыши первого игрока

		a11	a12	...	a1n
	aij m n	a21	a22	...	a2n	.
		...	... ... ...
		am1	am 2	...	amn m n

Нижней ценой игры α называется гарантированный выигрыш, который может обеспечить

себе первый игрок	max min aij . Первому игроку необходимо выбрать сначала
	i	j

минимальный элемент в каждой строке, а затем из всех минимальных элементов выбрать максимальный

min a11 , a12 ,...., a1n

max min a21 , a22 ,...., a2n .

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

min am1 , am 2 ,...., amn

Верхней ценой игры β называется минимальный гарантированный проигрыш второго игрока

min max aij . Второму игроку необходимо выбрать максимальный элемент в каждом

j i

столбце, а затем из всех максимальных выбрать минимальный: max a11 , a21 ,...., am1

max a12 , a22 ,...., am 2	.
min .......... .......... .......... ...
max a1n , a2n ,...., amn

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

14

10. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ)

ОСНОВНАЯ ЛИТЕРАТУРА Л1. Красс М.С., Чупрынов Б.П. Математика для экономического бакалавриата.

http://znanium.com/catalog.php?item=bookinfo&book=221082– М.: ИНФРА-М, 2011–471 с.

Л2. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании: Учеб. — 5-е изд., испр. и доп.— М.: Дело, 2006. — 720 с.

Л3. Письменный Д.Т. Конспект лекций по высшей математике. / полный курс; 8-е изд - М.: Айрис-пресс, 2009

Л4. Гончарь П.С., Гончарь Л.Э., Завалищин Д.С. Теория игр. Учебное пособие; – Екатеринбург: УрГУПС, 2011–112 с.

Л5. Гончарь П.С., Гончарь Л.Э., Завалищин Д.С. Задания по теории игр с примерами решения. Учебно-методическое пособие; – Екатеринбург: УрГУПС, 2012–74 с.

ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА Д1. Электронное учебное пособие «Математика»/Г.А. Тимофеева и др.

https://www.usurt.ru/in/files/index2/7_5/001_2_7_5. УрГУПС, 2007

Д2. Гниломедов П.И., Пирогова И.Н., Скачков П.П. Линейное программирование. Методические указания/ Методические указания для проведения занятий и самостоятельной работы студентов заочной формы обучения по курсу «Линейное программирование»– Екатеринбург:УрГУПС, 2007

ИНТЕРНЕТ РЕСУРСЫ Электронное учебное пособие «Математика»/Г.А. Тимофеева и др.

https://www.usurt.ru/in/files/index2/7_5/001_2_7_5. УрГУПС, 2007

Интернет-сайт издательства «Лань» http://www.lanbook.ru Электронная библиотечная система http://znanium.com/

11.МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

−Презентации, мультимедиа-оборудование;

−Раздаточные материалы к практическим занятиям;

−Электронные учебно-методические материалы;

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

15

12. ЛИСТ ИЗМЕНЕНИЙ И ДОПОЛНЕНИЙ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Федеральное бюджетное государственное образовательное учреждение высшего

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

«Уральский государственный университет путей сообщения» (ФБГОУ ВПО УрГУПС)

ДОПОЛНЕНИЯ И ИЗМЕНЕНИЯ РАБОЧЕЙ ПРОГРАММЫ На 20__ - 20__ учебный год

по дисциплине МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ для направления подготовки 080100 «Экономика»

Профили подготовки «Экономика предприятий и организаций, Бухгалтерский учет, анализ и аудит, Экономика труда, Мировая экономика»

очной формы обучения

Основание: ___________________________________________________________

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

___________________________________________________________

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

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

Дополнения и изменения внесены на заседании кафедры ________________________

Протокол № ____от «__»____________20___г.

Автор рабочей программы	____________________	/Гончарь Л.Э./
Зав. кафедрой
«Высшая и прикладная математика» ____________________		/Тимофеева Г.А./
Зав. кафедрой
«Экономика транспорта»	____________________	/Рачек С.В./
Декан факультета
экономики и управления	____________________	/Ревина Е.В./

16

Приложение

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ОРГАНИЗАЦИИ ТЕКУЩЕГО КОНТРОЛЯ РАБОТЫ СТУДЕНТОВ

1. Организация текущего контроля

Пример организации текущего контроля по дисциплине «Методы оптимальных решений»

	Номер	Темы рабочей программы, подлежащие								Всего
Вид		контролю						Сроки	Макс.	баллов
	контр.						Методы и способы контроля
занятий								проведения	балл	по виду
	точки	1	2	3	4	5
										занятий
1	2	3					4	5	6	7
Лекции	Л-1		*				Теоретическая часть защиты РГР часть 1	5 неделя	10	20
	Л-2			*	*		Теоретическая часть защиты РГР часть 2	11 неделя	10
	П-1		*				Практическая часть защиты РГР часть 1	5 неделя	10
	С-1		*				Выполнение РГР часть 1	2–5 неделя	10
Практи
	П-2			*	*		Практическая часть защиты РГР часть 2	14 неделя	10
ческие										80
	С-2			*	*		Выполнение РГР часть 2	11–13 неделя	10
занятия
	П-3					*	Письменная контрольная работа	16 неделя	20
	П-4		*	*	*	*	Деловая игра (итоговое занятие)	18 неделя	20
ИТОГО:			35	35		30				100

17

2. График текущего контроля

Пример графика текущего контроля

										Номер недели										Всего
Вид занятий																				часов
	1	2	3	4	5	6	7	8	9		10	11	12	13	14	15	16	17	18
Лекции	2	2	2	2	2	2	2	2	2		2	2	2	2	2	2	2	2	2	36
					Л-1							Л-2						Л-2
Практическ.	2	2	2	2	2	2	2	2	2		2	2	2	2	2	2	2	2	2	36
Занятия					П-1							П-2					П-3		П-4
Самостоят.	4	4	4	4	4	4	4	4	4		4	4	4	4	4	4	4	2	2	72
Работа											С-1						С-2
Групповые			1		1		1				1			1		1	1		1	8
консультац.
					Рейтинг							Рейтинг						Рейтинг
																			Итого:	152

18

3.Оценивание знаний студентов

3.1.Оценка знаний по теоретической подготовке

Каждая из контрольных точек Л-1, Л-2 (теоретическая часть защиты индивидуальной расчетно-графической работы), охватывает несколько тем, вынесенных на текущий контроль, и оценивается 10 баллами каждая. Контроль проводится в форме собеседования.

Максимальная оценка каждой темы составляет 10 баллов. Оценка каждого ответа формируется по следующей шкале:

10 баллов – ответ на вопрос дан правильный и полный; 5 баллов– ответ дан правильный, но неполный;

0 баллов – ответ на вопрос отсутствует или содержание ответа не совпадает с поставленным вопросом.

Работа может быть зачтена без защиты с максимальным баллом по результатам взаимодействия с преподавателем в процессе ее выполнения. Оценка снижается до 5 баллов в случае задержки представления или защиты работы более чем на 3 недели.

Суммарный балл по всем контрольным точкам составляет 20.

3.2. Оценка знаний по практической подготовке

Каждая из контрольных точек П-1, П-2 (практическая часть защиты индивидуальной расчетно-графической работы), охватывает несколько тем, вынесенных на текущий контроль, направлена на контроль усвоения студентами материала соответствующих практических занятий, состоит задач и оценивается 10 баллами каждая. Контроль проводится в форме собеседования по решению задач РГР.

Максимальная оценка каждой темы составляет 10 баллов. Оценка каждого ответа формируется по следующей шкале:

10 баллов – ход решения задачи описан правильно, аналогичная задача решена

верно;

5 баллов– ход решения задачи описан правильно, аналогичная задача решена с арифметическими ошибками;

0 баллов – ход решения задачи не описан, задача не решена.

Работа может быть зачтена без защиты с максимальным баллом по результатам взаимодействия с преподавателем в процессе ее выполнения. Оценка снижается до 5 баллов в случае задержки представления или защиты работы более чем на 3 недели

Контрольная точка П-3 представляют собой письменную контрольную работу из 5 заданий. Максимальный балл за каждое задание – 4. Оценка работы формируется следующим образом:

4 баллов –задача решена верно;

1 балл –задача решена частично; 0 баллов –задача не решена или студент отсутствовал.

При повторном (последующем) написании контрольной работы оценка снижается до 2 баллов за задание.

Контрольная точка П-4 представляет из себя деловую игру. Баллы выставляются всей команде группой экспертов, назначенных из студентов. Баллы группе экспертов выставляются за полноту аргументов в оценке выступления товарищей. Максимальный балл за контрольную точку 20.

Суммарный балл по всем контрольным точкам составляет 80.

3.3. Оценка самостоятельной работы студентов

Каждая из контрольных точек С-1, С-2 (индивидуальная расчетно-графическая работа в двух частях) оценивается 10 баллами по факту выполнения и сдачи на проверку. Количество заданий в работе преподаватель выбирает сам.

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

Оценка снижается до 4 баллов, в случае задержки представления работы более чем на 3 недели

Суммарный балл по всем контрольным точкам составляет 20.

19