Транспортная параметрическая задача

↑

▷ Содержание

⇐ ПредыдущаяСтр 17 из 20Следующая ⇒

Суть ТПЗ заключается в том, что затраты на перевозку от какого-то поставщика к какому-то потребителю, в силу разных причин не остаются постоянными, а меняются в течение планового периода, т.е. целевая функция выглядит следующим образом:

где:
- целея часть затрат;
- переменная часть затрат.

Задача формулируется следующим образом: для всех значений параметра d£l£j, где d,j - произвольные действительные числа, найти такие значения x_ij ( которые обращают в минимум функцию.

При ограничениях:

Алгоритм решения ТПЗ:

1. Пользуясь методом потенциалов, решаем задачу при l=d до получения оптимального решения. Признаком оптимальности являются условия:

для незанятых клеток,

для занятых клеток,

где a_i и b_j - потенциалы строк и столбцов.

Оценки представим в виде ∆_ij=μ_{ij +} lυ_ij

2. Вычисляем интервал значений , при котором этот план остаётся постоянным. Вычисляем значение целевой функции.

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

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

Имеются три поставщика однородного товара с объемами поставок: а₁=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 потенциалы строк и столбцов. Для занятых клеток они определяются из условия

,

тогда:

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

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

Найдём диапазон изменения l, при котором решение будет оставаться оптимальным из условия:

Изобразим решение графически и найдём область допустимых значений для параметра l.

ОДР

-4/3 0 1/3 2/5 3/4 1 6

То есть полученный план будет сохранять оптимальность при значении от -4/3 до 1/3. Так как по заданию ³0, то интервал оптимальности: 0£ £1/3.

Нетрудно заметить, что нижняя граница определяется неравенствами (оценками) вида , а верхняя из неравенств (оценок) вида , т.е.

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

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

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 и

х_опт2=

Мы выяснили, что если l≥ , то оценка клетки (3,1) становится положительной, например l= 0,4, тогда ₃₁= -1 + 3l = -1 +3+0,4=0,2 > 0,4, следовательно полученный план становится неоптимальным. Чтобы получить оптимальное решение при l ≥ перераспределим поставки в клетку (3,1), где l , по соответствующему контуру.

30 _(1,1) 70_{(1,2) (1,1)} 100 _(1,2)

_(3,1) 50 _(3,2) 30 _(3,1) 20_(3,2)

Вновь полученное распределение представлено в таблице.

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

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

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

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

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

l₁= max

l₂ = min =min = ,

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

Х_опт2=

Замечание. На каждом шаге необходимо проверить правильность решения, а именно: значение целевой функции при равной верхней границы на предыдущем шаге должно быть равно значению целевой функции при равной нижней границе на последующем шаге. В нашем примере целевая функция при 0 равна 1430 + 440l, а при =1460 + 350l, т.е. при l =

F₁(x) _опт = 1430 + 440* = 4730

F₂(x) _опт = 1460 + 350* = 4730

Значения F(x) совпадают, значит, решение верно

Проведя аналогичные вычисления на последнем шаге получаем

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

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, _ij<0;

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

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

Вывод

При l х₁₁=30, х₁₂=70, х₂₁ =50, х₂₃=150, х₃₂=50, х₃₄=50. F(x) =1430+440

При l х₁₂=100, х₂₁=50, х₂₃=150, х₃₁=30, х₃₂=20, х₃₄=50. F(x)=1460+350

При l х₁₂=100, х₂₁=80, х₂₃=120, х₃₂=20, х₃₃=30, х₃₄=50.F(x)=1490+290

При l х₁₂=50, х₁₄=50, х₂₁=80, х₂₃=120, х₃₂=70, х₃₃=30. F(x)=1540+240

При l х₁₂=100, х₂₁=80, х₂₃=70, х₂₄=50, х₃₂=20, х₃₃=80. F(x)=1890-10

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

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

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

Тестовое задание к транспортной параметрической задаче (ТПЗ)

1.Целевая функция ТПЗ записывается как:

2.Ограничения ТПЗ совпадают с ограничениями классической транспортной задачей.

1.да; 2.нет.

3.Решение ТПЗ методом потенциалов при начинается при значении

1. = 0; 2. = 5;

3. = любому числу; 4. = любому числу в интервале 0-5.

4.В полученном плане ТПЗ потенциал первой строки равен 0, тогда потенциал второго столбца равен:

1. 5+ ; 2. - 3. 7; 4. 4-

5. В полученном плане ТПЗ потенциал второй строки равен: -1+ , тогда потенциал первого столбца равен:

1. 5- ;2. 5; 3. 4; 4.6- .

6.Для плана ТПЗ потенциалы рассчитали:

1. верно; 2. неверно; 3. ответ дать невозможно.

7.Для плана ТПЗ оценка клетки 1.1 равна:

1. 4+2l; 2. 10; 3. -6+2l; 4. 10+2l.

8. На предыдущем шаге ТПЗ значение целевой функции равно 1000+200l, при 0 ; На следующем шаге получено значение целевой функции 1500-200l. Решение:

1. верно; 2. неверно.

9. На очередном шаге решения ТПЗ получены следующие оценки свободных клеток:

D₁=1-3l; D₂= -1+l; D₃= -7+4l; D₄= -2+l; D₅ = -5; D₆= -1+2l, тогда пределы изменения l, при котором найденный план будет оптимальным:

1. (1-2); 2. ; 3. ; 4. .

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры