Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Транспортная параметрическая задача
Суть ТПЗ заключается в том, что затраты на перевозку от какого-то поставщика к какому-то потребителю, в силу разных причин не остаются постоянными, а меняются в течение планового периода, т.е. целевая функция выглядит следующим образом:
где: Задача формулируется следующим образом: для всех значений параметра d£ l£ j, где d, j - произвольные действительные числа, найти такие значения xij ( которые обращают в минимум функцию.
При ограничениях:
Алгоритм решения ТПЗ:
1. Пользуясь методом потенциалов, решаем задачу при l=d до получения оптимального решения. Признаком оптимальности являются условия: для незанятых клеток, для занятых клеток, где ai и bj - потенциалы строк и столбцов. Оценки представим в виде ∆ ij=μ ij + lυ 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, решаем задачу методом потенциалов, определим оптимальное решение перевозок. Распределительная таблица этого решения будет иметь следующий вид.
В таблице 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, то интервал оптимальности: 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)
Вновь полученное распределение представлено в таблице.
Находим оценки свободных клеток: 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) совпадают, значит, решение верно Проведя аналогичные вычисления на последнем шаге получаем
Оценки свободных клеток: 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, тогда потенциал второго столбца равен:
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. На очередном шаге решения ТПЗ получены следующие оценки свободных клеток: 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; Просмотров: 845; Нарушение авторского права страницы