Нос. 4: Линейно програмиране
1 глава. 4: Линейно програмиране професор д-р Петра Мутцел Катедра по алгоритъмно инженерство, LS11 Факултет по компютърни науки, ТУ Дортмунд 13./14. VO A&D WS 08// Petra Mutzel Alg. & Dat. WS 08/09 1
2 Литература за този VO V. Chvatal: Линейно програмиране D. Bertsimas: Линейно програмиране B. Vöcking: Crash Course Линейно програмиране, Лекционни ефективни алгоритми в Университета на Дортмунд SS2003 (вж. Web) P. Mutzel: Оптимизиране на част от скрипта (вж. Web ) Petra Mutzel Alg. & Date. WS 08/09 2
3 3.1 Въведение Пример Общ преглед на рафинерия Пример Диетичен проблем Геометрична интерпретация Стандартни форми Симплекс алгоритъм Мотивация на двойствеността 3.2 Симплекс алгоритъм VO в четвъртък се пропуска поради Погребение на проф. Вегенер Петра Муцел Алг. И Дат. 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. 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 kcal, 55 g протеин, 800 g калций Условия на закупуване: Овесени люспи до опаковки от 28 g, 110 kcal, 4 g протеин, 2 mg калций до 3 цента пиле в опаковки от 100 g, с 205 kcal, 32 g протеин, 12 mg калций до 24 цента яйца в двойни опаковки от 160 kcal, 13 g протеин, 54 mg калций до 13 цента мляко на опаковка 237 ml, 160 kcal, 8 g протеин, 285 g калций до 9 цента черешова торта в 179 g Опаковка с 420 kcal, 4 g протеин, 22 mg калций на 20 цента боб в 260 g пакет с 19 цента, 260 kcal, 14 g протеин, 80 mg калций на 19 цента
10 LP за самия проблем с диетата Допълнително вторично условие: Овесените люспи не трябва да се ядат без мляко: Половин опаковка мляко се изисква за една опаковка овесени люспи: 0,5 х 4 х 1 Petra Mutzel 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. Ax b, x 0 с целева функция z и разтвор многогранник P. H хиперплоскост, ортогонална на z, която пресича P. Представяме си, че 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. Ax b, x 0 с разтвор полиедър P има поне един връх на P, който приема оптималната стойност на целевата функция (оптималният ъгъл). Ъгъл без подобряване на ръба на инцидента е оптимален ъгъл.
19 Линейно програмиране Има три различни възможности за допустимия диапазон P на линейна програма: P = няма едно допустимо решение LP е неразрешим P и inf не съществува (например 0x -1) LP е разрешим, но няма оптимално решение P и мин. съществува LP е разрешим и има крайно решение x * с c T x * = мин. Petra Mutzel Alg. & Dat. WS 08/09 19
20 Дуалност на линейното програмиране Изгодно е да може да се определят граници за линейни програми Точка, която удовлетворява (2) - (4), също удовлетворява неравенството: 2 (2) + (3) Търсим най-добрите граници: Дуалност Петра Mutzel Alg. & Date. WS 08/09 20
21 Двойственост на линейното програмиране Основна програма: Двойна програма: Petra Mutzel 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 * са оптимални Детайли: по-късно в лекцията Petra Mutzel Alg. & Dat. 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 stop: v е оптимален. (3) Последователност на всеки подобряващ ръб e от v. Ако e е неограничен, т.е. stop няма друга крайна точка: LP е неограничен. (4) Нека u е другата крайна точка на e. Задайте v = u. Отидете на (2)
27 Отворени въпроси за симплекс алгоритъма Как да намерите начален ъгъл v от P? За допустими LP в стандартна форма с неотрицателни a ij и bi, началото (точка 0) винаги е възел на P. В противен случай се използва предварителна обработка (фаза 1), която може да започне на пресечка извън P и чрез подобни основни стъпки за обмен изтича до един ъгъл в 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 Симплекс уравнителна схема и таблица Simplex 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 Схема за уравнение на Simplex и теорема на Simplex Tableau: Нека 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, s. Черна дъска