книги / Математические методы принятия решений

Номер

итерации

г= 1

г= 2

г= 3

г = 4

Т аблица 5 .1

Симплекс-таблицы для линейной задачи параметрического программирования

Х\	Х2	Хъ	X4	X5	a-o	Базис
- 1	ш	1	0	0	4	x 3
1	1	0	1	0	5	3C4
2	- 1	0	0	1	8	x 5
- 2	- 3	0	0	0	0	- a l
- t	t	0	0	0	t	—bjt
1/2	1	1/2	0	0	2	X2
3/2	0	—1/2	1	0	3	X4
3/2	0	1/2	0	1	10	x 5
- 7 / 2	0	3/2	0	0	6	-al.
- i / 2	0	- t i l	0	0	- t
0	1	1/3	1/3	0	3	x 2
1	0	- 1 / 3	Ш	0	2	X\
0	0	m	- 1	1	7	x 5
0	0	1/3	7/3	0	13	- a l
0	0	- l t /Ъ	t/3	0	0	-b]t
		71 = -	1
1/2	1	1/2	0	0	2	x 2
3 /2	0	- 1 / 2	1	0	3	X4
3/2	0	1/2	0	1	10	x 5
- 7 / 2	0	3 /2	0	0	6	~ a0-
-< /2	0	—t/2	0	0	- t

71 = +1

г = 4	0	1	0	2/3	- 1 / 3	2/3	x 2
	1	0	0	1/3	1/3	13/3	X\
	0	0	1	-1	1	7	x3
	0	0	0	8/3	- 1 / 3	32/3	- a 05.
	0	0	0	-t/3	2f/3	14f/3	-b*t
г — 5	0	3/2	0	1	- 1 / 2	1	X4
	1	- 1 / 2	0	0	1/2	4	x 2
	0	1	1	0	1/2	8	x 3
	0	- 8 / 2	0	0	1	8	—a l
	0	t/2	0	0	t/2	5t	-Щг

решения задачи определены неоднозначно. Если существует вто­ рое базисное решение, то, изменяя базис, можно задавать соседнюю критическую область значений t. Если при попытке заменить базис обнаружена неограниченность решения, то гиперплоскость, соот­ ветствующая целевой функции при рассматриваемом ее значении, оказывается параллельной одной из граней выпуклого многогран­ ника, определяемого системой ограничений задачи. Такая грань со­ держит точки, хотя бы одна из координат которых сколь угодно велика по абсолютному значению. В этом случае достигнута конеч­ ная нижняя (верхняя) грань области Q. Пусть при построении кри­ тической области стало известно, что некоторая точка найденного интервала имеет координату, меньшую (большую), чем координата верхней (нижней) границы интервала, полученного на предыдущем шаге построения. В таком случае говорят, что эта верхняя (ниж­ няя) граница превзойдена. Тогда сама эта верхняя (нижняя) граница является и нижней (верхней) границей строящегося интервала.

Определим критическое значение tp = т£. Индекс к ——1 применяют при нахождении нижней границы области Q, индекс к = +1 — при нахождении верхней границы. В нашем случае г = 3; ищем нижнюю границу области Q, т. е. к = —1. Положив р = к = —1 (для bj > 0, j = 1 ,2,..., п + т), получим

t - 1 = m i! = max j — —o o | = —7.

Из табл. 5.1 для r = 3	следует, что при	t = l получим /(t) =13,
х\ = 2(1 —X), Х2 = 2Х +	3(1 —X), 0 ^ X ^	1. Это критическое значе­

ние может быть превзойдено. В табл. 5.1 при г = 3 выбран разре­ шающий элемент, равный 2/3 при j = 4. Общее условие для выбора этой небазисной переменной имеет вид

