Кејп. 4: Линеарно програмирање
1 погл. 4: Професор по линеарно програмирање Др. Петра Муцел Стол за алгоритамско инженерство, LS11 Факултет за компјутерски науки, ТУ Дортмунд 13./14. VO A&D WS 08// Petra Mutzel Alg. & Датум WS 08/09 1
2 Литература за ова VO V. Чватал: Линеарно програмирање Д. Берцимас: Линеарно програмирање Б.Векинг: Линеарно програмирање на курсот за уривање, Ефикасни алгоритми на предавања на Универзитетот во Дортмунд SS2003 (види Веб) П.Муцел: Оптимизација на скриптниот дел (види веб ) Петра Муцел Алг. & Датум на СВ 08/09 2
3 3.1 Вовед Пример Преглед на рафинерија за нафта Пример Проблем со диета Геометриско толкување Стандардни форми Симплекс алгоритам Мотивација на двојноста 3.2 Симплекс алгоритам VO во четврток е изоставен поради Погребна служба за проф. Вегенер Петра Муцел Алг. & Дат СО 08/09 3
4 Проблеми со линеарна оптимизација Дефинирање на проблем со линеарна оптимизација: Проблем со наоѓање на вектор кој, под сите вектори, ги исполнува условите Ax 5 Пример рафинерија за масло 2 Процес на пукање на сурова нафта со следниве приноси и трошоци: Процес на пукање 1: 2S, 2M, 1L, трошоци Процес на пукнатина 3 EUR 2: 1S, 2M, 4L, чини 5 EUR Цели: произведете најмалку 3S, 5M, 4L (услови за испорака) произведете што е можно поевтино Петра Муцел Алг. & Дата. WS 08/09 5
6 Пример рафинерија за нафта Објективна функција предмет на ограничувања го дефинира просторот на решението Забележување на матрицата: (табла) Петра Муцел Алг. & Дат. 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 Пример: Рафинерија за нафта Петра Муцел Алг. & Дат. WS 08/09 8
9 Пример проблем со диета Цел: Купете што е можно поевтино, така што најмалку 2000 kcal, 55g протеини, 800 g калциум Услови за купување: Овесни снегулки до 28g пакувања, 110 kcal, 4 g протеини, 2 mg калциум до 3 центи пилешко во 100g пакувања, со 205kcal, 32 g протеини, 12 mg калциум до 24 центи јајца во двојни пакувања од 160 kcal, 13 g протеини, 54 mg калциум до 13 центи млеко на пакување 237 ml, 160 kcal, 8g протеини, 285 g калциум до 9 центи цреша торта во 179 g Пакување со 420 kcal, 4 g протеини, 22 mg калциум на 20 центи грав во 260 g пакување со 19 центи, 260 kcal, 14 g протеини, 80 mg калциум на 19 центи
10 ЛП за самиот проблем на диета Дополнителен секундарен услов: Снегулки од овес не треба да се јадат без млеко: Потребно е половина пакет млеко за едно пакување снегулки од овес: 0,5 х 4 х 1 Петра Муцел Алг. & Дат. WS 08/09 10
11 Проблеми со линеарна оптимизација Проблемите со линеарна оптимизација се појавуваат во различни формулации и сите можат да се претворат една во друга: максимум или мин c T x: Axe min min T T x: Axe b и x 0 min c T x: Ax = b и x 0 Сметаме дека Стандардна форма: максимум Т х: Секира = б и х 0 Петра Муцел Алг. & Дат. СС 08/09 11
12 Проблеми со линеарно оптимизирање LP во својата најопшта форма: Секој вектор (x, y) што ги исполнува сите ограничувања се нарекува изводливо решение на LP. Петра Муцел Алг. & Датум на СР 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. Можеме да ја визуелизираме оваа насока со зрак кој започнува од потеклото и минува низ точката в. Нека H биде хиперплан кој е ортогонален на зракот на објективната функција, т.е. има вредност z R таква што H =. Сите точки на H имаат иста објективна вредност на z, што ја нарекуваме z (h). LP чијашто вредност на вредноста z (x) е ограничена нагоре со ограничувањата (на максимум z (x)) се нарекува ограничена LP. Инаку ЛП е неограничен. Извадок од Vöcking (видете погоре)
15 Геометриска претстава: аголни решенија Секој n линеарно независен хипер-авион се пресекува на точка на пресек. Точките на пресек содржани во растворот полиедрон Р се нарекуваат темиња на П. Два агли се соседни ако се разликуваат точно во една хиперпланија. Соседните агли се поврзани едни со други со раб. Работ одговара на пресекот на n-1 заедничките хиперплани на овие агли. Извадок од Vöcking (видете погоре)
16 Геометриска претстава: оптимално решение Ограничен LP во форма max c T x s.t. Axe b, x 0 со објективна функција z и раствор полиедрон P. H хиперплан ортогонален на z што се пресекува со П. Замислуваме дека H е поместен нагоре (т.е. во насока на објективната функција). Како резултат, z (h) постојано се зголемува. Ние го поместуваме H точно така што повеќе нема точка над H. Нека H * биде хиперпланот добиен на овој начин. Тогаш H * P ги содржи оптималните решенија на LP. Поради конвексноста, барем една од овие точки е агол на 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. Axe b, x 0 со раствор полиедрон P има барем едно теме на P што ја зема оптималната вредност на целната функција (оптималниот агол). Агол без подобрување на работ на инцидентот е оптимален агол.
19 Линеарно програмирање Постојат три различни можности за опсег на допуштеност P на линеарна програма: P = не постои единствено допуштено решение LP е нерешлив P и inf не постои (на пр. 0x -1) LP е решлив, но не постои оптимално решение P и мин постои ЛП е решлив и има конечно решение x * со c T x * = мин Петра Муцел Алг. & Дат. WS 08/09 19
20 Двојност на линеарно програмирање Поволно е да може да се одредат граници за линеарни програми. Точка што ги задоволува (2) - (4) исто така ја задоволува нееднаквоста: 2 (2) + (3) Ние ги бараме најдобрите граници: Двојност Петра Муцел Алг. & Датум СВ 08/09 20
21 Двојство на линеарно програмирање Примарна програма: Двојна програма: Петра Муцел Алг. & Дат. WS 08/09 21
22 Двојство на линеарно програмирање Примална програма (Р): Двојна програма (Д): Теорема на слаба двојност: Нека x биде валидна точка за (P) и y валидна за (D). Потоа: y T b c T x Резултат: Ако (P) е неограничен, тогаш (D) е нерешлив. Петра Муцел Алг. & Датум на СР 08/09 22
23 Двојност на линеарно програмирање Примална програма (Р): Двојна програма (Д): Силна теорема на двојност: Нека x * е дозволена точка за (P) и y * дозволена за (D). Потоа: y * T b = c T x * двата решенија x * и y * се оптимални Детали: подоцна на предавањето Петра Муцел Алг. & Дат. WS 08/09 23
24 3.2 Алгоритам на симплекс Во пракса, линеарните програми се решаваат со помош на алгоритмот на симплекс [Dantzig 1955]. Макс 3х 1 + 2х 2 + 2х 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 Визуелизација на алгоритмот на симплекс Макс 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) Низа на кој било подобар раб на v. Ако e е неограничен, т.е. нема друга крајна точка на запирање: LP е неограничен. (4) Нека биде друга крајна точка на д. Поставете v = u. Одете на (2)
27 Отворени прашања во врска со алгоритмот на симплекс Како наоѓате почетен агол v на P? За дозволените ЛП во стандардна форма со негативни ij и bi, потеклото (точка 0) е секогаш јазол на P. Во спротивно, се користи пред-обработка (фаза 1), што може да започне на пресек надвор од Р и преку слични основни чекори на размена трча на еден агол во П. Како се зачувува полиедронот? Системот на равенки опишани со ограничувањата е зачуван во форма на табела. Во секој чекор од симплекс, табелата се менува и излезните рабови на тековниот агол може да се пресметаат од табелата. Тестирајте дали тековниот агол е оптимален? Ако не, кој додаток за подобрување го избирате? Дали алгоритмот завршува? види предавање: исто
28 Дефиниции Да се даде систем на равенки Ax = b со A R m n, m 29 Дефиниции Ако A B е регуларен (= превртен), A B се нарекува основна матрица или основа на A и B се нарекува вектор на основен индекс или основа на A; аналогно на не-базниот индекс вектор. Векторот 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 Шема на равенки на симплекс и табела на симплекс макс 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 БАН) x N Шема на едноставни равенки: x B = A 1 B b A 1 ЗАБРАНА 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 намалените трошоци. (а) Ако 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, видете ја табелата