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

Таблица 2.26

Разделение на базисные и свободные

				Таблица 2.27
Допустимое базисное решение
Переменные	—Х\\	—Х2Ъ	—Хп	—ХЪЪ	1
Я22	- 1	1	1	1	1
Х2\	ш	0	- 1	- 1	0
хз\	0	0	1	1	1
Х\2	1	- 1	0	- 1	0
Z13	0	1	0	1	1
т	- 1	4	4	1	10

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

Таблица 2.28

Оптимальное решение

Из табл. 2.28 следует, что максимальная суммарная производи­ тельность всех механизмов равна 10 (условным единицам) и дости­ гается при

Ж ц = 0 ,	Х12 =	0,	Х13 =	1,	2 2 1 = 0 , 222 = 1,
223 = 0 ,		231 =	1,	232 =	0, 2 з з = 0 ,
т. е. механизм А\	выполняет вид работы В%, механизм A i — вид ра­

боты B i и механизм А^ — вид работы В \.

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

§ 2.10. Задачи о покрытии множества

Одним из вариантов задачи размещения производства является задача о покрытии множества, т. е. задача определения мест раз­ мещения каких-либо элементов и их количества. Например, задача размещения складов, при котором расстояние от склада до каждо­ го потребителя не превышает 100 км, может быть сформулирована как задача о покрытии множества. Другим примером такой задачи является задача определения числа и места размещения на терри­ тории города студенческих общежитий, при котором каждый сту­ дент тратит на дорогу до учебного заведения не более одного часа, или задача размещения пожарных команд, при котором расстояние до любой точки города «покрывается» за 5 мин.

Задача о покрытии множества может быть записана следующим образом:

	/ ( 2) =	^	Cjхj —>min		(2.11)
при ограничении		j = 1
П
^	Q>ijXj ^	1,	î	1,2,..., 771,
3 = •
Xj e	{0; 1},		J =	1,2, ...,n.

Величины dij называются коэффициентами покрытия и при­ нимают значения, равные единице, если г-й потребитель находится

в пределах j -й области (т. е. покрывается j -й областью), в против­ ном случае равны нулю. Аналогично, Xj принимает значение, равное единице, если в j -й области расположен некоторый объект, и нулю в противном случае. Ограничения в задаче требуют, чтобы каждый из т потребителей был «покрыт» по крайней мере одним из объектов. Цель в этом случае состоит в том, чтобы «покрыть» потребителей с минимальными затратами, причем Cj — стоимость помещения объекта в j -ю область.

Поясним смысл термина «покрытие». Если имеется комплекс жилых строений и решается задача размещения пожарных команд, то г-е жилое строение считается «покрытым», если пожарная ко­ манда находится в пределах пяти минут езды от этого строения; аналогично, если существует г-й потребитель и речь идет о раз­ мещении заводов, один из которых должен удовлетворять спросу этого потребителя, то последний считается «покрытым» при усло­

вии, что завод расположен, например, в местах	1, 2 или 3. Таким
образом, оц = Oj2 = йгз = 1, и все остальные	равны нулю для
j ^ 1,2,3.

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

Обычно задача о покрытии множества при решении проблемы размещения состоит в определении минимального числа объектов, необходимых для удовлетворения (покрытия) запросов некоторого множества потребителей. В подобной ситуации задача (2.11) сво­ дится к так называемой задаче о полном покрытии, которая получа­ ется из (2.11), если положить все равными единице. Некоторые задачи размещения экстренных служб могут быть сформулированы как задачи о полном покрытии.

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

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

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

т

f{x ) = ^ m a x aijXi —►max, j = 1,2, ... ,n ,

П	i=1	(2-12)
	Xj e {0; 1},	j = 1,2, ... ,n ,
j =i

где К — максимальное число объектов, подлежащих размещению, величины a,ij и Xj те же, что и в задаче (2.11).

Из вида функционала max a^Xj, используемого в целевой функ­ ции задачи (2.12), следует, что если некоторое место расположе­ ния потребителя «покрывается» более чем одним размещаемым объектом, то при вычислении функции f(x ) учитывается только максимальная величина о^-. Из ограничений в задаче (2.12) следует, что в лучшем случае существует К объектов для размещения. Заме­ тим, что если функция f(x ) равна т —числу потребителей, то это значит, что К достаточно велико, чтобы полностью удовлетво­ рить всех потребителей. Таким образом, задача о полном покрытии может быть сведена к задаче о частичном покрытии (2.12) для различных значений К , и решение задачи (2.12) при наименьшем значении К , для которого f(x ) = т, будет оптимальным решением задачи о полном покрытии.

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

