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

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

Транспортная задача линейного программирования записывается в следующем виде. Найти.

при условиях:

где — номер поставщика;

— число поставщиков;

— номер потребителя;

— число потребителей;

— количество ресурса, распределяемого отго поставщикаму потребителю;

— оценка распределения ресурса отго поставщикаму потребителю;

— наличие ресурса уro поставщика;

— потребность в ресурсего потребителя.

Решение задач с помощью симплексного метода и метода потенциалов рассмотрим на примерах.

Пример 2. В хозяйстве за время уборки при заготовке силоса необходимо перевезти 4000 т зеленой массы с пяти полей к четырем фермам, в том числе с первого поля 600 т, со второго — 240 т, третьего —1360 т, четвертого — 1000 т и пятого — 900 т. Для первой фермы требуется 600 т зеленой массы, второй — 800 т, третьей — 1400 т и четвертой — 1200 т.

Расстояние перевозки зеленой массы с полей к фермам приведено в табл. 4.

Таблица 4

Требуется составить такой план перевозок, чтобы общие транспортные затраты были минимальными.

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

В рассматриваемом нами примере наличие зеленой массы на полях превышает потребность в ней ферм на 100 т. В этом случае вводится пятая «фиктивная» ферма с потребностью в 100 т зеленой массы. Расстояние от нее до полей принимается равным 0.

Таблица 5

Данную задачу можно решить как симплексным методом, так и методом потенциалов. Для решения задачи симплексным методом необходимо, как и в примере 1, составить развернутую экономико-математическую модель. Переменными величинами в задаче будут:

x_1,1 — количество зеленой массы, перевозимой с 1-го поля на 1-ю ферму, т;

x_1,2 — количество зеленой массы, перевозимой с 1-го поля на 2-ю ферму, т;

x_1,5 — количество зеленой массы, перевозимой с 1-го поля на 5-ю ферму, т;

X_5,1 — количество зеленой массы, перевозимой с 5-го поля на 1-ю ферму, т;

X_5,2 — количество зеленой массы, перевозимой с 5-го поля на 2-ю ферму, т;

X_5,5 — количество зеленой массы, перевозимой с 5-го поля на 5-ю ферму, т.

Развернутая экономико-математическая модель оптимизации перевозки зеленой массы с полей к фермам будет иметь следующий вид:

Ограничения по наличию зеленой массы на полях:

на 1-м поле.

x_1,1 + x_1,2 + x_1,3 + x_1,4 + x_1,5 = 600;

на 2-м поле.

x_2,1 + x_2,2 + x_2,3 + x_2,4 + x_2,5 = 240;

на 3-м поле.

x_3,1 + x_3,2 + x_3,3 + x_3,4 + x_3,5 = 1360;

на 4-м поле.

x_4,1 + x_4,2 + x_4,3 + x_4,4 + x_4,5 = 1000;

на 5-м поле.

x_5,1 + x_5,2 + x_5,3 + x_5,4 + x_5,5 = 900;

Ограничения по наличию зеленой массы на полях:

1-й фермы х1,1 + x2,1 + x3,1 + x4,1 + x5,1 = 600;

2-й фермы х_1,2 + x_2,2 + x_3,2 + x_4,2 + x_5,2 = 800;

3-й фермы х_1,3 + x_2,3 + x_3,3 + x_4,3 + x_5,3 = 1400;

4-й фермы х_1,4 + x_2,4 + x_3,4 + x_4,4 + x_5,4 = 1200;

5-й фермы (фиктивной) х_1,5 + x_2,5 + x_3,5 + x_4,5 + x_5,5 = 100.

Целевая функция — минимум затрат (тонно-километров) на перевозку зеленой массы:

Z = 5x_1,1 + 6x_1,2 + 2x_1,3 +2 x_1,4 + 0x_1,5 +9 x_2,1 + 7x_2,2 + 4x_2,3 + 6x_2,4 + 0x_2,5 + 7x_3,1 +1x_3,2 + 4x_3,3 + 5x_3,4 + 0x_3,5 + 5x_4,1 + 2x_4,2 + 2x_4,3 + 4x_4,4 + 0x_4,5 + 6x_5,1 + 4x_5,2 + 3x_5,3 + 4x_5,4 + 0x_5,5 min.

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

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