Методы оптимизации в экономике (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Саратовский государственный университет имени

Экономический факультет

УТВЕРЖДАЮ

Проректор по учебно-

методической работе, проф.

_________________

"__" __________________2013 г.

Рабочая программа дисциплины

Методы оптимизации в экономике

Направление подготовки

080400 Управление персоналом

Профиль подготовки

Управление персоналом организации

Квалификация (степень) выпускника

Бакалавр

Форма обучения очная

Саратов, 2013
1. Цели освоения дисциплины «Методы оптимизации в экономике»

Необходимость изучения дисциплины «Методы оптимизации в экономике» для студентов объясняется фундаментальной ролью, которую играют математические модели в управлении пер

соналом.

Основными целями освоения дисциплины «Методы оптимизации в экономике» являются:

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

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

3. Обучение самостоятельному решению типовых экономических задач с использованием экономико-математических методов и персональных ЭВМ.

2.  Место дисциплины «Методы оптимизации в экономике» в структуре ООП бакалавриата 080400 Управление персоналом

Дисциплина «Методы оптимизации в экономике» является дисциплиной по выбору вариативной части математического и естественно научного цикла Б2.ДВ1.

При изучении дисциплины «Методы оптимизации в экономике» студентам достаточно знать содержание курса «Математика», пройденного в 1,2 и 3 семестрах.

Знания, полученные студентами в процессе изучения дисциплины «Методы оптимизации в экономике» могут быть использованы при изучении дисциплин предметной области.

3.  Компетенции обучающегося, формируемые в результате освоения дисциплины «Методы оптимизации в экономике»

Процесс изучения дисциплины направлен на формирование следующих компетенций:

·  владением методами количественного анализа и моделирования, теоретического и экспериментального исследования (ОК-14).

(Наименование в соответствии с ФГОС ВПО).

В результате освоения дисциплины студент должен:

Знать:

- основные понятия и теоремы математического моделирования.

Уметь:

- построить математическую модель в соответствии с целью исследования и с исследуемой ситуацией;

- определить критерии и ограничения при моделировании;

- связать построение плана с прогнозом спроса и доступными ресурсами, с прогнозом развития ситуации;

- дать графическое представление решений для простых ситуаций;

- провести компьютерную оптимизацию решений средствами пакетов прикладных программ;

- выявлять источники неопределенности в работе системы;

- определить характеристики надежности (устойчивости) оценок решений средствами пакетов прикладных программ;

- применять полученные знания к анализу и решению задач производства;

- применять полученные знания к анализу и решению задач транспортной логистики;

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

Владеть:

- понятийным аппаратом математического моделирования;

- методами построения, анализа и применения математических моделей для оценки состояния и прогноза развития экономических явлений и процессов (в части компетенций, соответствующих методам математического моделирования).

4. Структура и содержание дисциплины «Методы оптимизации в экономике»

Общая трудоемкость курса «Методы оптимизации в экономике» составляет 3 зачетных единиц (108 часов).

	Наименование темы	Бюджет учебного времени	форма текущего и итогового контроля
всего часов	в том числе
лек- ции	лабор. и практ. занятия	семин. занятия	сам. работа
1	2	3	4	5	6	7	8
Очная форма обучения
1.	Задача линейного программирования	12	2	4		6	Устный опрос, разбор практических задач
2.	Симплексный метод линейного программирования	24	4	8		12	Промежуточный контроль
3.	Двойственность в линейном программировании	24	4	8		12	Устный опрос, разбор практических задач
4.	Транспортная задача	24	4	8		12	Устный опрос, разбор практических задач
5.	Матричные игры	24	4	8		12	Устный опрос, разбор практических задач
6.	Промежуточная аттестация
	Итого	108	18	36		54	Зачет

Содержание учебной дисциплины

«Методы оптимизации в экономике»

Темы и краткое содержание лекций

Тема 1. Задача линейного программирования (ЛП)

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

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

Тема 2. Симплексный метод линейного программирования

Задача линейного программирования в симплексной форме. Первое опорное решение. Исследование опорного решения на оптимальность, критерий оптимальности. Условия неограниченности функции цели на множестве допустимых решений. Переход от одного опорного решения к другому. Алгоритм симплекс-метода в невырожденном случае, понятие о зацикливании. Метод искусственных базисных неизвестных. Геометрическая интерпретация симплекс-метода. Формализация и решениена ЭВМ оптимизационных экономических задач.

Тема 3. Двойственность в линейном программировании

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

Тема 4. Транспортная задача

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

Тема 5. Матричные игры

Игры как модель конфликтной ситуации. Основные понятия теории игр. Матричная игра двух лиц с нулевой суммой. Нижняя и верхняя цена игры, понятие о седловой точке. Чистые и смешанные стратегии игроков, математическое ожидание выигрыша. Игры с седловой точкой. Оптимальные стратегии и цена игры. Неравновесные игры. Основная теорема теории игр. Эквивалентность матричной игры двух лиц с нулевой суммой паре двойственных задач линейного программирования. Решение игры симплексным методом. Приближенное решение матричной игры. Редукция матрицы игры. Доминирующие стратегии.

Игры с «природой». Критерии принятия решения в условиях неопределенности.

5.  Образовательные технологии дисциплины «Методы оптимизации в экономике»

При проведении лекционных и практических занятий предусматривается использование информационных технологий, включающих такие математические программ, как Mathematica, Maple и другие. Реализация компетентностного подхода предусматривает использование в учебном процессе активных и интерактивных форм проведения занятий (компьютерных симуляций, деловых и ролевых игр, разбор конкретных ситуаций, электронное тестирование знаний, умений и навыков и др.) в сочетании с внеаудиторной работой с целью формирования и развития профессиональных навыков обучающихся. Например, одним из видов дидактической игры является анализ профессиональных ситуаций. Студентам предлагается самостоятельно изучить основные понятия линейного программирования.

6.  Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины «Методы оптимизации в экономике»

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

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

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

Глава 1. Линейное программирование

1.1 Введение

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

1.1.2. Основные понятия линейного программирования

Определение. Общей задачей линейного программирования называется задача, которая состоит в определении максимума (минимума) целевой функции

Z(x1,...xn) = c1x1+...+cnxn max (min) ( 1)

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

(2)

(3)

xj>=0, ( j = 1,….n

Определение. Функция (1) называется целевой функцией или линейной формой задачи линейного программирования, а условия ограничениями данной задачи.

Определение. Стандартной (симметричной) задачей линейного программирования называется задача, которая состоит в определении экстремального значения целевой функции (1) при выполнении условий (2) и (4).

Определение. Основной (канонической) задачей линейного программирования называется задача, которая состоит в определении экстремального значения целевой функции (1) при выполнении условий (3) и (4).

Определение. Вектор или совокупность чисел `Х = (х1, х2, .... , хn), удовлетворяющих ограничениям задачи , называется допустимым решением или планом задачи линейного программирования.

Определение. План `Х*=(х1*, х2*, .... , хn*), при котором целевая функция (1) принимает свое оптимальное (минимальное или максимальное) значение, называется оптимальным планом.

Таким образом, линейное программирование является частью математического программирования, особенностью которого является то, что исследуемая целевая функция является линейной: Z(x1,...,xn)=c1x1+...+cnxn, а ограничения, накладываемые на переменные, представляют собой линейные уравнения или неравенства.

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

Если требуется провести поиск целочисленных значений xj, то приходим к задаче целочисленного линейного программирования (ЦЛП).

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

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

Как известно, линейное уравнение a1x1 + a2x2 = b задает на плоскости (в пространстве R2) прямую; уравнение a1x1 + a2x2 + a3x3 = b - плоскость в R3. Точно так же уравнение ai1x1 + ... + ainxn= bi (i - е ограничение в канонической задаче ЛП) определяет в пространстве Rn некоторое множество, называемое гиперплоскостью.

Определение. Фигура на плоскости называется выпуклой, если наряду с любыми ее точками М1 и М2 ей принадлежат и все точки отрезка М1М2.

Например, отрезок, треугольник, квадрат, острый угол.

Определение. Множество X называется выпуклым, если вместе с любыми двумя точками (элементами) (x, y); (x, y) X оно содержит отрезок между этими точками, т. е. точки вида

y+(1-)x, (01).

Это уравнение является уравнением отрезка.

Теорема. Пересечение любого числа выпуклых множеств является выпуклым множеством.

Очевидно, прямая в R2, плоскость в R3 являются выпуклыми множествами. Точно так же, выпуклым множеством является гиперплоскость ai1x1 + ... + ainxn = bi и полупространство (вместе с границей) в Rn, определяемое i-м ограничением в стандартной задаче:

ai1x1 + ... + ainxnbi.

Система ограничений (2.2) задает множество М - пересечение m выпуклых множеств в n-мерном евклидовом пространстве Rn, поэтому само является выпуклым множеством. Множество М называется выпуклым многогранником (областью) допустимых решений.

При наличии только двух переменных М задает многоугольник решений в R2, а в случае переменных x1, x2, x3 - выпуклый многогранник в пространстве R3.

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

Теорема. Функция цели (2.1) задачи линейного программирования достигает экстремума в угловой точке выпуклого множества допустимых решений.

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

Основные шаги графического метода

1. Составляется задача линейного программирования в общем виде.

2. От ограничений - неравенств переходят к ограничениям - равенствам.

3. Строят графики прямых, соответствующих полученным уравнениям.

4. Выделяют полуплоскости, удовлетворяющие каждому неравенству-ограничению, и общую часть (пересечение) полуплоскостей, удовлетворяющую всем неравенствам системы, то есть область (многоугольник) допустимых решений (ОДР).

5. Строят прямую, соответствующую функции цели Z.

6. Перемещают прямую, соответствующую функции цели, параллельно самой себе до положения, когда прямая и область допустимых решений будут иметь одну общую точку или сторону ОДР. Это будет экстремумом целевой функции.

7. Определяют координаты точки экстремума, решая систему уравнений прямых, пересекающихся в этой точке.

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

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

Задача 1 (Производственная задача)

Предприятие производит продукцию двух видов А и В, для производства которых используется сырье трех видов. На изготовление единицы изделия А требуется затратить сырья каждого вида 16, 8 и 5 кг соответственно, а для единицы изделия В - 4, 7 и 9 кг. Производство обеспечено сырьем каждого вида в количестве 784 кг, 552 кг и 567 кг соответственно. Стоимость единицы изделия А составляет 4 руб., единицы изделия В - 6 руб.

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

Решение

Дадим математическую постановку задачи.

Пусть продукции А производится x1 единиц, а продукции В - x2единиц.

Стоимость всех изделий А составит 4х1 рублей, изделий В -6х2 рублей, суммарная: Z = 4x1 + 6x2.

Требуется затратить 16x1кг – количество сырья первого вида, идущего на изготовление всех изделий вида A; 4x2 – количество сырья первого вида, идущего на изготовление всех изделий вида B.

Получим ограничение по сырью первого вида: 16x1+4x2£784.

Аналогично определяем ограничение по сырью 2 вида: 8x1+7x2£552 и ограничение по сырью 3 вида: 5x1+9x2£567.

Количество выпускаемых изделий не может быть отрицательным. Следовательно, условие неотрицательного решения: x1³0, x2³0.

Получим задачу линейного программирования.

Требуется максимизировать функцию доходов (стоимости готовой продукции):

Z = 4x1 + 6x2 max.

При наличии системы ограничений:

Решим задачу графически.

Так как переменные x1, x2неотрицательны, то допустимые решения лежат в первом координатном углу.

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

Первому условию в системе ограничений соответствует равенство:

16x1+ 4x2=784.

Построим эту прямую по точкам:

x1	0	49
x2	196	0

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

Если прямая не проходит через начало координат, то в качестве произвольно выбранной точки удобно брать начало координат, то есть точку О (0, 0).

Для нашего случая возьмем начало координат О (0; 0) и, поставив ее координаты в неравенство, получим:

16×0 + 4×0 < 784.

Имеем верное равенство. Следовательно, полуплоскость, которой принадлежит точка О(0, 0) и есть геометрическое решение неравенства. Решением первого неравенства системы является полуплоскость, лежащая ниже прямой 16x1 + 4x2= 784. Таким же образом найдем решения каждого неравенства системы (см. рис. 1).

Решением системы неравенств будет пересечение всех полуплоскостей. Это пересечение есть выпуклое множество, называемое областью допустимых решений(ОДР).

В общем случае, ОДР может быть замкнутым выпуклым многоугольником, незамкнутым или пустым.

Для нахождения оптимального решения, то есть такого, при котором целевая функция принимает свое максимальное (минимальное) значение, дадим целевой функции Z произвольное численное значение, то есть положим Z=С (стоимость постоянная).

Множество точек 4x1+6x2=С определяет прямую, называемой линией уровня функции цели Z(x1,x2). При различных значенияхСполучаем семейство линий уровня - параллельных прямых с одним и тем же нормальным вектором . С увеличением Z они будут передвигаться в одну сторону, с уменьшением - в противоположную.

Интерес представляют линии уровня, имеющие общие точки с ОДР. ПриС = 0 общая стоимость равна нулю. Так как коэффициенты функции цели Z положительны, ее значение увеличивается при движении прямых от линии уровня, проходящей через точку O (0,0), в направлении вектора . Крайняя прямая из семейства параллельных прямых имеет с многоугольником решений общую точку А.

Координатами нормального вектора являются коэффициенты при текущих координатах в уравнении прямой Z, то есть (4;6). Поэтому для определения оптимального плана на графике достаточно построить нормальный вектор (4;6), провести прямую, перпендикулярную через крайнюю точку ОДР (рис.1), то есть точку, в которой прямая Z касается ОДР.

Рис.1. Геометрическое решение задачи

линейного программирования