Дидактические цели
А что делать, когда переменных так много, что задачу уже не нарисовать? Эта лаборатория продолжает Линейную оптимизацию: там оптимум находили по чертежу допустимой области, а здесь строится машина, которая находит его вслепую — симплекс-метод, — а затем задача переворачивается наизнанку, и мы приходим к теневым ценам и двойственной задаче. Одна и та же мастерская со столами и стульями проходит через первые 23 зала и всегда даёт 36 €; последний зал применяет всё к полной задаче с тремя продуктами, как на экзамене. Рассчитано на университетский уровень.
Чему учит
- Вспомнить, что такое задача линейной оптимизации, что такое допустимая область и почему оптимум всегда в вершине (зал 1).
- Переворачивать задачу так, чтобы она подошла методу: минимум как максимум, ≥ как ≤ (залы 2 и 5).
- Приводить задачу к стандартной форме с переменными запаса и избытка, отличать базисные переменные от небазисных (залы 3, 4 и 6).
- Понять, почему перебор всех вершин безнадёжен: их число растёт экспоненциально (зал 7).
- Строить симплекс-таблицу по условию и читать её: что стоит в каждой строке, в каждом столбце и в строке Z (зал 8).
- Выбирать входящий столбец и выходящую строку и видеть, что это значит на чертеже: переход из вершины в соседнюю (залы 9 и 10).
- Применять метод Гаусса-Жордана к таблице: сначала наблюдая каждое вычисление, затем выполняя его целиком, строка за строкой (залы 11 и 13), заранее решив, кто входит и кто выходит (зал 12).
- Увидеть симплекс-метод таким, какой он есть — прогулкой по вершинам без отступлений — и убедиться, что на трёхмерном многограннике он работает точно так же (залы 14 и 15).
- Решить полную задачу от начала до конца самостоятельно (зал 16).
- Толковать теневые цены: сколько стоит ещё одна единица ресурса и до какого предела (зал 17).
- Построить двойственную задачу, понять её экономический смысл и убедиться, что её решение уже было в итоговой симплекс-таблице (залы 18–23).
- Отвечать на вопросы анализа полной задачи по итоговой таблице: дополнительные переменные и исчерпанные ресурсы, теневые цены, сильная двойственность, выгодна ли покупка ресурса, почему продукт не выпускается и с какой прибыли это станет выгодно (зал 24).
Ключевые математические идеи
- Любое ограничение
≤становится равенством, если прибавить переменную запаса; любое≥— если вычесть избыток. Ни одна из них не может быть отрицательной. - В стандартной форме переменных больше, чем степеней свободы: в каждой вершине ровно столько переменных равны нулю, сколько было исходных. Это небазисные переменные, остальные образуют базис.
- Каждая итерация меняет базис: одна переменная входит (самый отрицательный коэффициент в строке Z), другая выходит (минимальное отношение). На их пересечении стоит ведущий элемент.
- Симплекс-метод не перебирает все вершины: он идёт от одной к другой, всегда улучшая, поэтому и заканчивается. Область выпукла, поэтому вершина, лучшая всех соседей, лучшая вообще — локальных максимумов, не являющихся глобальными, нет.
- Строка Z итоговой таблицы даёт не только оптимум: её коэффициенты под запасами — это теневые цены ресурсов и одновременно решение двойственной задачи.
- Двойственная задача строится механически: по переменной на каждое ограничение, по ограничению на каждую переменную, максимум меняется на минимум, а матрица коэффициентов транспонируется. Свободные члены и коэффициенты цели меняются ролями.
- Слабая двойственность: любое допустимое решение прямой задачи не превосходит любого допустимого решения двойственной. Сильная двойственность: в оптимуме они совпадают. Дополняющая нежёсткость: если ресурс в избытке, его цена 0; если цена положительна, ресурс исчерпан.
- Под небазисной переменной итоговая строка Z даёт её приведённую стоимость: стоимость по теневым ценам ресурсов на одну единицу минус то, что она приносит. Это то, на сколько упадёт Z за каждую вынужденную единицу; переменная становится выгодной, когда её коэффициент в целевой функции вырастет на эту величину. То, что переменная вошла в базис на какой-то итерации, не гарантирует, что она будет в оптимуме.
Перед началом
Полезно пройти Линейную оптимизацию или хотя бы уметь строить допустимую область и находить оптимум по чертежу: зал 1 быстро это повторяет, но не учит с нуля.
Содержание по залам
Зал 1 · Что нужно знать
Быстрое повторение того, что даёт предыдущая лаборатория, с прямой ссылкой на неё, если её нужно пройти сначала: три составляющие линейной задачи (переменные решения, целевая функция и ограничения), мастерская со столами и стульями, которая проходит через всю лабораторию, и её начерченная допустимая область с оптимумом в точке (2, 6) и Z = 36.
Задания для ученика
- Определить, какая из четырёх задач не является линейной.
- Дать определение допустимой области и сказать, какую форму она может иметь.
- Вспомнить, где всегда достигается оптимум и чему он равен в задаче о мастерской.
Зал 2 · Переворачиваем задачу
Метод, о котором пойдёт речь, умеет только максимизировать и понимает только ≤. Показаны два приёма, которые готовят к нему любую задачу: минимизировать W — то же, что максимизировать −W (оптимальная точка не сдвигается, меняется только знак значения), а ограничение ≥ превращается в ≤ умножением на −1.
Задания для ученика
- Превратить задачу на минимум в задачу на максимум и сказать, чему равен новый оптимум.
- Изменить направление неравенства и проверить, что происходит с коэффициентами.
Зал 3 · У запаса появляется имя
Зазор сверху каждого столбика ресурса — уже знакомый по предыдущей лаборатории — получает имя: переменная запаса. Столбики двигаются вместе с точкой, и каждый показывает свой запас числом: h₁, h₂ и h₃.
Задания для ученика
- Вычислить запас каждого ресурса для конкретного плана.
- Понять, что означает нулевой запас.
Зал 4 · Стандартная форма
Машина не понимает знак ≤: она умеет решать только равенства. Каждое ограничение становится равенством, если прибавить к нему собственную переменную запаса, и требуется, чтобы все переменные — в том числе запасы — были ≥ 0. Вся задача о мастерской записывается в стандартной форме.
Задания для ученика
- Записать стандартную форму конкретного ограничения.
- Сказать, сколько переменных в задаче после добавления запасов.
Зал 5 · Приведение задачи на минимум к стандартному виду
Неудобный случай: задача о диете с ограничениями ≥. Зазор нельзя прибавить — он оказался бы не с той стороны, — поэтому вычитается переменная избытка; а поскольку после вычитания начало координат перестаёт годиться как отправная точка, появляются искусственные переменные.
Задания для ученика
- Превратить ограничение ≥ в равенство с переменной избытка.
- Объяснить, зачем нужна искусственная переменная и какую роль она играет.
Зал 6 · Пять шкал, две руки
В мастерской 5 переменных (x, y, h₁, h₂, h₃), но только 2 степени свободы: как только заданы x и y, три запаса определены. При перетаскивании точки видно, как все пять шкал меняются одновременно, и в каждой вершине ровно две переменные равны 0 — небазисные, — а три остальные образуют базис.
Задания для ученика
- Перетаскивать точку и наблюдать, как одновременно меняются пять значений.
- Сосчитать, сколько переменных равны 0 в вершине, и сказать, какие из них образуют базис.
Зал 7 · А если перебрать все?
Очевидная идея — проверить все углы — опровергается одним ползунком: число базисных решений равно биномиальному коэффициенту C(n+m, m) и с ростом задачи увеличивается от 10 до более чем ста квадриллионов, а рядом показано время вычисления. После этого появляются Данциг и симплекс-метод с идеей переходить от вершины к вершине.
Задания для ученика
- Вычислить, сколько вершин нужно проверить при n = 4 и m = 3.
- Оценить по порядку величины случай n = m = 25.
- Объяснить, почему достаточно остановиться, когда ни один сосед не даёт улучшения.
Зал 8 · Симплекс-таблица
Условие задачи о мастерской, формализованное со всеми коэффициентами на виду, и рядом его таблица: по строке на каждое ограничение, по столбцу на каждую переменную, внизу строка Z с коэффициентами целевой функции, взятыми с противоположным знаком, а справа столбец свободных членов. Коэффициенты основных переменных выделены синим и в условии, и в таблице, чтобы было видно, что это одни и те же числа; запасы образуют единичную матрицу.
Задания для ученика
- Сказать, что означает последний столбец таблицы.
- Прочитать значение Z в начальной таблице.
- Полностью составить таблицу новой задачи — все 15 клеток.
Зал 9 · Кто входит?
Строка Z показывает, на сколько растёт прибыль от каждой единицы каждой переменной, поэтому входит столбец с самым отрицательным коэффициентом. Объясняется также, что значит, что одна переменная входит в базис, а другая выходит из него. Две кнопки за две секунды проводят точку от начала координат до соседней вершины, а за ней следуют линия уровня и растущий столбик прибыли.
Задания для ученика
- Выбрать входящий столбец в начальной таблице мастерской.
- Вычислить, на сколько растёт Z от каждой единицы y.
- Вычислить, на сколько вырастет прибыль при переходе в вершину (0, 6).
Зал 10 · Как далеко можно пройти?
Тест минимального отношения, с двумя отношениями, выделенными цветом — оранжевым выходящая строка, синим другая, — и в тексте, и прямо в клетках таблицы. Столбики запасов заполняются по мере движения точки, и тот, что доходит до предела, показывает, что его запас равен 0. На пересечении выходящей строки и входящего столбца стоит ведущий элемент, обведённый кольцом.
Задания для ученика
- Определить, какая переменная выйдет, если войдёт столбец x.
- Объяснить, что произошло бы, если бы взяли большее отношение вместо меньшего.
Зал 11 · Метод Гаусса
Три шага метода Гаусса-Жордана сначала объясняются анимацией на небольшом примере, не связанном с мастерской: каждый шаг ждёт четыре секунды, чтобы его успели прочитать, а затем выписывает по строке на каждую клетку с полным вычислением, одновременно заполняя таблицу. После нажатия «Понятно» объяснение исчезает, и ученик с подсказками выполняет первую итерацию для мастерской: указать ведущий элемент, разделить его строку и исключить остальные, по одной за шаг.
Задания для ученика
- Просмотреть весь метод, вычисление за вычислением, и нажать «Понятно».
- Указать ведущий элемент, щёлкнув по таблице.
- Разделить ведущую строку и пересчитать каждую из остальных строк.
Зал 12 · Вторая итерация: кто входит и кто выходит?
Здесь уже ничего не дано в готовом виде: перед учеником преобразованная таблица, и вторую итерацию он определяет сам, применяя оба правила. В конце точка за две секунды перескакивает из (0, 6) в (2, 6), а прибыль растёт с 30 до 36.
Задания для ученика
- Выбрать входящий столбец по строке Z.
- Вычислить два конкурирующих отношения.
- Определить, какая переменная выходит из базиса.
Зал 13 · Закончите вторую итерацию
Тот же пересчёт с подсказками, что и в зале 11, теперь с ведущим элементом 3 и настоящими дробями, которые нужно записывать через косую черту, без десятичных. В конце в строке Z не остаётся отрицательных чисел: симплекс-метод останавливается, и таблица показывает x = 2, y = 6, Z = 36. Попутно обращается внимание на числа 0, 3, 1 под запасами — как на предвестие блока о теневых ценах.
Задания для ученика
- Указать ведущий элемент второй итерации.
- Разделить ведущую строку, записывая дроби.
- Пересчитать остальные строки и строку Z.
Зал 14 · Прогулка по углам
Обе итерации вместе: путь (0,0) → (0,6) → (2,6) на чертеже, рядом таблица для каждой остановки и термометр прибыли, который поднимается 0 → 30 → 36. Главная мысль: Z никогда не уменьшается, а вершин конечное число, поэтому метод обязан остановиться.
Задания для ученика
- Объяснить, почему симплекс-метод всегда завершается.
- Обосновать, почему он не может застрять в локальном максимуме, худшем, чем глобальный.
Зал 15 · С тремя переменными
Тот же метод на многограннике с тремя переменными, который можно вращать мышью; оси x, y, z нарисованы стрелками из вершины (0,0,0), а симплекс-таблица всё время рядом. Полный путь — по двум рёбрам — анимируется автоматически, и термометр Z поднимается по мере движения точки.
Задания для ученика
- Посмотреть полный путь по многограннику и повернуть фигуру.
- Сказать, что произошло бы с Z при переходе из оптимума в непосещённую соседнюю вершину.
- Определить, какие переменные вышли из базиса, а какие вошли.
Зал 16 · Симплекс от начала до конца
Последняя остановка метода: фабрика с max Z = 45x + 60y при ограничениях 4x + 6y ≤ 150 и 8x + 3y ≤ 144, выбранная нарочно так, чтобы оптимум был нецелым и подбор не помогал. Ученик решает, какой столбец входит и какая строка выходит, в обеих нужных итерациях.
Задания для ученика
- Выбрать входящий столбец и выходящую строку на первой итерации.
- Повторить на второй и прочитать оптимум в итоговой таблице.
Зал 17 · Сколько стоит лишний час?
Три ползунка по одной увеличивают ёмкости мастерской, а график для каждого ресурса показывает, как откликается прибыль: наклон этой линии и есть теневая цена. Рядом итоговая симплекс-таблица, пересчитываемая вживую, со строкой Z под запасами, выделенной красным, — именно там теневые цены и были с самого начала.
Задания для ученика
- Вычислить Z, если время на обивку увеличится с 6 до 7 часов.
- Сравнить теневые цены трёх ресурсов и объяснить, почему одна из них равна 0.
- Найти три теневые цены в итоговой таблице.
Зал 18 · Рецепт целевой функции
Каждое ограничение указывает своё направление — (1,0), (0,1) и (3,2), — и целевая функция тоже: (3,5). Двойственная задача спрашивает, сколько каждого направления нужно взять, чтобы в сумме получить вектор цели: три ползунка двигают три стрелки, соединённые «конец к началу», пока сумма не совпадёт с этим вектором.
Задания для ученика
- Двигать три стрелки, пока они в сумме не дадут вектор цели.
- Вычислить y₂ и y₃ при y₁ = 0.
- Истолковать, что значит, что множитель оказался равен 0.
Зал 19 · Двойственная задача в деньгах
Экономический смысл двойственности: прямая задача — это мастерская, которая производит, а двойственная — покупатель, который хочет купить у неё ресурсы по самой низкой цене, на которую мастерская согласится. Отсюда ограничения ≥: никто не продаёт дешевле, чем заработал бы, производя сам. Обе задачи показаны рядом, ёмкости синим, прибыли красным, а под ними две матрицы коэффициентов: матрица двойственной задачи — это транспонированная матрица прямой.
Задания для ученика
- Истолковать в деньгах, что означает y₂ = 3.
- Определить, чья это задача — двойственная к задаче магазина, который закупает ветчину у трёх поставщиков.
- Решить, выгодно ли продать единицу обивки за 2 €.
Зал 20 · Двойственная задача
Механические правила построения двойственной задачи; прямая и двойственная записаны рядом, все коэффициенты на виду, включая 1 и 0. При наведении мыши на число загорается его точная пара в другой задаче: свободный член 4 — с 4 в целевой функции двойственной, 1 из 1x — с 1 из 1y₁, а метка ограничения — со всем столбцом его двойственной переменной.
Задания для ученика
- Сказать, чему соответствуют переменные прямой задачи.
- Прочитать конкретный коэффициент целевой функции двойственной задачи.
- Выбрать из четырёх вариантов двойственную к новой задаче.
Зал 21 · Постройте двойственную сами
Большое задание блока: поэтапно построить двойственную к задаче не о мастерской — кондитерской с тремя ограничениями и двумя переменными, чтобы два подсчёта не совпадали. Двойственная задача сама выписывается в рамке справа по мере того, как верно решается каждый этап, пока не будет записана целиком.
Задания для ученика
- Сказать, как будет выглядеть двойственная задача, ещё ничего не вычисляя.
- Сосчитать, сколько в ней будет переменных и сколько ограничений.
- Записать коэффициенты целевой функции и обоих ограничений.
Зал 22 · Свободные переменные и знаки
Что делать, если переменная может быть отрицательной: приём x = x^+ − x^−, где обе части ≥ 0. И таблица соответствия знаков между двумя задачами — ограничение ≤ ↔ переменная ≥ 0, ограничение = ↔ свободная переменная, и наоборот, — с объяснением сути: то, что ограничивает только с одной стороны, даёт цену, которая не может быть отрицательной.
Задания для ученика
- Сказать, во что превращается равенство прямой задачи в двойственной.
- Выбрать правильный знак в приёме со свободной переменной.
- Разложить отрицательное значение на x^+ и x^−.
Зал 23 · Двое встречаются
Завершение лаборатории: слабая двойственность, сильная двойственность и дополняющая нежёсткость, каждая объяснена отдельно, с рыночным прочтением (теневая цена — это цена, при которой мастерской всё равно, продавать или производить). Анимированный график показывает, как двойственная оценка опускается, а прямой план поднимается, пока разрыв не закроется на 36; столбики запасов следуют за планом по мере его продвижения.
Задания для ученика
- Посмотреть, как закрывается разрыв между двумя оценками.
- Сказать, начиная с какой цены выгодно продать единицу обивки.
- Объяснить, что означает, что разница между двумя оценками стала равна 0.
- Вывести, чему равна теневая цена ресурса, который остаётся в избытке.
Зал 24 · О чём говорит итоговая таблица
Пункты, которые в экзаменационной задаче идут после «решите симплекс-методом», на полной задаче с тремя продуктами и тремя ресурсами (фабрика игрушек: max 4x₁ + 5x₂ + 9x₃). Сначала проходятся три итерации; x₃ входит на первой и снова выходит на третьей. Итоговая таблица всё время перед глазами: по ней читаются дополнительные переменные (какие ресурсы исчерпаны и сколько часов остаётся, с проверкой по ограничениям), теневые цены, сильная двойственность (W = Z = 72) и выгодность покупки отдельных часов по заданной цене. Последний блок объясняет, почему самый прибыльный продукт не выпускается: число в строке Z под x₃ — его приведённая стоимость, то есть стоимость потребляемых ресурсов по теневым ценам минус прибыль, и из неё следует порог прибыли, выше которого выпуск выгоден. Ползунок c₃ проверяет это, заново решая задачу. В конце — сводка, как отвечать на каждый пункт.
Задания для ученика
- Найти значения дополнительных переменных в итоговой таблице и проверить их подстановкой оптимального плана в ограничение.
- Найти теневые цены и проверить сильную двойственность, вычислив двойственную целевую функцию.
- Решить, какие покупки отдельных часов увеличивают прибыль, сравнивая цену с теневой.
- Объяснить, почему переменная, вошедшая в базис, может отсутствовать в оптимуме.
- По приведённой стоимости найти прибыль при одной вынужденной единице и порог, выше которого выпуск выгоден.
Залы для показа
Самые наглядные для показа и обсуждения в классе.