Тр е {т | OQX + b(>Ttp = 0, xz —небазисная переменная}.

Здесь т = 4.

Получим новые значения элементов табл. 5.1 при к = —1 и г = 4, которые совпали с элементами этой таблицы при г = 2. Поскольку все bj отрицательны или равны нулю, то t _2 = —00 и является ниж­ ней границей области Q. Из табл. 5.1 при г = 4 и t < —7 получаем,

ЧТО f(t) = 6 - t , X \ = 0, Х2 = 2.

Найдем верхнюю границу области Q, полагая тс = р = +1, г = 3. Тогда для bj < 0, j = 1,2, ... , п + т, имеем

t +1 = m + , = m i n | - - | ^ ; + о о |	2'
При t = 1/2 получим /(t) = 13, х\ = 2Х + 13(1 —Х)/3, х2 =
= ЗХ + 2(1 —Х)/3, 0 < X < 1.

Выбираем разрешающий элемент из столбца для хз и вычис­ ляем новые элементы табл. 5.1 при тс = +1 и г = 4, откуда найдем новое t+2, превышающее критическое значение £+1 = 1/2. Получим

новое значение £+i при —7 < t < 1/2, /(£) =				13, х\ = 2, хг = 3:
t+\ = т +j = min { - Г		Г ^	’ + 0 ° } =		:
При t = 8 имеем
/(£) = у (32+ 14-8) = 48,	х , = у Х		+ 4(1 -Х ),
при 1/2 < t < 8 имеем
32 + 14f	^	13	,	Л	2
?(t) =	Х ! = Т			Х2 =	т .

Строим табл. 5.1 при г = 5 и тс = +1. Получаем t > 8. Окончательные результаты приведены в табл. 5.2. На рис. 5.1

показаны «вращение» целевой функции, поведение решающей функции /(£) и геометрические образы отношений x\(t) и х2(£).

Алгоритм решения линейной параметрической задачи в слу­ чае зависимости от параметра коэффициентов целевой функции в предположении, что допустимая область, заданная ограничения­ ми задачи, не пуста и что для некоторого значения параметра t = to существует оптимальное решение, имеет следующий вид.

1.При t = to г-я симплекс-таблица является оптимальной. По­ лагаем тс = —1, р = тс и переходим к п. 2.

2.Определяем критическое значение tp = т гк:

а) если \tp\= оо, то достигнута граница области Q;

а') при тс = —1 находим нижнюю границу области Q, затем по­ лагаем тс = +1, р = тс, заменяем г на г + р + 1 и определяем новое критическое значение tp;

				Таблица 5 .2
	Решение параметрической задачи
	t	№		X2
	t < - l	6 — t	0	2
	t = - l	13	2 ( 1 - X )	2X + 3 ( 1 - X )
	—7 < * < y	13	2	3
	1	13	2X+ 13(1, - X)	зх + 2(|Г х)
	2
				D
	i < * < 8	32 + 141	13	2
		3	3	3
	2
	t = 8	48	13X ................	2X
			— + 4 ( 1 — X)	T
	t> 8	8 + 51	4	0
	а") при к = +1 находим верхнюю границу области Q и перехо­
	дим к п. 3;
	б) если \tp\ < о о ,	то определяем, можно ли превзойти критиче­

ское значение tp: с помощью выражения для т£, иногда выбором

*2(0

Рис. 5.1. Решение задачи параметрического линейного программирова­ ния: а —«вращение» целевой функции; б —поведение х \(t), x2(t) и решающей функции /(£) в зависимости от параметра t

из нескольких возможных значений, определяем новую базисную переменную; в этом случае следует учитывать существование мно­

жества различных решений;
б') если а ” ^ 0, г = 1,2,	то достигнута граница обла­

сти Q; переходим к п. а') или п. а");

б") в противном случае строим новую симплекс-таблицу; заме­ няя г на г + 1 , р на р + к, определяем новое критическое значе­ ние tp.

3. Вычисления прекращаем. Для каждой критической области значение решающей функции /(£) берем из табл. 5.1. Там же опре­

делены оптимальные значения решающих отношений Si (£),...

..., x n ( t).

На практике часто возникают следующие частные случаи пара­ метрической задачи:

1)значение параметра t принадлежит некоторому заранее вы­ бранному интервалу L c R 1;

2)требуется найти только минимум (максимум) решающей

функции /(£) для всех t e R 1, т.е. требуется определить те значе­ ния t, при которых возможно достижение этого минимума (макси­ мума);

