Лабораторная работа № 25. «Параметрическая транспортная задача с параметром в целевой функции»

Теоретическая часть

При решении транспортных задач мы рассматривали перевозку однородного груза. Часто на практике решают параметрические транспортные задачи с параметром в целевой функции, то есть коэффициенты транспортных затрат заданы с параметром. Так при перевозке груза разными марками автомашин с неодинаковой грузоподъёмностью затраты на перевозку одной тонны груза могут изменяться. В этом случае возможность изменения коэффициентов транспортных затрат учитывается с помощью параметра. Параметр 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{x_ij} в четных клетках цикла, перемещение l по вершинам цикла (прибавление l к переменным в нечётных вершинах цикла и вычитание l из переменных в чётных вершинах цикла). Переменная, находящаяся в свободной клетке цикла, становится базисной, свободная клетка цикла становится занятой, а одна из базисных переменных (из клеток) цикла становится свободной. При этом ранг задачи не меняется. Баланс строчек и столбцов таблицы не нарушается.

 

Пример выполнения работы

Задание. Записать транспортную задачу с параметром в целевой функции в распределительную таблицу и решить её.

Необходимо перевезти груз от трёх поставщиков пяти потребителям с минимальными затратами на грузоперевозку. Ресурсы, потребности и коэффициенты транспортных затрат даны в таблице. Параметр t принадлежит интервалу [0, 1].

Потребности   Ресурсы	b1	b2	b3	b4	b5
а1 20	1+t	12-t	2t	1+2t	2+t
а2 30		1+t	2t+1	4-t	6-t
а3 50	t+1	4-t	3-t	t+2	2t-1

Найдём исходное опорное решение методом минимального элемента в таблице, приняв t=0.

Потребности Ресурсы						Ui
	1+t	12-t	2t	1+2t	2-t
		1+t	2t+1	4-t	6-t
	t+1	4-t	3-t	t+2	2t-1	2t-1
Vj	-t+2	t	2t	3-t

Проверяем решение на оптимальность. Находим потенциалы по формуле: Cij = U_i +V_j, где U₁ =0, Cij - коэффициенты транспортных затрат базисных клеток (переменных).

Вычисляем характеристики свободных клеток по формуле:

D_ij =(U_i +V_j)-Cij. Тогда D₁₁=(0-t+2)-(1+t)=1-2t; D₁₂=(0+t)- (12-t)=2t-12;

D₁₄=(0+3-t)- (1+2t)=2-3t; D₁₅=(0+0)- (2-t)=t-2; D₂₁=(1-t+2)- 2=1-t;

D₂₅=(0+1)- (6-t)=t-5; D₃₂=(2t-1+t)-(4-t)=4t-5; D₃₃=(2t-1+2t)- (3-t)=5t-4.

Решение неоптимальное, так как при t=0 есть неотрицательные характеристики (оценки) свободных клеток. Это D₁₁=1; D₁₄=2; D₂₁=1; выбираем среди них максимальную. D₁₄=2 - максимальная неотрицательная характеристика. Для этой клетки строим замкнутый цикл: [1, 4]-[1, 3]-[2, 3]-[2, 4]-[1, 4], имеющий соответственно знаки вершин: +, -, +, -. l=5. Перемещаем l=5 по циклу. Строим новую таблицу.

Потребности Ресурсы						Ui
	1+t	12-t	2t	1+2t	2-t
		1+t	2t+1	4-t	6-t
	t+1	4-t	3-t	t+2	2t-1	-t+1
Vj	2t	t	2t	1+2t	3t-2

Проверяем решение на оптимальность. Находим потенциалы по формуле: C_ij = U_i +V_j, где U₁ =0, C_ij - коэффициенты транспортных затрат базисных клеток (переменных).

Вычисляем характеристики свободных клеток по формуле:

D_ij =(U_i +V_j)-C_ij. Тогда D₁₁=(0+2t)-(1+t)= -1+t; D₁₂=(0+t)- (12-t)=2t-12;

D₁₅=(0+3t-2)- (2-t)=4t-4; D₂₁=(1+2t)- 2= -1+2t; D₂₄=(1+1+2t)- (4-t)=--2+3t;

