Е. Корныхин - Задачи по курсу Методы оптимизации

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М.В.ЛОМОНОСОВАфакультет Вычислительной Математики и КибернетикиЕ. КорныхинЗадачи по курсу«Методы оптимизации»Москва2005Оглавление1Введение в теорию1.1 задача №1 . . .1.2 задача №2 . .1.3 задача №3 . .1.4 задача №4 . .сложности. . . . . . ..

. . . . . .. . . . . . .. . . . . . .....................2 Основы линейного программирования2.1 задача №5 . . . . . . . . . . . . . .2.2 задача №6 . . . . . . . . . . . . . .2.3 задача №6.1 . . . . . . . . . . . . . .2.4 задача №7 . . . . . . . . . .

. . . .2.5 задача №8 . . . . . . . . . . . . . ...................................................................................................................................22489.....1111121415183 Элементы математического программирования203.1 задача №9 . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . 203.2 задача №10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 Экзаменационные задачи254.1 Построение двойственной задачи линейного программирования 254.2 Применение градиентного метода . . . . . . . . . . . . . . . . 261Глава 1Введение в теорию сложностиОпределение (ЗАДАЧА КОММИВОЯЖЕРА в форме распознавания свойства).

[2,стр.35] Заданы конечное множество C = {c1 , c2 , . . . , cm } "городов"мощности m,"расстояние"d(ci , cj ) ∈ N для каждой пары различных городов ci , cj ∈ C и границаB ∈ N. Существует ли "маршрут", проходящий через все города C, длина которого не превосходит B? Другими словами, существует ли последовательностьcπ(1) , cπ(2) , . .

. , cπ(m) элементов C такая, чтоm−1d(cπ(i) , cπ(i+1) ) + d(cπ(m) , cπ(1) ) B?i=1Определение (ВЫПОЛНИМОСТЬ). По данной булевой формуле, представленной в видеКНФ, выяснить, выполнима ли она, т.е. существует ли набор переменных, откоторых зависит эта КНФ, на которых она обращается в истину [3, c.357].Определение (N-ВЫПОЛНИМОСТЬ). По данной булевой формуле, представленной ввиде КНФ, в которой каждый дизъюнкт имеет длину N , выяснить, выполнимали она, т.е. существует ли набор переменных, от которых зависит эта КНФ, накоторых она обращается в истину [3, c.357].1.1 задача №1Постановка задачи. Предложить неизбыточную кодировку задачи коммивояжера (задачи КМ); оценить длину входа.Решение. Будем использовать десятичное кодирование натуральных чисел,а для их разделения в слове применять специальный символ (♦).

Итак,2Глава 1. Введение в теорию сложности3пусть конечный алфавит для кодировки будет таким:Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ♦}.Все данные в задаче расстояния поместим в матрицу так, чтобы на пересечении i-й строки и j-го столбца стоял d(ci, cj ). Такую матрицу будемпредставлять по строкам: сначала первая строка, затем вторая, третья ит.д., и, наконец, последняя строка. При кодировании этой матрицы для разделения строк будем использовать тот специальный символ-разделитель,который присутствует в алфавите кодирования.Введем следующую кодировку e: сначала идет запись m, затем символразделитель, затем - запись B, символ-разделитель, запись матрицы D =||d(ci , cj )||1i,jm. Т.к.

