Исходные данные транспортной задачи

Поставщики	Потребители	Ресурсы поставщиков
S1	S2	S3	S4
Р1	C11 =1 X1	C12 =2 X2	C13 =3 X3	C14 =4 X4
Р2	C21 =4 X5	C22 =3 X6	C23 =2 X7	C24 =0 X8
Р3	C31 =0 X9	C32 =2 X10	C33 =2 X11	C34 =1 X12
Фонды потребителей

Решим задачу симплекс-методом.

Запишем ограничения модели:

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

X₁ + X₂ + X₃ + X₄ = 6.

X₅ + X₆ + X₇ + X₈ = 8.

X₉ + X₁₀ + X₁₁ + X₁₂ = 10.

2. Продукция, поступающая в каждый пункт потребления, должна удовлетворять потребности в ней.

X₁ + X₅ + X₉ = 4. X₃ + X₇ + X₁₁ = 8.

X₂ + X₆ + X₁₀ = 6. X₄ + X₈ + X₁₂ = 6.

Требуется определить наименьшую сумму транспортных издержек:

F(x) = X₁ + 2X₂ + 3X₃ + 4X₄ + 4X₅ + 3X₆ +2X₇ + 2X₁₀ + 2X₁₁ + X₁₂ ®min.

Решение транспортной задачи симплекс-методом основано на отыскании базисных переменных. Выразим базисные переменные:

X₁ = 6 – X₂ – X₃ – X_4. X₁₀ = -2 – X₂ + X₅ + X₇ + X_8. (1)

X₆ = 8 – X₅ – X₇ - X₈. X₁₁ = 8 –X₃ –X_7. (2)

X₁₂ = 6 – X₄ – X_8. X₉ = -2 + X₂ + X₃ + X₄ – X_5. (3)

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

Базисные переменные X₁, X₆, X₉, X₁₀, X₁₁, X₁₂, а свободные – X₂, X₃, X₄, X₅, X₇, X₈.

Выразим через свободные члены целевую функцию:

F(x) = 6 – X₂ – X₃ – X₄ + 2X₂ + 3X₃ + 4X₄ + 4X₅ + 24 – 3X₅ –3X₇ - 3X₈ + 2X₇ – - 4 – 2X₂ + 2X₅ + 2X₈ + 2X₇ + 16 – 2X₃ - 2X₇ + 6 – X₄ – X₈ = 48 – X₂ + 2X₄ + + 3X₅ – X₇ – 2X_8.

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

Получим X₇ = 8 – X₅ – X₈ – X_6. (4)

Запишем новую целевую функцию:

F(x) = 48 – X₂ + 2X₄ + 3X₅ - 8 + X₅ + X₈ + X₆ – 2X₈ = 40 – X₂ + 2X₄ + 4X₅ - - X₈ + X_6.

Заменим базисный член X₁₂ на свободный X_8.

Получим X₈ = 6 – X₄ – X₁₂ (5)

Запишем новую целевую функцию:

F(x) = 34 – X₂ + 3X₄ + X₁₂ + 4X₅ + X_6.

Заменим базисный член X₁ на свободный X_2.

Получим X₂ = 6 – X₃ - X₄ – X₁; (6)

F(x) = 28 + X₃ + 4X₄ + X₁ + X₁₂ + 4X₅ + X_6.

Следовательно, мы получили базисные переменные X₂, X₇, X₈, X₉, X₁₀, X₁₁; свободные – X₁, X₃, X₄, X₅, X₆, X₁₂.

Приравняем свободные члены к нулю и найдем базисные переменные:

Если X₁ = 0; X₃ = 0; X₄ = 0; X₅ = 0; X₆ = 0; X₁₂ = 0, то из уравнений (1), (2), (3), (4), (5), (6) получим X₂ = 6; X₇ = 2; X₈ = 6; X₉ = 4; X₁₀ =0; X₁₁ = 6.

F(x) = 28

Запишем в таблицу результат решения задачи:

Поставщики	Потребители	Ресурсы поставщиков
S1	S2	S3	S4
Р1
Р2
Р3
Фонды потребителей

