Условие
Два поставщика имеют запасы 10 и 20. Три потребителя требуют 7,11,12. Матрица тарифов C=((8,5,4),(6,7,3)). Минимизируйте Σcᵢⱼxᵢⱼ при заданных суммах строк и столбцов, xᵢⱼ≥0. Сравните методы северо-западного угла и минимального элемента; найдите двойственную задачу и оптимум.
Решение источника
Источник отмечает линейную зависимость уравнений и четыре базисные переменные из шести. Таблицы начальных и оптимального планов в нём не заполнены.
Редакционное объяснение
Баланс выполнен: 10+20=7+11+12=30. Сумма двух уравнений поставщиков равна сумме трёх уравнений потребителей. Ранг системы равен 2+3−1=4, поэтому в базисе четыре переменные, небазисных две. Для симплекс-формы можно удалить одно из пяти равенств; оно выполнится автоматически.
Уравнение x₁₁ x₁₂ x₁₃ x₂₁ x₂₂ x₂₃ Правая часть
Поставщик 1 1 1 1 0 0 0 10
Поставщик 2 0 0 0 1 1 1 20
Потребитель 1 1 0 0 1 0 0 7
Потребитель 2 0 1 0 0 1 0 11
Потребитель 3 0 0 1 0 0 1 12 Северо-западный угол даёт X=((7,3,0),(0,8,12)). Стоимость 8·7+5·3+7·8+3·12=163. Метод минимального элемента сначала заполняет клетку (2,3) объёмом 12, затем (1,2) объёмом 10. Остатки дают x₂₁=7, x₂₂=1. План X*=((0,10,0),(7,1,12)) стоит 135.
Двойственная задача: max(10u₁+20u₂+7v₁+11v₂+12v₃) при uᵢ+vⱼ≤cᵢⱼ. Потенциалы свободны по знаку, поскольку исходные ограничения — равенства. Условия дополняющей нежёсткости: xᵢⱼ(cᵢⱼ−uᵢ−vⱼ)=0 для каждой клетки.
Возьмём u=(0,2), v=(4,5,1). На четырёх положительных клетках X* суммы потенциалов равны тарифам. На пустых клетках (1,1),(1,3) зазоры равны 4 и 3. Двойственная цель равна 40+28+55+12=135 и совпадает с прямой. План глобально оптимален. Положительные зазоры требуют x₁₁=x₁₃=0 в любом оптимуме, а балансы после этого однозначно восстанавливают X*.
Проверка
Суммы строк равны 10,20, столбцов — 7,11,12. Все двойственные неравенства проверены точно, прямая и двойственная стоимости совпадают. Это независимый сертификат, не зависящий от выбора алгоритма начального плана.
Что не следует из ответа
Метод минимального элемента вообще не гарантирует оптимальность: здесь её доказывают потенциалы. Четыре базисных переменные не обязаны все быть положительными в вырожденной задаче; в данном плане они положительны. Пять уравнений нельзя считать независимыми.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 1832 · CC0 1.0. Адаптация damirock.com: заполнены начальные планы и двойственная задача, добавлены точный сертификат и доказательство единственности.