Метод сжатия текстовой информации

 

СОДЕРЖАНИЕ 
 
 

    ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    5

1. КРАТКИЙ  ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ 

     ДАННОГО ТИПА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      6

       1.1 Математическое программирование . . . . . . . . . . . . . . . . . . .      6

       1.2 Табличный симплекс - метод . . . . . . . . . . . . . . . . . . . . . . . . . .     7

       1.3 Метод искусственного базиса . . . . . . . . . . . . . . . . . . . . . . . . .      8

       1.4 Модифицированный симплекс - метод  . . . . . . . . . . . . . . . . .       8

2. СОДЕРЖАТЕЛЬНАЯ  ПОСТАНОВКА ЗАДАЧИ . . . . . . . . . . . .    10

3. РАЗРАБОТКА  И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ

    ЗАДАЧИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   11

       3.1 Построение математической модели  задачи . . . . . . . . . . . . . .   11

       3.2 Решение задачи вручную . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   12

4. АНАЛИЗ  МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ . . . . . . . . . . . .    16

       4.1 Построение двойственной задачи  и её численное 

             решение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     16

       4.2 Определение статуса ресурсов . . . . . . . . . . . . . . . . . . . . . . . . .     16

       4.3 Определение значимости ресурсов . . . . . . . . . . . . . . . . . . . . . .    17

       4.4 Определение допустимого интервала  изменения запаса 

            ресурсов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      17

      4.5 Исследование зависимости оптимального  решения от 

            изменений запасов ресурсов . . . . . . . . . . . . . . . . . . . . . . . . . . .      19 
 
 
 
 
 
 

- 4 - 

5. ГРАФИЧЕСКОЕ  ПРЕДСТАВЛЕНИЕ ПОЛУЧЕННЫХ 

    РЕЗУЛЬТАТОВ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     20   

6. ВЫВОДЫ  И РЕКОМЕНДАЦИИ ПО ПРАКТИЧЕСКОМУ 

    ИСПОЛЬЗОВАНИЮ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     22

    ПРИЛОЖЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    23

    ЛИТЕРАТУРА  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      11

 

- 5 - 
 

ВВЕДЕНИЕ 
 

       Цель данного курсового проекта  - составить план производства  требуемых изделий, обеспечивающий максимальную прибыль от их реализации, свести данную задачу к задаче линейного программирования, решить её              симплекс  -  методом  и  составить программу для решения задачи этим методом  на ЭВМ.

 

 - 6 - 

1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ

     ДАННОГО ТИПА  

    1.1 Математическое программирование  

    Математическое  программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом :  найти экстремум некоторой функции многих переменных f ( x₁, x₂, ... , x_n ) при ограничениях                g_i ( x₁, x₂, ... , x_n ) * b_i ,  где g_i - функция, описывающая ограничения,  *  -  один из следующих знаков £ ,  = ,  ³ ,  а b_i - действительное число, i = 1, ... , m.                      f  называется  функцией цели ( целевая функция ).

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

    Задачу  линейного программирования можно  сформулировать так . Найти max

    при условии :          a₁₁ x₁ + a₁₂ x₂ + . . . + a_1n x_n £ b₁ ;

                                                       a₂₁ x₁ + a₂₂ x₂ + . . . + a_2n x_n £ b₂ ;

                                                        _{.  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .}

                                      a_m1 x₁ + a_m2 x₂ + . . . + a_mn x_n £ b_m ;

                                    x₁ ³ 0,  x₂ ³ 0,  _{. . .} ,  x_n ³ 0 _.

    Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической.  

    - 7 - 

    В матричной форме  задачу линейного  программирования записывают следующим образом. Найти   

    max c^T x

    при условии

    A x  £  b ;

    x  ³  0 ,

    где А - матрица ограничений размером ( m´n), b^(m´1) - вектор-столбец свободных членов, x^{(n ´ 1)} - вектор переменных,  с^Т = [c₁, c₂, ... , c_n ] - вектор-строка коэффициентов целевой функции.

    Решение х₀ называется оптимальным, если для него выполняется условие        с^Т х₀  ³ с^Т х ,  для всех х Î R(x).

    Поскольку  min f(x)  эквивалентен  max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации. 

    Для решения задач данного типа применяются  методы:

    1) графический;

    2) табличный ( прямой, простой ) симплекс - метод;

    3) метод искусственного базиса;

    4) модифицированный симплекс - метод;

    5) двойственный симплекс - метод. 

 

       1.2 Табличный симплекс - метод 

    Для его применения необходимо, чтобы  знаки в ограничениях были вида       “ меньше либо равно ”, а компоненты вектора b - положительны.

    Алгоритм  решения сводится к следующему :

 Приведение  системы ограничений к каноническому  виду путём введения   дополнительных переменных для приведения неравенств к равенствам.

 Если  в исходной системе ограничений  присутствовали знаки “ равно  ”  

- 8 - 

или    “ больше либо равно ”, то в указанные  ограничения добавляются 

искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.

 Формируется  симплекс-таблица.

 Рассчитываются  симплекс-разности.

 Принемается  решение об окончании либо  продолжении счёта.

 При  необходимости выполняются итерации.

 На  каждой итерации определяется  вектор, вводимый в базис, и  вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом. 

1.3 Метод  искусственного базиса 

    Данный  метод решения применяется при  наличии в ограничении знаков        “ равно ”, “ больше либо равно  ”, “ меньше либо равно ” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m ,  а в задачи минимизации - с положительными m . Таким образом из исходной получается новая m - задача.

    Если  в оптимальном решении m - задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении m - задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима. 

       1.4 Модифицированный симплекс - метод

    В основу данной разновидности симплекс-метода положены такие особен - 

    - 9 - 

    ности линейной алгебры , которые позволяют  в ходе решения задачи работать с  частью матрицы ограничений. Иногда метод называют методом обратной матрицы.

    В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Хорош для ситуаций, когда число переменных n значительно превышает число ограничений m.

    В целом, метод отражает традиционные черты общего подхода к решению  задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс-разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана-Гаусса.

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

 

     - 10 - 

2. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 

      Для производства двух видов  изделий А и В используется  три типа технологического оборудования. На производство единицы изделия А идёт времени, часов :  оборудованием 1-го типа - а₁ ,   оборудованием 2-го типа - а₂ ,  оборудованием 3-го типа - а₃ . На производство единицы изделия В идёт времени, часов :  оборудованием 1-го типа - b₁ , оборудованием 2-го типа - b₂ ,_, оборудованием 3-го типа - b₃ .

    На  изготовление всех изделий администрация предприятия может предоставить оборудование 1-го типа не более, чем на  t₁ ,  оборудование 2-го типа не более, чем на  t₂ ,  оборудование 3-го типа не более, чем на  t₃  часов.

    Прибыль от реализации единицы готового изделия  А составляет a рублей, а изделия В -  b рублей.

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