Доза/добу за лімітом 0 x 1 4 0 x 2 3 0 x 3 2 0 x 4 8 0 x 5 2 0 x 6 2 Відповідно до добової потреби 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 Тут ми враховуємо, що ми не можемо споживати негатив кількість або занадто багато їжі, і ми підсумували харчову цінність у них. Нарешті, вартість дієти може бути виражена введеними змінними та заданими константами: 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 Після цього математичний опис проблеми дієти такий: min 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 x 1 4 x 2 3 x 3 2 x 4 8 x 5 2 x 6 2 x 1, x 2, x 3, x 4, x 5, x 6 0 Зазвичай під лінійним програмуванням ми розуміємо такі проблеми:

верхню межу немає

Звичайно, змінні x 4, x 5, x 6 можуть приймати лише невід’ємне значення, інакше вихідні нерівності не будуть задоволені. Тож спробуйте збільшити x 1 так, щоб значення змінних x 4, x 5, x 6 залишалося невід’ємним; тому, звичайно, існують обмеження на х 1; (1) x 1 5 2 (2) x 1 11 4 (3) x 1 8 3 Оскільки (1) дає найсильніше обмеження, новим рішенням є: x 1 = 5/2, x 2 = 0, x 3 = 0, x 4 = 0, x 5 = 1, x 6 = 1/2, z = 25/2. З (1) отримуємо x 1, виражене як: x 1 = 5 2 3 2 x 2 1 2 x 3 1 2 x 4 (1) Підставляємо це у (2) та (3): x 5 = 11 4 (5 2 3 2 x 2 1 2 x 3 1 2 x 4) x 2 2x 3 (2) x 6 = 8 3 (5 2 3 2 x 2 1 2 x 3 1 2 x 4) 4x 2 2x 3 (3) z = 5 (5 2 3 2 x 2 1 2 x 3 1 2 x 4) + 4x 2 + 3x 3 x 1 = 5 2 3 2 x 2 1 2 x 3 1 2 x 4 (1) x 5 = 1 + 5x 2 + 2x 4 (2) x 6 = 1 2 + 1 2 x 2 1 2 x 3 + 3 2 x 4 (3) z = 25 2 7 2 x 2 + 1 2 x 3 5 2 x 4 Виклик змінних на ліворуч, x 1, x 5 та x 6, основа. Позабазові змінні приймають 0. Значення цільової функції - константа, показана тут, отже z = 25/2. Тепер не варто було б збільшувати x 2 і x 4, оскільки це зменшило б цільову функцію z. Вибираємо х 3 і бачимо, як довго його можна збільшувати. 6

Доказ. Це видно із сказаного дотепер. Визначення. Два словники еквівалентні, якщо всі (довільні дійсні) розв’язки описуваної ними системи рівнянь та відповідні їм цільові функції однакові. Твердження 2 Перетворення словника, використаного у прикладі, веде до словника, еквівалентного попередньому. Доказ. Це очевидно, оскільки застосовані алгебраїчні маніпуляції (перестановка рівняння, множення його на ненульове число або підстановка змінних) не змінюють рішень системи рівнянь. Примітка: Існує тісний взаємозв'язок між можливими рішеннями стандартної задачі LP та невід'ємними рішеннями словників, утворених з неї, оскільки неотрицательная природа штучних змінних означає виконання нерівностей оригінальної LP. Якщо x 1. x n - можливе рішення LP, то x 1. x n доповнюється різницею між лівою та правою сторонами як x n + 1. Зі значеннями змінних x n + m словник дає негативне рішення. І навпаки, опускання штучних змінних із невід’ємного рішення у словнику дає можливе рішення для оригінального LP. 9

Лекція 2 У нашому прикладі ми побачили, що симплексний алгоритм в основному можна розділити на такі основні етапи: 1. Ініціалізація (початкова точка) 2. Ітерація (наближення) 3. Припинення (закінчення) Наразі ми навмисно ігнорували труднощі та розгалуження можливості алгоритму. Проблема ініціалізації буде обговорюватися в наступному класі, але питання ітерації та припинення будуть з'ясовані зараз. 1. Ініціалізація max cjxja ij xjb (i = 1, 2. m) xj 0 (j = 1, 2. n) x n + i = bina ij xj (i = 1, 2. m) z = cjxj Якщо всі bi 0, тоді (0, 0, 0) є можливим рішенням. В іншому випадку ми не можемо розпочати ітерацію. Тож для початку нашого процесу нам знадобиться словник, який визначає можливе рішення. 2. Ітерація z = z + c j x j, j N, де z - миттєве значення цільової функції; N - набір неосновних змінних, B - набір базових змінних. 10

