Материал: Роль транспортной задачи в экономике

Решение . Строим начальное опорное решение методом минимальной стоимости :

Затем вычисляем значение целевой функции да нем: (X1) = 20∙1 + 30∙5 + 10∙8 + 40∙15 = 850

Таблица

Находим цикл для свободной клетки (1, 2) таблицы, он включает клетки (1, 2), (1, 3), (3, 3), (3, 2). Вычисляем оценку Δ12 = (3 + 15) -- (2 + 8) = 8. Так как Δ12 = 8 > 0, переходим к следующей свободной клетке (2, 1). Для нее цикл таков: (2, 1), (1, 1), (1,3), (3, 3), (3, 2), (2, 2) (см. табл.). Оценка Δ21 = (4 + 2 + 8) - (1 + 15 + 5) =14 - 21 = -7. Так как Δ21| =- -7 < 0, определяем величину груза, перераспределяемого по циклу,

Приращение целевой функции ΔF=-7∙20=-140. Получим новое опорное решение X2. Значение целевой функции на нем F(X2)=20∙2+20∙4+10∙5+30∙8+20∙15=710.

Вычисляем Δ11 = (1 + 15 + 5) - (2 + 8 + 4) =7>0 , Δ 12 = (3 + 15) - (2 + 8) =8>0, Δ 23 = (7 + 8) - (5 + 15)=-5<0, Δ31= (6 + 5) - (8 + 4) =-1<0. Оценки можно вычислять до первой отрицательной. Так какΔ23 =-5<0, осуществляем сдвиг по циклу (2,3), (3,3), (3,2), (2,2) на величину. Приращение целевой функции ΔF=-5∙10=-50. Получаем третье опорное решение X3. Значение целевой функции на нем F(X3)=20∙2+20∙4+10∙7+40∙8+10∙15=660.

Вычисляем оценки для свободных клеток Δ11 = (1 + 7) - (2 + 4) =2>0 , Δ12 = (3 + 15) - (2 + 8) =8>0, Δ22 =(5 + 15) - (7 + 8) =5>0, Δ31 = (6 + 7) - (4 + 15) =-6<0. Так как Δ31 =-6<0, осуществляем сдвиг по циклу (3,1), (2,1), (2,3), (3,3), на величину. Приращение целевой функции ΔFm=-6∙10=-60. Получаем четвертое опорное решение X4 Значение целевой функции на нем F(X4)=20 ∙2+10∙4+20∙7+10∙6+40∙8=600.

Вычисляем оценки для свободных клеток Δ11 = (1 + 7) - (2 + 4) =2>0 , Δ12 = (3 + 7+ 6) - (2 +4+ 8) =2>0, Δ22 =(5 + 6) - (4 + 8) =-1<0. Так как Δ22 =-1<0, осуществляем сдвиг по циклу (2,2), (3,2), (3,1), (2,1), на величину. Приращение целевой функции ΔF=-1∙10=-10. Получаем пятое опорное решение X5.

Значение целевой функции на нем F(X5)=20 ∙2+10∙5+20∙7+20∙6+30∙8=590. Вычисляем оценки для свободных клеток Δ11 = (1 + 7) - (2 + 4) =2>0 , Δ12 = (3 + 7) - (2 +5) =3>0, Δ33 =(15 + 5) - (7 + 8) =5>0. Все оценки для свободных клеток положительные, следовательно, последнее опорное решение оптимально.

Транспортные задачи с неправильным балансом.

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

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

в рассмотрение вводится фиктивный потребитель с потребностью

и тарифами на перевозку ci ( k +1) =0. Если же

то вводится фиктивный поставщик, запасы которого равны

с тарифами на перевозку c ( n +1)j=0. Этим приемом задача сводится к закрытой транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. Заметим, что при составлении начального опорного решения для ускорения вычислений в последнюю очередь следует (хотя и не обязательно) распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствуют наименьшие тарифы на перевозку (равные 0).

Транспортная задача с ограничениями на пропускную способность.

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

Возможны ограничения двух типов

I ) xlm > а ; 2) xlm<b ,

где а и b - постоянные величины.

. Если xlm > a , то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l-го поставщика и запросы m-го потребителя на величину а (зарезервировать перевозку xlm =а). После решения задачи в оптимальном решении следует увеличить объем перевозки xlm на величину а.

. Если xlm <b , то необходимо вместо m -го потребителя с запросами bm ввести двух других потребителей. Один из них с номером m должен иметь запросы b 'm=b, а другой с номером п + 1- запросы bп+1= bm - b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости cl(n+1) которая принимается равной сколь угодно большому числу М (М >> 1). После получения оптимального решения величины грузов, перевозимых к (n + 1)-му потребителю, прибавляются к величинам перевозок l-го потребителя. Так как cl(n+1)) = М- самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l, n+ 1) останется пустой, xl{n+1) = 0 и объем перевозки хlm не превзойдет b.

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

Глава 3. Применение транспортной задачи для решения экономических задач

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

Пример:

 = m+n-1=3+4-1=6 (невырожденная).

) F(

)

Для заполнения клеток вычислим значения потенциалов:

(1; 1)

(1; 2)

(2; 1)

(3; 2)

(3; 3)

(3; 4)

Вычислим оценки для пустых клеток:

 = min

) F= (

Для заполненных клеток вычислим значения потенциалов:

(1; 1)

(1; 2)

(1; 3)

(2; 1)

(3; 2)

(3; 4)

Оценки