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

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

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

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

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

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

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

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

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

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

(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.