Белорусский государственный университет

информатики и радиоэлектроники

Факультет информационных технологий и управления

Кафедра информационных технологий автоматизированных систем

«К защите допускаю»

______________Н.В. Батин

“___”______________2001г.

КУРСОВАЯ РАБОТА по дисциплине «Системный анализ и исследование операций» на тему: «Решение оптимизационной задачи линейного программирования»

Выполнил студент гр. 920603 Журавкин
А.В.

Руководитель работы Батин
Н.В.

Минск, 2001

СОДЕРЖАНИЕ:
ВВЕДЕНИЕ…….………………………………………………………………...3
1. Постановка задачи оптимизации……………………………………….…8
2. Построение аналитической модели…………………………………….…9
3. Обоснование и описание вычислительной процедуры………………..11

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

2. Основная идея симлекс-метода……………………………………..12

3. Двухэтапный симплекс-метод………………………………………12
4. Решение задачи оптимизации на основе симплекс-таблиц……………14

1. Приведение задачи к стандартной форме………..………………..14

2. Определение начального допустимого решения…………………14

3. Построение искусственного базиса………...………………………15

4. Первый этап двухэтапного симплекс-метода…………………….16

5. Второй этап двухэтапного метода………………………………….19
5. Анализ модели на чувствительность……………………………………..22

1. Статус ресурсов……….………………………………………………22

2. Ценность ресурсов……………………………………………………22

3. Анализ на чувствительность к изменениям правых частей ограничений……………………………………………………….…..23

4. Анализ на чувствительность к изменениям коэффициентов целевой функции……………………………………………...………25
6. Определение оптимального целочисленного решения…………………26

6.1. Метод Гомори для частично целочисленных задач……..……….26
ЗАКЛЮЧЕНИЕ…………………………………………………………...……33
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ………………….……..34
УСЛОВНЫЕ СОКРАЩЕНИЯ………………………….……………………35
ПРИЛОЖЕНИЕ…………………………………………………………….…..36