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

Автор работы: Лена Шугалеева, 25 Сентября 2010 в 19:08, курсовая работа

Краткое описание

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x1, x2, ... , xn ) при ограничениях gi ( x1, x2, ... , xn )  bi , где gi - функция, описывающая ограничения,  - один из следующих знаков  ,  ,  , а bi - действительное число, i = 1, ... , m. f называется функцией цели ( целевая функция ).
Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные.
Задачу линейного программирования можно сформулировать так . Найти max
при условии : a11 x1 + a12 x2 + . . . + a1n xn  b1 ;
a21 x1 + a22 x2 + . . . + a2n xn  b2 ;
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
am1 x1 + am2 x2 + . . . + amn xn  bm ;
x1  0, x2  0, . . . , xn  0 .
Эти ограничения называются условиями неотрицательности. Если все ограни-чения заданы в виде строгих равенств, то данная форма называется канонической.
- 7 -
В матричной форме задачу линейного программирования записывают следующим образом. Найти
max cT x
при условии
A x  b ;
x  0 ,
где А - матрица ограничений размером ( mn), b(m1) - вектор-столбец свобод-ных членов, x(n  1) - вектор переменных, сТ = [c1, c2, ... , cn ] - вектор-строка коэффициентов целевой функции.
Решение х0 называется оптимальным, если для него выполняется условие сТ х0  сТ х , для всех х  R(x).
Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.
Для решения задач данного типа применяются методы:
1) графический;
2) табличный ( прямой, простой ) симплекс - метод;
3) метод искусственного базиса;
4) модифицированный симплекс - метод;
5) двойственный симплекс - метод.

1.2 Табличный симплекс - метод
Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны.
Алгоритм решения сводится к следующему :
Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.
Если в исходной системе ограничений присутствовали знаки “ равно ”

- 8 -

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

Скачать целиком (36.74 Кб) Сколько стоит заказать работу?
Содержимое работы - 1 файл

МЕТОД СЖАТИЯ ТЕКСТОВОЙ ИНФОРМАЦИИ.DOC

— 177.00 Кб (Скачать файл)

    а1 = 1          b1 = 5          t1 = 10          a  = 2

    а2 = 3          b2 = 2          t2 = 12          b = 3

    а3 = 2          b3 = 4          t3 = 10              
 
 
 
 
 
 
 
 

- 11 - 

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

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

  На произв-во изделия А, часов На произв-во изделия B, часов Предпр-е предоставит, часов
Оборуд-е 1го типа 1 5 10
Оборуд-е 2го типа 3 2 12
Оборуд-е 3го типа 2 4 10
Прибыль от реализации, за ед. изд-я 2 3  
 

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

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

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

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

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

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

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

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

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

    - 12 - 

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

       x1  + 5x2    £    10 ;       3x1  + 2x2   £  12 ;      2x1  + 4x2  £  10 .

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

    x1  ³ 0 ;                x2 ³ 0 .

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

    max F = max ( 2x1  + 3x2 )

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

    x1  + 5x2    £    10 ;

    3x1  + 2x2   £  12 ;     

    2x1  + 4x2  £  10 .

    x1  ³ 0 ;  x2 ³ 0 . 

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

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

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

    x1  + 5x2    £    10 ;

    3x1  + 2x2   £  12 ;     

    2x1  + 4x2  £  10 .

    x1  ³ 0 ;  x2 ³ 0 .

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

    - 13 - 

      x1  + 5x2   + x3                        =  10 ;

    3x1  + 2x2          + x4         = 12 ;     

    2x1  + 4x2                  + x5 = 10 .

    x1  ³ 0 ;  x2 ³ 0 .

    A1         A2     A3    A4    A5    A0

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

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

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

    C 2 3 0 0 0
Б Cб A0 A1 A2 A3 A4 A5
A3 0 10 1 5 1 0 0
A4 0 12 3 2 0 1 0
A5 0 10 2 4 0 0 1
  d 0 -2 -3 0 0 0
 

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

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

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

    min 

  при аi j > 0 
 

    - 14 - 

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

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

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

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

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

    a ij = aij - a i j × aij    , где i ¹ i*  ,  j ¹ j*

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

    C 2 3 0 0 0
Б Cб A0 A1 A2 A3 A4 A5
A2 3 2 1/5 1 1/5 0 0
A4 0 8 13/5 0 -2/5 1 0
A5 0 2 6/5 0 -4/5 0 1
  d 6 -7/5 0 3/5 0 0
 

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

    C 2 3 0 0 0
Б Cб A0 A1 A2 A3 A4 A5
A2 3 5/3 0 1 1/3 0 -1/6
A4 0 11/3 0 0 4/3 1 -13/6
A1 2 5/3 1 0 -2/3 0 5/6
  d 8  1/3 0 0 -1/3 0 7/6
 
    C 2 3 0 0 0
Б Cб A0 A1 A2 A3 A4 A5
A2 3 3/4 0 1 0 -1/4 3/8
A3 0 11/4 0 0 1 3/4 -13/8
A1 2 7/2 1 0 0 1/2 -1/4
  d 9  1/4 0 0 0 1/4 5/8

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