Главная страница
Навигация по странице:

  • Теорема двойственности (без доказательства).

  • Понятие о симплекс-методе.

  • Делимость целых чисел.

  • Частное и остаток.

  • Количество и сумма натуральных делителей числа. Теорема о делении с остатком и ее приложения.

  • Утверждение

  • Теорема

  • 1. Каноническое разложение натурального числа. 3


    Скачать 0.66 Mb.
    Название1. Каноническое разложение натурального числа. 3
    Дата15.04.2022
    Размер0.66 Mb.
    Формат файлаdocx
    Имя файлаAlgebra_i_teoria_chisel.docx
    ТипДокументы
    #476997
    страница4 из 9
    1   2   3   4   5   6   7   8   9

    Стандартные и канонические задачи линейного программирования. Допустимые и оптимальные векторы.





    1. Теорема двойственности (без доказательства).


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

    Если одна из пары двойственных задач не имеет решения вследствие неограниченности целевой функции, то двойственная задача не имеет решения вследствие несовместимости системы ограничений.
    1. Понятие о симплекс-методе.


    Симплексный метод – это итеративная процедура, позволяющая улучшать решение на каждом этапе. Эта процедура завершается, когда невозможно улучшить решение.

    Начиная со случайного значения вершины целевой функции, метод Simplex пытается многократно найти другое значение вершины, которое улучшает предыдущее. Поиск осуществляется через сторону многоугольника (или по краям многогранника, если число переменных выше). Поскольку число вершин (и ребер) конечно, он всегда сможет найти результат. (См. графический метод)

    Симплексный метод основан на следующем свойстве: если целевая функция F не принимает максимальное значение в вершине A, то есть ребро, начинающееся с A, вдоль которого растет значение функции.

    Вы должны позаботиться о том, чтобы метод Simplex работал только с неравенством типа «≤» и независимыми коэффициентами выше или равными нулю, и вам придется стандартизировать ограничения для алгоритма. В случае, если после этой процедуры "≥" o "=" ограничения типа появляются (или не изменяются), вы должны попробовать другие способы, так как двухфазный симплексный метод является лучшим выбором
    1. Делимость целых чисел.


    Если с≠0с≠0 и aa являются целыми числами, мы говорим, что nn делит aa (и напишите с| aн| a), если существует mm такой, что a=nma=nm. Когда с| aн| a мы также говорим: nn является делителем aa и aa кратно nn.

    Предостережение: Символ с| aн| a — это не дробь, а формула. Это означает, что между двумя числами существует связь, которая либо истинна, либо ложна (2 и 6 имеют это отношение, 2 и 7 нет). Пока мы изучаем теорию чисел, у нас не будет повода упоминать рациональные числа — мы, по сути, будем избегать их. Причин тому несколько. Один из них практичен: данная дробь имеет более одного представления (например, 4/12=5/154/12=5/15). Также возможно, что число, которое не выглядит как целое число, на самом деле является целым числом (например, 45/15 )
    1. Частное и остаток.


    частное — это результат процесса деления. Делением называется такая операция, которая обратна умножению, то есть показывает, сколько одинаковых чисел способно содержаться в другом.

    это сумма, "оставшаяся" после выполнения некоторых вычислений. В арифметикеостаток-это целое число, "оставшееся" после деления одного целого числа на другое, чтобы получить целое частное (целочисленное деление). В алгебре многочленов остаток-это многочлен, "оставшийся" после деления одного многочлена на другой.
    1. Количество и сумма натуральных делителей числа. Теорема о делении с остатком и ее приложения.


    Теорема 1 дает возможность определить, делится число m на n, если эти числа разложены на простые множители.

    Если m делится на n, то n является кратным m:

    m=nq.

     

    Тогда любое простое число, входящее в n, должно входить и в m, поэтому в n не могут входить другие простые множители, которые не входят в m и притом эти простые множители в n входят не более число раз, чем в m.

    Справедливо и обратное. Если каждый простой множитель числа n входит по крайней мере столько же раз в число m, то m делится на n.

    Утверждение 3. Пусть a1,a2,a3,... различные простые числа входящие в m так, что



     

    Тогда все делители n числа m можно представить формулой



    (6)

    где i=0,1,...αj=0,1,...,β, k=0,1,...,γ. Заметим, что αi принимает α+1 значений, βj принимает β+1 значений, γk принимает γ+1 значений, ... .

    Каждая из чисел n вычисленная формулой (6) является делителем числа m.

    Очевидно, при разных значениях i, j, k имеем разные делители числа m. Тогда число всех делителей m равно:



     

    Мы доказали следующую теорему:

    Теорема 4. Пусть



     

    каноническое разложение числа m. Тогда число делителей числа m равно:



     

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



     

    Тогда для произведения вида   берем по одному множителю из каждого горизонтального ряда. Используя правила умножения многочленов, получим:



     

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

    Следовательно сумма всех делителей числа m равна



    (7)

    Мы доказали следующую теорему:

    Теорема 5. Пусть



     

    каноническое разложение числа m. Тогда сумма всех делителей числа m равна выражению (7).

    Пример . Возьмем число 280=23·5·7 .

    Множество делителей этого числа такова

    1 2 4 5 7 8 10 14 20 28 35 40 56 70 140 280

     

    Число делителей числа 280 равно:

    (3+1)(1+1)(1+1)=16.

     

    Сумма делителей числа 280 равна:

    .

    Теорема о делении с остатком и ее приложения.

    Определение.

    Пусть а - целое неотрицательное число , а b - число натуральное. Разделить а на b с остатком - это значит найти такие целые неотри­цательные числа q и r, что а= bq + r, причем r больше или равно нулю, но меньше b.

    Теорема.

    Для любого целого неотрицательного числа а и натурального числа b существуют целые неотрицательные числа q и r, такие что а= bq + r, причем r больше или равно нулю, но меньше b. И эта пара q и r единственная для заданных а и b.

    Доказательство существования.

    Обозначим через Ь множество целых неотрицательных чисел, крат­ных b и не превосходящих а :

    М = {x|x=by, x меньше или равен a}.

    Так как для всех чисел из этого множества выплняется неравенство х<а+1, то в множестве М есть наибольше число, которое обозначим через х0. Это число имеет вид х0=bq, причем число b(q+1) уже не принадлежит множеству М и поэтому b(q+1) >a. Итак, найдено число q , такое что a больше или равно bq, но меньше bq+b. Из этих неравенств следует, что a-bq больше или равно 0, но меньше b. Если обозначить a-bq через r , то имеем a-bq =r, т.е. r +bq =a и r больше или равно нулю .Это означает, что q- неполное частное, а r - остаток при делении.

    Доказательство единственности.

    Предположим, что а= bq + r, где r больше или равно нулю, но мень­ше b и а= bq1 + r1, r1 больше или равно нулю, но меньше b, причем, например, r> r1 . Тогда имеем bq + r=bq1 + r1, r-r1= bq1 -bq=b(q1 -q). Поскольку 0 меньше или равен r1


    1. 1   2   3   4   5   6   7   8   9


    написать администратору сайта