12.2. Аналитический метод решения задач параметрического программирования
Фиксируем значение t из заданного промежутка, допустим самое меньшее t = а. Тогда в целевой функции все коэффициенты станут постоянными.
Решаем полученную задачу симплекс-методом и находим вершину, в которой Za достигает максимума.Определяем все значения параметра для которых максимум достигается в той же вершине. Найденный интервал исключаем из заданного отрезка [а, Р]. Для оставшегося интервала снова решаем задачу, т. е. переходим к п.1 алгоритма. Так продолжаем до тех пор, пока не будет разделен на частичные интервалы весь отрезок[а, Р].
Проанализируем пункты алгоритма более подробно.
1. Полагая t = а, целевая функция принимает вид:
п
Za= I (су +dja)Xj.
М
Составляем первую симплекс-таблицу, добавляя две строки: для коэффициентов Cj и dj (табл. 12.1):
Таблица 12.1
Форма симплекс-таблицы для решения задачи параметрического программирования Свободный
Базисный Свобод-ные члены хь х2у... хп хп + 1 •• хп + т хп + 1 aij 1
1 1 хп + т <>т 1 Za 0 -(сх + dxa) ...
(сп + dna) 00... 0 Zt - СЬ - С2... 00... 0 - d{, - d2... ~dn 00... 0
В строке Za табл. 12.1 в каждом столбце фактически будет стоять одно число, равное Cj + djCL. В последних двух строках записаны индексы линейной формы Z, для произвольного параметра t.
Обычным симплекс-методом находим оптимальный план, причем этим же преобразованиям подвергаются элементы двух последних строк. В итоге получаем данные табл. 12.2.
Необходимо отметить, что в табл. 12.2 столбцы, соответствующие базисным переменным, являются нулевыми (т. е. содержат 1 на пересечении ^-столбца и ^-строки, а остальные нули).
Поскольку план, полученный в табл. 12.2, оптимален, все коэффициенты Za строки неотрицательны:
(Pj + <7/0 > 0.
После этого переходим ко второму пункту алгоритма.
Надо выделить интервал времени в котором максимум Z, достигается в той же вершине. Иными словами, надо найти такие значения t, дляОбщий вид оптимального плана Свободный
Базисный Свободные члены хь х2, ... хп —Х„ + 1 ... хп + т Х\ *s
хп + т Ъ\ h 1
1
1
1 Za P+Qa рх + qxa ... рп + qnа Рп + т + Яп + та А p Р\... Рп Рп + т Q Qn Яп + т
которых план, полученный в табл. 12.2, будет оставаться оптимальным. План оптимален, если все коэффициенты функции Zt будут неотрицательны:
px+qxt> О
p2+q2t>0 (12.3)
pn+qnt> 0.
Столбцы, соответствующие базисным переменным, можно не рассматривать. Из решения полученной системы неравенств можно найти интересующий нас интервал.
Рассмотрим несколько случаев:
а) Пусть все коэффициенты qj > 0,j = 1 ,п. Тогда t > -Pj/qp па-раметр t, удовлетворяющий системе (12.3), определяется выраже
IL Я]
нием />тах
. Верхняя граница для t стремится к +
Таким образом, окончательно
.El я І
cq =max
(12.4)
(+oo = a2.
В интервале (12.4) целевая функция достигает максимума в той же вершине.
б) Пусть все коэффициенты qj < 0, тогда из (12.3) имеем t < < —pj/qj. Для того чтобы значение t удовлетворяло всей системе
с \
Нижняя граница для t
(12.3), необходимо положить /ьтіп стремится к — поэтому V
qj
а{ = -оо(/ < min {-pj/qj) = а2. (12.5)
в) Пусть среди элементов qj имеются как положительные, так и отрицательные числа.
Разделив неравенства системы (12.3) на две группы соответственно знакам fy, получаем два интервала (12.4) и (12.5), объединяя эти интервалы, получим
ах = max (-Pj/qj) < t < min (-pJq)= a2.
(12.6)
Qj >0 qj < 0
г) Если qj — 0, то соответствующий коэффициент функции будет неотрицательным при любом /, поэтому на такой столбец можно не обращать внимания.
Сравниваем полученный интервал (cq; а2) с заданным [а, Р]. Независимо от значения аь левой границей первого интервала бу-дет а, так как щ больше а быть не может.
Если а2 > Р, то весь отрезок попадает внутрь интервала [а1? а2], и задача решена. Для любого значения параметра t є [а, Р] максимум Zt достигается в одной и той же вершинеа
іа2.
Для найденного решения снова определяем интервал изменения параметра t и т. д. Если в разрешающем столбце не окажется положительных элементов, задача на оставшемся интервале не имеет решения. Пример 12.2. Решить задачу параметрического программиро-вания 2xi +3x2 +*3 3*! +2^2 ~2х3<3; 4х!+2х2+х3 <4; xj>О у=Г3; Z, = + (1+/)х2 + (6 - 2/)х3 -> шах; /е[1; 8]. Решение Приведем задачу к виду, допускающему применение алгоритма, и найдем выражение целевой функции при /=7 (левый конец за-данного промежутка): 2xi + 3x2 + х3 + Х4 Зхі+х2~2хз+ Х5 + Хб=3; 4xj + 2x2 + *3 + х6 = 4; Z! = Xj + 2х2 + 4х3 -> max. Составим первую симплекс-таблицу с дополнительными строч-ками для функции Zt и выполним преобразование симплекс-таблицы для решения задачи (табл. 12.3—12.4). Таблица 12.3
0 1 2 4 0 0 0
\ Сво- \ бод- \ные БаД зис-\ ные \ св. ч *2 *3 х4 *5 ч 2
х4 1 2 3 1 0 0
*5 3 3 1 -2 0 1 0
Ч 4 4 2 1 0 0 1
zt 0 -1 -2 -4 0 0 0
zt 0 0 -1 -6 0 0 0
0 -1 -1 2 0 0 0
0 1 2 4 0 0 0
\ Сво- \ бод- \ ные БаД зис- \ ные \ св. ч *2 *3 *4 *5 *6 X
*3 1 2 3 1 1 0 0
*5 5 7 7 0 2 1 0
*6 3 2 -1 0 -1 0 1
4 7 10 0 4 0 0
6 12 17 0 6 0 0
-2 -5 -7 0 -2 0 0
Таблица 12.5
0 1 2 4 0 0 0
\ Сво- \ бод- \ ные БаД зис- \ ные \ св. ч *2 *з *4 *5 ч 2
*3 1 Ш 3 1 1 0 0
5 7 7 0 2 1 0
*6 3 2 -1 0 -1 0 1
Z\2/5 6/5 0 1/5 0 6/5 0 0
zt 6 12 17 0 6 0 0
1 -2 -5 -7 0 -2 0 0
0 1 2 4 0 0 0
\ Сво-
\ бод-
\ ные
БаД св. В табл. 12.4 получено оптимальное решение, так как все коэффициенты Zj-строки неотрицательны — х = (0; 0; 1; 0; 5; 3). Определим интервал для в котором оптимальное решение будет в той же вершине. Так как все qj < 0 (табл. 12.4), то согласно (12.5) а{ = —а2 = 12,5. Для нашего случая а{ = 1 (левый конец заданного отрезка). Таким образом, на отрезке [1; 12/5] решение будет в точке х = (0; 0,1; 0; 5; 3). Исключаем найденный отрезок из рассмотрения и решаем задачу для оставшегося отрезка [12/5; 8]. Для этого, полагая t = 12/5, вычисляем для него строку Z12/5. В первом столбце получим нуль; остальные коэффициенты Z12/5 строки положительны, а другие элементы остаются прежними (табл. 12.5). За разрешающий столбец в табл. 12.5 выбираем тот, по которому определено значение t = а2. Если нули находятся в нескольких столбцах, то за разрешающий можно брать любой из них. Новый план х = (1/2; 0; 0; 0; 3/12; 0) оптимален, так как в строке Z12/5 нет отрицательных элементов (практически элементы строки ^72/5 остались без изменения). В последней строке табл. 12.6 все q: > 0, поэтому согласно (табл. 12.6) а{ = 12/5, а2 = +<*>; t є [12/5; 8]. Таким образом, заданный промежуток разбился на два; при t = 12/5 оптимальное значение достигается в обеих вершинах и в любой точке, являющейся их выпуклой линейной комбинацией А = \{А{ + Х2А2; >0; Х2> 0; Х{ + Х2 = 1. Задачи Решить графическим методом Zt = (2 + 2t)xx + (4 - 2t)x2 max; Xj + x2 < 6; x2<4; 2xx + x2 < 10; X! > 0; x2 > 0; te [1; 15]. Z, = 4x!. + (2 + 0x2 —> max; 2xx - 5X2 < 10; Xj + x2 < 5; —xx + x2 < 4; 4xx + 5X2 < 40; Xj > 0; x2 > 0; te [0; 8]. Решить аналитически Z, = (1 + t)xx + (2 - t)x2 + (2 - Зґ)х3 + (1 - 2Ґ)Х4 max; Xj + x2 + 2x3 — x4 < 5; xx + 2X2 + x4 < 7; XJ + x3 + 2X4< 3; Xj > 0; у = 1,4; t e [1; 20]. Z, = (10 - 10/)xj + (9 + t)x2 + (7 - 2/)x3 -> max; Xj + x2 < 5; 2xx + x3 < 7; Xj + 2X2 + 3x3 < 3; xy>0;y = 1,3; te [1; 10]. Zt = txx + (1 + ґ)х2 —» max; -3xx + 4X2 < 12; 4xj + x2 < 8; xx > 0; x2 > 0; te [1; 7]. Глава 13