Практическая часть. 
Многоэтапная транспортная задача оптимального размещения и концентрации производства

Транспортная система состоит из пяти пунктов производства, шести пунктов промежуточной переработки и шести пунктов потребления. Известны объемы производства каждого из пунктов Ai (1 тыс. ед. товаров), пропускные способности пунктов промежуточной переработки Dk (1 тыс. ед. товаров), а так же потребности по потребителям Bj (1 тыс. ед. товаров). Известна стоимость доставки 1 тыс. ед. товаров на склад и доставки 1 тыс. ед. товара со склада потребителю. Эти данные представлены в таблицах.

Таблица 1

Поставки от производителей А1-А5 на склады D1-D6 и стоимость доставки партии товара на склад (тысячи денежных единиц).

Таблица 2

Поставки со складов потребителям и стоимость доставки партии товара со склада потребителям (тысячи денежных единиц).

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

1. Решить двухэтапную транспортную задачу.

составить математическую модель.

изобразить задачу графически.

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

2. Решить эту же задачу путем раздельного прикрепления поставщиков к складам и складов к потребителям.

составить математическую модель.

изобразить задачу графически.

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

Сравнить полученные результаты и сделать выводы.

Решить двухэтапные транспортные задачи с учетом дополнительных ограничений:

Из А1 в Д1 можно перевезти не менее 80 единиц груза, Из А3 в Д4 перевозки не осуществляются и из Д4 в В2 перевозки так же запрещены, Из Д6 в В5 можно перевезти не более 50 единиц груза.

Оценить и проанализировать раздельное влияние этих ограничений и общее их влияние на затраты.

5. Решить задачи п. 1, п. 2 и п. 4 (4 задачи) с использованием ЭВМ.

Решим двухэтапную транспортную задачу.

Обозначим через X_ik — количество продукции, поставляемое от i-го пункта производства на к-й промежуточный пункт (i=1, 2, 3, 4, 5; k= 1, 2, 3, 4, 5, 6), а через X_kj — количество продукции, поставляемое с к-го промежуточного пункта j-му потребителю (k= 1, 2, 3, 4, 5, 6; j=1, 2, 3,4, 5, 6). Тогда целевая функция, характеризующая суммарные транспортные расходы, запишется в виде:

Ограничения запишутся в виде:

120,.

80,.

300,.

250,.

• 50.
• 100,
• 30,
• 70,
• 240,
• 160,
• 200.
• 100,
• 30,
• 70,
• 240,
• 160,
• 200.

40,.

160,.

120,.

150.

200.

Условия положительности переменных:

X_ik0 (i=1, 2, 3, 4, 5; k= 1, 2, 3, 4, 5, 6); X_kj0 (k= 1, 2, 3, 4, 5, 6; j=1, 2, 3,4, 5, 6).

Так как 800, то можно решать двухэтапную транспортную задачу. Определяем число заполненных клеток первоначального опорного плана: 11 + 12 — 1 = 22.

Составляем начальный опорный план методом минимального элемента. Вначале заполняем первый или четвертый квадрант, затем третий, а затем оставшийся (первый или четвертый). В таблице 2.1 получен первоначальный опорный план. Проверим полученный план на оптимальность, для этого находим потенциалы U_i и V_j.

После того как мы определили потенциалы U_i и V_j, находим оценки свободных клеток:

S₈₃ = 0 — (1+0) = -1; S_{8 10} = 1 — (1+2) = -2; и так далее.

Полученный опорный план не оптимален, так как имеются отрицательные оценки, наибольшая по модулю из них S_{8 10}. Строим для заданной клетки замкнутый контур и улучшаем, полученный опорный план.

В результате получаем таблицу 2.2.

После того как мы определили потенциалы U_i и V_j, находим оценки свободных клеток:

S₈₃ = 0 — (1+0) = -1; S_{8 12} = 4 — (4+1) = -1; и так далее.

Полученный опорный план не оптимален, так как имеются отрицательные оценки, наибольшая по модулю из них S₈₃ и S_{8 12}. Строим для клетки S_{8 12} замкнутый контур и улучшаем, полученный опорный план.

В результате получаем таблицу 2.3.

Поскольку в таблице 2.3 нет свободных клеток с отрицательными оценками, то мы получили оптимальный план. В таблице 2.3 имеются нулевые оценки свободных клеток, следовательно, полученный нами оптимальный план не является единственным. Данному плану отвечают минимальные затраты, величина которых составляет:

f= (50•3 + 70•1 + 80•1 + 140•2 + 160•1 + 30•1+ 20•3 + 200•2 + 50•1) + (100•2 + 30•1 + 70•1 + 160•2 + 80•1+ 10•2 + 120•1 + 30•2 + 100•1 + 100•3) = 1280 + 1300 = 2580 ден. ед.

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

Запишем начальные условия первого этапа задачи в форме табл. 2.3.

Таблица 2.4

Составим математическую модель задачи.

