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, если только верхняя вершина не ВЫРОЖДЕННАЯ вырожденная вершина: более двух прямых через одну точку - там производная не существует, поэтому теневая цена не определена