3) требуется найти интервал возможных изменений какого-то одного из коэффициентов целевой функции.

Особый интерес представляет задача нахождения наибольше­ го отрезка t\ такого, что оптимальное базисное решение любой из задач, принадлежащих значениям t из этого отрезка, сов­ падает с оптимальным базисным решением задачи, принадлежащей значению t = 0.

Если область определения Q решающей функции /(£) ограни­ чена заданным заранее интервалом L, то вычисления, проводимые в п. 2 алгоритма, заканчивают, когда будут достигнуты границы интервала L. Если отрезок £_ i ^ t ^ t+\ не имеет общих точек с ин­ тервалом L, то полагают к = —1 или к = +1 в зависимости от того, будут ли значения t e L меньше t- \ или больше t +\.

Если в задаче необходимо установить только минимум (макси­ мум) значения решающей функции /(£), то вычисления, предписы­ ваемые п. 2, проводят при к = —1 или к = +1 в зависимости от того, в каком направлении уменьшается значение функции /(f).

Пусть необходимо определить только возможность вариации од­ ного из коэффициентов. Сначала устанавливают, существует ли ре­ шение при t = 0, и находят это решение. Вводя затем параметр t, определяют значения t- \ (равные ti) и t+\ (равные <г).

§ 5.3. Многопродуктовые потоки в сетях

Существует немало практических задач о перевозке нескольких различных продуктов.

Рассмотрим упрощенную задачу [78] транспортировки трех ви­ дов фруктов из садов, расположенных в Калифорнии, в магазины, ведущие оптовую торговлю. Предположим, что сады расположе­ ны в городах Санта-Барбара, Бейкерсфилд и Сакраменто. В период уборки урожая из этих садов поставляют в различных количествах апельсины, лимоны и лаймы (табл. 5.3).

Таблица 5.3

Производительность (ящики в неделю)

	Город	Перевозимый продукт
		Апельсины	Лимоны	Лаймы
	Санта-Барбара	800	700	7 0 0
	Бейкерсфилд	1000	800	5 0 0
	Сакраменто	500	1000	5 0 0

По контракту необходимо доставлять в оптовые магазины, рас­ положенные в Денвере, Сиэтле и Канзас-Сити, такое количество фруктов, которое указано в табл. 5.4. Перевозка осуществляется по железной дороге, однако в каждом поезде для фруктов отведено ограниченное место. Пропускные способности путей между раз­ личными пунктами отправления и пунктами назначения приведены

Таблица 5.4

Величина спроса (ящики в неделю)

	Город	Перевозимый продукт
		Апельсины	Лимоны	Лаймы
	Денвер	9 0 0	9 0 0	7 0 0
	Сиэтл	7 0 0	1000	500
	Канзас-Сити	700	6 0 0	5 0 0

в табл. 5.5. Независимо от вида фруктов данные величины зада­ ются числом ящиков, перевозимых в неделю (предполагается, что все фрукты упакованы в ящики одинаковых размеров). Вес каждого ящика, а следовательно, и соответствующие транспортные затраты зависят от вида упакованных в него фруктов. Затраты на транспор­ тировку одного ящика приведены в табл. 5.6.

Таблица 5.5

Пропускная способность железных дорог (ящики в неделю)

	Из города		В город
		Денвер	Сиэтл	Канзас-Сити
	С анта-Барбара	1200	9 0 0	1000
	Бейкерсф илд	1200	1000	1100
	С акраменто	9 5 0	1300	1000

Таблица 5.6

Транспортные затраты (центы за ящик)

	Из города		В город
		Денвер	Сиэтл	Канзас-Сити
	С анта-Барбара
	Апельсины	3,2	2,5	5 ,6
	Лимоны	2 ,4	1,9	4 ,3
	Лаймы	2,3	1,7	4 ,0
	Бейкерсф илд
	Апельсины	3,0	2,1	5,5
	Лимоны	2,3	1,7	4 ,4
	Лаймы	2 ,0	1,4	4,3
	С акраменто
	Апельсины	3,1	2 ,0	5 ,7
	Лимоны	2,2	1,6	4 ,8
	Лаймы	2 ,0	1,5	4,3

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

