«Вопросы ГАК»

На практике, однако, или принципиально невозможно выразить из уравнений gi(X) = 0 группу переменных, или это может оказаться слишком громоздкой операцией. В этом случае можно эффективно использовать метод множителей Лагранжа.

Определение 4. Функция , где - постоянные множители, называется функцией Лагранжа.

Теорема 6. Если в точке Х0 выполняются условия: , точка Х0 является стационарной точкой для функции Лагранжа, и если второй дифференциал функции Лагранжа в этой точке является положительно (отрицательно) определенной квадратичной формой переменных dx1, dx2,., dxn при условии, что они удовлетворяют соотношениям

то точка Х0 является точкой условного строгого минимума (максимума) для функции у = f(X) относительно условий gi(X) = 0.

3. Симплекс-метод. Преобразование симплекс  таблиц на языке Pascal.

Симплекс (от лат. semplex – простой) – это простейший выпуклый многогранник данного числа измерений n. Количество точек вершин, определяющих симплекс, равно (n+1).[22] Симплекс-метод, таким образом, является алгебраической формой решения задачи ЛП, непосредственно вытекающей из приведенного выше геометрического представления.

В его непосредственной форме симплекс-метод предназначен для решения канонической задачи ЛП ((4.5) – (4.6)). [23]

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

Первый шаг.

Нахождение допустимого плана, соответствующего одной из вершин области допустимых планов.

Второй шаг.

Проверка найденного плана на оптимальность. Если ответ положителен (да, план оптимален), вычисления окончены. Если нет – осуществляется переход к следующему плану.

Третий шаг.

Переход к другой вершине симплекса (к другому плану), в котором значение целевой функции \"лучше\", проверка его на оптимальность и т. д.

Отсюда видно, что первым шагом должно быть получение координат одной из вершин многогранника допустимых планов. Для этого необходимо преобразовать систему уравнений вида (4.6) так, чтобы с ее помощью получить координаты вершины симплекса допустимых решений.

Для этого нужно выразить одни переменные в системе ограничений (4.6) через другие. Система в этом случае примет вид:

х1 = ?4х4 + ?5х5 + ?

х2 = b4х4 + b5х5 + b (4.9)

х3 = g4х4 + g5х5 + g

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

Можно заметить, что в каждой из вершин симплекса (n – m) переменных равны нулю. Поэтому нужно принять равными нулю переменные, число которых составляет (n – m), а затем найти значения m переменных из системы уравнений. В совокупности последние дадут один из допустимых планов, соответствующих некоторой вершине.

Симплекс-метод основан на следующих свойствах задачи ЛП:

1) Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный;

2) Множество всех допустимых планов задачи ЛП выпукло;

3) Целевая функция задачи ЛП достигает своего экстремального значения в угловой точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек;

4) Допустимые базисные (опорные) планы совпадают с угловыми точками многогранника решений;

5) Число положительных элементов допустимого базисного решения меньше или равно числу ограничений m;

6) Число угловых точек и число допустимых базисных решений конечно;

7) Число положительных элементов невырожденного (т. е. такого, где число нулевых значений соответствует n – m, а ненулевых значений – m) [24] допустимого базисного решения равно числу ограничений m.

4. Двойственные задачи: симметричные и несимметричные. Двойственность в линейном программировании.

Любая задача ЛП имеет двойственную к ней

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

Различают

-симметричные двойственные задачи

-не симметричные двойственные задачи

-смешанные

Симметричная двойственная задача

L(x) = C1x1 + C2x2 +…+ Cnxn → max

Алгоритм построения симметричной двойственной задачи

L(x) = b1y1 + b2y2 +…+bmym → min

-Каждому неравенству системы ограничений исходной задачи поставим в соответствие переменную yi

-Построим целевую функцию, слагаемыми которых являются произведения свободных коэффициентов исходной системы на соответствующие новые

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

-Свободными членами в системе ограничений являются коэффициенты целевой функции исходной задачи. Знаки неравенства меняются на противоположные, целевая функция стремиться к минимуму, все yi ≥0

