Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Лабораторная работа № 25. «Параметрическая транспортная задача с параметром в целевой функции» ⇐ ПредыдущаяСтр 5 из 5
Теоретическая часть При решении транспортных задач мы рассматривали перевозку однородного груза. Часто на практике решают параметрические транспортные задачи с параметром в целевой функции, то есть коэффициенты транспортных затрат заданы с параметром. Так при перевозке груза разными марками автомашин с неодинаковой грузоподъёмностью затраты на перевозку одной тонны груза могут изменяться. В этом случае возможность изменения коэффициентов транспортных затрат учитывается с помощью параметра. Параметр t задаётся на интервале [a, b], a – нижняя (начальная) граница интервала, b – верхняя (конечная) граница данного интервала.
Алгоритм решения параметрической транспортной задачи с параметром в целевой функции 1. Записывают условие транспортной задачи в распределительную таблицу, причём коэффициенты транспортных затрат - с параметром t. 2. Проверяют, является ли модель задачи закрытой. Если да, то переходят к пункту 3, если нет, то введением фиктивного отправителя или фиктивного потребителя сводят задачу к закрытой модели. 3. Если навык решения транспортной задачи есть, то мысленно, если нет, то письменно полагают t=t нижней границе рассматриваемого интервала. 4. Любым известным методом находят оптимальный план (оптимальное решение) грузоперевозок при этом t. 5. Выписывают характеристики свободных переменных (клеток) для оптимального решения и составляют неравенства, наложив на них условие неположительности. 6. Из решения системы неравенств неположительности характеристик свободных клеток определяют интервал, на котором найденный план грузоперевозок останется оптимальным (t нижняя граница£ t £ £ t верхняя граница). 7. Проводят преобразование однократного замещения по циклу свободной клетки, характеристика которой при подстановке t=tверхняя граница обратится в ноль, а при подстановке t> tверхняя граница станет положительной. 8. Переход к пункту 5. Процесс решения выполняется до тех пор, пока не будет исследован весь заданный интервал изменения параметра t. Замечание. Преобразование однократного замещения по циклу свободной клетки – это нахождение l= min{xij} в четных клетках цикла, перемещение l по вершинам цикла (прибавление l к переменным в нечётных вершинах цикла и вычитание l из переменных в чётных вершинах цикла). Переменная, находящаяся в свободной клетке цикла, становится базисной, свободная клетка цикла становится занятой, а одна из базисных переменных (из клеток) цикла становится свободной. При этом ранг задачи не меняется. Баланс строчек и столбцов таблицы не нарушается.
Пример выполнения работы Задание. Записать транспортную задачу с параметром в целевой функции в распределительную таблицу и решить её. Необходимо перевезти груз от трёх поставщиков пяти потребителям с минимальными затратами на грузоперевозку. Ресурсы, потребности и коэффициенты транспортных затрат даны в таблице. Параметр t принадлежит интервалу [0, 1].
Найдём исходное опорное решение методом минимального элемента в таблице, приняв t=0.
Проверяем решение на оптимальность. Находим потенциалы по формуле: Cij = Ui +Vj, где U1 =0, Cij - коэффициенты транспортных затрат базисных клеток (переменных). Вычисляем характеристики свободных клеток по формуле: Dij =(Ui +Vj)-Cij. Тогда D11=(0-t+2)-(1+t)=1-2t; D12=(0+t)- (12-t)=2t-12; D14=(0+3-t)- (1+2t)=2-3t; D15=(0+0)- (2-t)=t-2; D21=(1-t+2)- 2=1-t; D25=(0+1)- (6-t)=t-5; D32=(2t-1+t)-(4-t)=4t-5; D33=(2t-1+2t)- (3-t)=5t-4. Решение неоптимальное, так как при t=0 есть неотрицательные характеристики (оценки) свободных клеток. Это D11=1; D14=2; D21=1; выбираем среди них максимальную. D14=2 - максимальная неотрицательная характеристика. Для этой клетки строим замкнутый цикл: [1, 4]-[1, 3]-[2, 3]-[2, 4]-[1, 4], имеющий соответственно знаки вершин: +, -, +, -. l=5. Перемещаем l=5 по циклу. Строим новую таблицу.
Проверяем решение на оптимальность. Находим потенциалы по формуле: Cij = Ui +Vj, где U1 =0, Cij - коэффициенты транспортных затрат базисных клеток (переменных). Вычисляем характеристики свободных клеток по формуле: Dij =(Ui +Vj)-Cij. Тогда D11=(0+2t)-(1+t)= -1+t; D12=(0+t)- (12-t)=2t-12; D15=(0+3t-2)- (2-t)=4t-4; D21=(1+2t)- 2= -1+2t; D24=(1+1+2t)- (4-t)=--2+3t; D25=(1+3t-2)- (6-t)=4t-7; D32=(-t+1+t)-(4-t)=t-3; D33=(2t-t+1)- (3-t)=2t-2.
Решение оптимальное, так как при t=0 все характеристики (оценки) свободных клеток неположительные. Находим интервал изменения t, на котором решение остаётся оптимальным. Выписываем характеристики свободных переменных (клеток) для оптимального решения и составляем неравенства, наложив на них условие неположительности. Dij =(Ui +Vj)-Cij £ 0.
Получаем систему: -1+t£ 0; 2t-12£ 0; 4t-4£ 0; -1+2t£ 0; -2+3t£ 0; 4t-7£ 0; t-3£ 0; 2t-2£ 0. Откуда: t£ 1; t£ 6; t£ 1; t£ 0, 5; t£ 2/3; t£ 7/4; t£ 3; t£ 1. Решением системы является tÎ (-¥; ½ ]. По условию tÎ [0; 1]. Поэтому суживаем интервал изменения t. Получаем при tÎ [0; ½ ] сохраняется оптимальное решение X= min Z= 2t× 15+(1+2t)× 5+ (1+t ) × 20+(2t+1)× 10+(t+1)× 10 +(t+2)× 10 +(2t-1)× 30= =30t +5+10t+20+20t+20t+10+10 t+10+10 t+20+60t-30= 160 t+35. Переходим к новой распределительной таблице. Проводим преобразование однократного замещения по циклу свободной клетки, характеристика которой при подстановке t=tверхняя граница обратится в ноль. Это клетка [2, 1]. Строим для неё цикл: [2, 1]-[2, 3]-[1, 3]-[1, 4]-[3, 4]-[3, 1]-[2, 1]. Из переменных в нечётных клетках (с отрицательными вершинами цикла) выбираем l=5. Перемещаем l=5 по циклу. Заполняем следующую таблицу.
Проверяем балансы строк, балансы столбцов и ранг. Всё совпадает; таблица построена верно. Проверяем решение на оптимальность. Подсчитываем потенциалы строк и столбцов и вносим их в таблицу. Находим характеристики (оценки) свободных клеток. Dij =(Ui +Vj)-Cij. Тогда D11=(0-1)-(1+t)= -t; D12=(0+t)- (12-t)=2t-12; D14=(0+2)- (1+2t)=1-2t; D15=(0+ t-1)- (2-t)=2t-3; D24=(1+2)- (4-t )=-1+ t; D25=(1+ t-1)- (6-t)=2t-6; D32=(t+t)-(4-t)=3t-4; D33=(t+2t)- (3-t)=4t-3. При t=1/2 все характеристики неположительные. Следовательно, решение оптимальное. Находим интервал изменения t, на котором решение остаётся оптимальным. Выписываем характеристики свободных переменных (клеток) для оптимального решения и составляем неравенства, наложив на них условие неположительности. Dij =(Ui +Vj)-Cij £ 0. Получаем систему: Dij =(Ui +Vj)-Cij. Тогда D11=(0-1)-(1+t)= -t; D12=(0+t)- (12-t)=2t-12; D14=(0+2)- (1+2t)=1-2t; D15=(0+ t-1)- (2-t)=2t-3; D24=(1+2)- (4-t )=-1+ t; D25=(1+ t-1)- (6-t)=2t-6; D32=(t+t)-(4-t)=3t-4; D33=(t+2t)- (3-t)=4t-3. -t£ 0; 2t-12£ 0; 1-2t£ 0; 2t-3£ 0; -1+ t£ 0; 2t-6£ 0; 3t-4£ 0; 4t-3£ 0. Откуда: t³ 0; t£ 6; t³ 1/2; t£ 3/2; t£ 1; t£ 3; t£ 4/3. t£ 3/4. Решением системы является tÎ [1/2; 3/4]. По условию tÎ [0; 1]. Поэтому весь интервал не исследован. Получаем при tÎ [1/2; 3/4] сохраняется оптимальное решение X= min Z= 2t× 20+2× 5+ (1+t ) × 20+(2t+1)× 5+(t+1)× 5 +(t+2)× 15 +(2t-1)× 30= =40t +10+20+20t+10t+5+5t+5+15t+30+60t-30= 150 t+40. Переходим к новой распределительной таблице. Проводим преобразование однократного замещения по циклу свободной клетки, характеристика которой при подстановке t=tверхняя граница обратится в ноль. Это клетка [3, 3]. Строим для неё цикл: [3, 3]-[2, 3]-[2, 1]-[3, 1]-[3, 3]. Из переменных в нечётных клетках (с отрицательными вершинами цикла) выбираем l=5. Перемещаем l=5 по циклу. Заполняем следующую таблицу.
Проверяем балансы строк, балансы столбцов и ранг. Всё совпадает; таблица построена верно. Проверяем решение на оптимальность. Находим интервал изменения t, на котором решение остаётся оптимальным. Выписываем характеристики свободных переменных (клеток) для оптимального решения и составляем неравенства, наложив на них условие неположительности. Dij = ( Ui +Vj)-Cij £ 0. Получаем систему: Dij =(Ui +Vj)-Cij. Тогда D11=(0+4t-2)-(1+t)= 3t-3; D12=(0+5t-3)- (12-t)=6t-15; D14=(0+4t-1)- (1+2t)= -2+2t; D15=(0+ 5t-4)- (2-t)=6t-6; D23=(4-4t+2t)- (2t+1)= -4t+3. D24=(4-4t+4t-1)- (4-t )= -1+ t; D25=(4-4t+5t-4)-(6-t)=2t-6; D32=(3-3t+5t-3)-(4-t)=3t-4; 3t-3£ 0; 6t -15£ 0; -2+2t£ 0; 6t-6£ 0; -4t+3£ 0; -1+t£ 0; 2t-6£ 0; 3t-4£ 0; Откуда: t£ 1; t£ 5/2; t£ 1; t£ 1; t³ 3/4; t£ 1; t£ 3; t£ 4/3. Решением системы является tÎ [3/4; 1]. По условию tÎ [0; 1]. Так как t=tверхняя граница=b=1, то поэтому весь интервал исследован.
Получаем, что при tÎ [3/4; 1] сохраняется оптимальное решение. Кроме того решение вырожденное, так как одна из базисных переменных (x31 =0) равна нулю. X= min Z= 2t× 20+2× 10+ (1+t ) × 20+( t+1)× 0 +(3-t)× 5+(t+2)× 15 +(2t-1)× 30= =40t +20+20+20t+0+15-5t+15t+30+60t-30= 130t+55.
Ответ. Заданный интервал изменения параметра t (tÎ [0; 1]) разбит на три интервала: на 1-ом интервале tÎ [0; ½ ] получено оптимальное решение X= min Z= 160 t+35; на 2-ом интервале tÎ [1/2; 3/4] получено оптимальное решение X= min Z= 150 t+40; на 3-ем интервале tÎ [3/4; 1] найдено вырожденное оптимальное решение X= min Z= 130t+55. Индивидуальное задание Общая постановка задачи Записать транспортную задачу с параметром в целевой функции в распределительную таблицу. Найти оптимальные планы перевозки однородного груза от поставщиков к потребителям, обеспечивающие минимальные транспортные расходы и учитывающие параметры в целевой функции. Исследовать весь интервал изменения параметра. |
Последнее изменение этой страницы: 2017-03-14; Просмотров: 520; Нарушение авторского права страницы