Точное решение задачи (2.12) может быть получено с помощью методов динамического программирования, метода ветвей и границ

и двойственных методов. Однако они не приемлемы с вычисли­ тельной точки зрения при п ^ 20 и К ^ 10, и поэтому для решения задачи (2.12) были разработаны эвристические методы.

§2.11. Дробно-линейное программирование

Вдробно-линейном программировании (ДЛП) целевая функция является дробно-линейной, т. е. имеет вид

__ стх + а

Z ~ <Гх + р ’

где а и (3 — скалярные константы, с и d —векторы, х —вектор иско­ мых переменных, х е D,

D = {хеЖ п \А х = Ь, х ^ О , b e R m}.

Таким образом, в качестве целевой функции используется отно­ шение двух линейных функций; условия-ограничения задачи оста­ ются линейными: линейные равенства и неравенства.

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

Задачи ДЛП решают в тех приложениях, когда оптимизируются относительные показатели. Особенно часто такие задачи встреча­ ются в области финансовой деятельности: планировании доходов корпораций, управлении статьями банковского баланса и т. п.

Поверхности уровня целевой функции в задаче ДЛП линейны. Покажем это. Пусть значение целевой функции равно zo. Тогда

стх + а = zo(cFx + Р),

или (с —zo d fx = zoP + а, т. е. получили линейное уравнение, когда знаменатель целевой функции на допустимом множестве D не ра­ вен нулю.

Таким образом, если задача ДЛП имеет оптимальное решение, то по крайней мере одна крайняя точка из D будет оптимальной. Однако линии уровня целевой функции расходятся как лучи от мно­ жества вращения размерности п —2. Множество вращения — это множество всех точек пересечения нулевой линии уровня числите­ ля (стх + а = 0) с нулевой линией уровня знаменателя (сРх + р = 0),

т. е. множество точек, удовлетворяющих системе уравнений

стх = —а, dTx = - р .

Вращая линию уровня целевой функции в направлении векто­ ра d против часовой стрелки, увеличиваем значение целевой функ­ ции; вращая линию уровня по часовой стрелке —уменьшаем значе­ ние целевой функции.

Если знаменатель целевой функции отрицателен на допустимом множестве D, то следует дробь умножить на —1, не изменяя при этом условия максимума или минимума целевой функции.

Для решения задач ДЛП применяют метод преобразования пе­ ременных и процедуру обновления целевой функции.

1. П р е о б р а з о в а н и е п е р е м е н н ы х . Путем преобразова­ ния переменных задачу ДЛП при положительном на допустимом множестве D знаменателе сводят к задаче линейного программиро­ вания.

Делаем замену переменных р = (dTx + р)-1 и гц = Xip для всех г. Задача ДЛП принимает вид

сту + ар —►max

при условиях

^ - = Ь,

Р

(сРж + Р)р= 1,

0 < y e R n, O ^ p e R 1

Появляется новая переменная р. Получили задачу линейного

программирования

сту + ар —►max

при условиях

А у - Ь р = О,

еРу + рр= 1,

O ^ y e R ", O ^ p e R 1,

имеющих 771+1 ограничений и п + 1 переменных. Пример. Решить задачу ДЛП

	z =	Х2 — 5	шах
		----------------— Х\ — Х2 + 9

при условиях

2xi + 5x2 ^ 10.
4xi + 3x2 ^ 20,
- X i + Х2 ^ 2,
Х 1 , Х 2	^ 0 .
После замены переменных получим задачу линейного програм­
мирования
У2 —5р —>max
при условиях
2j/i + 5у2 -	Юр ^ 0,
4yi + Зу2 -	20р < 0,
—2/1 + У2 ~	2р ^ 0,
-2/1 “ 2/2 + 9р= 1,
2/ь 2/2. р ^ 0.

Решая эту задачу симплекс-методом, получим yi = 2 /3 ,2/2 = 4/3,

р = 1/3, или оптимальное		решение xi = 2, хг = 4.
2.	О б н о в л е н и е	ц е л е в о й ф у н к ц и и . Задача ДЛП реша­

ется как последовательность задач ЛП, где на каждой итерации пересчитывается градиент целевой функции

__ (dTx + р)с —(стх + оt)d Z ~ (dTx + P)2

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

На допустимом множестве D могут быть следующие случаи: 1) знаменатель принимает на D как положительные, так и отри­ цательные значения, тогда целевая функция z не имеет ни конечно­

го максимума, ни конечного минимума;

2)знаменатель всюду на D равен нулю, тогда всем точкам из D соответствуют неопределенные значения целевой функции z;

