Оптимизация логистики и выбор размещения склада: Решение транспортной задачи линейного программирования методом потенциалов и верификация в Excel Solver

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

Перед нами стоит задача выбора наиболее выгодного места для нового склада: либо в точке C, либо в точке D. Каждый из этих вариантов предполагает свою уникальную конфигурацию транспортных затрат для доставки товаров от существующих поставщиков к потребителям. Мы будем рассматривать эту дилемму как классическую транспортную задачу линейного программирования.

Цель данной работы — определить оптимальную структуру поставок и минимальные общие транспортные расходы для каждого из двух предлагаемых вариантов размещения склада (C и D), а затем на основе полученных результатов сделать экономически обоснованный выбор. В процессе решения мы используем классический Метод потенциалов для ручного расчета и верифицируем его результаты с помощью надстройки «Поиск решения» (Solver) в Microsoft Excel, а также проведем анализ чувствительности, что позволит оценить устойчивость принятого решения.

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

Теоретические основы экономико-математического моделирования

Сущность транспортной задачи и линейного программирования

Транспортная задача, известная также как задача Монжа—Канторовича, представляет собой фундаментальный класс оптимизационных проблем в области линейного программирования (ЛП). Её цель — найти такой план перевозок однородного груза от нескольких пунктов отправления (поставщиков) к нескольким пунктам потребления (потребителям), при котором общие транспортные расходы будут минимальными. Эта задача является краеугольным камнем логистики и теории цепей поставок, что определяет её незаменимость в стратегическом планировании.

Исторические корни задачи уходят в XVIII век, когда Гаспар Монж в 1781 году сформулировал её в контексте теории меры для непрерывного случая. Однако в привычном нам дискретном виде, пригодном для методов линейного программирования, она была разработана советским математиком Леонидом В. Канторовичем в 1939 году. За свой вклад в теорию оптимального распределения ресурсов, включая работы по транспортной задаче, Канторович в 1975 году был удостоен Нобелевской премии по экономике. Это подчеркивает не только математическую, но и огромную экономическую значимость данной модели, демонстрируя её прямое влияние на эффективность распределения ресурсов в масштабах экономики.

Что отличает транспортную задачу от общего случая линейного программирования? Её специфическая структура матрицы ограничений позволяет использовать более эффективные алгоритмы, чем универсальный симплекс-метод. Например, Метод потенциалов (Модифицированный распределительный алгоритм), который мы будем использовать, является специализированной версией симплекс-метода. Он ускоряет процесс решения, поскольку не требует формирования полной симплекс-таблицы и оперирует непосредственно с таблицей перевозок, что значительно сокращает вычислительную сложность итераций, особенно для задач большого размера. Это достигается за счет использования свойства унимодулярности матрицы ограничений транспортной задачи, которое гарантирует целочисленность оптимального решения при целочисленных исходных данных, что является ключевым для практического применения, где дробные объемы перевозок часто нелогичны.

Формализация математической модели

Математическая модель транспортной задачи формулируется как задача линейного программирования со следующими компонентами:

1. Целевая функция (минимизация общих затрат):
Нам необходимо минимизировать суммарные транспортные расходы, которые рассчитываются как сумма произведений объемов перевозок на соответствующие тарифы.

Z = Σi=1m Σj=1n cij xij → min

Где:

  • cij — стоимость перевозки единицы груза из пункта отправления i в пункт потребления j.
  • xij — искомый объем перевозки груза из пункта i в пункт j.
  • m — количество пунктов отправления (поставщиков).
  • n — количество пунктов потребления (потребителей).

2. Ограничения по запасам (поставщики):
Сумма всех перевозок, исходящих из каждого пункта отправления, должна быть равна (или не превышать) его доступному запасу. В сбалансированной задаче мы используем равенство, так как весь груз должен быть перевезен, что обеспечивает полную загрузку мощностей.

Σj=1n xij = ai, i = 1, 2, ..., m

Где:

  • ai — объем запаса i-го поставщика.

3. Ограничения по потребностям (потребители):
Сумма всех перевозок, поступающих в каждый пункт потребления, должна удовлетворять его потребности, что гарантирует своевременное снабжение.

Σi=1m xij = bj, j = 1, 2, ..., n

Где:

  • bj — объем потребности j-го потребителя.

4. Ограничения на переменные (неотрицательность):
Объемы перевозок не могут быть отрицательными, так как груз не может быть перевезен в обратном направлении или в отрицательном количестве, что является фундаментальным логическим ограничением.

xij ≥ 0

Условие сбалансированности (закрытая задача): Транспортная задача считается сбалансированной (или закрытой), если суммарный запас всех поставщиков равен суммарной потребности всех потребителей:

Σi=1m ai = Σj=1n bj

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

  • Если суммарный запас превышает суммарную потребность (Σ ai > Σ bj), вводится фиктивный потребитель, потребность которого равна этой разнице. Тарифы перевозки к фиктивному потребителю принимаются равными нулю (cij = 0), так как по сути этот излишек груза остается на складах поставщиков, не неся дополнительных транспортных расходов.
  • Если суммарная потребность превышает суммарный запас (Σ ai < Σ bj), вводится фиктивный поставщик, запас которого равен недостающей разнице. Тарифы перевозки от фиктивного поставщика также равны нулю (cij = 0), что означает неудовлетворение части потребностей и позволяет учесть «штраф» за нехватку без прямого увеличения стоимости.

Введение фиктивного пункта позволяет трансформировать любую несбалансированную задачу в сбалансированную, что является необходимым условием для применения стандартных алгоритмов решения, таких как Метод потенциалов.

Алгоритм решения транспортной задачи методом потенциалов

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

Построение начального опорного плана

Первым шагом к решению транспортной задачи является построение начального опорного плана. Опорный план — это допустимое решение, которое удовлетворяет всем ограничениям задачи. Важным условием является наличие m + n - 1 заполненных (базисных) клеток, где m — количество поставщиков, а n — количество потребителей. Если это условие не выполняется, план является вырожденным, что требует дополнительных действий.

Существует несколько методов построения начального опорного плана:

  1. Метод северо-западного угла: Простейший, но не всегда самый эффективный, так как не учитывает тарифы. Распределение начинается с левого верхнего угла таблицы (ячейка (1,1)) и последовательно заполняется до тех пор, пока не исчерпается запас поставщика или потребность потребителя.
  2. Метод минимального элемента (наименьших затрат): Более эффективен, так как стремится минимизировать затраты уже на начальном этапе. Выбирается клетка с минимальным тарифом cij, в неё помещается максимально возможный объем груза, после чего соответствующая строка или столбец (или оба) исключаются из рассмотрения. Процесс повторяется до полного распределения груза, что часто дает лучший начальный результат.
  3. Метод аппроксимации Фогеля: Наиболее сложный, но часто дающий план, близкий к оптимальному. Основан на расчете «штрафов» (разницы между двумя наименьшими тарифами в строке/столбце) и выборе строки/столбца с максимальным штрафом для заполнения клетки с минимальным тарифом.

Проблема вырожденности: Иногда при построении начального опорного плана количество заполненных клеток оказывается меньше, чем m + n - 1. Такая ситуация называется вырожденностью. Вырожденность возникает, когда при распределении груза запас в строке и потребность в столбце исчерпываются одновременно, что затрудняет дальнейшие вычисления потенциалов.

Устранение вырожденности: Чтобы преодолеть вырожденность, в базис вводят фиктивную (базисную) перевозку xij = 0 (или бесконечно малое положительное число ε). Эта нулевая перевозка помещается в одну из свободных клеток так, чтобы общее число базисных клеток стало равным m + n - 1, и при этом не образовывался замкнутый цикл из базисных клеток. Важно выбрать такую клетку, чтобы она не формировала замкнутый контур с уже существующими базисными клетками, иначе нарушится структура базиса.

Проверка на оптимальность и улучшение плана

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

1. Определение потенциалов:
Для всех базисных (заполненных) клеток xij > 0 должна выполняться связь между тарифами cij и потенциалами ui (для строк-поставщиков) и vj (для столбцов-потребителей):

cij = ui + vj

Эта система уравнений имеет m + n - 1 неизвестных потенциалов и m + n - 1 уравнений. Для её решения обычно один из потенциалов (например, u1) принимается за ноль, а остальные рассчитываются последовательно, что позволяет однозначно определить все значения.

2. Вычисление оценок для свободных клеток:
Для всех свободных (незаполненных) клеток, то есть тех, где xij = 0, вычисляются оценки (разности) ΔCij по формуле:

ΔCij = cij - (ui + vj)

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

3. Условие оптимальности:
План является оптимальным для задачи минимизации, если все оценки свободных клеток ΔCij ≥ 0. Если это условие выполняется, то найденный план является наилучшим, и дальнейшие улучшения невозможны, что означает достижение минимальных затрат.

4. Улучшение плана (Перераспределение):
Если среди оценок свободных клеток есть отрицательные значения, это означает, что текущий план неоптимален и его можно улучшить. Необходимо найти маршрут, который принесет наибольшую экономию.

  • Выбирается свободная клетка с наибольшим отрицательным значением ΔCij. Это указывает на наиболее «выгодный» для перераспределения маршрут.
  • Для выбранной клетки строится замкнутый цикл пересчета. Этот цикл представляет собой ломаную линию, углы которой находятся только в базисных клетках (или в самой выбранной свободной клетке). Цикл начинается и заканчивается в выбранной свободной клетке, а все промежуточные вершины являются базисными клетками.
  • В вершины цикла поочередно ставятся знаки «+» и «-» (начиная с «+» в выбранной свободной клетке). Знак «+» означает увеличение перевозки, «-» — уменьшение.
  • Объем пересчета θ равен минимальному значению в клетках цикла со знаком «-«. Это гарантирует, что ни одна перевозка не станет отрицательной, и при этом одна из базисных клеток со знаком «-» обнулится, выходя из базиса, а выбранная свободная клетка войдет в базис.
  • Этот объем θ добавляется к клеткам со знаком «+» и вычитается из клеток со знаком «-«.
  • После перераспределения формируется новый опорный план, и процесс возвращается к Этапу 2 для проверки на оптимальность.

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

Расчет и сравнение вариантов размещения склада

Для решения нашей логистической задачи мы последовательно рассмотрим два варианта размещения нового склада: C и D. Для каждого варианта мы применим Метод потенциалов, подставив значение переменной V = 22 в исходные тарифы. Это позволит нам получить конкретные числовые результаты для сравнения.

Вариант 1: Размещение склада C

Предположим, у нас есть три поставщика (П1, П2, П3) с определенными запасами и три потребителя (По1, По2, По3) с определенными потребностями. В исходной матрице тарифов одна из ячеек содержит переменную V.

Исходные данные (тарифы cij и запасы/потребности) для Варианта 1 (склад C) при V=22:

Поставщик / Потребитель По1 По2 По3 Запасы ai
П1 10 15 12 100
П2 8 11 14 150
П3 7 22 9 200
Потребности bj 120 180 150 Сумма: 450

Проверим условие сбалансированности:
Сумма запасов: 100 + 150 + 200 = 450.
Сумма потребностей: 120 + 180 + 150 = 450.
Задача является сбалансированной (Σ ai = Σ bj), поэтому вводить фиктивные пункты не требуется, что упрощает дальнейший расчет.

Далее необходимо последовательно применить Метод потенциалов.

1. Построение начального опорного плана (Метод минимального элемента):

По1 По2 По3 Запасы ai
П1 100
П2 150
П3 200
Потребности bj 120 180 150 450
  • Минимальный тариф c31=7. Отправляем x31 = min(200, 120) = 120.
    П3: 200-120=80. По1: 120-120=0.
  • Следующий минимальный тариф c33=9. Отправляем x33 = min(80, 150) = 80.
    П3: 80-80=0. По3: 150-80=70.
  • П3 исчерпан. Следующий минимальный тариф c22=11. Отправляем x22 = min(150, 180) = 150.
    П2: 150-150=0. По2: 180-150=30.
  • П2 исчерпан. Следующий минимальный тариф c12=15. Отправляем x12 = min(100, 30) = 30.
    П1: 100-30=70. По2: 30-30=0.
  • По2 исчерпан. Следующий тариф c13=12. Отправляем x13 = min(70, 70) = 70.
    П1: 70-70=0. По3: 70-70=0.

Начальный опорный план:

xij По1 По2 По3 ai ui
П1 30 70 100
П2 150 150
П3 120 80 200
bj 120 180 150 450
vj

Число базисных клеток: 5. Должно быть m+n-1 = 3+3-1 = 5. План невырожденный, что подтверждает его корректность для дальнейших расчетов.

2. Расчет потенциалов ui, vj (принимаем u1 = 0):

  • c12 = u1 + v2 ⇒ 15 = 0 + v2 ⇒ v2 = 15
  • c13 = u1 + v3 ⇒ 12 = 0 + v3 ⇒ v3 = 12
  • c22 = u2 + v2 ⇒ 11 = u2 + 15 ⇒ u2 = -4
  • c33 = u3 + v3 ⇒ 9 = u3 + 12 ⇒ u3 = -3
  • c31 = u3 + v1 ⇒ 7 = -3 + v1 ⇒ v1 = 10
xij По1 По2 По3 ai ui
П1 30 70 100 0
П2 150 150 -4
П3 120 80 200 -3
bj 120 180 150 450
vj 10 15 12

3. Проверка на оптимальность (ΔCij = cij - (ui + vj)):

  • ΔC11 = c11 - (u1 + v1) = 10 - (0 + 10) = 0
  • ΔC21 = c21 - (u2 + v1) = 8 - (-4 + 10) = 8 - 6 = 2
  • ΔC23 = c23 - (u2 + v3) = 14 - (-4 + 12) = 14 - 8 = 6
  • ΔC32 = c32 - (u3 + v2) = 22 - (-3 + 15) = 22 - 12 = 10

Все оценки ΔCij ≥ 0. План оптимален. Это означает, что мы нашли наилучшее распределение для склада C с первого раза, что встречается не всегда и указывает на эффективность начального метода.

Оптимальный план перевозок для склада C:

Xij По1 По2 По3 Запасы ai
П1 0 30 70 100
П2 0 150 0 150
П3 120 0 80 200
bj 120 180 150 450

Минимальные общие затраты (Zmin, C):
Zmin, C = 30 × 15 + 70 × 12 + 150 × 11 + 120 × 7 + 80 × 9
Zmin, C = 450 + 840 + 1650 + 840 + 720 = 4500 у.е.

Вариант 2: Размещение склада D

Теперь рассмотрим вариант размещения склада D. Предположим, что при этом меняются некоторые тарифы, включая тариф, зависящий от V. Это демонстрирует, как даже незначительные изменения в исходных данных могут повлиять на общую картину.

Исходные данные (тарифы cij и запасы/потребности) для Варианта 2 (склад D) при V=22:

Поставщик / Потребитель По1 По2 По3 Запасы ai
П1 11 14 13 100
П2 9 22 15 150
П3 6 10 8 200
Потребности bj 120 180 150 Сумма: 450

Проверим условие сбалансированности:
Сумма запасов: 100 + 150 + 200 = 450.
Сумма потребностей: 120 + 180 + 150 = 450.
Задача также является сбалансированной, что позволяет применять те же алгоритмы.

1. Построение начального опорного плана (Метод минимального элемента):

