VІ. Элементы нелинейного программирования

Министерство образования и науки Украины

Донецкий государственный университет

Экономики и торговли

Им. М.Туган-Барановского

Кафедра высшей и прикладной математики

М а т е м а т и ч е с к о е

П р о г р а м м и р о в а н и е

Учебное пособие

Для студентов УФФ

(II, III курс сокращенной формы обучения)

Утверждено

На заседании кафедры высшей

И прикладной математики

Протокол № ____

от “___” 2003 г.

Одобрено

учебно-методическим советом

университета

Протокол № ____

от “___” 2003 г.

Донецк 2003

УДК 319.2

Математическое программирование. Учебное пособие для студентов УФФ (II, III курс сокращенной формы обучения).

/Составитель Г.Г. Пенина. – Донецк, ДонДУЕТ, 2003. – 110 с.

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

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

Рецензенты: Узбек Е.К., канд.физ.-мат наук, доцент

Орлова Л.М., ст. преподаватель

Ó Донецкий государственный университет экономики и торговли им. М. Туган-Барановского, 2003

С о д е р ж а н и е

	стр.
1. Программа курса………………………………………………………
Введение……………………………………………………………………
2. Методические рекомендации………………………………………
2.1 Постановка задач линейного программирования…………
2.2 Графический метод……………………………………………...
2.3 Симплексный метод……………………………………………..
2.4 Двойственные задачи……………………………………………
2.5 Матричные игры…………………………………………………
2.6 Метод потенциалов……………………………………………..
2.7 Задачи о назначении……………………………………………
2.8 Дробно-линейное программирование………………………
2.9 Параметрическое программирование……………………….
3. Задания для индивидуальной работы……………………………
3.1 Постановка задач ……………………………………………….
3.2 Графический метод……………………………………………..
3.3 Симплексный метод и двойственные задачи……………….
3.4 Матричные игры…………………………………………………
3.5 Транспортные задачи…………………………………………...
3.6 Задачи о назначении……………………………………………
3.7 Дробно-линейные задачи………………………………………
3.8 Параметрические задачи……………………………………….
3.9 Целочисленные задачи…………………………………………
4. Использование компьютерных технологий для решения задач математического программирования ……………………
4.1 Пакет “The management scientist” …………………………….
4.2 Пакет “QSB”………………………………………………………
5. Литература……………………………………………………………….

1. Программа курса

Введение

1. Роль методов оптимизации в решении вопросов совершенствования управления экономикой.

2. Место математического программирования в системе планирования экономики. Примеры задач оптимизации.

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

Литература: 1(стр. 4), 2(стр. 7), 3(гл. 1), 13.

I. Математические основы программирования

1. Различные методы определения линейной зависимости векторов. Понятие базиса. Неединственность базиса.

2. Выпуклые множества, основные теоремы о них.

3. Системы линейных уравнений и неравенств. Их геометрическая интерпретация.

Литература: 1(гл. 1), 2(гл. 2), 4(гл. 2), 5(гл. 1,5), 13.

II. Общий вид задачи линейного программирования

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

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

3. Математическая постановка задач о смесях, их отличительные особенности.

4. Основная задача линейного программирования, приведение к ней. Формы модели, способы ее преобразования.

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

Литература: 1(гл. 1), 2(гл. 1,3), 4(гл. 3), 5(гл. 3), 12(гл. 2), 13

III. Методы решения общей задачи линейного программирования

1. Графический метод решения, его характерные особенности и ограниченность применения.

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

3. Метод искусственного базиса – модификация симплексного метода. Изменения в форме задачи, алгоритме решения и интерпретации переменных.

4. Алгебраический, экономический, геометрический смысл универсального метода решения.

5. Случаи вырожденности задачи, зацикливание и их устранение. Монотонность и конечность симплексного метода.

Литература: 1(гл.1), 2(гл.3), 4(гл. 4.6), 5(гл.4), 6(гл.2), 7(гл.2), 12(гл.4),13.

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

1. Структура, свойства и построение симметричных задач.

2. Основные неравенства и теоремы теории двойственности. Связь решений двойственных задач.

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

4. Несимметричные двойственные задачи и интерпретация их решений.

Литература: 1(гл. 1), 4(гл. 5), 5(гл. 5), 6(гл. 2), 7(гл. 2), 12(гл. 5).

V. Распределительные методы

1. Характеристические признаки распределительных задач, их связь с общей задачей линейного программирования.

2. Различные способы построения исходного опорного плана на примере транспортной задачи.

3. Критерий оптимальности плана транспортной задачи. Алгоритм решения методом потенциалов. Метод дифференциальных рент.

4. Задачи линейного программирования, приводящиеся к транспортным.

Литература: 1(гл. 2), 2 (гл. 4), 4(гл. 10), 5 (гл. 6), 7 (гл. 3), 12(гл. 6).

VІ. Элементы нелинейного программирования

1. Целочисленное программирование. Экономические задачи, приводящиеся к ним. Понятие о методах решения, геометрическая интерпретация целочисленных задач.

2. Параметрическое программирование. Экономические задачи, приводящиеся к ним. Алгоритм решения параметрической задачи, содержащей параметр в целевой функции или в правой части. Геометрический смысл решения параметрической задачи.

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

Литература: 1, 9, 10, 12