3)векторы e n d коллинеарны:

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

б) множество вращения не пусто, тогда числитель и знамена­ тель имеют идентичные нулевые линии уровня; целевая функция z постоянна на D, кроме некоторых точек, где z имеет значение 0/0;

4) векторы с и d не коллинеарны:

а) D — подмножество множества вращения, тогда всем точкам из D соответствуют значения z вида 0/0;

б) знаменатель всюду равен нулю, т. е. z = 0 везде, кроме тех то­ чек из D, принадлежащих множеству вращения, где целевая функ­ ция z принимает значения 0/0;

в) на D существуют точки, в которых знаменатель в целевой функции z не равен нулю; тоща могут быть:

—конечные минимумы и конечные максимумы;

—конечные минимумы, но неограниченные максимумы;

—неограниченные минимумы и максимумы.

§ 2.12. Анализ устойчивости оптимального решения задачи линейного программирования

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

В других случаях параметры задачи ЛП являются случайны­ ми величинами, и тогда важно знать, как может изменяться ре­ шение задачи в зависимости от изменения исходных данных. При

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

Как правило, в подобных случаях для получения ответа решают серию прямых близких задач, изменяя значения параметров.

Особенностью задач ЛП является тот факт, что полученное оп­ тимальное решение может не меняться при изменении значений параметров целевой функции и условий-ограничений в достаточно широких пределах. Более привычным является «непрерывный» ва­ риант: при небольших изменениях параметров задачи обязательно изменяется и решение — координаты точки оптимума. Чтобы оце­ нить изменения решений в задачах ЛП, можно использовать пара­ метрическое программирование, когда определяется поведение ре­ шения задачи ЛП в зависимости от параметра t, введенного в коэф­ фициенты целевой функции и в элементы матрицы и правой части условий-ограничений. Однако эти процедуры даже для одного пара­ метра t громоздки, и путем введения одного параметра t не удается описать все возможные изменения параметров задачи. Рассмотрим алгоритм, который позволяет определить допустимые множества значений параметров задачи ЛП, не приводящих к изменению най­ денного оптимального решения, и таким образом указать диапазон изменения каждого параметра.

Имеем задачу линейного программирования (с одним крите-

рием):
z = стх —►m ax	(2.13)
при условиях
А \х ^ Ь \,	(2.14)
А 2Х = i>2,	(2.15)
х ^ О ,

где с —вектор коэффициентов целевой функции, z —целевая функ­ ция, х — вектор исходных (структурных) переменных, Ь\ и &2 — век­ торы правых частей условий, А\ и Аг — матрицы системы ограни­ чений соответственно неравенств и равенств.

Для аналитического решения задача ЛП записывается в канонической форме:

z = сТх —*■шах
при условиях
А х = Ь, х ^ 0,	(2.16)

где х —вектор, включающий в себя исходные и дополнительные

(слабые) переменные;	А — прямоугольная матрица размерности
т х п, расширенная за	счет столбцов дополнительных перемен­

ных, преобразующих неравенства (2.14) в равенства; Ь —вектор правых частей условий (объединяет векторы 6i и ЪгУ, с —вектор коэффициентов целевой функции. Будем исследовать устойчивость точки оптимального решения задачи (2.13)—(2.15) при следующих допущениях и предположениях:

1)неопределенность или погрешность имеют только коэффици­ енты с целевой функции;

2)неопределенность или погрешность имеют только элементы вектора 6;

3)неопределенность или погрешность имеют только элементы матриц А\ и A i (т. е. элементы матрицы А, кроме элементов, отно­ сящихся к дополнительным переменным).

Алгоритмы учета других комбинаций неопределенностей осно­ вываются на этих случаях.

Будем далее полагать, что задача ЛП решается с помощью сим­ плекс-метода.

1. Н е о п р е д е л е н н о с т ь в к о э ф ф и ц и е н т а х ц е л е в о й ф у н к ц и и . Точка оптимума в симплекс-методе определяется усло­

вием
Cj Z j ï=0, Zj — (cb, CLj), j	1,2,..., îl,

где сь —вектор из элементов Cj, относящихся к базисным перемен­ ным; a,j — j -й столбец матрицы А; (сь, aj) — скалярное произведе­ ние. Целевая функция имеет вид z = сьЬ.

Пусть элементы Cj имеют неопределенность Acj, т. е. имеют вид

Cj + Acj, j	= 1,2,..., п; тогда условие оптимума будет определяться
величиной
Cj Acj	((с;, + Ась), dj) = (cj (cb,ûj)) -Ь (Acj	(Ась, a,j)),
	j — 1,2, ... ,n .	}