Обозначим через Хik (i = 1,5; k = 1,6) объем продукции, который планируется перевезти от поставщика А_i, в промежуточный пункт D_k, а через f₁ — общие затраты на первом этапе транспортировки.

Целевая функция задачи запишется в виде:

f₁=3* X₁₁ + 5 * X₁₂ +…+ 4*X₅₆ (min) (2.2.1).

Сравнивая суммарную мощность поставщиков 120 + 80 + 300 + 250 + 50 = 800 со спросом на промежуточных пунктах 100 + 30 + 70 + 240 + 160 + 200 = 800, видим, что эти суммы совпадают. Следовательно, данная транспортная задача обладает закрытой моделью.

Переходя к ограничениям на переменные Х_ik, следует учесть, что спрос на промежуточных пунктах D_k, не может превышать мощности поставщиков, т. е.

X₁₁ + X₁₂ + X₁₃ + X₁₄ + X₁₅ + X₁₆ =120.

X₂₁ + X₂₂ + X₂₃ + X₂₄ + X₂₅ + X₂₆ = 80 (2.2.2).

X₃₁ + X₃₂+ X₃₃ + X₃₄+ X₃₅ + X₃₆ = 300.

X₄₁ + X₄₂+ X₄₃ + X₄₄+ X₄₅ + X₄₆ = 250.

X₅₁ + X₅₂+ X₅₃ + X₅₄+ X₅₅ + X₅₆ = 50.

Условия удовлетворения спроса на промежуточных пунктах D_k:

X₁₁ + X₂₁ + X₃₁+ X₄₁+ X₅₁ = 100.

X₁₂ + X₂₂ + X₃₂ + X₄₂+ X₅₂ = 30.

X₁₃ + X₂₃+ X₃₃+ X₄₃+ X₅₃ =70.

X₁₄ + X₂₄+ X₃₄+ X₄₄ + X₅₄ = 240 (2.2.3).

X₁₅ + X₂₅+ X₃₅+ X₄₅ + X₅₅ = 160.

X₁₆ + X₂₆+ X₃₆+ X₄₆ + X₅₆ = 200.

Условия неотрицательности переменных:

Х_ij ?0 (i=1,5; k=1,6) (2.2.4).

Соотношения (2.2.1) — (2.2.4) образуют экономико-математическую модель рассматриваемой задачи. Таким образом, математическая модель задачи: целевая функция (2.2.1), описывающая суммарные затраты на первом этапе транспортировки, минимизируется при ограничениях (2.2.2) — (2.2.4).

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

Таблица 2.5

Приступая к составлению исходного опорного плана, устанавливаем, что в нашем случае любой опорный план должен «загружать» m+n-1= 5+6−1=10 клеток.

Построим исходный опорный план методом минимального элемента.

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

U1 + V1 = 3.

U₁ + V₃ = 1.

U₁ + V₅ = 2.

U₂ + V₄ =1.

U₃ + V₄ =2.

U₃ + V₅ = 1.

U₄ + V₂ = 1.

U₄ + V₄ = 3.

U₄ + V₆ = 2.

U₅ + V₁ = 1.

составленных по заполненным клеткам. Это неопределенная система, т.к. неизвестных на одно больше числа уравнений. Придадим одному из неизвестных определенное числовое значение, например, U₄ = 0. Тогда остальные неизвестные находятся из системы.

Получаем.

U₁ = 0, U₂ = -2, U₃ = -1, U₄ = 0, U₅ = -2, V₁ = 3, V₂ = 1, V₃ = 1, V₄ = 3, V₅ = 2, V₆ = 2.

Теперь можно найти оценки свободных клеток:

Д₁₂ = C₁₂ — (U₁ + V₂) = 5-(1 + 0)= 4, Д₁₄= 1, Д₁₆ = 1, Д₂₁ = 4, Д₂₂ = 7, Д₂₃ = 5, Д₂₅ = 8, Д₂₆= 3, Д₃₁= 1, Д₃₂= 1, Д₃₃ = 5, Д₃₆= 2 и т. Д.

Поскольку в табл. 2.5 свободных клеток с отрицательными оценками нет, то опорный план является оптимальным. Итак, получен оптимальный план:

Этому плану соответствуют минимальные суммарные затраты в 1280 ден. ед.

(f₁= 50•3 + 70•1 + 80•1 + 140•2 + 160•1 + 30•1+ 20•3 + 200•2 + 50•1 = 1280).

Запишем начальные условия второго этапа задачи в форме таблицы 2.6.

Таблица 2.6

Обозначим через Х_kj (k = 1,6; j = 1,6) объем продукции, который планируется перевезти из промежуточного пункта D_k к потребителю b_j, а через f₂ — общие затраты на втором этапе транспортировки.

Целевая функция задачи запишется в виде:

f₂ =9* X₁₁ + 3 * X₁₂ +…+ 3*X₆₆ (min) (2.2.5).