Не симметричные двойственные задачи - это задачи, в которых исходная система ограничений является равенством (задача в каноническом виде)

смешанные двойственные задачи строятся по алгоритму предыдущих двух.

4) Размещение из n по k — это упорядоченный набор из k различных элементов некоторого n-элементного множества.

5) Разбиение числа на слагаемые.

6) Все возможные подмножества заданного множества.

7) Разбиение множества на подмножества такие, что в объединении они дают исходное множество, но при этом ни одно из них не пересекается с любым другим.

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

Количество размещений с повторениями обозначается и равно nk.

Размещениями без повторений из n элементов по k называются всевозможные комбинации по k элементов, составленные из элементов данных n видов. При этом две комбинации считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

Количество размещений без повторений обозначают . Общее правило вычисления количества размещений:

=n(n – 1)…(n – k+1)=.

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

Число n-перестановок обозначают через Рn. Общее правило вычисления количества перестановок:

Рn=Аnn=n (n-1)  (n-2) .21=n!

Перестановками с повторениями из n1 элементов первого типа, n2 элементов второго типа, . , nk элементов k-го типа называются всевозможные комбинации из этих элементов, каждая из которых содержит ni элементов i-го вида. Комбинации отличаются друг от друга лишь порядком элементов.

Число перестановок с повторениями обозначают через Р(n1, n2, ., nk). Общее правило вычисления количества перестановок с повторениями:

Р(n1, n2, ., nk)=. .

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

Количество сочетаний из n элементов по k обозначают .

Формула для вычисления числа сочетаний получается из формулы для вычисления количества размещений. Составим сначала все k-сочетания из n элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получатся все k-размещения из n элементов, причем каждое только по одному разу. Элементы каждого k-сочетания можно переставить k! способами, а число этих сочетаний равно . Значит, справедлива формула . Получаем

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

Количество сочетаний с повторениямиизn элементов по k обозначают . Общее правило вычисления количества сочетаний с повторениями:

6. 6.Метод производящих функций. Бином Ньютона. Основные тождества с биномиальными коэффициентами.

Производящие функции.

Пусть есть последовательность комбинаторных чисел и последовательность функций . Рассмотрим формальный ряд:

называется производящей функцией (для заданной последовательности комбинаторных чисел , относительно заданной последовательности функций )

Обычно используют или

Пример

Из формулы бинома Ньютона при у:=1 имеем:

Таким образом, является производящей функцией для биномиальных коэффициентов.

Свойства производящих функций.

1)(Экспоненциальная) производящая функция суммы (или разности) двух последовательностей равна сумме (или разности) соответствующих (экспоненциальных) производящих функций.

2) Если и – производящие функции последовательностей и , то , где

3) Если и – экспотенциальные производящие функции последовательностей и , то , где

Правила и формулы комбинаторики часто используют при решении различных задач математики. Комбинаторные доказательства отличаются простотой и особой изысканностью. Рассмотрим применение комбинаторики к доказательству формулы бинома Ньютона.

Биномом Ньютона называют формулу для вычисления выражения (а+b)n для натуральных n.

Теорема

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

Данную формулу можно доказать методом математической индукции. Ниже представлено комбинаторное доказательство.

Запишем (a+b)n в виде произведения (a+b)n=(a+b)  (a+b)  … (a+b).

Раскроем скобки в правой части этого равенства и запишем все слагаемые в виде произведения n сомножителей а и b в том порядке, в котором они появляются.

Например, (a+b)2 запишется в виде (a+b)2=(a+b)  (a+b)=aa+ab+ba+bb, а (a+b)3– в виде (a+b)3=(a+b)(a+b)(a+b) =aaa+aab+aba+abb+baa+bab+bba+bbb.

Видно, что в обе формулы входят все размещения с повторениями, составленные из букв а и b по две (три) буквы в каждом.

В общем случае – после раскрытия скобок получим всевозможные размещения с повторениями букв а и b, состоящие из n элементов. Используя коммутативность, приведем подобные члены. Подобными будут члены, содержащие одинаковое количество букв а (тогда и букв b в них будет одинаковое количество). Членов, в которые входит k букв a и, следовательно, (n–k) букв b ровно Р(k, n–k)=. Отсюда вытекает, что после приведения подобных членов выражение akbn-k войдет с коэффициентом , поэтому формула примет вид: .

