Тема 4. Задачи линейного программирования

Основные понятия исследования операций. Основные понятия задач и методов математического программирования. Постановка задачи линейного программирования. Виды задач линейного программирования. Линейное и целочисленное программирование. Графическая интерпретация двумерной задачи линейного программирования. Теория двойственности в анализе оптимальных решений экономических задач. Постановка и различные формы записи задач линейного программирования. Стандартная и каноническая формы представления. Симплекс-метод и симплексные таблицы. Экономическая интерпретация элементов таблицы. Двойственные задачи и методы, их интерпретация. Экономическая и математическая формулировки транспортной задачи. Правила построения цепей. Смысл потенциалов, метод потенциалов. Основные способы построения начального опорного решения. Транспортные задачи с нарушенным балансом производства и потребления.

 

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

Контрольные вопросы по теме 4:

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

2. Чем выделяется задача целочисленного программирования?

3. Как построить многоугольник решений?

4. Что называется нулевой линией уровня целевой функции?

5. Как получить каноническую форму записи задачи линейного программ-мирования?

6. Как заполняется симплекс-таблица?

7. Какие преобразования симплекс таблицы необходимо выполнять для получения экстремального решения?

8. Сформулируйте критерий оптимальности допустимого решения.

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

10. Как выписать решение основной задачи, опираясь на решение двойственной задачи?

Тема 5. Нелинейное программирование

Выпуклые множества и их свойства. Угловые точки. Выпуклые и вогнутые функции. Основная задача выпуклого программирования. Условия Куна-Таккера в градиентной форме. Необходимый признак локального максимума для задач с выпуклыми ограничениями. Достаточный признак для задач выпуклого программирования. Усиленные условия Куна-Таккера.

 

Основные термины: множество, выпуклое множество, выпуклая функция, вогнутая функция, угловые точки.

 

Контрольные вопросы по теме 5:

1. Дайте понятие выпуклого множества.

2. Приведите примеры выпуклых и невыпуклых множеств.

3. Дайте понятия выпуклой и вогнутой функций.

4. Приведите примеры выпуклых и вогнутых функций.

 

ПЛАНЫ ПРАКТИЧЕСКИХ ЗАНЯТИЙ

Практическое занятие 1 по теме: «Нахождение наибольшего и наименьшего значений непрерывной функции на отрезке»

План:

1. Изучение понятие наибольшего и наименьшего значения функции на отрезке

2. Знакомство с алгоритмом вычисления наибольшего и наименьшего значения функции на отрезке.

3. Применение изученного алгоритма при решении задач.

 

Контрольные вопросы и задачи

1) Найти наибольшее и наименьшее значения функции f (x) = 2 x ³ – 6 x + 5 на отрезке .

Решение. Находим критические точки, принадлежащие :

f¢ (x) = 6 x ² – 6 = 6(x ² – 1), 6(x ² – 1) = 0, x ₁ = –1, x ₂ = 1.

Вычислим значения функции в этих точках:

f (–1) = 2 × (–1)³ – 6 × (–1) + 5 = 9; f (1) = 2 × 1³ – 6 × 1 + 5 = 1.

Вычислим значения функции на концах отрезка:

Таким образом, наибольшее значение данной функции на рассматриваемом отрезке есть f (–1) = 9, а наименьшее

Ответ: f (–1) = 9,

2) Найти наибольшее и наименьшее значения функции f (x) = 5 на отрезке [4; 40].

Решение. Находим критические точки функции, лежащие внутри данного отрезка:

Вычисляем значения функции на концах отрезка и в критической точке: f (4) = 11, f (12) = 13, f (40) = 5. Из полученных значений выбираем наибольшее и наименьшее:

, .

Ответ: , .

3) Дана функция f (x) = | x ² – 6 x + 5 |. Найти наибольшее и наименьшее значения функции f на отрезке [2; 6].

Решение. Рассмотрим функцию f на отрезке [2; 6]:

Для нахождения критических точек функции f, непрерывной на [2; 6], нужно найти внутренние точки отрезка [2; 6], в которых производная равна нулю или не существует. Имеем:

В точке x = 5 производная не существует; при x = 3. Итак, критические точки: 3 и 5.

Вычисляем значение функции в критических точках и на концах отрезка: f (2) = 3, f (3) = 4, f (5) = 0, f (6) = 5;

, .

Ответ: , .

4) Найти наибольшее значение функции f (x) = x ln 5 – x ln x на отрезке .

Решение. = ln 5 – ln x – 1 = при . Сравнение значений функции на концах отрезка и в критической точке приводит к сложным вычислениям. Вместо этого проведем исследование функции на монотонность. Учитывая непрерывность функции в точке и тот факт, что при производная положительна, а при отрицательна, приходим к выводу, что на промежутке функция возрастает, а на промежутке убывает. Это и означает, что значение функции в точке является наибольшим из всех значений функции на данном отрезке.

Литература

Основная:

1. Высшая математика для экономистов / под ред. Н.Ш. Кремера. - М.: ЮНИТИ, 2002. - С. 217-224.

2. Замков, О.О. Математические методы в экономике: учебник. / О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемых. - М.:, Изд-во МГУ им. М.В.Ломоносова «ДИС», 1988. - С. 61–64, 70.

3. Ильин, В.А., Высшая математика: учебник / В.А. Ильин, А.В. Куркина. - М.: Проспект, 2009. - С. 258–258.

4. Красс, Математика для экономических специальностей: учебник / М.С. Красс. - М.: ИНФРА-М, 1999. - С. 115–117.

Дополнительная:

