Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



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


 

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

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

 

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

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

 

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

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

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

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

Оценки представим в виде ∆ ijij + ij

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

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

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

Имеются три поставщика однородного товара с объемами поставок: а1=100т, а2= 200т, а3=100т, и четыре потребителя с объемами потребления b1=80т, b2=120т, b3=150т, b4=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, решаем задачу методом потенциалов, определим оптимальное решение перевозок. Распределительная таблица этого решения будет иметь следующий вид.

 

bj   ai ai
  5+2l 4-l 3+l
  4+2l 7-l -1-2l
    1+3l -1+l
bj 5+2l 4-l 5+4l 2+2l  

 

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

,

тогда:

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

Аналогично находим, что D24=-6+l, D31=-1+3l, D33=-2+5l.

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

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

 

ОДР

 

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

 

То есть полученный план будет сохранять оптимальность при значении от -4/3 до 1/3. Так как по заданию ³ 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(x1)min=1430+440l и

 

хопт2=

Мы выяснили, что если l≥ , то оценка клетки (3, 1) становится положительной, например l= 0, 4, тогда 31= -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)

 

 

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

bj   ai         ui
  5+2l   4-l 3+l
  4+2l 7-l -2+l
  1+3l -1+l
uj 6-l 4-l 6+l 2+2l  

 

 

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

D11=1-3l, D13= -2+l,

D14= -1+l, D22= -5,

D24= -7+4l, D33= -1+2l.

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

l1= max

l2 = min =min = ,

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

Хопт2=

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

F1(x) опт = 1430 + 440* = 4730

F2(x) опт = 1460 + 350* = 4730

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

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

bj   ai ui
  5+2l   4-l 3+l
  4+2l 7-l -3+3l
    1+3l -1+l
uj 7-3l 4-l 7-l 2+2l  

 

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

D11=2-5l, D13= -1-l,

D14= 7-5l, D22= -6+2l,

D31= 1-2l, D34= -8-6l.

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

l1 =max (2/5; -1; 7/5; 1/2; -8/6)=7/5, ij< 0;

l2=min (3)=3, ij> 0.

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

 

Вывод

При l х11=30, х12=70, х21 =50, х23=150, х32=50, х34=50. F(x) =1430+440

При l х12=100, х21=50, х23=150, х31=30, х32=20, х34=50. F(x)=1460+350

При l х12=100, х21=80, х23=120, х32=20, х33=30, х34=50.F(x)=1490+290

При l х12=50, х14=50, х21=80, х23=120, х32=70, х33=30. F(x)=1540+240

При l х12=100, х21=80, х23=70, х24=50, х32=20, х33=80. F(x)=1890-10

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

Имеются три поставщика однородного товара с объектами поставок: а1=100 т., а2=200 т., а3=100 т. И четыре потребителя с объектами потребления b1=80 т., b2=120 т., b3=150 т., b4=50 т. Стоимость транспортных расходов изменяется в определенном диапазоне в зависимости от загрузки дороги, и задана матрицей

 

 

 

 

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

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

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







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

1.да; 2.нет.

 

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

1. = 0; 2. = 5;

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

 

 

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

5+2l 4-l 70
4 7

 

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

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

4 7
5 3

 

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

 

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

7 4+2l   -3+3l
3 6   -1+l
  4-l   7-l ai bj

 

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

 

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

7 4+2l 70
3 6

 

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

 

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

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

 

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

D1=1-3l; D2= -1+l; D3= -7+4l; D4= -2+l; D5 = -5; D6= -1+2l, тогда пределы изменения l, при котором найденный план будет оптимальным:

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

 


Поделиться:



Последнее изменение этой страницы: 2017-04-13; Просмотров: 831; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.055 с.)
Главная | Случайная страница | Обратная связь