Мис. 4: Лінійне програмування
1 розділ 4: Професор лінійного програмування д-р Петра Мутцель Кафедра інженерії алгоритмів, факультет обчислювальної техніки LS11, ТУ Дортмунд 13./14. VO A&D WS 08// Petra Mutzel Alg. & Date WS 08/09 1
2 Література до цього VO V. Chvatal: Лінійне програмування D. Bertsimas: Лінійне програмування B. Vöcking: Лінійне програмування Crash Course, Ефективні алгоритми лекцій в Університеті Дортмунда SS2003 (див. Інтернет) P. Mutzel: Оптимізація частин сценарію (див. Web ) Petra Mutzel Alg. & Date WS 08/09 2
3 3.1 Вступ Приклад Огляд нафтопереробного заводу Приклад Дієта Завдання Геометрична інтерпретація Стандартні форми Симплексний алгоритм Мотивація двоїстості 3.2 Симплексний алгоритм VO у четвер опущений через Похоронна служба за професором Вегенер Петрою Мутцель Alg. & Dat. WS 08/09 3
4 Задачі лінійної оптимізації Визначення задачі лінійної оптимізації (LP): Проблема пошуку вектора, який за всіх векторів, що відповідають умовам Ax 5 Приклад нафтопереробного заводу 2 Процес крекінгу сирої нафти з такими виходами та витратами: Процес крекінгу 1: 2S, 2M, 1L, витрати 3 EUR Процес розтріскування 2: 1S, 2M, 4L, коштує 5 EUR Цільові завдання: виробляти принаймні 3S, 5M, 4L (умови доставки) виробляти якомога дешевше Petra Mutzel Alg. & Dat. WS 08/09 5
6 Приклад нафтопереробного заводу Цільова функція з урахуванням обмежень визначає простір рішення Позначення матриці: (дошка) Petra Mutzel Alg. & Dat. WS 08/09 6
7 y (0,6) Геометрична цільова функція інтерпретації = 0,9 * * 0,706 = 13,1 мільйона NB1 Збільшити 0,90 xy за умови NB1: 0,42 xy = 0 NB5: y> = 0 (0,1,5) (0,1) (0,882.0.706 ) (0.0) Допустимі рішення (1.0) NB2 (2.0) (3.0) x
8 Геометрична інтерпретація LP Приклад: Нафтопереробний завод Petra Mutzel Alg. & Dat. WS 08/09 8
9 Приклад дієтичного завдання Завдання: придбати якомога дешевше, щоб мінімум 2000 ккал, 55 г білка, 800 г кальцію Умови придбання: вівсяні пластівці в упаковках по 28 г, 110 ккал, 4 г білка, 2 мг кальцію в 3 центах курятини в упаковках по 100 г, з 205 ккал, 32 г білка, 12 мг кальцію до 24 центів яйця в подвійних упаковках по 160 ккал, 13 г білка, 54 мг кальцію до 13 центів молоко в пачці 237 мл, 160 ккал, 8 г білка, 285 г кальцію до 9 центів вишневий пиріг у 179 г Упаковка з 420 ккал, 4 г білка, 22 мг кальцію по 20 центів в зернах в 260 г упаковка з 19 центів, 260 ккал, 14 г білка, 80 мг кальцію при 19 центів
10 LP для самої проблеми дієти Додаткова вторинна умова: Вівсяні пластівці не можна їсти без молока: На одну пачку вівсяних пластівців потрібно половину пакета молока: 0,5 x 4 x 1 Петра Муцель, Alg. & Dat. WS 08/09 10
11 Задачі лінійної оптимізації Задачі лінійної оптимізації виникають у різних формулюваннях і можуть бути перетворені одна в одну: max або min c T x: Ax b min c T x: Ax b та x 0 min c T x: Ax = b і x 0. Стандартна форма: max c T x: Ax = b та x 0 Petra Mutzel Alg. & Dat. WS 08/09 11
12 Задачі лінійної оптимізації LP у найзагальнішому вигляді: Кожен вектор (x, y), який відповідає всім обмеженням, називається можливим рішенням LP. Petra Mutzel Alg. & Date WS 08/09 12
13 Геометричне подання: простір рішення Розподіл змінних x = (x j) відповідає точці в n-мірному просторі R n. Кожне обмеження a it x b i визначає напівпростір. Межею цього напівпростору є гіперплощина a it x = b i. Напівпростір складається з точок на одній стороні цієї гіперплощини, включаючи точки на самій гіперплощині Перетин напівпросторів над усіма обмеженнями є простором допустимих рішень. Простір розв’язку утворює багатогранник. Обмежені багатогранники називаються багатогранниками. Набір точок, описаний багатогранником, є опуклим, тобто для кожної пари точок x, y P всі точки на сполучній лінії між x та y знаходяться в P. Витяг з Vöcking (див. Вище)
14 Геометричне зображення: цільова функція Цільова функція z (x) = c T x вказує напрямок у R n. Ми можемо візуалізувати цей напрямок за допомогою променя, що починається з початку координат і проходить через точку c. Нехай H - гіперплощина, яка є ортогональною променю цільової функції, тобто існує значення z R таке, що H =. Усі точки на H мають однакове значення цільової функції z, яке ми називаємо z (h). LP, значення цільової функції z (x) обмежене вгору обмеженнями (при max z (x)), називається обмеженим LP. В іншому випадку LP не обмежений. Витяг з Vöcking (див. Вище)
15 Геометричне зображення: кутові рішення Кожна n лінійно незалежних гіперплощин перетинається в точці перетину. Точки перетину, що містяться у розчині многогранника P, називаються вершинами P. Два кути сусідні, якщо вони відрізняються рівно в одній гіперплощині. Суміжні кути з'єднані між собою ребром. Ребро відповідає перетину загальних гіперплощин n-1 цих кутів. Витяг з Vöcking (див. Вище)
16 Геометричне зображення: оптимальне рішення Обмежений LP у вигляді max c T x s.t. Осі b, x 0 з цільовою функцією z та розв’язком багатогранника P. H гіперплощиною, ортогональною z, що перетинає P. Ми уявляємо, що H зміщується вгору (тобто у напрямку цільової функції). В результаті z (h) безперервно зростає. Ми рухаємо H точно так, щоб над H. більше не було жодної точки Нехай H * - отримана таким чином гіперплощина. Тоді H * P містить оптимальні рішення ЛП. Через опуклість, принаймні одна з цих точок є кутом P. Таким чином, завжди є кут з оптимальним цільовим значенням. Будьте витягом з Vöcking (див. Вище)
17 Геометричне зображення: Оптимальний кут Нехай v - довільний кут багатогранника P. Нехай H v - гіперплощина, ортогональна z, що проходить через v. Нехай e - одне з ребер, що мають v падаюче. Якщо e працює вище H v, цільове значення покращується, якщо починати з v і проходити вздовж e. Таке ребро називається покращуючим ребром. Якщо v не має покращаючого краю, ми не можемо перемістити H v вгору, не виходячи з P (через опуклість). Отже H v = H * і, отже, v є оптимальним. Тут застосовується таке: Глобальний оптимум відповідає локально оптимальному куточку. Витяг з Vöcking (див. Вище)
18 Підсумкова теорема: Для кожного обмеженого LP виду max c T x s.t. Ax b, x 0 з розчином багатогранника P є принаймні однією вершиною P, яка приймає оптимальне значення цільової функції (оптимальний кут). Кут без поліпшення краю падаючої ситуації є оптимальним кутом.
19 Лінійне програмування Існує три різні можливості для допустимого діапазону P лінійної програми: P = немає єдиного допустимого рішення LP нерозв'язний P і inf не існує (наприклад, 0x -1) LP є розв'язним, але немає оптимального рішення P і min min LP є розв'язним і має кінцевий розв'язок x * з c T x * = min Petra Mutzel Alg. & Dat. WS 08/09 19
20 Подвійність лінійного програмування Вигідно мати можливість задавати межі для лінійних програм Точка, яка задовольняє (2) - (4), також задовольняє нерівність: 2 (2) + (3) Ми шукаємо найкращі межі: Подвійність Петра Mutzel Alg. & Date WS 08/09 20
21 Подвійність лінійного програмування Основна програма: Подвійна програма: Петра Мутцель, Alg. & Dat. WS 08/09 21
22 Подвійність лінійного програмування Первинна програма (P): Подвійна програма (D): Теорема слабкої двоїстості: Нехай x є допустимою точкою для (P), а y - для (D). Тоді: y T b c T x Висновок: Якщо (P) необмежений, то (D) нерозв'язний. Petra Mutzel Alg. & Date WS 08/09 22
23 Подвійність лінійного програмування Первинна програма (P): Подвійна програма (D): Теорема про сильну подвійність: Нехай x * є допустимою точкою для (P), а y * допустимою для (D). Тоді: y * T b = c T x * обидва рішення x * і y * є оптимальними Детальніше: пізніше в лекції Петра Муцел Алг. & Дат. WS 08/09 23
24 3.2 Симплексний алгоритм На практиці лінійні програми вирішуються за допомогою симплексного алгоритму [Dantzig 1955]. Макс. 3x 1 + 2x 2 + 2x 3 За умови x 1 + x 3 8 x 1 + x 2 7 x 1 + 2x 2 12 x 1, x 2, x 3 0 Petra Mutzel Alg. & Dat. WS 08/09 24
25 Візуалізація симплексного алгоритму Max z = 3x 1 + 2x 2 + 2x 3 x 3 (0,0,8) (0,6,8) Оптимально! (2,5,6) z = 28 z = 0 (0,6,0) x 2 (7,0,1) z = 23 (2,5,0) x 1 (7,0,0) z = 21-го
26 Симплексний алгоритм Дано: LP з розв’язком багатогранника P (1) Знайти довільний кут (початковий кут) v від P. (2) Якщо немає покращення ребра, що падає на v зупинку: v є оптимальним. (3) Послідовність будь-якого вдосконалюючого ребра e v. Якщо e необмежене, тобто не має іншої зупинки кінцевої точки: LP є необмеженим. (4) Нехай u - інша кінцева точка e. Встановіть v = u. Перейти до (2)
27 Відкриті запитання про симплексний алгоритм Як знайти початковий кут v від P? Для допустимих LP в стандартній формі з невід’ємними a ij і bi початком (точка 0) завжди є вузол P. В іншому випадку використовується попередня обробка (фаза 1), яка може розпочатися на перетині поза P і через подібні основні етапи обміну біжить до кутка у П. Як зберігається багатогранник? Система рівнянь, описана обмеженнями, зберігається у вигляді таблиці. На кожному кроці симплекса таблиця змінюється, і вихідні краї поточного кута можна обчислити з таблиці. Перевірте, чи поточний кут оптимальний? Якщо ні, то який покращуючий край ви вибрали? Чи закінчується алгоритм? див. лекцію: те саме
28 Визначення Нехай дана система рівнянь Ax = b з A R m n, m. 29 Визначення Якщо A B регулярний (= обернений), A B називається базовою матрицею або базисом A і B називається базисним індексним вектором або базисом A; аналог A N, N неосновного вектора індексу. Вектор x R n з x N = 0, x B = AB -1 b називається основним рішенням Ax = b основи A B. Якщо AB є базою, змінні називаються xj, j B, базовими змінними, а xj, j N Неосновні змінні. Якщо A B є основою і застосовується A B -1 b 0, то A B, B та відповідне основне рішення x називаються допустимими, інакше не допустимими. Можливий базовий розв'язок x для базису A B називається неродженим, якщо (x B) i = (A B -1 b) i> 0 для всіх i B, інакше виродженим.
30 Схема рівняння симплекса та таблиця симплекса max c T x s.t. Ax = b, x 0 max c B c N T x B x N s.t. (AB, AN) x B = b, x B 0 x N x NAB x B + AN x N = bx B = AB 1 b AB 1 AN x N Значення цільової функції: z = c BT x B + c NT x N = c BT (AB 1 b AB 1 AN x N) + c NT x N = = c TBA 1 B b + (c TN c TBA 1 BAN) x N Схема симплексного рівняння: x B = A 1 B b A 1 BAN x N z = c TBA 1 B b + (c TN c TBA 1 BAN) x N
31 Схема рівняння симплекса та таблиця Симплекс Схема рівняння симплекса: x B = AB 1 b AB 1 AN x N z = c BTAB 1 b + (c NT c BTAB 1 AN) x N Значення цільової функції Симплекс-таблиця: значення основних змінних - c BTAB 1 b AB 1 bc NT c BTAB 1 ANAB 1 AN зменшені витрати
32 Схема рівняння симплекса та теорема симплексного таблиці: Нехай A B є реальною базою з базовим розв’язком x, A = A 1 B A N, b = A 1 B b і c T = c T N c T B A 1 B A N зменшених витрат. (a) Якщо c T x 0, то x є оптимальним (b) Нехай q s N із c s> 0. (b1) Якщо A s 0, то c T x на P = (A, b): = необмежений. (b2) Якщо A S 0, то нехай λ 0 = min b i i = 1,2. m, a дорівнює> 0 a є і r < 1,2. m>так що b r = λ 0, a rs> 0 a rs, тоді A B з B = (p 1. p r-1, q s, p r + 1. p m) є можливою основою для основного розчину x і c T x c T x. (b3) Якщо застосовуються припущення (b2) і A B не є виродженим, то застосовується c T x> c T x. Доказ: наступний приклад VO Di, див. Таблицю