Е. Корныхин - Задачи по курсу Методы оптимизации (1125258)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М.В.ЛОМОНОСОВАфакультет Вычислительной Математики и КибернетикиЕ. КорныхинЗадачи по курсу«Методы оптимизации»Москва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Постановка задачи.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
