Математика и компјутерски науки - PDF бесплатно преземање
1 Проф. Курс Винфрид Хохтјетлер по линеарна оптимизација LESEPROBE математика и компјутерски науки
2 Делото е заштитено со авторско право. Правата утврдени со ова, особено правото на репродукција и дистрибуција, како и превод и повторно печатење, се задржани, дури и делумно. Ниту еден дел од делото не смее да се репродуцира во каква било форма (печатење, фотокопија, микрофилм или кој било друг процес) или обработен, удвоен или дистрибуиран со употреба на електронски системи без писмено одобрение од FernUniversität.
3 содржини Вовед Индекс на нотација vii xi xiv 1 Линеарна оптимизација - Задача и моделирање Први примери Проблем со диетата Алчноста не е секогаш добра Проблем со мешање Општ проблем со линеарна оптимизација Техники за еквивалентни трансформации Решавање на диетален проблем од тестенини до компири Графички метод Предложени решенија за вежби Завиткување и комбинации Афински потпростори на K n Конвексни конуси во K n Конвексни множества во K n Резиме Предложени решенија за вежби Двојност Друг поглед на диеталниот проблем Farkas lemma iii
4 iv Содржина 3.3 Теорема на двојност на линеарно програмирање Дуализација на линеарни програми Теорема на комплементарно лизгање Предложени решенија за вежбите Полиедрон Двокласно општество? Странични површини Аспекти Агли и рабови На пример пермутаедрон Латералниот конус на решетката и густата верзија на Фаркас Лема Теорема Вејл Трик за поларизација за конуси и теорема Минковски Вежби Симплекс метод 1 скелет на политоп Геометриска идеја на симплекс алгоритам Повторување на алгоритмот Гаус-Јордан Табела форма на алгоритам на симплекс Избор на пивот, дегенерација, конечност Коментари за нумериката Двофазен метод Методот Биг М Ревидиран симплекс алгоритам чекори Анализа на оптимизација и чувствителност Име на играта Предложени решенија за вежбите
5 содржини v 6 За комплексноста на алгоритмот на симплекс, строго полиномски алгоритми и фракциониот ранец Планирање за распоредување на персонал Klee-Minty Cubes Средното време на траење на алгоритмот на симплекс Данциг-Волф Распаѓање Додаток: Симболите на Ландау Предложени решенија за вежби Проблеми на елипсоидот со должина Тест за прифатливост на линеарни програми и оптимизација на експлоатација на двојно бинарно пребарување Геометриска идеја за методот на елипсоид Метод на елипсоид во линеарно програмирање Како го решавате проблемот со точна аритметика? Оптимизирање и раздвојување на математички предлози за решение на Спутник за вежбите Методи на внатрешна точка Методот Кармакар Проективната трансформација на единицата симплекс Геометриската идеја на методот Кармакар за анализа на точноста и времето на траење Нормалната форма на Кармакар Алгоритам кој го следи патот Геометриски идеи Централна патека и оптимална партиција Наоѓање на оптимална партиција Наоѓање на точно решение Резултат на методот на општа внатрешна точка
6 vi Содржина 8.4 Предложени решенија за вежбите Библиографија 319
7 Поглавје 6 За комплексноста на алгоритмот на симплекс Симплекс алгоритмот се утврди како ефикасен метод во пракса од неговото откривање. Од теоретска гледна точка, нема навистина задоволително објаснување за ова. Во ова поглавје ќе го запознаеме првиот, поедноставен концепт на сложеност и ќе го разгледаме алгоритмот на симплекс од оваа гледна точка. 6.1 Строго полиномски алгоритми и дробен ранец Ако сакаме да го процениме квалитетот на алгоритмот, исто така, ќе дозволиме добра постапка да пресметува подолго на поголемите задачи. Но, прво мора да ја дефинираме големината на задачата. Исто така, треба да дадеме барем приближна дефиниција за алгоритам. Со алгоритам за проблем (или за класа на проблеми) разбираме низа добро дефинирани правила или команди што генерираат специфичен излез од секој специфичен влез, пример на проблем, во конечен број на основни чекори. Значи, ние бараме: i) Алгоритам мора да биде опишан во текст со конечна должина. ii) Редоследот на чекорите е единствен во секоја пресметка. iii) Секој основен чекор може да се изврши механички и ефикасно. 189 година
18 200 Поглавје 6. Комплексноста на алгоритмот на симплекс Ако бараме почнувајќи од третиот консултант, имаме консултанти 1 и 3, а клиент 1 во Т. Значи, ги зголемуваме променливите на консултантот 1 и 3 и ги намалуваме оние на клиентот 1. Од в 12 = 2, можеме само да се зголемиме за 1 без да ја изгубиме допуштеноста. Сега му доделуваме консултант 1 на клиент 2 и консултант 3 на клиент 1. Во следниот чекор ја зголемуваме двојната променлива на консултантот 4 на два и го доделуваме на третиот клиент. Потоа, ја поставивме двојната променлива на консултантот 5 на 1. Сепак, клиентот 2 е веќе доставен. Така, ние повторно го конструираме нашето дрво Т. Ова содржи советници 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) максимум 2 n 1 xn 2 xxn 1 + xn под x 1 5 4x 1 + xx 1 + 4x 2 + xnxn 1 xxn 1 + xn 5 н. X 0 Пред сè, сакаме да докажеме дека ова е всушност е искривена хиперкуба. Наб obserудуваме: Предлог. Нека x биде допуштен за (LP n). Тогаш за сите i = 1. n: i) Ако x i = 0, тогаш i-тата нееднаквост е строга. ii) Ако i-тата нееднаквост не е строга, тогаш x i> 0. Доказ. з) Тврдењето е очигледно точно за i = 1. Ако i> 1, тогаш (i 1)-та нееднаквост дава 2 i 1 x i 2 x x i 2 + x i 1 5 i 1.
23 6.3. Коцки Klee-Minty 205 мин. 5 год. 1 година под година 1 + 4 г. 2 + 8 год. 2 год. 2 год. 2 + 4 гг. 1 год. 2 год. 2 год. 2 год. Задачата 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, со тоа и уникатноста на растворот. По овие подготовки покажуваме: Реченица. Симплекс алгоритмот со стожерното правило на Данциг бара 2 n 1 стожерни чекори за (LP n). Доказ. Побарувањето е очигледно еквивалентно на фактот дека ние поминуваме низ 2 n табели во оваа постапка. Ова го покажуваме со целосна индукција на н.Поточно, покажуваме:
25 6.3. Klee-Minty Cubes 207 2c n 1 A 0 0 I nb 2c n 1 4c n 1 Tableau 2 n 1 Единствената колона со позитивно намалени трошоци е колоната на n-та променлива и ја добиваме следната табела: 2c n 1 A 0 0 I nb 2c n 1 4c n 1 Tableau 2 n Ова исто така изгледа како продолжено прво табело за LP n 1, освен што колоните на (n 1) -th променлива и (n 1) -th променлива на лизгање се заменети. Сепак, ова не го менува стожерот, кој треба да ја разбере оваа размена, бидејќи не-нула записите во намалените трошоци се различни во парови и затоа колоната со најголем запис е секогаш единствена. Значи, мора повторно да направиме 2 n 1 повторувања за да слетаме на Tableau 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 битови.