ЛР4 · Метод минимального элемента → Метод потенциалов
Постановка и решение транспортных оптимизационных задач линейного программирования. Смородинский С. С., Батин Н. В., 2010: §5.2, §5.3, §5.5.
Склады → Магазины
| Поставщик | Магазин 1j = 1 | Магазин 2j = 2 | Магазин 3j = 3 | Магазин 4j = 4 | Ai |
|---|---|---|---|---|---|
| Склад 1i = 1 | 40 | ||||
| Склад 2i = 2 | 30 | ||||
| Склад 3i = 3 | 30 | ||||
| Bj | 20 | 25 | 30 | 25 |
Слева снизу — объем поставки. Зеленая клетка входит в базис; даже если здесь 0.
i = 1 — Склад 1; j = 1 — Магазин 1. Тариф = 4.
Клетка не входит в текущий базис: ее перевозка принята равной нулю. Для нее проверяем оценку; в базис она войдет при обмене по циклу.
Базисная переменная · как в пособии
Смородинский С. С., Батин Н. В., издание 2010 года, §5.2, стр. 61.
«Переменные, принявшие ненулевые значения, называются базисными, остальные (нулевые) – небазисными».
Сразу следующее примечание уточняет:
«Иногда некоторые из базисных переменных также принимают нулевые значения (см. подраздел 5.5). Однако количество базисных переменных всегда должно быть равно M+N–1».
В §2.3.1 (стр. 17) небазисные переменные полагаются равными нулю, а остальные определяются из системы ограничений. Поэтому признак базиса в таблице — включение переменной в выбранный базис, а не просто ненулевое число.
В этом плане отмечено 0 базисных клеток; для полного базиса требуется 3 + 4 − 1 = 6. Во время построения план еще не полный.
Потенциалы, псевдостоимость, оценка · в чем разница?
В §5.3 (стр. 62) потенциалы вводятся как платежи поставщиков и потребителей. Это вспомогательные величины для проверки оптимальности, а не новые перевозки. Один платеж задают произвольно: здесь U₁ = 0.
По известному платежу и тарифу определяем соседний: сначала только связанные базисом значения. Для небазисной клетки сумма платежей — псевдостоимость; разность с тарифом — оценка.
Отрицательная оценка указывает направление снижения затрат на единицу сдвига. Если все оценки неотрицательны — план оптимален. Нулевой сдвиг при вырожденности меняет базис без снижения затрат.
Как называются работа и методы?
Лабораторная работа №4: «Постановка и решение транспортных оптимизационных задач линейного программирования» — точное название из задания, стр. 1.
Метод минимального элемента строит допустимый план. Метод потенциалов проверяет его и ищет оптимальный. В пособии 2010 года это §5.2 и §5.3; вырожденность — §5.5. В задании даны номера §4.2, §4.3 и §4.5: нумерация изданий различается.
Опорный план — допустимый план с выбранным базисом из M+N−1 независимых переменных. Оптимальный план — допустимый план с наименьшими суммарными затратами. Назначить все перевозки еще не означает доказать оптимальность.
Проверь, что запомнил
Не открывая ответ, объясни: почему ноль бывает базисным? Чем тариф отличается от перевозки? По каким клеткам вычисляют потенциалы? Что означает отрицательная оценка? Почему при θ = 0 стоимость не меняется?
Сверить объяснение
Базис выбирают по независимым ограничениям; его переменная может оказаться нулевой. Тариф задан, перевозка ищется. Потенциалы связываются по базисным клеткам. Отрицательная оценка дает направление улучшения, а θ — допустимый объем сдвига: при θ = 0 объемы и стоимость прежние.