Math
Симплекс на площині
Допустима область лежить на столі, а над нею висить плита на висоті цілі. Ціль лінійна, тож плита рівна й похила, і найкраща точка — буквально її найвищий кут.
Що відбувається
Дві змінні та кілька обмежень: кожне — стінка на столі, а те, що лишилося всередині, і є допустима область. Над нею висить плита, висота якої в кожній точці дорівнює цілі p·x + q·y. Ціль лінійна, отже плита — рівна похила площина, пагорба посередині в неї немає, і найкраща точка це її найвищий кут. Звідси все: відповідь завжди у вершині, і 60 000 проб усередині області не перевершили її жодного разу. Симплекс іде цими сходами: від початку координат до сусіднього кута, що стоїть вище, по кроку за раз, і спиняється там, де вищих сусідів немає. Його відповідь звірено з перебором усіх вершин, який про таблицю не знає нічого. Відсунь стінку на одиницю — і оптимум зросте рівно на її тіньову ціну; але якщо у верхньому куті сходяться три стінки, жодної єдиної швидкості зростання там уже немає.
Рівняння модуля
Рівняння максимізувати p·x + q·y за умови a·x + b·y ≤ c для кожного рядка, а також x ≥ 0, y ≥ 0 допустима область є перетином півплощин; цільова функція лінійна, тому її графік над областю є плоскою похилою площиною отже, максимум досягається у ВЕРШИНІ - точці, де перетинаються дві з прямих (осі враховуються) і всі обмеження ще виконуються симплекс: почати з початку координат (кожне c ≥ 0, тож він допустимий), переходити до сусідньої вершини, що збільшує цільову функцію, зупинитися, коли такої немає правило Бленда - входить змінна з найменшим допустимим індексом, виходить із найменшим базисним індексом серед рівних відношень - робить циклування неможливим тіньова ціна рядка є двоїстою змінною: збільште його c на h, і оптимум зросте на h·y, якщо тільки верхня вершина не ВИРОДЖЕНА вироджена вершина: більше двох прямих через одну точку - там похідна не існує, тому тіньова ціна не визначена
