Математика и компютърни науки - PDF безплатно изтегляне
1 проф. Д-р Курс на Winfried Hochstättler по линейна оптимизация LESEPROBE математика и компютърни науки
2 Произведението е защитено с авторски права. Установените с това права, по-специално правото на възпроизвеждане и разпространение, както и превод и препечатване, са запазени, дори и само частично. Никоя част от произведението не може да бъде възпроизвеждана под каквато и да е форма (печат, фотокопия, микрофилм или друг процес) или обработвана, дублирана или разпространявана с помощта на електронни системи без писменото разрешение на FernUniversität.
3 Съдържание Въведение Индекс на нотация vii xi xiv 1 Линейна оптимизация - Задачи и моделиране Първи примери Диетичен проблем Алчността не винаги е добра Проблем със смесването Общият проблем с линейната оптимизация Техники за еквивалентни трансформации Решаване на диетичния проблем От макаронени изделия до картофи Графичен метод Предложени решения за упражненията Опаковане и комбинации Affine подпространства на K n Изпъкнали конуси в K n Изпъкнали набори в K n Обобщение Предложени решения за упражненията Дуалност Друг поглед върху проблема с диетата Farkas lemma iii
4 iv Съдържание 3.3 Теорема за двойствеността на линейното програмиране Дуализация на линейни програми Теорема за допълващо приплъзване Предложени решения за упражненията Многогранно двукласно общество? Странични повърхности Фасети Ъгли и ръбове Например пермутаедъра Страничният решетъчен конус и плътната версия на лекмата на Фаркас Теоремата на Weyl Полицизационният трик за конусите и теоремата на Минковски Упражнения Симплексният метод 1-скелетът на многоъгълник Геометричната идея на симплексния алгоритъм Повторение на алгоритъма на Гаус-Йордан Таблица форма на симплексния алгоритъм Избор на пивот, дегенерация, крайност Коментари за числата Двуфазен метод The Big M Методът Ревизиран симплекс алгоритъм Пост-оптимизация и граници на чувствителност Двоен симплекс граници Име на играта Предложени решения за упражненията
5 Съдържание v 6 За сложността на симплексния алгоритъм Строго полиномиални алгоритми и частична раница Планиране на разполагане на персонала Klee-Minty Cubes Средното време на работа на симплекс алгоритъма Декомпозиция на Данциг-Улф Приложение: Символите на Ландау Предложени решения за упражненията Елипсоиден метод Намаляване на алгоритмичните решения Кодирането на алгоритмичните проблеми Кодирането Тест за допустимост на линейни програми и оптимизация Експлоатация на двойствеността Двоично търсене Геометричната идея на метода Елипсоид Методът Елипсоид в линейното програмиране Как решавате проблема с точна аритметика? Оптимизиране и разделяне на предложения за математическо решение на Sputnik за упражненията Методи на вътрешната точка Методът Karmarkar Проективна трансформация на единичния симплекс Геометричната идея на метода Karmarkar За коректност и анализ по време на работа Нормална форма на Karmarkar Алгоритъм, следващ пътя Геометрични идеи Някои подготовки Кососиметричният самодуален модел Централният път и оптималният дял Намиране на оптималния дял Намиране на точно решение Общ метод за вътрешна точка Outlook
6 vi Съдържание 8.4 Предложени решения за упражнения Библиография 319
7 Глава 6 За сложността на симплекс алгоритъма Симплекс алгоритъмът се е утвърдил като ефективен метод на практика от откриването си. От теоретична гледна точка няма наистина задоволително обяснение за това. В тази глава ще опознаем първата, по-проста концепция за сложността и ще разгледаме симплекс алгоритъма от тази гледна точка. 6.1 Строго полиномиални алгоритми и частична раница Ако искаме да оценим качеството на алгоритъма, ще позволим и добра процедура за изчисляване на по-дълги задачи. За да направите това обаче, първо трябва да определим размера на задачата. Трябва също така да дадем приблизително определение на алгоритъм. Под алгоритъм за проблем (или за клас проблем) разбираме поредица от добре дефинирани правила или команди, които генерират специфичен изход от всеки конкретен вход, екземпляр на проблема, в краен брой елементарни стъпки. Затова изискваме: i) Алгоритъмът трябва да бъде описан в текст с крайна дължина. ii) Последователността на стъпките е уникална при всяко изчисление. iii) Всяка елементарна стъпка може да се извърши механично и ефективно. 189
18 200 Глава 6. Сложността на симплекс алгоритъма Ако търсим, започвайки от третия съветник, имаме съветник 1 и 3 и клиент 1 в Т. Така че ние увеличаваме променливите на съветник 1 и 3 и намаляваме тези на клиент 1. Тъй като c 12 = 2, можем да увеличим само с 1, без да губим допустимост. Сега ние възлагаме консултант 1 на клиент 2 и консултант 3 на клиент 1. В следващата стъпка увеличаваме двойната променлива на консултант 4 на две и го присвояваме на третия клиент. След това задаваме двойната променлива на консултант 5 на 1. Въпреки това, клиент 2 вече е предоставен. Така че ние отново изграждаме нашето дърво T. Това съдържа съветници 1, 3 и 5 и клиенти 2 и 1. Тъй като c 13 = 3, ние отново се увеличаваме само с. Новият ръб включва също съветник 4 и клиент 3 в дървото. Тъй като c 14 = c 34 = 4, ние отново променяме само двойните променливи с 1.
20 202 Глава 6. Сложността на симплекс алгоритъма се дава само от n неравенства и n ограничения на знака. Входната променлива е I (w) = n 2. H n има 2 n върха, а именно всички вектори в n. Ако сега можем да направим алгоритъма на симплекса чрез подходящо изкривяване на този многоъгълник, при продължаване с правилото на Dantzig, всички върхове на Преминаването на хиперкуб, изкривен по този начин, показва, че методът има експоненциално време на работа в броя на променливите. Това не може да бъде полином в размера на входните данни. Следващият клас линейни програми (LP n) за n N прави това, което искаме, както ще покажем сега. (LP n) max 2 n 1 xn 2 xxn 1 + xn под x 1 5 4x 1 + xx 1 + 4x 2 + xnxn 1 xxn 1 + xn 5 n. X 0 На първо място, искаме да докажем, че това всъщност е е изкривен хиперкуб. Наблюдаваме: Предложение. Нека x е допустимо за (LP n). Тогава за всички i = 1. n: i) Ако x i = 0, тогава i-тото неравенство е строго. ii) Ако i-тото неравенство не е строго, тогава x i> 0. Доказателство. i) Твърдението очевидно е правилно за i = 1. Ако i> 1, тогава (i 1) -то неравенство дава 2 i 1 x i 2 x x i 2 + x i 1 5 i 1.
6.3. Klee-Minty Cubes 205 min 5y yn 1 ynnyn under y 1 + 4y 2 + 8y nyn 2 n 1 y 2 + 4y n 1 yn 2 n 2 yn 2 yn 2 nyn 1 + 4y n 2 yn 1 y 1st yn 0. Присвояването yn = 1, yi = 0 за i = 0. n 1 е допустимо за задачата за двойна оптимизация със стойност на целевата функция 5 n. Тъй като основният проблем за оптимизация с даденото решение приема същата стойност на целевата функция, и двете трябва да бъдат оптимални решения съгласно теоремата за двойствеността. От друга страна, ако x е оптимално решение на първоначалния проблем, тогава поради целевата функция и последното ограничение имаме 2 n 1 xn 2 xxn 1 + xn = 5 n 2 nxn 1 xxn 1 + xn 5 n 2 n 1 xn 2 xxn 1 0 Тъй като всички променливи са неотрицателни, следва, че x1 =. = x n 1 = 0 и по този начин xn = 5 n, като по този начин и уникалността на решението. След тези приготовления показваме: Изречение. Симплексният алгоритъм с правилото за завъртане на Dantzig изисква 2 n 1 стъпки за завъртане за (LP n). Доказателство. Твърдението очевидно е еквивалентно на факта, че провеждаме 2 n таблици в тази процедура. Показваме това чрез пълна индукция на n. По-точно показваме:
6.3. Klee-Minty Cubes 207 2c n 1 A 0 0 I nb 2c n 1 4c n 1 Таблица 2 n 1 Единствената колона с положително намалени разходи е колоната на n-та променлива и получаваме следващата таблица: 2c n 1 A 0 0 I nb 2c n 1 4c n 1 Таблица 2 n Това също изглежда като разширена първа таблица за LP n 1, с изключение на това, че колоните на (n 1) -та променлива и (n 1) -та променлива на приплъзване се разменят. Това обаче не променя основния избор, който трябва да разбере този суап, тъй като ненулевите записи в намалените разходи са различни по двойки и следователно колоната с най-голямото въвеждане винаги е уникална. Така че трябва да направим 2 n 1 итерации отново, за да кацнем на Таблица 2 n. 2c n A 0 0 I n b 2c n 1 4c n Таблица 2 n Това е оптимално, но е постигнато само след 2 n 1 стъпки. По този начин доказахме: Теорема. Симплексният алгоритъм, използващ правилото за въртене на Данциг, не е строго полиномиален алгоритъм и следователно не е полиномиален алгоритъм. Доказателство. Размерът на входните данни е I (LP n) = O (n 2) или LP n = O (n 3), тъй като най-големият срещащ се номер 5 n може да бъде кодиран, използвайки максимум 3n бита.