D₂₅=(1+3t-2)- (6-t)=4t-7; D₃₂=(-t+1+t)-(4-t)=t-3; D₃₃=(2t-t+1)- (3-t)=2t-2.

 

Решение оптимальное, так как при t=0 все характеристики (оценки) свободных клеток неположительные.

Находим интервал изменения t, на котором решение остаётся оптимальным. Выписываем характеристики свободных переменных (клеток) для оптимального решения и составляем неравенства, наложив на них условие неположительности. D_ij =(U_i +V_j)-C_ij £ 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 по циклу. Заполняем следующую таблицу.

 

Потребности Ресурсы						Ui
	1+t	12-t	2t	1+2t	2-t
		1+t	2t+1	4-t	6-t
	t+1	4-t	3-t	t+2	2t-1	t
Vj		t	2t		t-1

 

Проверяем балансы строк, балансы столбцов и ранг. Всё совпадает; таблица построена верно. Проверяем решение на оптимальность. Подсчитываем потенциалы строк и столбцов и вносим их в таблицу. Находим характеристики (оценки) свободных клеток.

D_ij =(U_i +V_j)-Cij. Тогда D₁₁=(0-1)-(1+t)= -t; D₁₂=(0+t)- (12-t)=2t-12;

D₁₄=(0+2)- (1+2t)=1-2t; D₁₅=(0+ t-1)- (2-t)=2t-3; D₂₄=(1+2)- (4-t )=-1+ t;

D₂₅=(1+ t-1)- (6-t)=2t-6; D₃₂=(t+t)-(4-t)=3t-4; D₃₃=(t+2t)- (3-t)=4t-3.

При t=1/2 все характеристики неположительные. Следовательно, решение оптимальное.

Находим интервал изменения t, на котором решение остаётся оптимальным. Выписываем характеристики свободных переменных (клеток) для оптимального решения и составляем неравенства, наложив на них условие неположительности. D_ij =(U_i +V_j)-C_ij £ 0.

Получаем систему:

D_ij =(U_i +V_j)-Cij. Тогда D₁₁=(0-1)-(1+t)= -t; D₁₂=(0+t)- (12-t)=2t-12;

D₁₄=(0+2)- (1+2t)=1-2t; D₁₅=(0+ t-1)- (2-t)=2t-3; D₂₄=(1+2)- (4-t )=-1+ t;

D₂₅=(1+ t-1)- (6-t)=2t-6; D₃₂=(t+t)-(4-t)=3t-4; D₃₃=(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 по циклу.   Заполняем следующую таблицу.

 

Потребности Ресурсы						Ui
	1+t	12-t	2t	1+2t	2-t
		1+t	2t+1	4-t	6-t	4-4t
	t+1	4-t	3-t	t+2	2t-1	3-3t
Vj	4t-2	5t-3	2t	4t-1	5t-4

Проверяем балансы строк, балансы столбцов и ранг. Всё совпадает; таблица построена верно. Проверяем решение на оптимальность.

Находим интервал изменения t, на котором решение остаётся оптимальным. Выписываем характеристики свободных переменных (клеток) для оптимального решения и составляем неравенства, наложив на них условие неположительности. D_ij = ( U_i +V_j)-C_ij £ 0.

Получаем систему:

D_ij =(U_i +V_j)-Cij. Тогда D₁₁=(0+4t-2)-(1+t)= 3t-3; D₁₂=(0+5t-3)- (12-t)=6t-15; D₁₄=(0+4t-1)- (1+2t)= -2+2t; D₁₅=(0+ 5t-4)- (2-t)=6t-6; D₂₃=(4-4t+2t)- (2t+1)= -4t+3. D₂₄=(4-4t+4t-1)- (4-t )= -1+ t; D₂₅=(4-4t+5t-4)-(6-t)=2t-6; D₃₂=(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] сохраняется оптимальное решение. Кроме того решение вырожденное, так как одна из базисных переменных (x₃₁ =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.

Индивидуальное задание

Общая постановка задачи

Записать транспортную задачу с параметром в целевой функции в распределительную таблицу. Найти оптимальные планы перевозки однородного груза от поставщиков к потребителям, обеспечивающие минимальные транспортные расходы и учитывающие параметры в целевой функции. Исследовать весь интервал изменения параметра.

⇐ Предыдущая12345

Поделиться: