Белорусский государственный университет информатики и радиоэлектроники Факультет информационных технологий и управления Кафедра информационных технологий автоматизированных систем
    
    
    "К защите допускаю"
    ______________Н.В. Батин
    "___"______________2001г.
    
    
    
    КУРСОВАЯ РАБОТА
    по дисциплине "Системный анализ и исследование операций"
    на тему: "Решение оптимизационной задачи
    линейного программирования"
    
    
    
    
    Выполнил студент гр. 920603 Журавкин А.В.
    Руководитель работы Батин Н.В.
    
    
    
    
    
    Минск, 2001
    СОДЕРЖАНИЕ: ВВЕДЕНИЕ..................................................................................3 1. Постановка задачи оптимизации.................................................8 2. Построение аналитической модели..............................................9 3. Обоснование и описание вычислительной процедуры....................11 3.1. Приведение задачи линейного программирования к стандартной форме..............................................................................11 3.2. Основная идея симлекс-метода............................................12 3.3. Двухэтапный симплекс-метод.............................................12 4. Решение задачи оптимизации на основе симплекс-таблиц...............14 4.1. Приведение задачи к стандартной форме...............................14 4.2. Определение начального допустимого решения.....................14 4.3. Построение искусственного базиса.......................................15 4.4. Первый этап двухэтапного симплекс-метода.........................16 4.5. Второй этап двухэтапного метода........................................19 5. Анализ модели на чувствительность............................................22 5.1. Статус ресурсов................................................................22 5.2. Ценность ресурсов............................................................22 5.3. Анализ на чувствительность к изменениям правых частей ограничений.....................................................................23 5.4. Анализ на чувствительность к изменениям коэффициентов целевой функции...............................................................25 6. Определение оптимального целочисленного решения.....................26
    6.1. Метод Гомори для частично целочисленных задач..................26 ЗАКЛЮЧЕНИЕ...........................................................................33 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ..............................34 УСЛОВНЫЕ СОКРАЩЕНИЯ.......................................................35 ПРИЛОЖЕНИЕ...........................................................................36
    ВВЕДЕНИЕ
    
    В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности.
    Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
    Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно. ............