Решим данную задачу методом потенциалов.

Потенциалами называется система чисел, приписанных, соответственно, каждой строке i (u_i) и каждому столбцу j (v_j).

Потенциал (u_i), который устанавливается для каждой строки, можно условно принять за цену продукта в пункте его производства, потенциал (v_j), который устанавливается для каждого столбца можно условно принять за цену продукта в пункте потребления.

В простейшем случае цена продукта в пункте потребления равна цене продукта в пункте производства плюс транспортные расходы на его перевозку (c_ij).

u_i + c_ij = v_j; u_i = v_j – c_ij.

Шаг 1. Построение первоначального плана методом «наименьшей стоимости» (по строкам или столбцам) или методом «северо-западного угла».

В первую очередь следует рассматривать строки (столбцы) с максимальными объемами производства (потребления). Искомой строкой является третья равная 10 т. В этой строке наименьшая стоимость перевозки находится на пересечении строки с первым столбцом и равна нулю. Поэтому есть возможность полностью удовлетворить потребность первого потребителя, равную 4 т, причем у третьего поставщика останется еще 6 т (10т – 4т) продукции. Заполним результат в таблицу:

Поставщики	Потребители	Ресурсы поставщиков
S1	S2	S3	S4
Р1
Р2
Р3
Фонды потребителей

Следующей по объему ресурсов является вторая строка (8т) и наименьшая стоимость перевозки находится в 4-ом столбце. Следовательно, можно полностью удовлетворить потребность четвертого потребителя (6т), а у поставщика останется 2т продукции. Аналогично распределяем продукцию первого поставщика. Минимальные затраты на перевозку имеет первый пункт потребления, который уже не нуждается в поставках. Следовательно, мы можем удовлетворить второго потребителя полностью и т.д.

Первоначально составленный план перевозок должен удовлетворять условию: оптимальное решение транспортной задачи то, в котором число перевозок не превышает i +j – 1. В нашем примере i = 3; j = 4 Þ 3 + 4 – 1 = 6.

Так как число перевозок (выделено жирными цифрами в левом нижнем углу квадрата) в полученном плане 5, то условие выполняется.

Шаг 2. Построение системы потенциалов, которое начинают с того, что строке 1 присваивают ноль, т.е. принимают условную цену продукта в первом пункте производства равной нулю (u₁ = 0). Продукт направляют второму потребителю. Следовательно, условная цена во втором пункте потребления составит v₂ = u₁ + c₁₂ = 0 + 2 = 2.

Находим цену в третьем пункте производства

u₃ = v₂ – c₃₃ = 2 – 2 = 0.

Находим цену продукта в пунктах потребления 1, 3.

v₁ = u₃ + c₃₁ = 0 + 0 = 0,

v₃ = u₃ + c₃₃ = 0 + 2 = 2.

Находим цену производства во втором пункте

u₂ = v₃ – c₂₃ = 2 – 2 = 0.

Находим цену продукта в 4 пункте потребления

v₄ = u₂ + c₂₄ = 0 + 0 = 0.

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

u_i + c_ij ³ v_j.

Осуществим проверку для свободных квадратов:

u₁ + c₁₁ = 0 + 1 = 1 > v₁ = 0, u₂ + c₂₂ = 0 + 3 = 3 > v₂ = 2,

u₁ + c₁₃ = 0 + 3 = 3 > v₃ = 2, u₃ + c₃₂ = 0 + 2 = 2 > v₂ = 2,

u₁ + c₁₄ = 0 + 4 = 4 > v₄ = 0, u₃ + c₃₄ = 0 + 1 = 1 > v₄ = 0.

u₂ + c₂₁ = 0 + 4 = 4 > v₁ = 0,

Условие оптимальности выполняется для всех квадратов.

Затраты на транспортировку составят 4*0+6*2+2*2+6*2+6*0=28.

Если условие оптимальности не выполняется, то переходят к шагу 4.