1. Баврин, И.И. Математика для гуманитариев: учебник / И.И. Баврин. - М.: Академия, 2011. - С. 101–111.

2. Математика: Математический анализ. Дифференциальные уравнения. Теория вероятностей. Математическая статистика.: учебно-методическое пособие / Под ред. А.Н. Данчула. - М.: 2004. - С. 20–23.

3. Шипачёв В.С. Высшая математика. Базовый курс: учебное пособие / под ред. А.Н. Тихонова. - М.: Юрайт, 2011. - С. 288-293.

Практическое занятие 2 по теме: «Локальный экстремум функций многих переменных. Наибольшее и наименьшее значения функции в ограниченной замкнутой области. Условный экстремум»

План:

1. Изучение понятие локального и условного экстремумов.

2. Формулирование необходимых и достаточных условий экстремума.

3. Решение задач.

 

Контрольные вопросы и задачи

1)Найти стационарные точки функции

Находим частные производные первого порядка, приравниваем их к нулю и записываем систему уравнений:

Из второго уравнения следует, что или , или . Подставляя по очереди эти значения в первое уравнение, найдём четыре стационарные точки:

2) Ранее в примере 1 было установлено, что функция

имеет четыре стационарные точки:

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

.

В точке имеем: A= 10, B= 0, C= 2. Здесь , значит, точка является точкой экстремума, и так как A положительно, то этот экстремум – минимум. В точке соответственно будет A=– 10, B= 0, C=– 4/3. Это точка максимума. Точки и не являются экстремумами функции, так как в них .

3) Исследовать функции на экстремум:

1. . Ответ: .

2. . Ответ: – седловая точка.

3. . Ответ: .

4. . Ответ: – седловые точки.

4) Найти условный экстремум функции при условии

Решение: Составим функцию Лагранжа

Имеем

Система имеет два решения

Далее,

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

5)Найти условные экстремумы функции при наличии ограничения

Решение: Построим функцию Лагранжа

Стационарные точки определим из системы

Умножим первое уравнение на , а второе – на . После вычитания получим

.

Если , то из первых двух уравнений системы . Но такие значения переменных и не удовлетворяют уравнению связи. Значит и так как , то . Подставляя это в уравнение связи, получаем: откуда , .

Итак, единственная стационарная точка функции Лагранжа .

Далее,

Тогда для при и получаем

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

 

Литература

Основная:

1. Высшая математика для экономистов / под ред. Н.Ш. Кремера. - М.: ЮНИТИ, 2002. С. 217–224.

2. Замков, О.О. Математические методы в экономике: учебник. / О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемых. - М.:, Изд-во МГУ им. М.В. Ломоносова «ДИС», 1988. - С. 61–64, 70.

3. Ильин, В.А., Высшая математика: учебник / В.А. Ильин, А.В. Куркина. - М.: Проспект, 2009. - С. 258–258.

4. Красс, Математика для экономических специальностей: учебник / М.С. Красс. - М.: ИНФРА-М, 1999. - С. 115–117.

Дополнительная:

1. Баврин, И.И. Математика для гуманитариев: учебник / И.И. Баврин. - М.: Академия, 2011. - С. 101–111.

2. Кремер, Н.Ш. Математика для экономистов: от Арифметики до Эконометрики: учебно-справочное пособие. / Н.Ш. Кремер. - М.: Юрайт, 2011. - С. 187-198.

3. Математика: Математический анализ. Дифференциальные уравнения. Теория вероятностей. Математическая статистика.: учебно-методическое пособие / Под ред. А.Н. Данчула. - М.: РАГС, 2004. - С. 20–23.

Практическое занятие 3 по теме: «Задачи линейного программирования»

План:

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

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

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

4. Решение задач.

 

Контрольные вопросы и задачи

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

2) Найдите решение задачи целочисленного программирования:

3) Для изготовления трёх видов изделий используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования указаны в таблице (см. ниже). В этой же таблице указан общий фонд рабочего времени каждого из типов используемого оборудования, а так же прибыль от реализации одного изделия данного вида. Требуется определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной.

 

Тип оборудования	Затраты времени (станко-ч) на обработку одного изделия вида	Общий фонд рабочего времени оборудования (ч.)
А	В	С
Фрезерное
Токарное
Сварочное
Шлифовальное
Прибыль (руб.)

Литература

Основная:

1. Замков, О.О. Математические методы в экономике: учебник. / О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемых. - М.: ДИС, 1988. - С. 130–133.

2. Кириллов, А.Л. Математика для управленцев: курс лекций. / А.Л. Кириллов. - СПб.: СЗАГС, 1999. - С. 158–176.

3. Соколов, А.В., Методы оптимальных решений. В 2 т. Т.1. Общие положения. Математическое программирование. / А.В. Соколов, В.В. Токарев. - М.: ФИЗМАТЛИТ, 2011. - С. 422–503.

Дополнительная:

1. Акулич, И.Л. Математическое программирование в примерах и задачах. / И.Л. Акулич. - М.: Высш. шк., 1993. - С. 336.

2. Алексеев, В.М., Сборник задач по оптимизации. Теория. Примеры. Задачи. / В.М. Алексеев, Э.М. Галеев, В.М. Тихомиров. - М.: Наука, 1984. - С. 288.

3. Гармаш, А.Н., Математические методы в управлении: учебное пособие. / А.Н. Гармаш, И.В. Орлов. - М.: ИНФРА-М, 2012. - С. 48–61.

4. Кремер, Н.Ш. Математика для экономистов: от Арифметики до Эконометрики: учебно-справочное пособие. / Н.Ш. Кремер. - М.: Юрайт, 2011. - С. 400–419.