По1 По2 По3 Запасы ai
П1 100
П2 150
П3 200
Потребности bj 120 180 150 450
  • Минимальный тариф c31=6. Отправляем x31 = min(200, 120) = 120.
    П3: 200-120=80. По1: 120-120=0.
  • Следующий минимальный тариф c33=8. Отправляем x33 = min(80, 150) = 80.
    П3: 80-80=0. По3: 150-80=70.
  • П3 исчерпан. Следующий минимальный тариф c13=13. Отправляем x13 = min(100, 70) = 70.
    П1: 100-70=30. По3: 70-70=0.
  • По3 исчерпан. Следующий минимальный тариф c12=14. Отправляем x12 = min(30, 180) = 30.
    П1: 30-30=0. По2: 180-30=150.
  • П1 исчерпан. Следующий тариф c22=22. Отправляем x22 = min(150, 150) = 150.
    П2: 150-150=0. По2: 150-150=0.

Начальный опорный план:

xij По1 По2 По3 ai ui
П1 30 70 100
П2 150 150
П3 120 80 200
bj 120 180 150 450
vj

Число базисных клеток: 5. Должно быть m+n-1 = 3+3-1 = 5. План невырожденный.

2. Расчет потенциалов ui, vj (принимаем u3 = 0):

  • c31 = u3 + v1 ⇒ 6 = 0 + v1 ⇒ v1 = 6
  • c33 = u3 + v3 ⇒ 8 = 0 + v3 ⇒ v3 = 8
  • c13 = u1 + v3 ⇒ 13 = u1 + 8 ⇒ u1 = 5
  • c12 = u1 + v2 ⇒ 14 = 5 + v2 ⇒ v2 = 9
  • c22 = u2 + v2 ⇒ 22 = u2 + 9 ⇒ u2 = 13
xij По1 По2 По3 ai ui
П1 30 70 100 5
П2 150 150 13
П3 120 80 200 0
bj 120 180 150 450
vj 6 9 8

3. Проверка на оптимальность (ΔCij = cij - (ui + vj)):

  • ΔC11 = c11 - (u1 + v1) = 11 - (5 + 6) = 11 - 11 = 0
  • ΔC21 = c21 - (u2 + v1) = 9 - (13 + 6) = 9 - 19 = -10
  • ΔC23 = c23 - (u2 + v3) = 15 - (13 + 8) = 15 - 21 = -6
  • ΔC32 = c32 - (u3 + v2) = 10 - (0 + 9) = 10 - 9 = 1

Имеются отрицательные оценки ΔC21 = -10 и ΔC23 = -6. План не оптимален. Выбираем ΔC21 = -10 (максимальное по модулю отрицательное значение), поскольку оно обещает наибольшее сокращение затрат.

4. Улучшение плана (Перераспределение):
Строим замкнутый цикл для клетки (2,1).

Цикл: (2,1)+ → (3,1)— → (3,3)+ → (1,3)— → (1,2)+ → (2,2)— → (2,1)

Значения в клетках со знаком «-«: x31=120, x13=70, x22=150.
Минимальное значение: θ = 70.

Прибавляем/вычитаем θ=70:

  • x21 = 0 + 70 = 70
  • x31 = 120 - 70 = 50
  • x33 = 80 + 70 = 150
  • x13 = 70 - 70 = 0 (выходит из базиса)
  • x12 = 30 + 70 = 100
  • x22 = 150 - 70 = 80

Новый опорный план (1-я итерация):

xij По1 По2 По3 ai ui
П1 100 0 100
П2 70 80 150
П3 50 150 200
bj 120 180 150 450
vj

Число базисных клеток: 5. План невырожденный.

5. Расчет потенциалов ui, vj для нового плана (принимаем u3 = 0):

  • c31 = u3 + v1 ⇒ 6 = 0 + v1 ⇒ v1 = 6
  • c33 = u3 + v3 ⇒ 8 = 0 + v3 ⇒ v3 = 8
  • c21 = u2 + v1 ⇒ 9 = u2 + 6 ⇒ u2 = 3
  • c22 = u2 + v2 ⇒ 22 = 3 + v2 ⇒ v2 = 19
  • c12 = u1 + v2 ⇒ 14 = u1 + 19 ⇒ u1 = -5
xij По1 По2 По3 ai ui
П1 100 0 100 -5
П2 70 80 150 3
П3 50 150 200 0
bj 120 180 150 450
vj 6 19 8

6. Проверка на оптимальность нового плана:

  • ΔC11 = c11 - (u1 + v1) = 11 - (-5 + 6) = 11 - 1 = 10
  • ΔC13 = c13 - (u1 + v3) = 13 - (-5 + 8) = 13 - 3 = 10
  • ΔC23 = c23 - (u2 + v3) = 15 - (3 + 8) = 15 - 11 = 4
  • ΔC32 = c32 - (u3 + v2) = 10 - (0 + 19) = 10 - 19 = -9

Есть отрицательная оценка ΔC32 = -9. План не оптимален. Выбираем клетку (3,2).

7. Улучшение плана (2-я итерация):
Строим замкнутый цикл для клетки (3,2).

Цикл: (3,2)+ → (2,2)— → (2,1)+ → (3,1)— → (3,2)

Значения в клетках со знаком «-«: x22=80, x31=50.
Минимальное значение: θ = 50.

Прибавляем/вычитаем θ=50:

  • x32 = 0 + 50 = 50
  • x22 = 80 - 50 = 30
  • x21 = 70 + 50 = 120
  • x31 = 50 - 50 = 0 (выходит из базиса)

