Математика та інформатика - Завантажити PDF безкоштовно
1 Проф. Курс Вінфріда Хохштэтлера з лінійної оптимізації LESEPROBE математики та інформатики
2 Твір захищено авторським правом. Права, встановлені цим, зокрема право на відтворення та розповсюдження, а також переклад та передрук, зберігаються, навіть якщо вони частково. Жодна частина твору не може бути відтворена у будь-якій формі (друк, ксерокопія, мікрофільм або будь-який інший процес) або оброблена, тиражована або розповсюджена за допомогою електронних систем без письмового дозволу FernUniversität.
3 Зміст Вступ Позначення індексів vii xi xiv 1 Лінійна оптимізація - Завдання та моделювання Перші приклади Проблема дієти Жадібність не завжди хороша Проблема змішування Загальна техніка завдання лінійної оптимізації для еквівалентних трансформацій Вирішення проблеми дієти від макаронних виробів до картоплі Графічний метод Запропоновані рішення для обгортання вправ та комбінації Аффінні підпростори K n опуклих конусів у K n опуклих наборів у K n Резюме Пропоновані рішення для вправ Подвійність Інший погляд на проблему дієти Лема Фаркаса iii
4 iv Зміст 3.3 Теорема подвійності лінійного програмування Дуалізація лінійних програм Теорема додаткового ковзання Пропоновані рішення для вправ Багатогранник Двокласне суспільство? Бічні поверхні Фасетки Кути та ребра Наприклад, пермутаедр Латеральний конус решітки та щільний варіант лемки Фаркаса Теорема Вейля Трюк поляризації для конусів та теорема Мінковського Вправи Симплексний метод 1-скелет багатогранника Геометрична ідея симплексного алгоритму Повторення алгоритму Гауса-Йордана Таблиця форми симплексного алгоритму Вибір повороту, виродження, скінченність Коментарі до чисельності Двофазний метод Великий метод М Перероблений симплексний алгоритм Пост-оптимізація та аналіз кроків чутливості Назва гри Пропоновані рішення вправ
5 Зміст v 6 Про складність симплексного алгоритму Строго поліноміальні алгоритми та дробовий рюкзак Планування розгортання персоналу Куби Клі-Мінті Середній час роботи симплексного алгоритму Декомпозиція Данцига-Вульфа Додаток: Символи Ландау Пропоновані рішення для вправ Еліпсоїдний метод Скорочення алгоритмічних задач Кодування алгоритмічних задач Кодування Перевірка допустимості лінійних програм та оптимізація використання подвійності Двійковий пошук Геометрична ідея методу еліпсоїдів Метод еліпсоїдів у лінійному програмуванні Як ви вирішуєте задачу за допомогою точної арифметики? Оптимізація та відокремлення математичного Sputnik Пропоновані рішення для вправ Методи внутрішніх точок Метод Кармаркара Проективне перетворення одиничного симплекса Геометрична ідея методу Кармаркара Для коректності та аналізу часу Нормальна форма Кармармара Алгоритм, що слідує за шляхами Геометричні ідеї Деякі підготовки Асиметрична симетрична самодуальна модель Центральний шлях та оптимальний розділ Пошук оптимального розділу Пошук точного рішення Загальний метод внутрішньої точки 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. Якщо тепер ми можемо створити симплексний алгоритм за допомогою відповідного спотворення цього багатогранника, при виконанні правила Данцига всі вершини Перехід спотвореного таким чином гіперкуба показує, що метод має експоненціальний час роботи у кількості змінних. Це не може бути поліномом у розмірі вхідних даних. Наступний клас лінійних програм (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. Куби Клі-Мінті 205 хв 5 р. 1 інн. Під 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 п. Оскільки основна задача оптимізації приймає одне і те ж значення цільової функції з даним рішенням, обидва повинні бути оптимальними рішеннями відповідно до принципу подвійності. З іншого боку, якщо 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, отже, також унікальність рішення. Після цих підготовчих дій ми показуємо: Вирок. Симплексний алгоритм із правилом зведення Данцига вимагає 2 n 1 кроків зведення для (LP n). Доказ. Претензія, очевидно, еквівалентна тому, що ми проглядаємо 2 n таблиць у цій процедурі. Ми показуємо це за допомогою повної індукції по п. Точніше, показуємо:
6.3. Куби Клі-Мінті 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 і 1 ітерації, щоб приземлитися на Таблиці 2 н. 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 біт.