D - симметричная матрица с нулевой главной диагональю, то для неизбыточности кодировки e будем кодировать только частьматрицы D, располагающаяся выше главной диагонали без самой диагонали так, как описано выше (по строкам), вставляя между элементами частитакой матрицы уже известный нам символ-разделитель. Например,⎞⎛ коди0 1 5ровка следующей индивидуальной задачи: m = 3, B = 11, D = ⎝1 0 3⎠5 3 0будет такой:3♦11♦1♦5♦3Исследуем некоторые свойства такой кодировки:а) эта кодировка однозначна, т.к. по данной строке легко выделить сначалаm, затем B и, наконец, по-элементно матрицу D.б) очевидно, что и кодировка, и её декодировка полиномиально вычислимы(алгоритм кодировки просто состоит из делений по модулям - степенямдесяти).Оценим длину кодировки. Для начала заметим, что для представлениянатурального числа n в нашей записи потребуется log10 n + 1 символовГлава 1. Введение в теорию сложности4алфавита Σ1 (подчеркну, что n - натуральное, т.е.

n 1, а это значит, чтоlog10 n определен и неотрицателен, а значит и длина записи n определенаи натуральна). Тогда длина закодированной индивидуальной задачи КМI может быть вычислена по следующей формуле: |e(I)| = log10 m + 1 +(log10 Dij + 1) + 1 + 1 + (m − 1 + m − 2 + . . . + 1) − 1 log10 B + 1 +1i<jmm2 − m + 2 + log10 m + log10 B +m(m−1)max log10 Dij 21i<jm1.2 задача № 2Постановка задачи. Предложить алгоритм проверки на простоту числа; найти его временную сложность.Определение (линейная двоичная кодировка). Назовем линейной двоичной кодировкой порядка n такое отображение Nn в Σ∗ (где Σ = {0, 1, ♦}- алфавит кодировки), переводящее числа (x1, x2, .

. . , xn) в слово σ =ξ11ξ12 . . . ξ1l1 ♦ξ21 ξ22 . . . ξ2l2 ♦ . . . ♦ξn1 ξn2 . . . ξnln , где ξi1 ξi2 . . . ξili - двоичная запись числа xi.Например, если e - линейная двоичная кодировка порядка 4, то e(3, 5, 1, 6) =1 1 ♦ 1 0 1 ♦ 1 ♦ 1 1 0.Лемма 1 (о сложности нахождения остатка). Существует алгоритм BMod,решающий массовую задачу нахождения остатка от деления одногонатурального числа на другое с линейной двоичной кодировкой порядка2, имеющий временную сложность TBMod (n) = O(n2 ).Доказательство.

Рассмотрим следующий алгоритм нахождения остаткаот деления одного числа на другое:function BMod(x, y: integer): integer;1 таккак при увеличении n в 10 раз число десятичных разрядов в записи n увеличивается на 1Глава 1. Введение в теорию сложности5var k, i: integer;begink := 0;while k + |y| <= |x| dobegini := subint(x, |y|, k);if i >= y thenminus(i, j);k := k + 1;end;return x;end;Поясним используемые в BMod функции.|y| длина слова, отвечающего переменной y на ленте Машины Тьюринга.i := subint(x, |y|, k) после этой функции число i будет идти в слове x,начиная с символа с номером k; при этом i будет иметь длину |y|.minus(i, j) отнять от числа i число j, причем результат записать на местоi.Поясним работу функции BMod на следующем примере: пусть x = 1510 =11112, y = 210 = 102 (индекс указывает основание системы счисления, вкоторой записано значение переменной).k=0ix= 11 11–y= 10k=1ix= 0 11 1–y=10x= 00 11–y=10x= 0111x= 0011x= 0001k=2iГлава 1.

Введение в теорию сложности6В качестве ответа принимаем полученное значение x (т.е. 1, что верно:15 mod 2 = 1).Перейдем к вопросу о сложности данной функции. Для начала заметим,что переменная k играет роль положения головки, поэтому на работе с kможно будет сэкономить по сложности. Проверка в цикле k+|y| <= |x| - этопроверка на невыход k за пределы установленных границ: от 0 до |x| − |y|.Достаточно поставить ограничитель и проверять, чтобы k не перешло этотограничитель. Поэтому на работу с k надо O(|x| − |y|) шагов МашиныТьюринга. На выделение подслова в слове x с присвоением подслову имениi вообще не надо тратить время Машины Тьюринга, потому как выделениеi просто влияет на то, где будет производиться вычитание из слова x словаy.

