Практическая работа №2 - Транспортная задача

Описание

Эта программа решает транспортные задачи - класс задач линейного программирования, связанных с оптимальным распределением грузов между поставщиками и потребителями при минимизации транспортных расходов.

Программа реализует полный цикл решения: получение начального плана тремя различными методами, выбор лучшего из них и оптимизацию методом потенциалов (MODI).

Возможности

Методы поиска начального решения:

• Северо-западный угол - простой и быстрый метод
• Минимальный элемент - выбирает клетки с наименьшими тарифами
• Фогеля - более сложный, но часто дающий лучшее начальное решение

Оптимизация:

• Метод потенциалов (MODI) - итеративное улучшение плана до оптимального
• Автоматическая балансировка - добавление фиктивных поставщиков/потребителей
• Обнаружение альтернативных оптимумов

Вывод результатов:

• «Тетрадный» формат таблиц - наглядное представление как на листе бумаги
• Пошаговые вычисления - показ всех промежуточных шагов оптимизации
• Потенциалы и оценки - отображение u_i, v_j и матрицы ΔC
• Подробная формула стоимости - разложение целевой функции

Использование

1. Откройте файл transport.py
2. Измените блок INPUT_DATA под свою задачу:

   SUPPLY = [200, 450, 250]  # объемы поставок (фабрики)
   DEMAND = [100, 125, 325, 250, 100]  # потребности (магазины)
   COSTS = [  # матрица тарифов перевозки
       [5, 8, 7, 10, 3],
       [4, 2, 2, 5, 6],
       [7, 3, 5, 9, 2],
   ]

3. Запустите программу:

   python3 transport.py

Аргументы командной строки

Программа поддерживает выбор начального плана для метода потенциалов (MODI), что влияет на количество шагов оптимизации и на промежуточные таблицы:

• --start BEST — использовать лучшее из трёх начальных решений (по умолчанию)
• --start NW — стартовать с метода северо‑западного угла
• --start MIN — стартовать с метода минимального элемента
• --start VOGEL — стартовать с метода Фогеля

Примеры запуска:

# Лучший из трёх (по умолчанию)
python3 transport.py

# Явно задать старт NW, чтобы совпасть со стилем конспекта с большим числом шагов
python3 transport.py --start NW

# Старт с минимального элемента
python3 transport.py --start MIN

Также можно зафиксировать старт через константу в начале transport.py:

POTENTIALS_START = 'BEST'  # или 'NW' | 'MIN' | 'VOGEL'

Формат пошагового вывода MODI

• Под каждой таблицей выводятся равенства базисных клеток вида u₁ + V₁ = 5.
• Затем печатаются матрицы:
  • Cₖ = u ⊕ V — сумма потенциалов по всем клеткам;
  • ΔCₖ = C − (u ⊕ V) — приведённые затраты.
• Нумерация шагов: k = 1, 2, ….

Формат задачи

Программа решает задачу вида:

min F = Σᵢⱼ cᵢⱼ × xᵢⱼ

при ограничениях:
Σⱼ xᵢⱼ = aᵢ  (поставки от i-го поставщика)
Σᵢ xᵢⱼ = bⱼ  (потребности j-го потребителя)
xᵢⱼ ≥ 0     (неотрицательность перевозок)

где:

• aᵢ - объем поставки i-го поставщика
• bⱼ - потребность j-го потребителя
• cᵢⱼ - стоимость перевозки единицы груза от i к j
• xᵢⱼ - количество груза для перевозки от i к j

Пример задачи

Условие: 3 фабрики производят кондитерские изделия, 5 магазинов нуждаются в продукции. Найти план перевозок с минимальными транспортными расходами.

Данные:

• Производство: a₁=200, a₂=450, a₃=250
• Потребности: b₁=100, b₂=125, b₃=325, b₄=250, b₅=100
• Тарифы указаны в матрице C

Пример вывода

Программа выводит:

1. Проверку сбалансированности задачи
2. Начальные планы всеми тремя методами с расчетом стоимости
3. Выбор лучшего начального плана
4. Пошаговую оптимизацию методом потенциалов:
   • Таблицы с потенциалами u_i, v_j
   • Матрицы приведенных затрат ΔC
   • Циклы пересчета при улучшении плана
5. Итоговый оптимальный план и минимальную стоимость
6. Альтернативные оптимумы (если есть)

Особенности реализации

• Автоматическая балансировка: если сумма поставок ≠ сумме потребностей, добавляется фиктивный поставщик/потребитель с нулевыми тарифами
• Обеспечение базисности: автоматическое добавление нулевых базисных клеток для получения остовного дерева
• Точность вычислений: работа с целыми числами для избежания ошибок округления
• Универсальность: код работает для любых размеров m×n

Требования

• Python 3.6+
• Стандартная библиотека (dataclasses, typing, itertools, collections)

Методическое назначение

Программа предназначена для изучения транспортных задач и демонстрации различных подходов к их решению. Подробный вывод всех промежуточных вычислений делает процесс решения наглядным и понятным для образовательных целей.