Шаг 4. Оптимизация плана. Тот квадрат, в котором не выполняется условие оптимальности, помечают точкой. Затем проводят замкнутую ломаную линию, одна из вершин которой соединена с точкой, а остальные находятся в занятых (перевозками) квадратах. Начиная с квадрата, в котором стоит точка, поочередно по часовой стрелке присваиваем квадратам с вершинами «+» и «-». Из квадрата со знаком «-» выбираем наименьшее количество продукта и перемещаем его в квадрат со знаком «+».

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

Решение транспортной задачи в сетевой форме (без ограничения пропускной способности).

Пример 2. На рис 8. представлена сеть с 11 вершинами и 18 звеньями. В каждом звене поставлено число, характеризующее расстояние с_ij между соседними вершинами, соединенными данным звеном. В круглых скобках против каждой вершины отмечены размеры ресурсов со знаком «+» и потребности со знаком «-». Необходимо распределить грузопотоки таким образом, чтобы минимизировать расстояние перевозок продукции. Решим задачу, сформулированную в сетевой форме без ограничения пропускной способности.

(-80) (-120) (-150)

(+300) (+100) (-40) (-60)

(-50) (-75) (-25) (+200)

Рис.8. Исходные данные для решения транспортной задачи

Решение:

Шаг 1. Составляем исходный план, при котором все ресурсы поставщиков должны быть распределены между соответствующими потребителями. Стрелками показывают направления грузопотоков, а цифрами над ними – количество перевозимой продукции (рис. 9).

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

Допустим, число 200. Затем приступаем к присвоению потенциалов остальным вершинам, придерживаясь следующего правила: при продвижении по дугам в направлении следования грузопотоков к потенциалу предыдущей вершины прибавляем длину звена (расстояние между вершинами), а при движении по дугам против потока эту длину из потенциала предыдущей вершины отнимаем (рис.10). В некоторых случаях дуги с грузопотоками могут образовать два замкнутых контура, не соединенных друг с другом. В этом случае оба контура соединяют дугами с нулевыми грузопотоками, которые включают в базис для определения потенциалов вершин.

(-80) (-120) (-150)

(+300) (+100) (-40) (-60)

(-50) (-75) (-25) (+200)

Рис.9. Направления грузопотоков плана

Шаг 3. Проверяем, выполняется ли условие оптимальности на всех дугах сети, на которых нет грузопотоков, т.е. соблюдается ли условие:

v_j – u_i £ c_ij.

(разница потенциалов двух вершин, соединенных дугой, на которой нет грузопотока. Таких дуг в нашем примере 7. Это дуги 1-10; 9-10; 10-7; 10-6; 11-5; 3-11; 8-7).

При невыполнения условия план перевозок не является оптимальным, т.к. при переводе грузопотока на данные дуги общее расстояние перевозок уменьшится.

Проверим условие оптимальности на дугах:

1-10: 210-200=10 <75;10-6: 290-210=80< 120;

9-10: 250-210=40< 110; 11-5: 330-280=50 = 50;

10-7: 370-210=160 > 100 – не выполняется; 3-11: 310-280=30 < 50;

8-7: 370-320=50= 50.

(-80) 280 (-120) 310 (-150) 380

(+300) 200 (+100) 210 (-40) 280 (-60) 330

(-50) 250 (-75) 320 (-25) 370 (+200) 290

Рис.10. Распределение потенциалов по вершинам сети

Шаг 4. По дуге с максимальными нарушениями условия оптимальности направляем грузопоток от вершины с меньшим потенциалом до вершины с большим потенциалом (от 10 к 7) в объеме необходимой потребности (25), одновременно отнимая ее из всех встречных грузопотоков (рис. 11).

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

1-10: 210-200=10 <75;11-5: 330-280=50 = 50;

9-10: 250-210=40< 110; 3-11: 310-280=30 < 50;

10-6: 290-210=80< 120; 8-7: 320-310=10< 50.

7-6: 310-290=20< 80;

Все условия оптимальности выполняются.

(-80) 280 (-120) 310 (-150) 380

(+300) 200 (+100) 210 (-40) 280 (-60) 330

(-50) 250 (-75) 320 (-25) 370 (+200) 290

Рис.11. Направление грузопотоков плана №2

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

Рис.12. Оптимальный план перевозок.

Дата добавления: 2014-12-07