На проверку i y надо O(|y|) шагов. На вычитание слова y из словаx тоже достаточно O(|y|) шагов Машины Тьюринга. И, наконец, ещё одиншаг на сдвиг головки, отвечающий оператору k := k + 1.В результате получим, что время работы алгоритма BMod будет равно|x|−|y|tBMod (e(x, y)) (2|y| + 1) = (2|y| + 1)(|x| − |y| + 1).k=0Обозначим |x| = α и |y| = β. Тогда TBMod (n) max (2β +1)(α−β +1) =max1αn−1−ββ1(2β + 1)(α − β + 1) α+β+1nα,β1max(2β + 1)(n − β) = max (2β + 1)(n −1αn−1−ββ1β)|β= n−(−1/2) = 2n+1 = (2n+3)(2n−1)8241βn−2β) = (2β + 1)(n −= O(n2 ).В выводе использовано такое свойство квадратного трехчлена: если старщий коэффициент отрицательный и существуют 2 вещественных корня, томаксимум достигается в точке с абсциссой, равной полусумме корней.Решение задачи №2.

Предложим очень простой алгоритм:function is_prime(n: integer): boolean;var m, k:integer;beginm := 2;Глава 1. Введение в теорию сложности7while m < n dobegink := BMod(n, m);if k = 0 thenreturn false;inc(m);end;return true;end;По определению TA (n) =maxσ∈Σ∗ :|σ|ntA (σ). По определению нашего алго-ритма максимум сложности будет достигаться на простом числе, так какдля него нужно наибольшее число итераций для доказательства того, чтооно на самом деле простое. Пусть x - максимальное простое число, длинакодировки которого не больше n. Будем использовать двоичную кодировкуe для натуральных чисел.

Тогда длина записи x равна log2 x + 1. Значит,log2 x + 1 n ⇔ x 2n−1 (это несложно сделать, используя определение·).x−1Итак, TA (n) = tA (e(x(n))) =(ti<x + tk := BMod (x,i) + tk=0 + tinc(m) ) + ti:=2.i=2ti<x = O(n).tk:= BMod (x,i)= O(n2 ) (по лемме о сложности нахождения остатка).tk=0 = O(n).tinc(i) = O(n).ti:=2 = 2 (т.к. число «2» имеет в двоичной кодировке длину 2).Тогда TA (n) =n 2O(2 n ).x−1i=2(n + O(n2 ) + O(n)) + 2 = (x − 2)O(n2) = O(2n )O(n2) =Глава 1. Введение в теорию сложности8Ответ.

TA (n) = O(2nn2 ).1.3 задача №3Постановка задачи. Доказать, что задача «Составные Числа» ∈ NP.Доказательство (конструктивное). Поставим задачу «Составные Числа»(СЧ): задано натуральное число x. Составное ли оно, т.е. имеет ли ононатуральный неединичный и не равный x делитель?Будем использовать линейную двоиную кодировку порядка 1 e для кодирования x.По определению класса NP: СЧ ∈ NP ⇔ ∃A = {As }s - недетерминированная Машина Тьюринга, решающая массовую задачу СЧ c линейной двоичной кодировкой порядка 1: ∃p(n) - полином: T̂A (n) p(n), гдеT̂A (n) = max min {|s| + tAs (σ)} - временная сложность алгоритма работыσ:|σ|n s:σ∈LAsМашины Тьюринга A.Предложим такую недетерминированную Машину Тьюринга: A(σ) ={As|As ≡ (BMod(σ, s) == 0)} s=e(y) .

Из доказательства леммы о сложностиσ=e(x)2yxнахождения остатка2 следует, что tAs (σ) = (m+|s|+1)(|σ|−|s|+1)+|σ| (+|σ|идет на сравнение результата с нулем). Здесь m - число единиц в записичастого e−1 (σ) и e−1(s). В этой формуле точно учтены только происходящиевызовы функции minus.Положим tA (σ) = min {(m + |s| + 1)(|σ| − |s| + 1) + |σ|}. Т.к. m |σ|,s:s=e(y)σ=e(x)2yx−1x mod y=0m=|e([ xy ])|(1)2 доказательствоможно найти в решении домашнего задания №1Глава 1.

Введение в теорию сложностито tA (σ) min9{(|σ|+1)2 −|s|2 +|σ|} = (|σ|+1)2 +|σ|−( max {|s|})2 s:s=e(y)σ=e(x)2yx−1x mod y=0(|σ| + 1)2 + |σ| − 4, т.к. y 2 ⇒ |s| 2 ⇒ max|s| 2.Итак, tA (σ) (|σ| + 1)2 + |σ| − 4 = |σ|2 + 3|σ| − 3.Осталось посчитать T̂A (n) max (|σ|2 + 3|σ| − 3).s:s=e(y)σ=e(x)2yx−1x mod y=0σ:|σ|nТак как квадратичный трехчлен y(x) = x2 + 3x − 3 возрастает на промежутке [1, n] (старший коэффициент положительный и абсцисса вершиныотрицательна), то max (|σ|2 + 3|σ| − 3) = (|σ|2 + 3|σ| − 3)||σ|=n = n2 + 3n − 3.σ:|σ|nТаким образом, мы доказали, что T̂A (n) n2 + 3n − 3. Это и означает,что СЧ ∈ NP c полиномом p(n) = n2 + 3n − 3.1.4 задача №4Постановка задачи.