Припустимо, що поточна ситуація така: x 2 = 5 + 2x 3 x 4 3x 1 x 5 = 7 3x 4 4x 1 z = 5 + 3x 3 x 4 x 1 Доцільно збільшити значення x 3 так, щоб x 2 і x 5 не повинні бути від’ємними. Однак жодне з наведених двох рівнянь не дає обмеження (верхня межа) на x 3, цільова функція задачі може набувати довільно великого значення. Поки ми продовжуємо, може статися наступне: а) У словнику всі коефіцієнти, що належать до поворотної змінної, дорівнюють 0, тобто немає обмежень. Тоді рішення не обмежується. б) Коефіцієнти змінних цільової функції не є додатними. Тоді ми в оптимальному. в) Кілька змінних можуть одночасно входити в базу; отже, ми повинні вибрати один із них. г) Значення вхідних змінних не може бути збільшено, а цільова функція не збільшена. Тоді ми говоримо, що сталася дегенерація. Визначення. нуль. Приклад: Словник вироджений, якщо містить значення базової змінної xi x 4 = 1 2x 3 x 5 = 3 2x 1 + 4x 2 6x 3 x 6 = 2 + x 1 3x 2 4x 3 z = 2x 1 x 2 + 8x 3 змінна, що виходить з основи, не є чітко визначеною, оскільки всі три рівняння дають обмеження на 1/2 на значення змінної x 3. Дегенерація 11

за допомогою якого ми можемо потрапити в особливо неприємну пастку, т. зв може статися циклізація. Приклад: x 5 = 1 2 x 1 + 11 2 x 2 + 5 2 x 3 9x 4 x 6 = 1 2 x 1 + 3 2 x 2 + 1 2 x 3 x 4 x 7 = 1 x 1 z = 10x 1 57x 2 8x 3 24x 4 Рівняння 1 і 2 (що виражають x 5 і x 6) дають найсильнішу верхню межу (x 1 = 0), тож, припустимо, x 5 замінено на x 1 змінну. x 1 = 11x 2 + 5x 3 18x 4 2x 5 x 6 = 4x 2 2x 3 + 8x 4 + x 5 x 7 = 1 11x 2 5x 3 + 18x 4 + 2x 5 z = 53x 2 + 41x 3 204x 4 20x 5 Рівняння 2 (виражаючи x 6) дає найсильнішу верхню межу (в 1: немає, в 2: x 2 = 0, в 3: x 2 1/11), тому x 6 замінюється базовою - змінна x 2. x 2 = 1 2 x 3 + 2x 4 + 1 4 x 5 1 4 x 6 x 1 = 1 2 x 3 + 4x 4 + 3 4 x 5 11 4 x 6 x 7 = 1 + 1 2 x 3 4x 4 3 4 x 5 11 4 x 6 z = 29 2 x 3 98x 4 27 4 x 5 53 4 x 6 12

Рівняння 1 і 2 (що виражають x 2 і x 1) дають найсильнішу верхню межу (в 1, 2: x 3 = 0, в 3: немає), тому давайте уникати x Замінити 1 в основі змінною x 3. x 3 = 2x 1 + 8x 4 + 3 2 x 5 11 2 x 6 x 2 = x 1 2x 4 1 2 x 5 + 5 2 x 6 x 7 = 1 x 1 z = 29x 1 + 18x 4 + 15x 5 93x 6 Рівняння 2 (виражаючи x 2) дає найсильнішу верхню межу (у 2: x 4 = 0, в 1, у 3: немає), тому змінна x 4 замінюється змінною x 4. x 4 = 1 2 x 1 1 2 x 2 1 4 x 5 + 5 4 x 6 x 3 = 2x 1 4x 2 1 2 x 5 + 9 2 x 6 x 7 = 1 x 1 z = 20x19x2 + 21 2 x 5 141 2 x 6 Рівняння 1 і 2 (що виражають x 4 і x 3) дають найсильніше обмеження (в 1 і 2: x 5 = 0, в 3: немає), тож, скажімо, x 3 замінено на x 5 в основі . 13

x 5 = 4x 1 8x 2 2x 3 + 9x 6 x 4 = 1 2 x 1 3 2 x 2 + 1 2 x 3 x 6 x 7 = 1 x 1 z = 22x 1 93x 2 21x 3 + 24x 6 A 2. рівняння (виражаючи x 4) дає найсильнішу верхню межу (у 2: x 4 = 0, в 1, у 3: немає), тому x 4 замінюється x 6 в основі. x 6 = 1 2 x 1 + 3 2 x 2 + 1 2 x 3 x 4 x 5 = 1 2 x 1 + 11 2 x 2 + 5 2 x 3 9x 4 x 7 = 1 x 1 z = 10x 1 57x 2 8x 3 24x 4 Це повертає нас до словника, з якого починався наш приклад. Сталася циклізація. Теорема 1 Якщо симплексний метод не зупиняється, він циклізується. Доказ. Неважко помітити, що існує 3 можливі основи на вибір (n + m) m шляхів. Тобто, якщо процедура триватиме нескінченно довго, рано чи пізно база, яка була раніше, знову з’явиться. Ми побачимо, що основа чітко визначає відповідний словник, тому повторення основ - це також повторення словників. Припустимо, що в двох словниках основи однакові: Словник 1: (2.1) 3 Згадайте, що () n k = n!, Опустіть n під k, дайте число k! (N k)! скільки способів ми можемо вибрати k елементів із набору з n елементів. 14

xi = bia ij xj (i B) j B z = v + j B cjxj Словник 2: (2.2) xi = bij B a ij xj (i B) z = v + j B cjxj Відповідно до пропозиції 1, два словники еквівалентно, тому згідно з визначенням 4 словник (2.1) - це будь-які x 1, x 2. xn, xn + 1. Рішення x n + m, z - це також рішення словника (2.2) і навпаки. Зокрема, для будь-якої неосновної змінної xk і нехай t буде дійсним числом: xk = t, тоді xj = 0 (j B, jk) xi = bia ik t (i B), z = v + ckt Це дає рішення з (2.1), що також повинно задовольняти (2.2) виходячи з вищевикладеного, тому bia ik t = bia ikt i B і v + ckt = v + c kt 15

Оскільки t було довільним дійсним числом, це можливо, лише якщо a ik = a ik i B b i = b i v = v c k = c k k N Отже, два словники насправді однакові, і з цього випливає теорема. Методи уникнення циклізації: 1. збурення або лексикографічний метод (див. Практику) 2. Метод неважкого характеру чи інший метод найменшого покажчика Примітка: Існування циклізації насправді лише заплутано в теорії, майже ніколи не трапляється на практиці. Дегенерація - явище набагато частіше, і в деяких випадках може незручно збільшити час роботи алгоритму. Так звані метод збурення також забезпечує певний захист від цього. 16

і z = v + c s y. Оскільки цільові функції повинні збігатися, v + csy = v + c sy + i B ci (bia є y) Ми переставляємо, що (cscs + cia є) y = cibii B i B Оскільки y було довільним, це можливо лише, якщо (cscs + i B cia також) = 0 і тому, звичайно, i B cibi = 0. Оскільки змінна, що вводить xxt в основу словника xsa D, дорівнює cs> 0. З іншого боку, змінна, що вводить базу в xsa D словник і s 0. Оскільки xta є базовим елементом у D словнику, ct> 0 і, отже, cta ts> 0, тобто xt і xr - це різні змінні, а r дорівнює 0. D і D дають однакові рішення. Зокрема, значення xr не змінюється під час ітерацій, і оскільки основа в D не є xr = 0, і, отже, вона, звичайно, також прийняла нульове значення в D, br = 0. Тоді база D повинна була бути xr, а не xt. залишилося б, і це суперечить нашому припущенню. Таким чином, із застосуванням правила Бленда не відбувається циклізації, а отже, завдяки теоремі 1, метод симплексу припиняється. 18

Лекція 3 Двофазний симплексний метод Наша мета все-таки вирішити проблему LP, приведену до стандартної форми. Проблема LP Словники max n c i x i x n + i = b i n a ij x j Ax b z = n c j x j x 0 Раніше ми успішно справлялися з можливими підводними каменями ітерації та припинення. Однак можливо, що ми також не можемо розпочати ітерацію, оскільки наш початковий словник не кодує можливого рішення, тобто для деяких i b i 0, y i = 0, коли a ij x j 0). Позначимо набір індексів вільних змінних через F. Зверніть увагу, що LP має стандартну форму тоді і тільки тоді, коли E = і F =. Лінійною комбінацією умов na ij xjbi (i I) та na ij xj = bi (i E) є наступна нерівність: (m) ma ij yixjbiyi, якщо y 1, y 2. ym є дійсними та yi 0, якщо i I Лінійна комбінація - це, звичайно, сума нерівностей amyi (na ij xj) mbiyi та an (ma ij yi) xj = m (na) ij xj) yi тотожності. Крім того, якщо числа y 1, y 2. y n такі, що m a ij y i c j ha j R і a m a ij y i = c j ha j F 40