Сравнивая суммарные возможности промежуточных пунктов 100 + 30 + 70 + 240 + 160 + 200 = 800 со спросом потребителей 40 + 160 + 120 + 150 + 130 + 200 = 800, видим, что эти суммы совпадают. Следовательно, данная транспортная задача обладает закрытой моделью.

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

X₁₁ + X₁₂ + X₁₃ + X₁₄ + X₁₅ + X₁₆ =100.

X₂₁ + X₂₂ + X₂₃ + X₂₄ + X₂₅ + X₂₆ = 30 (2.2.6).

X₃₁ + X₃₂+ X₃₃ + X₃₄+ X₃₅ + X₃₆ = 70.

X₄₁ + X₄₂+ X₄₃ + X₄₄+ X₄₅ + X₄₆ = 240.

X₅₁ + X₅₂+ X₅₃ + X₅₄+ X₅₅ + X₅₆ = 160.

X₆₁ + X₆₂+ X₆₃ + X₆₄+ X₆₅ + X₆₆ = 200.

Условия удовлетворения спроса поставщиков Вj:

X₁₁ + X₂₁ + X₃₁+ X₄₁+ X₅₁ + X₆₁ = 40.

X₁₂ + X₂₂ + X₃₂ + X₄₂+ X₅₂ + X₆₂ = 160.

X₁₃ + X₂₃+ X₃₃ + X₄₃ + X₅₃ + X₆₃ = 120.

X₁₄ + X₂₄+ X₃₄+ X₄₄ + X₅₄ + X₆₄ = 150 (2.2.7).

X₁₅ + X₂₅+ X₃₅+ X₄₅ + X₅₅ + X₆₅ = 130.

X₁₆ + X₂₆+ X₃₆+ X₄₆ + X₅₆ + X₆₆ = 200.

Условия неотрицательности переменных:

Х_ij ?0 (j=1,6; k=1,6) (2.2.8).

Соотношения (2.2.5) — (2.2.8) образуют экономико-математическую модель рассматриваемой задачи.

Таким образом, математическая модель задачи: целевая функция (2.2.5), описывающая суммарные затраты на втором этапе транспортировки, минимизируется при ограничениях (2.2.6) — (2.2.8).

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

Таблица 2.7

Приступая к составлению исходного опорного плана, устанавливаем, что в нашем случае любой опорный план должен «загружать» m+n-1= 6+6−1=11 клеток.

Построим исходный опорный план методом минимального элемента.

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

U₁ + V₆ = 2.

U₂ + V₁ = 1.

U₃ + V₄ = 1.

U₃ + V₆ = 4.

U₄ + V₂ = 2.

U₄ + V₄ = 1.

U₅ + V₁ = 2.

U₅ + V₃ = 1.

U₅ + V₅ = 2.

U₆ + V₅ = 1.

U₆ + V₆ = 3.

Это неопределенная система, т.к. неизвестных на одно больше числа уравнений. Придадим одному из неизвестных определенное числовое значение, например, U₁ = 0. Тогда остальные неизвестные находятся из системы.

Получаем.

U₁ = 0−2 U₂ = -1, U₃ = 0, U₄ = 0, U₅ = 0, U₆ = -1,V₁ = 2, V₂ = 2, V₃ = 2, V₄ = 1, V₅ = 2, V₆ = 4.

Теперь можно найти оценки свободных клеток: Д₁₁ = C₁₁ — (U₁ + V₁) = 9-(2−2)= 9 и так далее. Поскольку в таблице 2.8 свободных клеток с отрицательными оценками нет, то опорный план является оптимальным.

Итак, получен оптимальный план:

Этому плану соответствуют минимальные суммарные затраты в 1300 ден. ед.

(f₂ = 100•2 + 30•1 + 70•1 + 160•2 + 80•1+ 10•2 + 120•1 + 30•2 + 100•1 + 100•3 = 1300).

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

f = f₁ + f₂ = 1280 + 1300 = 2580 ден.ед.

Изобразим решение данной задачи на рисунке 2.2.

Сравнивая полученные результаты в пунктах 2.1 и 2.2, можем сделать вывод, что в нашем случае планы, полученные в пунктах 2.1 и 2.2 равнозначны. Так как суммарные транспортные затраты в обоих планах одинаковы и равны 2580 ден. ед.

Решим двухэтапные транспортные задачи с учетом дополнительных ограничений.

Все оценки свободных клеток в таблице 2.7. оказались положительными, следовательно, полученный нами опорный план, является оптимальным, и ему соответствуют минимальные транспортные затраты:

Z_min = (40•1 + 80•3 + 80•1 + 30•1 + 160•1 + 110•3+ 30•4 + 130•3 + 90•2 + 20•1 + 30•2) + (100•2 + 30•1 + 70•4 + 150•1 + 10•6+ 80•4 + 10•2 + 30•3 + 120•1 + 130•3+ 50•1+ 20•3) = 3420 тыс. ден. ед.

Можем сделать вывод, что введение дополнительных ограничений, привело к повышению значения целевой функции на 3420 — 2580 = 840 ден. ед.