Вычисляем значения параметра l

4. Если l<j, производим перераспределение поставок и получаем новое оптимальное решение. Если l=j, то процесс решения окончен.

Рассмотрим решение транспортной параметрической задачи на конкретном примере.

Пример 14. Имеются три поставщика однородного товара с объемами поставок: а₁=100т, а₂= 200т, а₃=100т, и четыре потребителя с объемами потребления b₁=80т,b₂=120т,b₃=150т,b₄=50т. Стоимость транспортных расходов изменяется в определенном диапазоне в зависимости от загрузки дороги, и задана матрицей

от 5 до 11 от 4 до 1 8 от 3 до 6

4 7 от 4 до 10 от 7 до 4

5 3 6 от 1 до 10

Определить оптимальное решение перевозок, обеспечивающее минимальные транспортные затраты.

Решение. В матрицу расходов введем параметр l, где 0£l£3. Получим

5+2l 4-l 8 3+l

4 7 4+2l 7-l

5 3 6 1+3l

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

В таблице a_i и b_j потенциалы строк и столбцов. Для занятых клеток они определяются из условия

a_i+b_j = c¢_ij+ dc²_ij

Полагая:

a₁+b₁=5+2la₁=0 a₁=0

a₁+b₂=4-la₂=-1-2l a₂=-1-2l

a₂+b₁=4 a₃=-1+l

a₂+b₃=4+2lb₁= 5+2l b₁=5+2l

a₃+b₂=3 b₂= 4-l

a₃+b₄=1+3lb₃=5+4l b₃=5+4l

b₄=2+2l b₄=2+2l

Оценки свободных клеток находим по формуле

D_ij=a_i+b_j – (c¢_ij+ dc²_ij)=

D₁₃=a₁+b₃ – c¢₁₃=5+4l+0-8= -3+4l,

D₁₄=a₁+b₄ – (c¢₁₄+lc²₁₄)=2+2l+0-3-l= -1+l,

D₂₂=a₂+b₂ – c¢₂₂ = -1-2l+4-l-7= -4-3l.

Аналогично находим, что D₂₄=-6+l, D₃₁=-1+3l, D₃₃=-2+5l.

Решение, полученное при l=0, является оптимальным для всех значений параметра l, удовлетворяющих условию

Так как по условию задачи l³0,то оптимальное решение сохраняется при 0£l£1/3. При этом минимальная стоимость транспортных расходов составляет

F(x)_min=30(5+2l)+70(4-l)+50*4+150(4+2l)+50*3+50(1+2l)=1430+440l

Таким образом, при lÎ[0;1/3], F(x₁)_min=1430+440l и

30 70 0 0

Х_опт1= 50 0 150 0

0 50 0 50

Чтобы получить оптимальное решение при l³1/3, перераспределим поставки товаров в клетку (3,1), где l₂=1/3. Вновь полученное распределение представлено в таблице.

Находим оценки свободных клеток:

D₁₁=1-3l, D₁₃= -2+l,

D₁₄= -1+l, D₂₂= -5,

D₂₄= -7+4l, D₃₃= -1+2l.

Определим пределы изменения l:

Полученное в таблице оптимальное решение сохраняется при 1/3£l£1/2. При этом F(x₂)_min=1460+350l.

0 100 0 0

Х_опт2= 50 0 150 0

30 20 0 50

Перераспределим поставки грузов в клетку (3,3), где l₂=1/2. Получим новое распределение:

Находим оценки свободных клеток:

D₁₁=2-5l, D₁₃= -1-l,

D₁₄= -1+l, D₂₂= -6+2l,

D₂₄= -8+6l, D₃₃= -1-2l.

Определим пределы изменения l:

Оптимальное решение сохраняется при 1/2£l£1. При этом F(x₃)_min=1490+290l.

0 100 0 0

Х_опт3= 80 0 120 0

0 20 30 50

Перераспределим поставки товаров в клетку (1,4), где l₂=1.

Оценки свободных клеток:

D₁₁=-1-2l, D₁₃= -1-l,

D₂₂= -6+2l, D₂₄= -7+5l,

D₃₁= 1-2l, D₃₄= -1-l.

Пределы изменения l:

Полученное в предыдущей таблице оптимальное решение сохраняется при 1£l£7/5. При этом F(x₄)_min=1540+240l.

0 50 0 50

Х_опт4= 80 0 120 0

0 70 30 0

Перераспределим поставки грузов в клетку (2,4), где l₂=7/5.

Оценки свободных клеток:

D₁₁=2-5l, D₁₃= -1-l,

D₁₄= 7-5l, D₂₂= -6+2l,

D₃₁= 1-2l, D₃₄= -8-6l.

Пределы изменения l:

l₁ =max (2/5;-1;7/5;1/2;-8/6)=7/5,b_ij<0;

l₂=min (3)=3,b_ij>0.

Оптимальное решение сохраняется при 7/5£l£3. При этом F(x₅)_min=1890-10l.

0 100 0 0

Х_опт5= 80 0 70 50

0 20 80 0

Варианты контрольной работы по теме «Параметрическая транспортная задача»

Имеются три поставщика однородного товара с объектами поставок: а₁=100 т., а₂=200 т., а₃=100 т. И четыре потребителя с объектами потребления b₁=80 т., b₂=120 т., b₃=150 т., b₄=50 т. Стоимость транспортных расходов изменяется в определенном диапазоне в зависимости от загрузки дороги, и задана матрицей

Определить оптимальное решение, обеспечивающее минимальные транспортные затраты.

Date: 2015-07-27; view: 473; Нарушение авторских прав