Числа называют биномиальными коэффициентами.

С помощью бинома Ньютона легко доказать свойства биномиальных коэффициентов (чисел ).

Свойства биномиальных коэффициентов.

Симметричность биномиальных коэффициентов =

Это свойство следует из тождества (a+b)n=(b+a)n. Разложим обе части равенства по биному Ньютона и рассмотрим коэффициенты при akbn-k. Справа коэффициент равен, а слева .

Основное свойство биномиальных коэффициентов

Если в формуле бинома Ньютона положить а=1, b=х то получим,

(1+x)n=.

Если положить n равным n-1 то верно равенство

(1+x)n-1=.

Умножим обе части этого равенства на (1+х), получим

(1+x)n=.

Выражение в левой части равенства снова разложим по формуле бинома Ньютона. Рассмотрим коэффициент при хk. Слева он будет равен . В правой части член содержащий хk появится дважды: при умножении на 1 и при умножении на х. Поэтому коэффициент в правой части при хk имеет вид . Слева и справа стоит один и тот же многочлен, поэтому коэффициенты при хk слева и справа должны быть одинаковыми. Поэтому .

Сумма биномиальных коэффициентов

Воспользуемся формулой бинома Ньютона, в которой положим а=1 и b=1. Тогда .

Знакопеременная сумма биномиальных коэффициентов

Воспользуемся формулой бинома Ньютона в которой положим а=1 и b=-1.

Сумма квадратов биномиальных коэффициентов

Как и при доказательстве основного свойства, используем равенство

(1+x)n=.

Умножим обе части этого равенства на (1+х)n:

(1+x)2n=.

Выражение в левой части равенства снова разложим по формуле бинома Ньютона. Рассмотрим коэффициент при хn. Слева он будет равен . В правой части член, содержащий хn, появится n раз: при умножении на , при умножении на , и так далее. Используем свойство симметричности биномиальных коэффициентов, получим коэффициент при хn в правой части равенства:

Так как слева и справа стоит один и тот же многочлен, то коэффициенты при хn слева и справа должны быть одинаковыми. Поэтому .

Биномиальные коэффициенты, упорядоченные специальным образом, образуют треугольник Паскаля.

Строится этот замечательный треугольник очень просто:

По краям треугольника ставятся единицы, а любое число, стоящее не с краю, вычисляется как сумма двух чисел, расположенных сверху слева и сверху справа от него. Например, 10=4+6, или 3=1+2. Итак, речь зашла о треугольнике Паскаля в связи с тем, что он как раз образован биномиальными коэффициентами:

Для наших целей (и для удобства) лучше записывать треугольник, выравнивая его по левому краю:

Нули появляются за счёт нуля в числителе (когда k>n). Заметьте, что в нулевом столбце ставятся единицы, так как

7. Рекуррентные соотношения. Способы решения рекуррентных соотношений. Числа Фибоначчи.

Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится.

Количество разбиений числа на слагаемые

Количество разбиений числа на слагаемые удовлетворяют рекуррентному соотношению:

, где t> 0,

,

, где первый параметр - это число, которое мы разбиваем, а второй - это максимальное слагаемое в разбиении.

Количество неупорядоченных разбиений n-элементного множества на k непустых подмножеств.

Оно выражается числами Стирлинга второго рода, которые удовлетворяют следующему рекуррентному соотношению:

, для n ≥ 0,

, для n> 0,

для 0 Решением рекуррентного соотношения называется любая последовательность, для которой данное соотношение выполнено тождественно.

Пример.

Последовательность 2, 4, 8, …, 2n является решением для соотношения

f(n+2)=3∙f(n+1) – 2∙f(n).

Доказательство:

Общий член последовательности имеет вид f(n)=2n. Значит, f(n+2)= 2n+2, f(n+1)= 2n+1. При любом n имеет место тождество 2n+2=3∙2n+1 – 2∙2n. Следовательно, при подстановке последовательности 2n в формулу f(n+2)=3f(n+1) – 2f(n) соотношение выполняется тождественно. Значит, 2n является решением указанного соотношения.

Решение рекуррентного соотношения k-го порядка называется общим, если оно зависит от k произвольных постоянных α1, α 2, … α k и путем подбора этих постоянных можно получить любое решение данного соотношения.

Линейные рекуррентные соотношения с постоянными коэффициентами

Для решения рекуррентных соотношений общих правил нет, но существует часто встречающийся класс рекуррентных соотношений, для которых известен алгоритм их решения. Это – линейные рекуррентные соотношения с постоянными коэффициентами, т.е. соотношения вида:

f(n+k)=c1f(n+k-1)+c2f(n+k-2)+…+ckf(n).

Найдем решение общего линейного рекуррентного соотношения с постоянными коэффициентами первого порядка.

Линейное рекуррентное соотношение с постоянными коэффициентами первого порядка имеет вид: f(n+1)=cf(n).

Пусть f(1)=а, тогда f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c2∙a, аналогично f(4)=c3∙a и так далее, заметим, что f(n)=cn-1∙f(1).

Докажем, что последовательность cn-1∙f(1) является решением рекуррентного соотношения первого порядка. f(n)=cn-1∙f(1), значит, f(n+1)=cnf(1). Подставляя это выражение в соотношение, получим тождество cnf(1)=с∙ cn-1∙f(1).

Рассмотрим теперь подробнее линейные рекуррентные соотношения с постоянными коэффициентами второго порядка, то есть соотношения вида

f(n+2)=C1∙f(n+1)+C2∙f(n). (*).

Заметим, что все рассуждения сохраняются и для соотношений более высокого порядка.

Свойства решений:

1. Если последовательность xn является решением (*), то и последовательность ∙xn тоже является решением.

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

xn является решением (*), следовательно, выполняется тождество xn+2=C1xn+1+C2xn. Домножим обе части равенства на . Получим ∙xn+2 =∙(С1∙xn+1+С2∙xn )= С1∙∙xn+1+С2∙∙xn . Это означает, что xn является решением (*).

2. Если последовательности xn и yn являются решениями (*), то и последовательность xn+yn тоже является решением.

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

xn и yn являются решениями, следовательно, выполняются следующие тождества:

xn+2=C1xn+1+C2xn.

yn+2=C1yn+1+C2yn.

Выполним почленное сложение двух равенств:

xn+2+yn+2=С1∙xn+1+С2∙xn + С1∙yn+1+С2∙yn= С1∙(xn+1+ yn+1)+С2∙(xn +yn). Это означает, что xn+yn является решением (*).

3. Если r1 является решением квадратного уравнения r2=С1r+С2, то последовательность (r1)n является решением для соотношения (*).

r1 является решением квадратного уравнения r2=С1r+С2, значит, (r1)2=C1r1+C2. Помножим обе части равенства на (r1) n. Получим

r12r1n=(С1r1+С2) rn.

r1n+2 =С1r1n+1+С2r1n.

Это означает, что последовательность (r1)n является решением (*).

Из этих свойств вытекает способ решения линейных рекуррентных соотношений с постоянными коэффициентами второго порядка:

1. Составим характеристическое (квадратное) уравнение r2=С1 r+С2. Найдём его корни r1, r2. Если корни различны, то общее решение имеет вид f(n)= r1n+βr2n.

2. Найдём коэффициенты  и β. Пусть f(0)=a, f(1)=b. Система уравнений

 + β =а

∙r1 + β∙r2=b

имеет решение при любых а и b. Этими решениями являются

=(b-a∙r2)/(r1-r2).

β =(a∙r1-b)/(r1-r2).

Числа Фибоначчи

Это классический пример, который приводят почти везде, где речь идет о решении рекуррентных соотношений. Рассмотрим рекуррентное соотношение для чисел Фибоначчи:

Это хорошо известная последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

Эти числа очень быстро растут, например, f10=55, f20=6765, f30=832040, f100=354224848179261915075.