Новый опорный план (2-я итерация):

xij По1 По2 По3 ai ui
П1 100 0 100
П2 120 30 150
П3 0 50 150 200
bj 120 180 150 450
vj

Число базисных клеток: 5. План невырожденный.

8. Расчет потенциалов ui, vj для нового плана (принимаем u3 = 0):

  • c32 = u3 + v2 ⇒ 10 = 0 + v2 ⇒ v2 = 10
  • c33 = u3 + v3 ⇒ 8 = 0 + v3 ⇒ v3 = 8
  • c12 = u1 + v2 ⇒ 14 = u1 + 10 ⇒ u1 = 4
  • c22 = u2 + v2 ⇒ 22 = u2 + 10 ⇒ u2 = 12
  • c21 = u2 + v1 ⇒ 9 = 12 + v1 ⇒ v1 = -3
xij По1 По2 По3 ai ui
П1 100 0 100 4
П2 120 30 150 12
П3 0 50 150 200 0
bj 120 180 150 450
vj -3 10 8

9. Проверка на оптимальность нового плана:

  • ΔC11 = c11 - (u1 + v1) = 11 - (4 + (-3)) = 11 - 1 = 10
  • ΔC13 = c13 - (u1 + v3) = 13 - (4 + 8) = 13 - 12 = 1
  • ΔC23 = c23 - (u2 + v3) = 15 - (12 + 8) = 15 - 20 = -5
  • ΔC31 = c31 - (u3 + v1) = 6 - (0 + (-3)) = 6 - (-3) = 9

Есть отрицательная оценка ΔC23 = -5. План не оптимален. Выбираем клетку (2,3).

10. Улучшение плана (3-я итерация):
Строим замкнутый цикл для клетки (2,3).

Цикл: (2,3)+ → (3,3)— → (3,2)+ → (2,2)— → (2,3)

Значения в клетках со знаком «-«: x33=150, x22=30.
Минимальное значение: θ = 30.

Прибавляем/вычитаем θ=30:

  • x23 = 0 + 30 = 30
  • x33 = 150 - 30 = 120
  • x32 = 50 + 30 = 80
  • x22 = 30 - 30 = 0 (выходит из базиса)

Новый опорный план (3-я итерация):

xij По1 По2 По3 ai ui
П1 100 0 100
П2 120 0 30 150
П3 0 80 120 200
bj 120 180 150 450
vj

Число базисных клеток: 5. План невырожденный.

11. Расчет потенциалов ui, vj для нового плана (принимаем u3 = 0):

  • c32 = u3 + v2 ⇒ 10 = 0 + v2 ⇒ v2 = 10
  • c33 = u3 + v3 ⇒ 8 = 0 + v3 ⇒ v3 = 8
  • c12 = u1 + v2 ⇒ 14 = u1 + 10 ⇒ u1 = 4
  • c23 = u2 + v3 ⇒ 15 = u2 + 8 ⇒ u2 = 7
  • c21 = u2 + v1 ⇒ 9 = 7 + v1 ⇒ v1 = 2
xij По1 По2 По3 ai ui
П1 100 0 100 4
П2 120 0 30 150 7
П3 0 80 120 200 0
bj 120 180 150 450
vj 2 10 8

12. Проверка на оптимальность нового плана:

  • ΔC11 = c11 - (u1 + v1) = 11 - (4 + 2) = 11 - 6 = 5
  • ΔC13 = c13 - (u1 + v3) = 13 - (4 + 8) = 13 - 12 = 1
  • ΔC22 = c22 - (u2 + v2) = 22 - (7 + 10) = 22 - 17 = 5
  • ΔC31 = c31 - (u3 + v1) = 6 - (0 + 2) = 6 - 2 = 4

Все оценки ΔCij ≥ 0. План оптимален. Многочисленные итерации показывают, насколько трудоемким может быть ручной расчет и почему автоматизированные средства так важны.

Оптимальный план перевозок для склада D:

Xij По1 По2 По3 Запасы ai
П1 0 100 0 100
П2 120 0 30 150
П3 0 80 120 200
bj 120 180 150 450

Минимальные общие затраты (Zmin, D):
Zmin, D = 100 × 14 + 120 × 9 + 30 × 15 + 80 × 10 + 120 × 8
Zmin, D = 1400 + 1080 + 450 + 800 + 960 = 4690 у.е.

Экономическое обоснование выбора

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

Вариант размещения склада Минимальные общие транспортные расходы (Zmin)
Склад C 4500 у.е.
Склад D 4690 у.е.

Обоснование выбора:
Исходя из представленных данных, менеджеру торгового дома следует выбрать вариант размещения склада C. Экономическая целесообразность этого выбора очевидна: при прочих равных условиях, размещение склада C обеспечивает минимальные общие транспортные расходы в размере 4500 у.е., что на 190 у.е. (4690 - 4500) меньше, чем при размещении склада D. Это прямое сокращение операционных издержек, которое положительно скажется на рентабельности и конкурентоспособности компании. Выбор склада C не только снижает текущие затраты, но и повышает общую финансовую устойчивость предприятия в долгосрочной перспективе, высвобождая ресурсы для дальнейшего развития.

Таким образом, математическое моделирование и последующий анализ показывают, что выбор склада C является более выгодным с точки зрения минимизации логистических затрат.

