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

СОДЕРЖАНИЕ 
 
 

    ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    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 рублей.

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

    а₁ = 1          b₁ = 5          t₁ = 10          a  = 2

    а₂ = 3          b₂ = 2          t₂ = 12          b = 3

    а₃ = 2          b₃ = 4          t₃ = 10              
 
 
 
 
 
 
 
 

- 11 - 

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

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

    Построение  математической модели осуществляется в три этапа :

1. Определение  переменных, для которых будет  составляться математическая модель.

   Так как требуется определить  план производства изделий А  и В, то переменными модели будут:

    x₁ - объём производства изделия А, в единицах;

      x₂ - объём производства изделия В, в единицах.

2. Формирование  целевой функции.

    Так как прибыль от реализации  единицы готовых изделий А  и В известна, то общий доход  от их реализации составляет  2x₁  + 3x₂  ( рублей ). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции : определить допустимые значения переменных  x₁  и x₂ , максимизирующих целевую функцию F =    2x₁  + 3x₂ .

3. Формирование  системы ограничений.

  При определении плана производства  продукции должны быть учтены  ограничения на время, которое администрация предприятия сможет пре - 

- 12 - 

   доставить на изготовления всех  изделий. Это приводит к следующим  трём ограничениям :

   x₁  + 5x₂    £    10 ;       3x₁  + 2x₂   £  12 ;      2x₁  + 4x₂  £  10 .

   Так как объёмы производства  продукции не могут принимать  отрицательные значения, то появляются  ограничения неотрицательности  :

x₁  ³ 0 ;                x₂ ³ 0 .

   Таким образом, математическая  модель задачи представлена в  виде : определить план  x₁ , x₂ , обеспечивающий максимальное значение функции :

max F = max ( 2x₁  + 3x₂ )

   при наличии ограничений :

x₁  + 5x₂    £    10 ;

3x₁  + 2x₂   £  12 ;     

2x₁  + 4x₂  £  10 .

x₁  ³ 0 ;  x₂ ³ 0 . 

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

    Табличный метод ещё называется метод последовательного улучшения оценки. Решение задачи осуществляется поэтапно.

    1. Приведение задачи к форме  :

x₁  + 5x₂    £    10 ;

3x₁  + 2x₂   £  12 ;     

2x₁  + 4x₂  £  10 .

x₁  ³ 0 ;  x₂ ³ 0 .

2. Канонизируем  систему ограничений : 
 
 
 

- 13 - 

  x₁  + 5x₂   + x₃                        =  10 ;

3x₁  + 2x₂          + x₄         = 12 ;     

2x₁  + 4x₂                  + x₅ = 10 .

x₁  ³ 0 ;  x₂ ³ 0 .

A₁         A₂     A₃    A₄    A₅    A₀

3. Заполняется  исходная симплекс-таблица и рассчитываются симплекс-разности по формулам :

d₀ =   - текущее значение целевой функции

d_i =    - расчёт симплекс-разностей, где j = 1..6  .

    Так как при решении задачи на max не все симплекс-разности положительные, то оптимальное  решение можно  улучшить.

    4. Определяем направляющий столбец  j^*. Для задачи на max он определяется минимальной отрицательной симплекс-разностью. В данном случае это вектор А₂

    5. Вектор i^*, который нужно вывести из базиса, определяется по отношению :

    min 

    - 14 - 

    В данном случае сначала это А₃ .

    5. Заполняется новая симплекс-таблица  по исключеню Жордана - Гаусса :

       а). направляющую строку  i^*  делим на направляющий элемент :   

    a _{i j} = a _{i j} / a _{i j}    , где j = 1..6

       б). преобразование всей оставшейся части матрицы :

    a _ij = a_ij - a _{i j} × a_ij    , где i ¹ i^*  ,  j ¹ j^*

    В результате преобразований получаем новую симплекс-таблицу : 

    Повторяя  пункты 3 - 5, получим следующие таблицы :