Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Транспортная параметрическая задача
Суть ТПЗ заключается в том, что затраты на перевозку от какого-то поставщика к какому-то потребителю, в силу разных причин не остаются постоянными, а меняются в течение планового периода, т.е. целевая функция выглядит следующим образом:
где: Задача формулируется следующим образом: для всех значений параметра 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-01-25; просмотров: 157; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.145.119.199 (0.152 с.) |