Верификация и анализ чувствительности в Microsoft Excel Solver

Для подтверждения корректности ручных расчетов и проведения углубленного анализа чувствительности мы используем надстройку «Поиск решения» (Solver) в Microsoft Excel. Этот инструмент является мощным средством для решения задач линейного программирования и позволяет быстро получать оптимальные решения и отчеты по их устойчивости, что значительно повышает надежность принятых решений.

Настройка модели в Excel Solver

Процесс настройки модели в Excel Solver включает несколько ключевых шагов:

  1. Структура таблицы: Создаются две матрицы одинакового размера m × n.
    • Матрица тарифов (расходов) Cij: Содержит исходные данные по стоимости перевозки единицы груза для каждого маршрута.
    • Матрица переменных Xij: Это пустые ячейки, которые будут заполнены Solver’ом искомыми объемами перевозок.
    • Добавляются столбцы для сумм по строкам (запасов) и строки для сумм по столбцам (потребностей), а также ячейки для исходных запасов ai и потребностей bj.
  2. Целевая функция (Ячейка цели):
    В отдельной ячейке рассчитывается общая стоимость перевозок. Для этого используется функция СУММПРОИЗВ() (SUMPRODUCT), которая умножает соответствующие элементы матрицы тарифов Cij на элементы матрицы переменных Xij и суммирует результаты. Эта ячейка указывается как «Целевая функция», которую необходимо минимизировать.

    • Например, если матрица тарифов находится в диапазоне A1:C3, а матрица переменных в E1:G3, то целевая функция будет выглядеть как =СУММПРОИЗВ(A1:C3;E1:G3).
  3. Изменяемые ячейки (Переменные):
    В Solver’е указывается диапазон ячеек, соответствующий матрице перевозок Xij (например, E1:G3). Это те переменные, значения которых Solver будет подбирать для достижения оптимального решения.
  4. Настройка ограничений:
    • Ограничения по запасам (строки): Для каждой строки матрицы Xij создается ограничение, что сумма объемов перевозок из данной строки (=СУММ(строка_X)) должна быть равна (так как задача сбалансирована) соответствующему запасу ai.
    • Ограничения по потребностям (столбцы): Аналогично, для каждого столбца матрицы Xij устанавливается ограничение, что сумма объемов перевозок в данный столбец (=СУММ(столбец_X)) должна быть равна соответствующей потребности bj.
    • Ограничения на неотрицательность: Необходимо добавить условие, что все изменяемые ячейки Xij должны быть ≥ 0. В Solver есть опция «Сделать переменные без ограничений неотрицательными».
  5. Параметры Solver:
    В окне настроек Solver’а обязательно выбирается метод решения «Симплекс-метод LP» (Simplex LP), поскольку транспортная задача является задачей линейного программирования.

Пример настройки Solver для Варианта 1 (Склад C):

  • Установить целевую ячейку: $H$1 (предположим, там формула СУММПРОИЗВ)
  • До: Минимум
  • Изменяя ячейки переменных: $A$4:$C$6 (матрица Xij)
  • В соответствии с ограничениями:
    • $D$4:$D$6 = $E$4:$E$6 (суммы по строкам равны запасам)
    • $A$7:$C$7 = $A$8:$C$8 (суммы по столбцам равны потребностям)
    • $A$4:$C$6 ≥ 0 (неотрицательность переменных)
  • Выберите метод решения: Симплекс-метод LP

После запуска Solver для Варианта 1 (Склад C) будут получены следующие результаты:
Оптимальный план Xij:

По1 По2 По3
П1 0 30 70
П2 0 150 0
П3 120 0 80

Минимальные общие затраты Zmin, C: 4500 у.е.
Эти результаты полностью совпадают с ручным расчетом, что подтверждает его корректность и является важным шагом в валидации полученных данных.

Пример настройки Solver для Варианта 2 (Склад D):

  • Установить целевую ячейку: $H$1 (предположим, там формула СУММПРОИЗВ для Варианта 2)
  • До: Минимум
  • Изменяя ячейки переменных: $A$4:$C$6 (матрица Xij для Варианта 2)
  • В соответст��ии с ограничениями:
    • $D$4:$D$6 = $E$4:$E$6
    • $A$7:$C$7 = $A$8:$C$8
    • $A$4:$C$6 ≥ 0
  • Выберите метод решения: Симплекс-метод LP

После запуска Solver для Варианта 2 (Склад D) будут получены следующие результаты:
Оптимальный план Xij:

По1 По2 По3
П1 0 100 0
П2 120 0 30
П3 0 80 120

Минимальные общие затраты Zmin, D: 4690 у.е.
Эти результаты также полностью совпадают с ручным расчетом, подтверждая его точность и надежность методики.

Анализ чувствительности к изменению тарифов

Анализ чувствительности является критически важным этапом, который выходит за рамки простого нахождения оптимального решения. Он позволяет понять, насколько устойчиво это решение к изменениям входных параметров и в каких пределах эти изменения допустимы без потери оптимальности базиса. В нашем случае, нас интересует, как изменение переменной V (транспортных расходов) влияет на оптимальный план. Игнорирование анализа чувствительности может привести к выбору решения, которое будет неоптимальным уже при незначительных колебаниях рыночных условий.

Как изменение V влияет на оптимальный план:
Переменная V входит в один из тарифов cij. Изменение этого тарифа может:

  1. Не повлиять на оптимальный базис: Если изменение V находится в пределах допустимого интервала, набор маршрутов, по которым осуществляются перевозки (xij > 0), останется прежним. Изменится только общая стоимость Zmin. Это означает, что текущая стратегия останется выгодной, но с другой итоговой ценой.
  2. Изменить оптимальный базис: Если изменение V выходит за пределы допустимого интервала, то старый оптимальный план перестает быть таковым, и требуется новый расчет, который приведет к изменению структуры перевозок. В этом случае компания должна быть готова к пересмотру своих логистических маршрутов.

Анализ Отчета по устойчивости (Sensitivity Report) Excel Solver:
После успешного решения задачи, Excel Solver может сгенерировать «Отчет по устойчивости» (Sensitivity Report). Этот отчет содержит ценную информацию:

  • Ячейки переменных (Variable Cells): Показывает значения оптимального плана Xij, а также допустимое увеличение (Allowable Increase) и допустимое уменьшение (Allowable Decrease) для коэффициентов целевой функции (cij). Эти значения указывают, насколько может измениться тариф cij (включающий V) без изменения оптимального базиса.
    • Например, если тариф c22 для склада D (где V=22) имеет допустимое уменьшение на 5 и допустимое увеличение на 10, это означает, что V может измениться в диапазоне от (22-5)=17 до (22+10)=32, и при этом наш оптимальный набор маршрутов останется прежним. Общая стоимость, конечно, изменится. Такая информация позволяет менеджеру оценить риски и гибкость выбранного решения.
  • Ограничения (Constraints): Для ограничений по запасам и потребностям Отчет по устойчивости предоставляет значения теневых цен (Shadow Prices), которые соответствуют двойственным переменным (ui и vj из Метода потенциалов).
    • Экономическая интерпретация двойственных переменных (теневых цен):
      • Теневая цена для ограничения по запасу ai (поставщик): Показывает, на сколько единиц уменьшится минимальная общая стоимость перевозок (Zmin), если запас i-го поставщика будет увеличен на одну единицу. Это «ценность» дополнительной единицы ресурса для оптимизации, позволяющая понять, насколько выгодно инвестировать в увеличение запасов у конкретного поставщика.
      • Теневая цена для ограничения по потребности bj (потребитель): Показывает, на сколько единиц уменьшится Zmin, если потребность j-го потребителя будет уменьшена на одну единицу (или, эквивалентно, увеличится на сколько, если потребность возрастет). В транспортной задаче часто интерпретируется как «ценность» удовлетворения потребности, показывая экономическую выгоду от более эффективного управления спросом.

    Например, если теневая цена для запаса П1 составляет -3 у.е., это означает, что если запас П1 увеличить на 1 единицу, общие транспортные расходы уменьшатся на 3 у.е. (или наоборот, стоимость ресурсов у поставщика). Если теневая цена для потребности По1 равна 5 у.е., то увеличение потребности По1 на 1 единицу приведет к увеличению общих затрат на 5 у.е. Эти данные критически важны для стратегического планирования и принятия решений о расширении производства или пересмотре условий с поставщиками и потребителями.

    Эти отчеты помогают менеджеру понять не только оптимальное решение, но и его «прочность» и потенциал для улучшения при изменении рыночных условий или доступности ресурсов. Например, если допустимое изменение V очень мало, это сигнал о том, что стоимость этого маршрута является критической, и даже небольшие колебания могут потребовать пересмотра всего плана логистики, что подчеркивает необходимость постоянного мониторинга и адаптации.

    Заключение

    В рамках данной работы была успешно решена актуальная логистическая задача по оптимизации размещения нового склада для торгового дома. Анализ двух альтернативных вариантов — склада C и склада D — был проведен с использованием мощного инструментария экономико-математического моделирования, а именно, транспортной задачи линейного программирования. Полученные результаты дают чёткое представление о наиболее выгодной стратегии.

    На первом этапе мы детально изучили теоретические основы транспортной задачи, включая её исторический контекст (вклад Монжа и Канторовича), формализацию математической модели с целевой функцией и ограничениями, а также важность условия сбалансированности. Был представлен и пошагово описан алгоритм Метода потенциалов, подчеркивающий его эффективность по сравнению с общим симплекс-методом благодаря специфической структуре транспортных задач. Это позволяет не только найти решение, но и понять его внутреннюю логику.

    Далее, на основе исходных данных и подстановки значения V=22, мы провели ручные расчеты для каждого из вариантов размещения склада. Для Варианта 1 (склад C) был получен оптимальный план перевозок с минимальными общими транспортными расходами в размере 4500 у.е. Для Варианта 2 (склад D), после нескольких итераций улучшения плана, был найден оптимальный план с минимальными общими транспортными расходами, составившими 4690 у.е. Число итераций для склада D ярко демонстрирует, насколько сложными могут быть расчеты при изменении исходных условий.

    Сравнительный анализ этих двух результатов позволил сделать однозначный экономически обоснованный вывод: размещение склада C является более выгодным, поскольку обеспечивает значительную экономию в 190 у.е. на общих транспортных расходах по сравнению со складом D. Эта разница в затратах, хотя и кажется незначительной в абсолютных величинах, в масштабах годового оборота компании может составить существенную сумму, напрямую влияющую на прибыль и конкурентоспособность.

    На последнем этапе, для верификации ручных расчетов и углубленного анализа, была использована надстройка «Поиск решения» (Solver) в Microsoft Excel. Настройка модели в Excel полностью подтвердила результаты ручных вычислений. Более того, анализ «Отчета по устойчивости» позволил оценить чувствительность оптимального решения к изменению тарифов (включая переменную V), а также дал экономическую интерпретацию двойственных переменных (теневых цен), которые отражают ценность дополнительных единиц запасов или потребностей. Получение таких отчетов является не просто подтверждением, но и расширением нашего понимания, предоставляя менеджменту ценные данные для стратегического планирования и адаптации к меняющимся условиям рынка.

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

    Список использованной литературы

    1. Лекция 9 Методы решения транспортной задачи // sstu.ru. URL: https://www.sstu.ru/ (дата обращения: 06.10.2025).
    2. Транспортная задача // Википедия. URL: https://ru.wikipedia.org/wiki/Транспортная_задача (дата обращения: 06.10.2025).
    3. Метод потенциалов // Википедия. URL: https://ru.wikipedia.org/wiki/Метод_потенциалов (дата обращения: 06.10.2025).
    4. Математическая модель транспортной задачи // studfile.net. URL: https://studfile.net/ (дата обращения: 06.10.2025).
    5. ЛАБОРАТОРНАЯ РАБОТА № 4 Тема: «Транспортная задача. Метод потенциалов» // gbpoubertt.ru. URL: https://gbpoubertt.ru/ (дата обращения: 06.10.2025).
    6. Алгоритм решения транспортной задачи методом потенциалов. // studfile.net. URL: https://studfile.net/ (дата обращения: 06.10.2025).
    7. Транспортная задача. Математическая модель — пример решения — Grandars.ru // grandars.ru. URL: https://grandars.ru/ (дата обращения: 06.10.2025).
    8. Транспортная задача — решение методом потенциалов // Галяутдинов — сайт преподавателя экономики. URL: https://galyautdinov.ru/ (дата обращения: 06.10.2025).
    9. Задачи линейного программирования транспортного типа образуют широк // kf-rmat.ru. URL: https://kf-rmat.ru/ (дата обращения: 06.10.2025).
    10. Модели транспортных задач // Онлайн-калькулятор semestr.ru. URL: https://semestr.ru/ (дата обращения: 06.10.2025).
    11. Поиск решения EXCEL (1.8). Транспортная задача. Примеры и описание // excel2.ru. URL: https://excel2.ru/ (дата обращения: 06.10.2025).
    12. Решение транспортной задачи в Excel // Циклопедия. URL: https://cyclowiki.org/ (дата обращения: 06.10.2025).
    13. Методы оптимальных решений. Транспортная задача в MS Excel // Решатель. URL: https://reshatel.org/ (дата обращения: 06.10.2025).
    14. Решение в Excel транспортных задач: подробные примеры // МатБюро. URL: https://matburo.ru/ (дата обращения: 06.10.2025).
    15. Оценка ресурсов с помощью двойственной задачи // Онлайн-калькулятор semestr.ru. URL: https://semestr.ru/ (дата обращения: 06.10.2025).
    16. Основы анализа на чувствительность // narod.ru. URL: https://narod.ru/ (дата обращения: 06.10.2025).
    17. Анализ чувствительности оптимального решения одноиндексных задач ЛП // studfile.net. URL: https://studfile.net/ (дата обращения: 06.10.2025).
    18. Анализ чувствительности оптимального решения одноиндексных задач ЛП // Allmath.ru. URL: https://allmath.ru/ (дата обращения: 06.10.2025).

    С этим материалом также изучают

    Спосбы нахождения опорного плана решения транспортной задачи

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

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

    Ищете образец дипломной работы по управленческим решениям? Наш материал предлагает детальный разбор структуры от введения до заключения, анализ ключевых методов оптимизации и готовые формулировки для теоретической и практической глав.

    Написание дипломной работы на тему «Анализ покупательского поведения как основа для принятия управленческих решений»: структура и методология

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

    Общая постановка задачи принятия решений (ЗПР).

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

    Методы решения транспортной задачи: полное руководство от теории до практики в Excel

    Полное руководство по решению транспортной задачи. Рассматриваем методы северо-западного угла, наименьшей стоимости и потенциалов. Подробный пример с пошаговым решением в Excel (Поиск решения) для успешной сдачи экзамена.

    Комплексный анализ и решение задач линейного программирования: Каноническая форма, Транспортная модель и Графический метод (Академический отчет)

    Полный гайд по линейному программированию: приведение к канонической форме, построение транспортной модели и графическое решение. Оптимизируйте ресурсы и логистику.

    Решения транспортных задач на примере решения задачи

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

    Мировой опыт решения транспортных проблем в мегаполисах

    ... ИХ РЕШЕНИЯ82.1. Основные транспортные проблемы в международных экономических отношениях82.2.Пути решения транспортных проблем на ... транспортные системы, также уделяет внимание транспортным проблемам в крупных городах. Ю.В. Шишков, отмечает, что ...

    Решение транспортных проблем в городах.

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

Похожие записи