ограничен ее пропускной способностью. Если бы это было не так, то можно было бы для каждого продукта независимо решить минимизационную транспортную задачу. Однако указанные выше огра­ ничения на пропускные способности дуг существенно усложняют решение задачи.

Задачи о многопродуктовом потоке, как и об однопродукто­ вом потоке, могут быть сформулированы в виде задач линейного программирования. Задача о транспортировке фруктов является примером многопродуктовой транспортной задачи.

Обозначим через поток fc-ro продукта из г-го источника в j -й

сток, а через с - — стоимость транспортировки единицы этого про­ дукта. Пусть далее а \ и bj — это соответственно предложение узла г и спрос узла j для k-ro продукта, а иц —пропускная способность дуги (г, j). Математическая постановка многопродуктовой транс­ портной задачи выглядит следующим образом:

г т п

E E S 4 4		^ min	(5-2)
к=\ г= 1 j=1
при у с л о в и и , ЧТО
г		j , k € N,
з
xij ^	uij>	3 ^
к
X i j ^ о ,	i, j, k e N .

Как и в однопродуктовой транспортной задаче, предполагается, что для каждого продукта суммарное предложение равно суммар­ ному спросу, т. е. для всех к

i j

Во многих задачах, называемых многопродуктовыми задача­ ми о перевозках, вводят промежуточные узлы, т. е. такие узлы,

которым не приписывают ни спрос, ни предложение, а только тре­ буют, чтобы для них выполнялось условие сохранения потока.

В качестве одного из таких примеров рассмотрим сеть, изоб­ раженную на рис. 5.2. Узлы / и 2 являются источниками первого продукта, при этом узел 2 —источник второго продукта. Узел 5 является пунктом назначения для обоих продуктов, а узлы 3 и 4 являются промежуточными.

Рис. 5.2. Сеть в многопродуктовой задаче о перевозках

Многопродуктовая задача о перевозках может быть сформули­ рована в виде следующей задачи линейного программирования:

			S	2 4 4 , -» min
			fc=i (i,j)eA
при условии, что:
1)	2	xij ~ 2	xji = ai>если Узел * является источником к-го про-
дукта; з		з
2)	2	x ij ~ H xji = 0»если Узел * является промежуточным узлом;
	3	3
3)	2	x ij ~ 2	xji = ~bj> если узел j является стоком к-го про­
дукта; 1
4 ) 2		х кц ^ Щj, а& ^ 0 для всех к и (г, j ) 6 А, где А — множество
	к

дуг сети.

Одна из трудностей решения задачи о многопродуктовом по­ токе вызвана тем, что оптимальные решения могут быть неце­ лочисленными. В качестве примера рассмотрим двухпродуктовую транспортную задачу, сетевая формулировка которой представлена на рис. 5.3. Дугам сети приписаны числа (cjj, cfj, и^). Оптимальное решение соответствующей задачи линейного программирования представлено в табл. 5.7.

ь) ъ)

2 2

2 2

2 2

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

Таблица 5.7 Оптимальное решение задачи линейного программирования

Дуга		Продукт 1	Продукт 2
0 , 1 )		3 /2	1/2
(1 ,2 )		0	3/2
(1 ,3 )		1/2	0
(2 ,1 )		0	3/2
(2, 2)		2	0
(2, 3)		0	1/2
(3,	1)	1/2	0
(3 ,2 )		0	1/2
(3,	3)	3 /2	3/2

матрицы ограничений является достаточным для существования це­ лочисленных оптимальных решений. Поскольку в задачах об одно­ продуктовом потоке данное условие выполнено, то для них можно разработать высокоэффективные алгоритмы, в которых по существу выполняются только две операции: сложение и вычитание, а такие операции, как, например, деление и обращение матрицы, не требу­ ются. С вычислительной точки зрения арифметические операции, выполняемые с целыми числами, проводятся намного быстрее, чем операции, использующие числа с плавающей точкой (десятичные).